高級操作系統(tǒng)AdvancedOperatingSystem

1、高級操作系統(tǒng)高級操作系統(tǒng)Advanced Operating System陳香蘭（代）0551_3606864-83中國科學技術大學計算機系第四章第四章 分布式路由算法分布式路由算法l分布式路由算法導論l一般類型網絡的最短路徑路由算法 l特殊類型網絡的單播算法l特殊類型網絡中的多播算法l虛信道和虛網絡 l完全自適應和無死鎖路由算法l幾個自適應和無死鎖路由算法 l容錯單播的一般方法 l網格和圓環(huán)中的容錯單播算法l超立方中的容錯單播算法l容錯組播算法上次課主要內容（上次課主要內容（4小節(jié)）小節(jié)）l4.1 分布式路由算法導論l進程間通信類型l通信延遲及其原因l路由算法分類l路由函數(shù)定義l4.2 一般

2、類型網絡的最短路徑路由算法lDijkstra集中式算法lFord分布式算法lARPAnet的路由算法 l4.3 特殊類型網絡的單播算法l雙向環(huán)上的單播算法及其一般化l網格和圓環(huán)上的單播算法l2維網格的XY路由、適應性路由、折線路由等l超立方l基于海明距離的一種簡單的路由算法l4.4 特殊類型網絡中的多播算法l基于（哈密爾頓）路徑l基于樹的多播l應用于超立方的Lan的貪婪多播算法lU-網格算法4.5 虛信道和虛網絡虛信道和虛網絡l網絡資源l在存儲轉發(fā)交換中，資源是緩沖區(qū)；l在蟲孔路由中，資源是信道。l網絡通信中，若消息在占有資源的前提下可以申請資源，就有可能發(fā)生死鎖l通過控制路由的自適應性可以預

3、防和避免死鎖，同時也保證一定的容錯性。 l虛信道和虛網絡經常用于實現(xiàn)無死鎖、自適應和（或）容錯的路由。4.5 虛信道和虛網絡虛信道和虛網絡通過網絡分區(qū)避免死鎖通過網絡分區(qū)避免死鎖l通過網絡分區(qū)可以避免死鎖l給定的網絡可以分成幾個子網。l根據(jù)源和目標的位置，消息被路由到不同的子網l舉例說明：l3X3網格的適應性雙Y信道路由l如圖：l在Y方向有兩個物理信道（雙向）（a）一個3X3網格的 雙Y信道網4.5 虛信道和虛網絡虛信道和虛網絡通過網絡分區(qū)避免死鎖（通過網絡分區(qū)避免死鎖（contd）l上述網格被分成正、負兩個子網（如下圖）l如果目標位于源的右側，則使用正網；l否則將使用負網。l當源和目標同列時

4、，兩個子網都不用。l由于兩個子網中都沒有回路，所以可避免死鎖。 （b）正網絡（c）負網絡4.5虛信道和虛網絡虛信道和虛網絡虛信道虛信道l若網絡沒有雙Y信道，則可用幾個虛信道復用一個物理信道l每個虛信道都有自己的緩沖區(qū)。l當物理信道被其它虛信道使用時，就用這個緩沖區(qū)保存消息l若虛信道間沒有循環(huán)等待，就可避免死鎖。l假設上例改為單Y信道網，那么原來的正、負子網中所有的Y信道都是虛信道。4.5虛信道和虛網絡虛信道和虛網絡虛信道虛信道（contd）l當兩個虛信道共享一個物理信道時，信道利用率大幅提高。l雖然虛信道提供了一個具有多重信道的網絡，但仍需仔細設計路由算法。例如，l可以按照信道標記的升序使用虛

5、信道，以便避免虛信道間循環(huán)依賴。4.5虛信道和虛網絡虛信道和虛網絡虛網絡虛網絡l比虛信道更高一級的虛擬化是虛網絡l一個給定的物理網絡被分成幾個虛網絡，每個虛網絡包括一系列的虛信道。l虛網絡中相鄰的節(jié)點被映射到物理網絡中時也要相鄰l一般地，一個虛網絡中的虛信道設置應避免信道間的回路。雖然仍有可能存在互相交叉的虛網絡回路，但可以通過使虛網絡遵循全序或偏序來避回路l前面那個例子中，若使用單Y信道，則前面的正、負子網可認為是兩個虛網絡。l顯然每個網絡中都沒有回路。因每個路由過程最多只使用一個虛網絡，所以不會產生互相交叉的虛網絡回路。 4.5虛信道和虛網絡虛信道和虛網絡l雖然虛網絡包含虛信道，二者是完全

6、不同的概念。l一般地，虛信道的使用是與路由過程緊密相連的，包括源和目標的位置。必須合理安排虛信道，以避免死鎖。l虛網絡通常設計為沒有回路，因而路由算法可以不必考慮死鎖，除非存在交叉虛網絡的依賴性4.5虛信道和虛網絡虛信道和虛網絡虛信道舉例虛信道舉例l考慮一個有四個節(jié)點的單向環(huán)。如果同時有幾個路由進程啟動，就會發(fā)生死鎖。4.5虛信道和虛網絡虛信道和虛網絡虛信道舉例虛信道舉例（contd）l通過給每個鏈接增加兩個虛信道可以避免死鎖l如圖，信道被分為l高虛信道，和Ch0, Ch1, Ch2, Ch3l低虛信道Cl0, Cl1, Cl2, Cl34.5虛信道和虛網絡虛信道和虛網絡虛信道舉例虛信道舉例（

