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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、徑B 。l一旦源收到來自目標(biāo)的兩個信號，就意味著RMP已建立起來。源就用任何一種適應(yīng)性最小路由發(fā)送路由消息。l遇到路徑A（或路徑B）的邊界時，剩下的路由就要沿著路徑A （路徑B ）發(fā)往目標(biāo)。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可用任一最小路由算法到達(dá)R1, R2, R3 , R7, R8中的點l可用XY路由（先X后Y）到達(dá)R6中的任何點。l可用YX路由（先Y后X）到達(dá)R4中的任何點。l用XY路由和YX路由都可到達(dá)R5 中的點。4.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最優(yōu)路由面向源的最優(yōu)路由（contd）l當(dāng)目標(biāo)節(jié)點位于R4或R6時，為達(dá)到最優(yōu)路由，位于L1（位于(x,y)西側(cè)的節(jié)點）和L2（位于(x,y)南側(cè)的節(jié)點）上的特定節(jié)點必須具有這個出錯塊的信息。這些信息可以用出錯塊的相應(yīng)角的位置來編碼。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目標(biāo)位于路徑1的南側(cè)或東側(cè)的路由消息不能通過路徑1。l目標(biāo)位于路徑2的北側(cè)或西側(cè)的路由消息不能通過路徑2。l路徑1的路徑信息存儲在(-,y)到(x,y)間的每個節(jié)點上l路徑2的路徑信息存儲在點(x,-)到(x,y)間的每個節(jié)上l為最小化路徑信息，只有每個轉(zhuǎn)彎（出錯塊的角落）的位置是必要的。l所以(x,y)和(x,y)對路徑1是必要的，而(x, y)和(x, y)對路徑2是必要的。4.

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

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

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

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

35、很直接的。l消息沿著n條點分離路徑進(jìn)行傳送，并且其中至少有一條是好的。l這樣，就可通過那條路徑到達(dá)目標(biāo)，路徑最大長度是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種情況是所希望的，但相應(yīng)的算法會引入特別的開銷。4.10.1 基于局部信息的模型基于局部信息的模型第第1種情況種情況等位序列定義等位序列定義l考慮一個第1種情況的算法。l為了容錯，一些訪問過的節(jié)點也保存在消息

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

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

38、型基于局部信息的模型算法的描述算法的描述l更正式地，這個路由算法可以描述如下。注意：u(i)表示沿著維度i的u的鄰居。4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例l考慮下圖中的出錯超立方。l假設(shè)消息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維（標(biāo)記=0100，標(biāo)記記下了要繞道時的首選維度），并發(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維（此時標(biāo)記=0101）, (2, 1, 2, m, 0111)被路由到1010。7.之后，消息將經(jīng)過101

40、1到達(dá)目標(biāo)1001。結(jié)果路徑的長度是8 。4.10.2 基于有限全局信息的模型：基于有限全局信息的模型：安全等級（定義）安全等級（定義）l下面討論具有節(jié)點故障的超立方中的有效路由l這種模式基于每個節(jié)點的有限全局信息l這種信息被標(biāo)記為安全等級。l從根本上說，安全等級就是每個節(jié)點周圍鄰居中失效節(jié)點的大致數(shù)目。l定義：設(shè)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次重復(fù)達(dá)到穩(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是安全的（藍(lán)色）非遞減序列為：0,4,4,4或1,1,4,4或0,2,4,4安全等級的性質(zhì)和安全等級的性質(zhì)和基于安全等級的路由基于安全等級的路由l安全等級有以下性質(zhì)：l如果一個節(jié)點的安全等級是k (0k=4)的圖中，一定有一個每個節(jié)點都至少出現(xiàn)兩次的軌跡。而且，任何一個有3個以上節(jié)點并且具有一個度數(shù)小于4 的

43、節(jié)點的圖都沒有那樣一個軌跡。l然而，每個節(jié)點出現(xiàn)兩次僅僅是必要非允分條件。l考慮下面的一部分軌跡，每個節(jié)點的上標(biāo)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ù)的哈密爾頓路徑需要一個更強(qiáng)的條件l然而，如果每個節(jié)點在軌跡中出現(xiàn)的次數(shù)不能多于兩次，那么兩個連續(xù)的哈密爾頓路徑就是一個充要條件了。基于軌跡的模式：基于軌跡的模式：兩個連續(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 使用安全等級在超立方中使用安全等級在超立方中進(jìn)行組播進(jìn)行組播l組播的關(guān)鍵問題是：l每個中間節(jié)點u

46、（包括源節(jié)點s）向它的合適的鄰居節(jié)點發(fā)送一個目標(biāo)節(jié)點集合u1, u2, um。l例如，l若一個目標(biāo)節(jié)點集合u1, u2, u3=0101, 1001, 0000并且節(jié)點u=1010相對地址相對地址l本節(jié)介紹的算法中涉及如下的定義：l相對地址ri：取節(jié)點u與目標(biāo)節(jié)點ui的地址值的異或值l上例中，u=1010；u1=0101則相對地址r1=u u1=1010 0101=1111l相對地址的某一位為1，表示在相應(yīng)的維度上必須進(jìn)行一次跳步l因此可以用目標(biāo)節(jié)點關(guān)于節(jié)點u的相對地址來代表目標(biāo)節(jié)點l使用相對地址的集合表示目標(biāo)節(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地址總和：表示集合中目標(biāo)節(jié)點在不同維度的分布，使用as表示l由于相對地址的每一位對應(yīng)于一個維度，取所有相對地址在某一維的值之和（1的個數(shù)），就是所有目標(biāo)節(jié)點在該維度的分布情況l因此，地址總和as=riRril如上例中， R=r1, r2, r3=

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

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

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

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