7、contd）l若源地址大于目標地址，l可從任何一個信道開始；l但一旦使用一個高（低）信道，那以后也要使用同一信道l若源地址小于目標地址，l首先使用高信道，經過節(jié)點P3后，高虛信道切換為低虛信道l圖示為相應的信道依賴圖l以信道為節(jié)點l邊為信道之間的切換關系P34.5虛信道和虛網絡虛信道和虛網絡虛網絡舉例虛網絡舉例l在上述虛信道方法中，給定的環(huán)被分成兩個虛環(huán)：Vr1和Vr2l每個環(huán)中都有一個回路。兩個虛環(huán)：Vr1：高信道形成的虛環(huán)Vr0：低信道形成的虛環(huán)虛環(huán)形成的回路。圖中，節(jié)點內的邊表示回路中信道的切換關系4.5虛信道和虛網絡虛信道和虛網絡虛網絡舉例虛網絡舉例（contd）l要避免虛網絡內部的回

8、路，可以l在vr1中禁止從Ch0切換到Ch3，和l在vr0中禁止從Cl0切換到C13。P3中，Ch0到Ch3的切換被禁止；Cl0到Cl3的切換也被禁止4.5虛信道和虛網絡虛信道和虛網絡虛網絡舉例虛網絡舉例（contd）l可在任一步進行從vr1到vr0 的虛網絡切換（如圖）l例如l若源地址大于目標地址，如l從P2到P0的路由可以從Ch2開始，并在P1切換至Cl1l從P3到P0的路由中，可在P2或P1進行切換l也可以不切換l但若目標地址大于源地址，則必須在節(jié)點P3切換，因為1.在單向環(huán)中，若目標地址大于源地址，則必然要經過P3路由2.兩個虛環(huán)都不允許在P3進行從Ch0到Ch3 和Cl0到Cl3 的

9、切換。所以在P3只能進行Ch0到Cl3的切換圖中，每個節(jié)點都可以進行vr1到vr0的虛網絡切換4.5虛信道和虛網絡虛信道和虛網絡虛網絡舉例虛網絡舉例（contd）l基于虛網絡的路由過程比基于虛信道的路由有更強的適應能力。在上例中，l虛信道路由僅在P3進行高虛信道到低虛信道的切換l虛網絡路由允許在任一點進行虛網絡切換l為了保證從vr1到vr0的切換生成一個合法的路由路徑，l若Cli是vr0中的切換信道，則i必須不能小于剩余的路由跳躍數(shù)。4.5虛信道和虛網絡虛信道和虛網絡雙環(huán)路由雙環(huán)路由l上述每一個單向信道增加一個虛信道的方法叫雙環(huán)路由l形式化地描述雙環(huán)路由：l假定使用n個進程：Pn-1,Pn-2

10、,P1, P0，信道是Ch或Cl：4.5虛信道和虛網絡虛信道和虛網絡雙環(huán)路由算法雙環(huán)路由算法4.5虛信道和虛網絡虛信道和虛網絡雙環(huán)路由雙環(huán)路由l在上述算法中，當進程發(fā)起路由時，l如果i des ，可以使用高信道或者低信道。l如果i des ，則只能使用高信道。4.6 完全自適應和無死鎖路由算法完全自適應和無死鎖路由算法 l適應性和無死鎖是兩個互相矛盾的要求。l像2 維網格的XY路由和n維立方的e-立方等決定性的無死鎖路由雖然簡單，但都不是適應性的。l一個決定性路由在存在錯誤組件（如鏈接或節(jié)點）的系統(tǒng)中有可能失效l例如，一個XY路由完成了X方向的路由，但在Y方向上由于錯誤被阻塞，這個信息就不能被

11、繼續(xù)轉發(fā)l但沒有限制的適應性路由可能引發(fā)死鎖。l因此，必須在不引發(fā)死鎖的前提下增加適應性4.6 完全自適應和無死鎖路由算法完全自適應和無死鎖路由算法l幾乎所有的完全適應性路由都可以通過增加一定數(shù)量的虛信道（或虛網絡）來避免死鎖。l例如，l一個最小化的適應性的n 維立方路由可以通過加入n個虛信道來避免死鎖。l每一步都使用比前一個具有更高標記的信道。l因為需要n步，所以n個虛信道足以避免虛信道之間的循環(huán)等待。l然而使用虛信道會引入附加的緩沖區(qū)等開銷。所以，要盡量限制虛信道的數(shù)目。4.6.1 虛信道類虛信道類 l如前所述，通過引入足夠多的虛信道，任何路由都可以保證避免死鎖。l當路由開始時，使用虛信道

12、1，vc1。l在第i 步使用虛信道i，vci及相應的鏈接。l如果一個給定網絡的最長路徑（也叫直徑）是Dmax那么就要用Dmax個虛信道；4.6.1 虛信道類虛信道類l為了減少虛信道的數(shù)量，可將一個網絡分成幾個節(jié)點的子集，每個子集都不會包含相鄰的接點。l例如，l考慮一個形似跳棋盤的2維網格，上面有黑白方格。l黑節(jié)點屬于個子集，白色節(jié)點屬于另外一個。l當一個消息從一個白色節(jié)點移動到黑色節(jié)點時，就將虛信道的標記加一。l如果是從黑色節(jié)點向白色節(jié)點移動，虛信道標記保持不變。l顯然，在2維網格中，節(jié)點標記的改變次數(shù)最多為路由步數(shù)的一半。這樣虛信道的總數(shù)就縮減了一半。4.6.1 虛信道類虛信道類l可以將上述

13、思想一般化：l將給定網絡分成k個子集S1, S2, Sk ，每個子集都不包含相鄰節(jié)點l當一個消息從子集Si中的一個節(jié)點移動到子集Sj中的一個節(jié)點（i j ）時，稱之為上移動；反之為負移動。l發(fā)生負移動時，虛信道標記加一l假定信道標記從1 開始l從而，所需信道的個數(shù)就是一個路由路徑中負移動的個數(shù)。l目標就是要選擇一個合適的k以及一個劃分，使路由過程中的負移動個數(shù)最小4.6.2 逃逸信道逃逸信道等待和非等待信道等待和非等待信道l使用逃逸信道的路由算法中，虛信道被分為等待信道（又稱為逃逸信道）和l若一個等待信道處于繁忙狀態(tài)，而此時一個消息需要通過該信道，則這個消息必須等待，直到該信道可用l即一個等待

14、信道能夠阻塞消息非等待信道（又稱為一般信道）l若一個消息碰到一個處于繁忙狀態(tài)的非等待信道，它不必被阻塞以等待該信道變得可用，可以選擇其他信道l因此，一個消息會首先考慮通過非等待信道到達目標l若所有的非等待信道都繁忙，它就考慮等待信道4.6.2 逃逸信道逃逸信道混合路由混合路由 l使用逃逸信道擴展完全適應的概念l例如，可以用兩個路由進程實現(xiàn)混合路由：路由進程1：完全適應性路由完全適應性路由，使用標記為非等待的虛信道；路由進程2：限制性但無死鎖路由限制性但無死鎖路由可能是XY路由或e-立方等決定性路由使用標記為等待的虛信道。4.6.2 逃逸信道逃逸信道混合路由混合路由（contd）l混合路由算法：

15、1.開始時，使用完全適應路由，直到阻塞為止；2.然后切換到限制性路由。l混合路由是無死鎖的l由于等待信道是在無死鎖路由中定義的，并且l消息僅僅等待上述等待信道l合理分配等待和非等待信道是關系到混合路由效率的關鍵問題4.6.2 逃逸信道逃逸信道混合路由的擴展混合路由的擴展Il擴展I：當消息發(fā)現(xiàn)等待信道被占用時，可以使用非等待信道l擴展I增加靈活性的同時也引入了選定的逃逸信道之間新的依賴性。l通過使用一個或多個中間的一般信道，一個逃逸信道可能間接地依賴于另一個逃逸信道。l因此無回路條件必須包括逃逸信道之間的所有間接依賴。l不幸的是，沒有循環(huán)依賴只是不發(fā)生死鎖的一個充分條件；也即，對于一個特定的蟲孔

16、網絡，若使用某一個路由算法，擴展I太弱，不會得到任何結果。擴展信道依賴圖中的一個回路可能表示一個死鎖狀態(tài)，也可能不是。4.6.2 逃逸信道逃逸信道混合路由的擴展混合路由的擴展I IlDuato通過使用基于消息目標的逃逸路徑進一步擴展了上述思想 l對于不同的目標，使用不同的逃逸信道。l在同樣的無回路條件下，可以得到一個無死鎖的充分必要條件。l然而，在生成擴展信道依賴圖的時候，直接依賴、間接依賴、直接交叉依賴（在不同目標的逃逸信道之間）和間接交叉依賴都要被考慮進去。4.6.2 逃逸信道逃逸信道l上述兩個擴展都可用于避免死鎖。l為了設計一個無死鎖的路由函數(shù)，首先創(chuàng)建一個名為R1(x,y)的路由子函數(shù)

17、，它的功能是將當前和目標節(jié)點映射到當前節(jié)點的輸出信道的子集。R1(x,y)是連通的，無回路的?？梢酝ㄟ^增加信道或者將已有信道分割為虛信道將R1(x,y)擴展為R(x,y)，以便增加可選路徑的數(shù)目，同時又不會在R1(x,y)的擴展信道依賴圖中增加回路。l這一設計規(guī)程又被稱為Duato協(xié)議。4.6.2 逃逸信道逃逸信道維度逆轉路由維度逆轉路由 l如果不要求最小路由，那么虛信道的數(shù)量還可以減少。l對于一個k元n維立方（沒有環(huán)繞連接），有如下的一般非最小無死鎖路由：l對每個物理信道，有k個虛信道與之對應l其中一個用于逃逸信道，以便進行無死鎖的按維排序的路由l消息可以按照任何方向路由，而不一定是最小路徑

18、。l每個消息都有一個維度逆轉數(shù)DR相對應，lDR：記錄消息從高維度路由到低維度的次數(shù)。4.6.2 逃逸信道逃逸信道維度逆轉路由維度逆轉路由（contd）l一旦一個消息取得一個信道，它就將該信道標記為當前的DR數(shù)。l為了避免死鎖，一個DR數(shù)為i的消息不能等待一個DR數(shù)為j的信道，這里ij。l此時，選用下一層的虛信道。l假定每個未被訪問的信道的DR標記為0。l當虛信道的標記達到k時，就使用決定性的按維度排序的路由。4.7 幾個部分適應和無死鎖路由算幾個部分適應和無死鎖路由算法法l很多路由算法的路由適應性僅對一小部分虛信道有效。這種算法屬于部分適應性路由l本節(jié)討論三個部分適應性和無死鎖路由算法l轉彎

19、模型l平面自適應模型l其他部分自適應模型4.7.1 轉彎模型轉彎模型 l2維網格的轉彎模型提供了一個部分適應性和無死鎖的路由。l下圖顯示了2維網格中的抽象回路。4.7.1轉彎模型轉彎模型基本思想基本思想l上圖顯示了XY路由中所允許的四個轉彎（實心箭頭所指）。l只允許先X方向路由后Y方向路由l顯然，這個條件太嚴格了，因為可以通過去掉回路中的一個角來打破回路。l轉彎模型的基本思想l通過禁止最小數(shù)目的轉彎來增加適應性，以避免回路。X方向Y方向4.7.1 轉彎模型轉彎模型正向優(yōu)先協(xié)議和負向優(yōu)先協(xié)議正向優(yōu)先協(xié)議和負向優(yōu)先協(xié)議l左下圖為一個正向優(yōu)先路由協(xié)議。l可以有6個轉彎l從負向到正向的轉彎，也即南到東

20、和西到北，被禁止l右下圖為一個負向優(yōu)先路由協(xié)議。l可以有6個轉彎l從正向到負向的轉彎，也即北到東和東到北，被禁止X方向Y方向X負到Y正Y負到X正X正到Y負Y正到X負正向優(yōu)先協(xié)議負向優(yōu)先協(xié)議4.7.1 轉彎模型轉彎模型轉彎模型的適應性轉彎模型的適應性l由于源和目標的位置的不同，轉彎模型可能有適應性，也可能沒有。l下圖顯示了源s和目標d的兩種不同位置。l若目標位于源的東北或西南方，那么正向優(yōu)先路由就是完全適應性的，如圖al否則，就是決定性的，如圖b（a）完全適應性路由（b）確定性路由東北東南OKNot OK4.7.1 轉彎模型轉彎模型轉彎模型的平衡性轉彎模型的平衡性l某些情況下，上述不平衡的適應可

21、能會導致?lián)砣虿黄胶獾墓ぷ髁?。l可以使用虛信道將幾種不同的協(xié)議結合起來。每個協(xié)議都是基于轉彎模型，但有不同的區(qū)域適應性，因而可以得到一種平衡的方法。l例如，若允許使用兩個虛信道，就可設計兩個具有互補適應性的轉彎模型。4.7.2 平面自適應模型平面自適應模型 l對應于一般的k元n維立方，Chien和Kim提出了一種部分適應性和無死鎖的路由。l基本思想是：l在某一時刻將路由的自由度限制到兒個維度以降低對硬件（虛信道）的要求。l例如，若每次只選兩個維度，就有A0, A1, An這些平面，其中Ai在維度di和di+1方向擴展。4.7.2 平面自適應模型平面自適應模型舉例舉例l下圖顯示了三個平面的例子：

22、A0（維度為d0和d1），A1（維度為d1和d2），和A2（維度為d2和d3）平面自適應路由所允許的路徑4.7.2 平面自適應模型平面自適應模型舉例舉例l對每個Ai，引入三個虛信道，一個沿著第i 維，兩個沿著第（i+1）維。l設di,j是維度j通過維度i的虛信道。lAi使用三個虛信道：di,2 、di+1,0和di+1,14.7.2 平面自適應模型平面自適應模型l由于每個虛信道都是雙向的，可將di,2分成兩個單向信道di,2+和di,2-lAi也就被分成兩個子網：包含di,2+和di+1,0的正向子網；以及包含di,2-和di+1,1的負向子網l本課開始的正負子網可看成是上述正向和負向子網的例

23、子：l將X和Y視為di和di+1正網絡負網絡4.7.2 平面自適應模型平面自適應模型lAi內部的路由可依據(jù)源和目標的位置不同而選用正向或負向子網。l若目標的標識大于源標識，則選用正向子網；l否則，選用負向子網。l注意：l虛信道di, di,0, di,1中的另外兩個也用于平面Ai-1，即相鄰平面有一個公共維度。l相對于完全適應而言，平面適應方法犧牲了一些路由自由度（適應性），從而大大降低了虛信道的數(shù)目。4.7.3 其他部分自適應模型其他部分自適應模型lLi出了e-立方路由的一個要求稍低的版本。l對一個超立方中的任意回路，我們總能找出沿著最低維度的兩個鏈接，比如設該維度為i 。l其中一個鏈接是從

24、第i 位為0 的節(jié)點到第i 位為1 的節(jié)點（負向鏈接）l另一個是從第i 位為1的節(jié)點到第i位為0 的節(jié)點（負向連接）。l為了打破一個回路，只需禁止從較高維度的正向連接向沿著維度i的負向連接轉換即可，除非這個轉換符合e立方路由。4.7.3 其他部分自適應模型其他部分自適應模型l如果e立方路由滿足維度遞增的順序，一個沿著維度dim(c1)的信道c1到一個沿著維度dim(c2)的信道c2的轉換是允許的當且僅當下述條件中的一個為真：1.dim(c1)0)網中，使用三個虛信道來避免死鎖。l對n維圓環(huán)，每個環(huán)繞信道需要兩個虛信道來打破同一個維度中的回路?？傊?，對n(n0)維圓環(huán)需要6 個虛信道。l2 維網

25、格中，使用兩個虛信道，網絡被分成正/負向兩個子網。l類似地，在2 維圓環(huán)中，使用4個虛信道。4.9.2 基于有限全局信息的路由基于有限全局信息的路由Wu的最優(yōu)容錯路由算法的最優(yōu)容錯路由算法lWu提出了一個有出錯塊的2維網格的最優(yōu)容錯路由算法。l首先，他證明：設節(jié)點(0, 0)是源節(jié)點，節(jié)點(i, j)是目標節(jié)點。若沒有出錯塊通過X和Y軸，那至少存在一個始于(0, 0)的最優(yōu)路徑，長度為|i|+|j| 。l在一給定的2維網格中，上述結果對任意位置的目標節(jié)點和任何數(shù)目和分布的出錯塊都成立，相應的源叫做安全的。l上述結果可以進一步擴展：允許X和Y軸有出錯塊，只要它們到源的距離分別大于|i|和|j|。

26、這樣的源節(jié)點叫做擴展安全的。4.9.2 基于有限全局信息的路由基于有限全局信息的路由Wu的最優(yōu)容錯路由算法的最優(yōu)容錯路由算法l有兩個最優(yōu)和適應性容錯的路由算法：l面向目標路由，和l面向源路由。l為簡單起見，假定源節(jié)點是(0, 0)，目標節(jié)點是(i, j)，且i, j =0，即路由永遠是向東北方向的。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目標的路由面向目標的路由l面向目標的路由使用最短路徑區(qū)域RMP的概念：l對給定的源和目標對，RMP包含最短路徑的所有中間節(jié)點l為建立RMPl做一條從目標節(jié)點(i, j)開始到Y軸結束的線。l遇到出錯塊時，先向南繞過出錯塊，然后繼續(xù)向西l類似

27、地，建立一個從(i, j)開始向南到X軸截止的線。l遇到出錯塊時，先向西繞過出錯塊，然后繼續(xù)向南。l已經證明由向西和向南的線以及X軸和Y軸圍起來的區(qū)域是RMP。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目標的路由面向目標的路由舉例舉例l下圖顯示了一個RMP的例子，這里向西的線標記為路徑A，向南的線標記為路徑B。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目標的路由面向目標的路由l僅當源是擴展安全的，才使用面向目標路由l源通過一個最優(yōu)或不是最優(yōu)的路徑向目標發(fā)一個信號l接到信號后目標發(fā)兩個信號，一個向西一個向南向西的信號建立RMP的路徑A，向南的信號建立RMP的路

28、徑B 。l一旦源收到來自目標的兩個信號，就意味著RMP已建立起來。源就用任何一種適應性最小路由發(fā)送路由消息。l遇到路徑A（或路徑B）的邊界時，剩下的路由就要沿著路徑A （路徑B ）發(fā)往目標。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最優(yōu)路由面向源的最優(yōu)路由l為支持面向源的最優(yōu)路由，必須把出錯塊的信息分布到系統(tǒng)中的特定節(jié)點上。l舉例說明：下圖顯示了一個出錯塊L1, L2, L3, L4與出錯塊的四條線平行x=0和y=0的區(qū)域被分成8 個子區(qū)域：R1R8L14上的點可劃歸任一相鄰區(qū)域。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最優(yōu)路由面向源的最優(yōu)路由（c

29、ontd）l顯然，l可用任一最小路由算法到達R1, R2, R3 , R7, R8中的點l可用XY路由（先X后Y）到達R6中的任何點。l可用YX路由（先Y后X）到達R4中的任何點。l用XY路由和YX路由都可到達R5 中的點。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最優(yōu)路由面向源的最優(yōu)路由（contd）l當目標節(jié)點位于R4或R6時，為達到最優(yōu)路由，位于L1（位于(x,y)西側的節(jié)點）和L2（位于(x,y)南側的節(jié)點）上的特定節(jié)點必須具有這個出錯塊的信息。這些信息可以用出錯塊的相應角的位置來編碼。l特別地，為每個出錯塊建立兩個概念上的路徑l路徑1（虛線）：(,y)(x,y)

30、(x,y)(x,y)(- ,y)l路徑2（實線）：(x, )(x,y)(x,y)(x,y)(x,- )4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最優(yōu)路由面向源的最優(yōu)路由（contd）l顯然，l目標位于路徑1的南側或東側的路由消息不能通過路徑1。l目標位于路徑2的北側或西側的路由消息不能通過路徑2。l路徑1的路徑信息存儲在(-,y)到(x,y)間的每個節(jié)點上l路徑2的路徑信息存儲在點(x,-)到(x,y)間的每個節(jié)上l為最小化路徑信息，只有每個轉彎（出錯塊的角落）的位置是必要的。l所以(x,y)和(x,y)對路徑1是必要的，而(x, y)和(x, y)對路徑2是必要的。4.

31、9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步驟面向源路由的步驟l面向源路由的步驟：l首先使用任何一個適應性最小路由，直到遇到出錯塊的一個（路徑1或路徑2）為止。1.（遇到路徑1的L1）若目標節(jié)點在路徑1的南/東側，那消息將一直留在L1直到到達出錯塊的L1和L4的邊界為止；否則將穿過L1。2.（遇到路徑2的L2）若目標節(jié)點在路徑2的北/西側，那消息將一直留在L2直到到達出錯塊的L2和L4的邊界為止；否則將穿過L2。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步驟面向源路由的步驟（contd）l上述方法中，兩個虛信道足以避免死鎖。l一個簡單的方法是為東

32、北和東南方向的路由使用正向子網，對西北和西南方向的路由使用負向子網。4.9.3 基于其他故障模型的路由基于其他故障模型的路由Wu的直角凸多邊形模型的直角凸多邊形模型l雖然矩形出錯塊很簡單，但它引入了很多被禁止的非出錯節(jié)點，即它們將不會在路由過程中起作用。l但矩形為凸形的特性使得可以用最少的虛信道把路由信息繞過出錯區(qū)域。l另外一些非矩形的凸形出錯塊也被引入了。lWu將出錯塊模型擴展為直角凸多邊形模型。l一個凸多邊形的定義是：多邊形P，P中的任意兩點之間的線段都在P內部。l在直角凸多邊形中，線段被限制為只能是水平或垂直的。4.9.3 基于其他故障模型的路由基于其他故障模型的路由直角凸多邊形直角凸多

33、邊形l可以將給定的矩形出錯塊轉換為一系列分離的直角凸多邊形l這一思想根源于這樣一個事實：l可以通過將出錯塊中的一些非出錯節(jié)點移出去，從而將它們激活，同時又保持這個區(qū)域的凸性。4.9.3 基于其他故障模型的路由基于其他故障模型的路由活躍活躍/不活躍節(jié)點不活躍節(jié)點l與標準出錯塊中的安全/非安全定義不同，Wu給出了活躍/不活躍節(jié)點的概念：l所有出錯節(jié)點都是非活躍的，所有安全節(jié)點都是活躍的。l一個非安全節(jié)點開始的時候是非活躍的但如果它有兩個或兩個以上的活躍鄰居，那么它就可以稱為活躍的。l因此，對于一個非出錯節(jié)點，有三種可能情況：1.安全且活躍。2.非安全但活躍。3.非安全且不活躍。4.9.3 基于其他

34、故障模型的路由基于其他故障模型的路由活躍活躍/不活躍節(jié)點舉例不活躍節(jié)點舉例l下圖是將wu的活躍/不活躍規(guī)則用于圖7-7的出錯塊的結果。l顯然，結果是一個直角凸多邊形。4.10 超立方中的容錯單播超立方中的容錯單播 l按照使用的錯誤信息類型對超立方中的容錯單播路由進行分類：l基于局部信息的l基于有限全局信息的l基于擴展安全等級模型的4.10.1 基于局部信息的模型基于局部信息的模型l已經證明，l對n維立方中的任何兩點u和w，如果H(u,w)=k，那么從u到w恰好有n條點分離路徑。其中，l有k條長度為k的路徑和(n-k)條長度為k+2的路徑l若出錯組件的數(shù)目L小于n，那么用多條路徑進行路由的方法是

35、很直接的。l消息沿著n條點分離路徑進行傳送，并且其中至少有一條是好的。l這樣，就可通過那條路徑到達目標，路徑最大長度是k+24.10.1 基于局部信息的模型基于局部信息的模型lchen和shin給出了下面四種容錯路由算法: 1.出錯組件小于n-1，不確保有最優(yōu)路徑。2.出錯組件小于n-1，確保有最優(yōu)路徑。3.出錯組件無限制，不確保有最優(yōu)路徑。4.出錯組件無限制，確保有最優(yōu)路徑。l第2和第4種情況是所希望的，但相應的算法會引入特別的開銷。4.10.1 基于局部信息的模型基于局部信息的模型第第1種情況種情況等位序列定義等位序列定義l考慮一個第1種情況的算法。l為了容錯，一些訪問過的節(jié)點也保存在消息

36、中。l定義：等位序列d1, d2, , dk為當前節(jié)點與目標節(jié)點不同的所有維度（也叫首選維度，preferred dimension）l例如，假設0010和0111是當前節(jié)點和目標節(jié)點，那相應的等位序列就是1,3l為表示一個消息的目標，等位序列要和消息一起傳送l因當前節(jié)點會隨著消息的傳遞而變化，故等位序列也隨著變化4.10.1 基于局部信息的模型基于局部信息的模型第第1種情況種情況消息的表示消息的表示l每個消息都有一個n位向量標志，用以保存“空余維度(Pare dimensions)”。l可以用這些維度來繞過出錯組件。l注意空余維度就是那些沒有在最初的等位序列中出現(xiàn)的維度l源節(jié)點發(fā)起路由時，標

37、志中的所有位都將清零。l消息的表示：(k, d1, d2, , dk, 消息, 標記)。lk為剩余路徑長度， k會在消息的發(fā)往過程中不斷更新l當k變?yōu)?時，消息就到達目標了。4.10.1 基于局部信息的模型基于局部信息的模型算法的描述算法的描述l當節(jié)點收到一個消息時，檢查k的值以判斷自身是否為消息的目標l若不是，節(jié)點將嘗試按照剩下的等位序列中指定的維度發(fā)送消息l每個節(jié)點都將努力沿著最短路徑發(fā)送消息。l然而，若通往最短路徑的維度的那些連接出錯，這個節(jié)點將使用空余維度通過另外的路徑發(fā)送消息。l開始時，等位序列為由源和目標地址異或得到的所有首選維度空余維度的所有位清零。4.10.1 基于局部信息的模

38、型基于局部信息的模型算法的描述算法的描述l更正式地，這個路由算法可以描述如下。注意：u(i)表示沿著維度i的u的鄰居。4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例l考慮下圖中的出錯超立方。l假設消息m從u=0110路由到w=1001。在u=0110處的最初消息是(4, 1, 2, 3, 4, m, 0000)l按照上述算法，1.節(jié)點0110將(3, 2 ,3 ,4, m, 0000)發(fā)送給01101=0111，2.隨后0111將(2, 3, 4, m, 0000)發(fā)送給01112=0101。4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例（contd）3

39、.由于0101的第3維鏈接出現(xiàn)錯誤，節(jié)點0101將發(fā)送(1, 3, m, 0000)到01014=1101。4.然而，由于1101的第3維的鏈接出現(xiàn)錯誤，節(jié)點1101將使用第1維（標記=0100，標記記下了要繞道時的首選維度），并發(fā)送消息(2, 3, 1 , m, 0101)到1100。4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例（contd）5.1100依次將發(fā)送(1, 1, m, 0101)到1000。6.隨后，節(jié)點1000的第一個鏈接又出現(xiàn)錯誤。這時將使用第2維（此時標記=0101）, (2, 1, 2, m, 0111)被路由到1010。7.之后，消息將經過101

40、1到達目標1001。結果路徑的長度是8 。4.10.2 基于有限全局信息的模型：基于有限全局信息的模型：安全等級（定義）安全等級（定義）l下面討論具有節(jié)點故障的超立方中的有效路由l這種模式基于每個節(jié)點的有限全局信息l這種信息被標記為安全等級。l從根本上說，安全等級就是每個節(jié)點周圍鄰居中失效節(jié)點的大致數(shù)目。l定義：設s(a)=k是節(jié)點a的安全等級，稱a是k-安全的；l一個失效節(jié)點是0-安全的，即最低的安全等級，l一個n-安全的節(jié)點（也叫安全節(jié)點）安全級別最高l若kn，那么一個k-安全的節(jié)點就是不安全的安全等級的定義及計算安全等級的定義及計算ln維立方中，令節(jié)點a的所有鄰居節(jié)點的安全等級的非遞減安

41、全狀態(tài)序列為：(S0, S1, S2, Sn-1)，0=Si=n且0=Si=Si-1=( 0, l, 2, n-1)，那么s(a) n；否則，如果(S0, S1, S2, Sk-1 )=( 0, l, 2, k-1)并且(Sk=k-1)，那么S(a)=k。安全等級的計算算法安全等級的計算算法l下述算法決定了每個節(jié)點的狀態(tài)。l每個節(jié)點a(i)都保存它所有鄰居節(jié)點的非遞減安全狀態(tài)序列l(wèi)開始時，所有非出錯節(jié)點都是n-安全的。l該算法需要n-1次重復達到穩(wěn)定狀態(tài)。安全等級舉例安全等級舉例l例如，下圖的出錯超立方中，出錯節(jié)點0011, 0100, 0110和1001是0-安全的（黑色）節(jié)點0001, 0

42、010, 0111和1011是1-安全的（棕色），因為每個都有兩個出錯節(jié)點，非遞減序列為0,0,2,2或 0,0,2,4或0,0,4,4,k=1節(jié)點0000和0101是2-安全的（紫色）。非遞減序列為：0,1,1,4,k=21000, 1010, 1100, 1101, 1110和1111是安全的（藍色）非遞減序列為：0,4,4,4或1,1,4,4或0,2,4,4安全等級的性質和安全等級的性質和基于安全等級的路由基于安全等級的路由l安全等級有以下性質：l如果一個節(jié)點的安全等級是k (0k=4)的圖中，一定有一個每個節(jié)點都至少出現(xiàn)兩次的軌跡。而且，任何一個有3個以上節(jié)點并且具有一個度數(shù)小于4 的

43、節(jié)點的圖都沒有那樣一個軌跡。l然而，每個節(jié)點出現(xiàn)兩次僅僅是必要非允分條件。l考慮下面的一部分軌跡，每個節(jié)點的上標i表示這個節(jié)點是第i次出現(xiàn)vi1vi2vj1vj24.11.2 基于路徑的路由基于路徑的路由 Wu的基于軌跡的模式：充要條的基于軌跡的模式：充要條件件l假定vi和vj在軌跡中僅僅出現(xiàn)兩次。顯然(vj,vi)不是這個軌跡上的一個可行的路由。l因此，問題的充要條件如下：對于一個任意給定的節(jié)點vi，在出現(xiàn)在最右邊的vi的左邊一定會至少有一個其他節(jié)點，并且在出現(xiàn)在最左邊的vi的右邊一定會至少有一個其他節(jié)點?；谲壽E的模式：基于軌跡的模式：兩個連續(xù)的哈密爾頓路徑兩個連續(xù)的哈密爾頓路徑l4.5節(jié)

44、中的基于路徑的雙環(huán)路由方法是符合這個充要條件的。l確切地說，任何兩個連續(xù)的哈密爾頓路徑都符合這個條件。l注意：兩個連續(xù)的哈密爾頓路徑需要一個更強的條件l然而，如果每個節(jié)點在軌跡中出現(xiàn)的次數(shù)不能多于兩次，那么兩個連續(xù)的哈密爾頓路徑就是一個充要條件了?；谲壽E的模式：基于軌跡的模式：兩個連續(xù)的哈密爾頓路徑兩個連續(xù)的哈密爾頓路徑（contd）l易知在任何2維圓環(huán)和任何k(=4)維立方中，都存在兩個連續(xù)的哈密爾頓路徑。l下圖顯示了在4維立方中的兩個邊分離的哈密爾頓回路?；谲壽E的模式：基于軌跡的模式：建立兩個連續(xù)的哈密爾頓路徑建立兩個連續(xù)的哈密爾頓路徑l在n(n=4)維立方中建立邊分離的哈密爾頓回路的

45、一般方法如下：1.將n維立方沿著維度n分成兩個n-1維立方。2.每個n-1維立方中建立兩個哈密爾頓回路。3.把n-1維立方的兩個邊分離的哈密爾頓回路連接起來，組成n維立方中的一個哈密爾頓回路。方法是：l在每個回路中去掉一個邊以便打破回路，沿著維度n增加兩個邊從而把兩個打破的回路連接起來。4.連接剩下的兩個哈密爾頓回路，從而形成n維立方中的另一個哈密爾頓回路。l在n維立方中建立兩個邊分離的哈密爾頓路徑。l從n維立方的兩個邊分離的哈密爾頓回路中去掉兩個鄰邊，就得到了兩個連續(xù)的哈密爾頓路徑。4.11.3 使用安全等級在超立方中使用安全等級在超立方中進行組播進行組播l組播的關鍵問題是：l每個中間節(jié)點u

46、（包括源節(jié)點s）向它的合適的鄰居節(jié)點發(fā)送一個目標節(jié)點集合u1, u2, um。l例如，l若一個目標節(jié)點集合u1, u2, u3=0101, 1001, 0000并且節(jié)點u=1010相對地址相對地址l本節(jié)介紹的算法中涉及如下的定義：l相對地址ri：取節(jié)點u與目標節(jié)點ui的地址值的異或值l上例中，u=1010；u1=0101則相對地址r1=u u1=1010 0101=1111l相對地址的某一位為1，表示在相應的維度上必須進行一次跳步l因此可以用目標節(jié)點關于節(jié)點u的相對地址來代表目標節(jié)點l使用相對地址的集合表示目標節(jié)點的集合，用R表示：R=ri ，其中ri=u ui, 1=i=m。l上例中： u=

47、1010； u1, u2, u3= 0101, 1001, 0000 則R=r1, r2, r3= 1111, 0111, 1010節(jié)點間的距離、地址總和節(jié)點間的距離、地址總和l由于相對地址中的1代表了一個必須的跳步，因此相對地址中1的個數(shù)|ri|=1=j=nri(j)代表節(jié)點u和ui的最短距離l如上例中：|r1|=4, |r2|=3, |r3|=2l地址總和：表示集合中目標節(jié)點在不同維度的分布，使用as表示l由于相對地址的每一位對應于一個維度，取所有相對地址在某一維的值之和（1的個數(shù)），就是所有目標節(jié)點在該維度的分布情況l因此，地址總和as=riRril如上例中， R=r1, r2, r3=

48、 1111, 0111, 1010，因此as = 2232相對地址的更新相對地址的更新l為避免重復計算相對地址，僅在源節(jié)點計算相對地址。l每當具有相對地址r的目標節(jié)點被沿著維度d發(fā)送到下一個節(jié)點，r的第d位就被置為0。即這個目標節(jié)點的新的相對地址是r(d)。l上例u=1010，u1=0101，相對地址r1=1111，假如u1沿著第2維被送到鄰居1000處，則在新的中間節(jié)點（1000）上，具有新的相對地址為1101，正好為r1(2)l為避免在新的中間節(jié)點1000上重新計算相對地址，只需要在發(fā)送消息時將目標地址的相應位置0即可（即r(d)操作）基于相對地址路由的基本描述基于相對地址路由的基本描述l

49、為保證時間最優(yōu)，使用下面的簡單策略：l當目標節(jié)點ui關于中間節(jié)點u的相對地址ri的第d位等于1 時，ri(d)將沿著d維度發(fā)送到u的鄰居u(d)。l當目標節(jié)點ui的相對地址ri在不同的位（維度）有超過一個的1值時，相對地址ri可以被轉發(fā)到任意一個維度。l此時，需要在n維中確定一個優(yōu)先級順序。這個優(yōu)先級順序的信息決定了組播的結果。l優(yōu)先級順序的定義應該能夠實現(xiàn)對路徑的最大限度的共享從而使流量最小使用安全等級的原因使用安全等級的原因l在組播中，組播消息不應到達死端（dead end）l當一個特定目標節(jié)點的所有海明距離路徑都被出錯鄰居阻塞時，死端就會出現(xiàn)在中間節(jié)點。l在這種情況下，為了到達那個目標必

50、須繞道或回退。l為了避免盡頭的出現(xiàn)，應該限制向附近有出錯節(jié)點的鄰居發(fā)送的目標的數(shù)目。l這就是在維度有限決策時使用安全等級的原因。基于安全等級的組播基于安全等級的組播l介紹三個方法l基于安全等級的組播SLBM；l修正的基于安全等級的組播（MSLBM）和l基于地址總和的組播ABSMSLBMlSLBM中，維度優(yōu)先級根據(jù)該維度上的鄰居的安全等級事先決定的。l沿著一個維度的鄰居的安全等級越高，這個維度的優(yōu)先級順序就越高l當有兩個或兩個以上的維度上的鄰居具有相同的最高安全等級時，可以使用兩個方法。1.SLBM中，隨機決定它們的優(yōu)先順序2.MSLBM（見下頁）MSLBMlMSLBM中，當兩個（或更多）鄰居具

51、有相同的安全等級時l維度優(yōu)先順序根據(jù)相應位在所有目標的地址總和中的值決定。l從根本上說，若維度d上的鄰居可以承擔最大可能的目標節(jié)點，即若as(d)在地址總和中具有最大值，則d就有最高優(yōu)先級。l當?shù)刂房偤椭杏谐^一個的位其有相同的最大值時，選擇是隨機的。l下一個優(yōu)先級的選擇使用同樣的方法，只不過此時要根據(jù)更新的目標節(jié)點集，即去掉上述被轉發(fā)到高優(yōu)先級維度的節(jié)點ASBMlASBM中，維度優(yōu)先級主要依賴于地址總和中的位值l若在一個維度上的鄰居節(jié)點能承受最大數(shù)目的節(jié)點，那這個維度就具有最高優(yōu)先級。l為保證時間最優(yōu)，只有與選定的鄰居的海明距離不超過k（k為該鄰居的安全等級）的目標節(jié)點才能被包括進來。l在這種情況下，所有鄰居的安全等級和目標節(jié)點的相對距離都在決策中體現(xiàn)出來了。l當存在一個以上的能承載同樣最大數(shù)目的目標節(jié)點的鄰居時1.可以使用一種修正的ASBM正如MSLBM那樣，這些鄰居的優(yōu)先級根據(jù)其安全等級確定2.在ASBM中，這些節(jié)點的優(yōu)先順序是隨機選擇的。SLBM、MSLBM和和ASBMl若源節(jié)點在出錯的n維立方中是安全的，那么由SLBM, MSLBM或ASBM產生的組播一定是時間最優(yōu)的。l當源節(jié)點不安全并且出錯節(jié)點的個數(shù)不超過n