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

1、.高級操作系統(tǒng)高級操作系統(tǒng)Advanced Operating System0551_3607394.第四章第四章 分布式路由算法分布式路由算法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容錯組播算法.4.10 超立方中的容錯單播超立方中的容錯單播 l按照使用的錯誤信息類型對超立方中的容錯單播路由進(jìn)行分類：l基于局部信息的l基于有限全局信息的l基于擴(kuò)展安全等級模型的.4.10.1 基于

2、局部信息的模型基于局部信息的模型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)行路由的方法是很直接的。l消息沿著n條點分離路徑進(jìn)行傳送，并且其中至少有一條是好的。l這樣，就可通過那條路徑到達(dá)目標(biāo)，路徑最大長度是k+2.4.10.1 基于局部信息的模型基于局部信息的模型lchen和shin給出了下面四種容錯路由算法: l出錯組件小于n-1，不確保有最優(yōu)路徑。l出錯組件小于n-1，確保有最優(yōu)路徑。l出錯組件無限制，不確保有最優(yōu)路徑。l出錯組件

3、無限制，確保有最優(yōu)路徑。1.第2和第4種情況是所希望的，但相應(yīng)的算法會引入特別的開銷。.4.10.1 基于局部信息的模型基于局部信息的模型l下面考慮上述第一種情況的算法，l首先，給出等位序列的定義l接著，給出消息的表示方法l然后，給出算法l最后，舉例.4.10.1 基于局部信息的模型基于局部信息的模型等位序列定義等位序列定義l定義：等位序列d1, d2, , dk為當(dāng)前節(jié)點與目標(biāo)節(jié)點不同的所有維度（也叫首選維度，preferred dimension）l注意：l為表示一個消息的目標(biāo)，等位序列要和消息一起傳送l因當(dāng)前節(jié)點會隨著消息的傳遞而變化，故等位序列也隨著變化例如： 當(dāng)前節(jié)點：0 0 1 0

4、 目標(biāo)節(jié)點：0 1 1 1等位序列是1,3.4.10.1 基于局部信息的模型基于局部信息的模型消息的表示消息的表示l每個消息都有一個n位的向量標(biāo)志，用以保存“空余維度(spare dimensions)”。l可以用這些維度來繞過出錯組件。l注意：空余維度就是那些沒有在最初的等位序列中出現(xiàn)的維度l源節(jié)點發(fā)起路由時，標(biāo)志中的所有位都將清零。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的值以判斷自

5、身是否為消息的目標(biāo)l若不是，節(jié)點將嘗試按照剩下的等位序列中指定的維度發(fā)送消息l每個節(jié)點都將努力沿著最短路徑發(fā)送消息。l然而，若通往最短路徑的維度的那些連接出錯，這個節(jié)點將使用空余維度通過另外的路徑發(fā)送消息。.4.10.1 基于局部信息的模型基于局部信息的模型算法的描述算法的描述注意：u(i)表示沿著維度i的u的鄰居。初始，等位序列為由源和目標(biāo)地址異或得到的所有首選維度，空余維度的所有位清零。每個節(jié)點努力沿著最短路徑傳送.4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例l假設(shè)消息m從u=0110 w=1001。最初消息是(4, 1, 2, 3, 4, m, 0000)l按照上述

6、算法，l節(jié)點0110將(3, 2 ,3 ,4, m, 0000)發(fā)送給01101=0111，1.隨后0111將(2, 3, 4, m, 0000)發(fā)送給01112=0101。.4.10.1 基于局部信息的模型基于局部信息的模型算法舉例算法舉例（contd）l由于0101的第3維鏈接出現(xiàn)錯誤，節(jié)點0101將發(fā)送(1, 3, m, 0000)到01014=1101。l然而，由于1101的第3維的鏈接出現(xiàn)錯誤，節(jié)點1101將使用第1維（標(biāo)記=0100，標(biāo)記記下了要繞道時的首選維度），并發(fā)送消息(2, 3, 1 , m, 0101)到1100。.4.10.1 基于局部信息的模型基于局部信息的模型算法舉

7、例算法舉例（contd）l1100依次將發(fā)送(1, 1, m, 0101)到1000。l隨后，節(jié)點1000的第一個鏈接又出現(xiàn)錯誤。這時將使用第2維（此時標(biāo)記=0101）, (2, 1, 2, m, 0111)被路由到1010。l之后，消息將經(jīng)過1011到達(dá)目標(biāo)1001。結(jié)果路徑的長度是8 。.4.10.2 基于有限全局信息的模型：基于有限全局信息的模型：安全等級（定義）安全等級（定義）l考慮具有節(jié)點故障的超立方中的有效路由l每個節(jié)點的有限全局信息使用安全等級來標(biāo)記。l從根本上說，安全等級就是每個節(jié)點周圍鄰居中失效節(jié)點的大致數(shù)目。l定義：設(shè)s(a)=k是節(jié)點a的安全等級，則稱a是k-安全的；l一

8、個失效節(jié)點是0-安全的，即最低的安全等級，l一個n-安全的節(jié)點（也叫安全節(jié)點）安全級別最高l若kn，那么一個k-安全的節(jié)點就是不安全的.安全等級的計算算法安全等級的計算算法l下述算法決定了每個節(jié)點的狀態(tài)。l每個節(jié)點a(i)都保存它所有鄰居節(jié)點的非遞減安全狀態(tài)序列l(wèi)開始，所有非出錯節(jié)點都是n-安全的，所有出錯節(jié)點都是0-安全的。l該算法需要n-1次重復(fù)達(dá)到穩(wěn)定狀態(tài)。.安全等級舉例安全等級舉例出錯節(jié)點0011, 0100, 0110和1001是0-安全的（黑色）節(jié)點0001, 0010, 0111和1011是1-安全的（棕色），因為每個都有兩個出錯節(jié)點，非遞減序列為0,0,2,2或 0,0,2,4

9、或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,400,10,1,2,3.安全等級的性質(zhì)和安全等級的性質(zhì)和基于安全等級的路由基于安全等級的路由l安全等級有以下性質(zhì)：l若一個節(jié)點的安全等級是k (0kn)，那么在k海明距離內(nèi)，至少存在一個從該節(jié)點到任意節(jié)點的海明距離路徑。l因此：l當(dāng)源的安全等級大于源和目標(biāo)間的距離時，就可以保證最優(yōu)路由。l在基于安全等級的路由中，一個引導(dǎo)向量被附加在路由消息上l引導(dǎo)向量

10、 = 當(dāng)前節(jié)點和目標(biāo)節(jié)點的按位異或.基于安全等級的路由舉例基于安全等級的路由舉例l圖中，每個圓圈（節(jié)點）中的數(shù)字表明該節(jié)點的安全等級。l考慮以s1=1110和d1=0001為源和目標(biāo)的單播路由引導(dǎo)向量是N1=s1 d1= 1111，從而H(s1, d1)=4。l由于源節(jié)點s1的安全等級是4，從而可以使用最優(yōu)算法（如下頁）。.l在源節(jié)點的首選節(jié)點中，節(jié)點1010, 1100 和1111的安全等級為4（藍(lán)色），節(jié)點0110 的安全等級為0（黑色）。l選擇一個具有最高安全等級的一個鄰居節(jié)點，比如沿0維度的1111l引導(dǎo)向量N的相應(yīng)維復(fù)位為0=11110=1110，和消息一起被發(fā)送。.l在中間節(jié)點11

11、11，根據(jù)引導(dǎo)向量1110，首選鄰居集合為0111, 1011, 1101，其中：l沿1維度的鄰居1101具有最高的安全等級4，因此它成為下一個中間節(jié)點，引導(dǎo)向量更新為11101=1100。.l在節(jié)點1101，兩個首選鄰居節(jié)點中：3維度鄰居0101的安全等級為2；2維度鄰居1001是出錯節(jié)點l選擇安全等級為2的0101，并更新引導(dǎo)向量為：11003=0100l在節(jié)點0101，只在2維度有一個首選鄰居0001l引導(dǎo)向量更新為：01002=0000。l收到引導(dǎo)向量為0000的單播消息后，節(jié)點0001把自已作為目標(biāo)節(jié)點，同時終止單播算法。.4.10.2 基于有限全局信息的模型：基于有限全局信息的模型

12、：安全等級安全等級l當(dāng)源s的安全等級小于它和目標(biāo)d間的距離|s d|時只要存在一個安全等級不小于|s d|-1的首選鄰居，仍可通過將信息轉(zhuǎn)發(fā)到這個節(jié)點來實現(xiàn)最優(yōu)路由否則，如果存在一個安全等級不低于|s d|+1的空閑鄰居，也可通過將消息轉(zhuǎn)發(fā)到這個節(jié)點實現(xiàn)次優(yōu)路由。結(jié)果路徑的長度是|s d|+2 .4.10.3 基于擴(kuò)展安全等級模型的基于擴(kuò)展安全等級模型的路由：路由：安全向量安全向量l安全等級模型具有以下缺陷：l節(jié)點的安全等級為k僅說明在k海明距離中存在一個海明距離路徑。并沒有提供關(guān)于是否存在到達(dá)超過k海明距離的節(jié)點的海明距離路徑。l安全向量的概念可以有效地引入失效鏈接的信息，并能提供系統(tǒng)中錯誤

13、的數(shù)量和分布的信息.安全向量安全向量l特別地，l設(shè)(a1, a2, , an)是n維立方中節(jié)點a的安全向量如果ak=1，則存在一個從a到任意一個k海明距離的節(jié)點的海明距離路徑。l一個節(jié)點的安全向量可以通過在鄰居節(jié)點中進(jìn)行n-1輪信息交換來計算。l一個出錯節(jié)點的安全向量是(0, 0, , 0)。 任意一個節(jié)點到a的海明距離在1n之間ak的取值為0或1.安全向量安全向量（contd）l對于一個非出錯節(jié)點a, 設(shè)a的安全向量是(a1, a2, , an), a在維度i上的鄰居的安全向量是(a1(i), a2(i), , an(i)若節(jié)點a是一個出錯鏈接的端節(jié)點，那在相鄰的其他端節(jié)點看來，a的安全向量

14、是(0, 0, , 0)且以及 a到相應(yīng)端節(jié)點的海明距離為1，但不存在到該端節(jié)點的距離為1的路徑求和的話，值在0n之間.4.10.3 基于擴(kuò)展安全等級模型的基于擴(kuò)展安全等級模型的路由：安全向量路由：安全向量l計算安全向量的方法與通過節(jié)點之間交換信息和鄰居之間互相更新而計算安全等級的方法類似。l路由算法和基于安全等級模型的方法也類似。.4.11 容錯組播容錯組播l如前所述，在沒有出錯組件的情況下，網(wǎng)和超立方中的大部分組播問題都是NP完全問題。l在出現(xiàn)錯誤的情況下，問題變得更復(fù)雜。l一般會使用啟發(fā)性方法。l本節(jié)l再一次使用n維立方來說明不同的方法。l僅考慮系統(tǒng)中的單一組播.4.11.1 一般方法一

15、般方法l幾種容錯組播方案已經(jīng)被提出來，可以按照每個節(jié)點使用的網(wǎng)絡(luò)信息對它們進(jìn)行分類l基于局部信息的容錯組播l每個節(jié)點僅僅知道它的相鄰節(jié)點和鏈接的狀態(tài)l優(yōu)點：簡單；缺點：在最壞的情況下需要的時間步數(shù)不可控l基于局部信息，并且限制性錯誤模型的容錯組播例如，每個節(jié)點最多有一個出錯鄰居l基于全局信息的組播：l假定每個節(jié)點都知道網(wǎng)絡(luò)中的錯誤分布。l可以保證時間最優(yōu)。l然而，它需要一個復(fù)雜的收集全局信息的過程。.4.11.1 一般方法一般方法l基于有限全局信息的組播是上述兩種方案的綜合。l可以得到一個最優(yōu)或次優(yōu)的方案l同時可以使收集和維護(hù)全局信息的過程相對不是很復(fù)雜l例如：Liang, Bhattacha

16、rya和Tsai提出了組播方案中，每個節(jié)點知道兩個跳躍之內(nèi)所有鏈接的狀態(tài)這個方案可以經(jīng)受n-1個錯誤鏈接，在最壞情況下額外的時間步數(shù)為2n。.4.11.2 基于路徑的路由基于路徑的路由為什么考慮路徑的路由？為什么考慮路徑的路由？l在使用樹結(jié)構(gòu)的特定系統(tǒng)中l(wèi)在路由過程中復(fù)制路由消息是很低效的。l而且，如果樹形結(jié)構(gòu)的一個樹枝阻塞，那么路由就被阻塞。l對于長消息這個問題更為嚴(yán)重。l因此需要考慮一個禁止在路由過程中分叉的方法，比如基于路徑的路由（參見4.4，使用哈密爾頓回路/路徑）。l本小節(jié)介紹Wu的基于軌跡的模式，該方法是對路徑模式的擴(kuò)展l下面首先給出Wu提出算法的背景.背景：背景：l前面講過，在L

17、in等人提出的基于路徑的路由中，使用了雙向信道模型，即每個信道都是雙向的l在網(wǎng)絡(luò)中找到一個哈密爾頓路徑。l所有的路由步驟都遵從選定的哈密爾頓路徑（在兩個方向）。l顯然，這樣避免了循環(huán)等待和死鎖。l每個（有序的）源和目標(biāo)對在路徑的一個方向上出現(xiàn)。l但系統(tǒng)使用半雙工信道時，信道可以在兩個方向發(fā)送信息，但是同時只能有一個方向發(fā)送。l用于雙向鏈接的哈密爾頓路徑方法就不再適用了。lWu將基于路徑的模式擴(kuò)展為基于軌跡的模式。.4.11.2 基于路徑的路由基于路徑的路由Wu的基于軌跡的模式：軌跡的定義的基于軌跡的模式：軌跡的定義l圖G中的一個軌跡v0v1v2vn是一次所有邊都不同的“行走(walk)”。l圖

18、G中的一次行走是一個有限的邊的序列。l路徑是一種特殊的軌跡：所有的點都是不同的。l為了保證每個源和目標(biāo)對都在軌跡中出現(xiàn)至少一次，每個節(jié)點都至少要出現(xiàn)兩次。.4.11.2 基于路徑的路由基于路徑的路由 Wu的基于軌跡的模式：充要條的基于軌跡的模式：充要條件件l由圖論可知，在每個節(jié)點都具有偶節(jié)點度數(shù)(4)的圖中，一定有一個每個節(jié)點都至少出現(xiàn)兩次的軌跡。而且，任何一個有3個以上節(jié)點并且具有一個度數(shù)小于4 的節(jié)點的圖都沒有那樣一個軌跡。l然而，每個節(jié)點出現(xiàn)兩次僅僅是必要非充分條件。l考慮下面的一部分軌跡，上標(biāo)i表示對應(yīng)節(jié)點是第i次出現(xiàn)vi1vi2vj1vj2l假定vi和vj在軌跡中僅僅出現(xiàn)兩次。顯然(

19、vj,vi)不是這個軌跡上的一個可行的路由。.4.11.2 基于路徑的路由基于路徑的路由 Wu的基于軌跡的模式：充要條的基于軌跡的模式：充要條件件l因此，問題的充要條件如下：對于一個任意給定的節(jié)點vi，在出現(xiàn)在最右邊的vi的左邊一定會至少有一個其他節(jié)點，并且在出現(xiàn)在最左邊的vi的右邊一定會至少有一個其他節(jié)點。.基于軌跡的模式：基于軌跡的模式：兩個連續(xù)的哈密爾頓路徑兩個連續(xù)的哈密爾頓路徑l4.5節(jié)中的基于路徑的雙環(huán)路由方法是符合這個充要條件的。l任何兩個連續(xù)的哈密爾頓路徑都符合這個條件。l注意：兩個連續(xù)的哈密爾頓路徑需要一個更強(qiáng)的條件l然而，如果每個節(jié)點在軌跡中出現(xiàn)的次數(shù)不能多于兩次，那么兩個連

20、續(xù)的哈密爾頓路徑就是一個充要條件了。.基于軌跡的模式：基于軌跡的模式：兩個連續(xù)的哈密爾頓路徑（兩個連續(xù)的哈密爾頓路徑（contd）l易知在任何2維圓環(huán)和任何k(4)維立方中，都存在兩個連續(xù)的哈密爾頓路徑。l下圖顯示了在4維立方中的兩個邊分離的哈密爾頓回路。.基于軌跡的模式：基于軌跡的模式：建立兩個連續(xù)的哈密爾頓路徑建立兩個連續(xù)的哈密爾頓路徑l在n(n4)維立方中建立邊分離的哈密爾頓回路的一般方法如下：l將n維立方沿著維度n分成兩個n-1維立方。l每個n-1維立方中建立兩個哈密爾頓回路。l把n-1維立方的兩個邊分離的哈密爾頓回路連接起來，組成n維立方中的一個哈密爾頓回路。方法是：l在每個回路中去

21、掉一個邊以便打破回路，沿著維度n增加兩個邊從而把兩個打破的回路連接起來。l連接剩下的兩個哈密爾頓回路，從而形成n維立方中的另一個哈密爾頓回路。l在n維立方中建立兩個邊分離的哈密爾頓路徑。1.從n維立方的兩個邊分離的哈密爾頓回路中去掉兩個鄰邊，就得到了兩個連續(xù)的哈密爾頓路徑。.4.11.3 使用安全等級在超立方中使用安全等級在超立方中進(jìn)行組播進(jìn)行組播l組播的關(guān)鍵問題是：l每個中間節(jié)點u（包括源節(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é)介紹的算法

22、中涉及如下的定義：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, 1im。l上例中： u=1010； u1, u2, u3= 0101, 1001, 0000 則R=r1, r2, r3= 1111, 0111, 1010.節(jié)點間的距離、地址總和節(jié)點間的距離、地址總和l由于相對地址中的1代表了一個必須的跳

23、步，因此相對地址中1的個數(shù)|ri|=1jnri(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= 1111, 0111, 1010，因此as = 2232.相對地址的更新相對地址的更新l為避免重復(fù)計算相對地址，僅在源節(jié)點計算相對地址。l每當(dāng)具有相對地址r的目標(biāo)節(jié)點被沿著維度d發(fā)送到下一個節(jié)點，r的第d位就被置為0

24、。即這個目標(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為保證時間最優(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值時，

25、相對地址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)必須繞道或回退。l為了避免盡頭的出現(xiàn)，應(yīng)該限制向附近有出錯節(jié)點的鄰居發(fā)送的目標(biāo)的數(shù)目。l這就是在維度有限決策時使用安全等級的原因。.基于安全等級的組播基于安全等級的組播l介紹三個方法l基于安全等級的組播SLBM；l

26、修正的基于安全等級的組播（MSLBM）和l基于地址總和的組播ABSM.SLBMlSLBM中，維度優(yōu)先級根據(jù)該維度上的鄰居的安全等級事先決定的。l沿著一個維度的鄰居的安全等級越高，這個維度的優(yōu)先級順序就越高l當(dāng)有兩個或兩個以上的維度上的鄰居具有相同的最高安全等級時，可以使用兩個方法。lSLBM中，隨機(jī)決定它們的優(yōu)先順序1.MSLBM（見下頁）.MSLBMlMSLBM中，當(dāng)兩個（或更多）鄰居具有相同的安全等級時l維度優(yōu)先順序根據(jù)相應(yīng)位在所有目標(biāo)的地址總和中的值決定。l若維度d上的鄰居可以承擔(dān)最大可能的目標(biāo)節(jié)點，即若as(d)在地址總和中具有最大值，則d就有最高優(yōu)先級。l當(dāng)?shù)刂房偤椭杏谐^一個的位其

27、有相同的最大值時，選擇是隨機(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é)點的鄰居時l可以使用一種修正的ASBM正如MSLBM那樣，這些鄰居的優(yōu)先級根據(jù)其安全等級確定1.在ASB

28、M中，這些節(jié)點的優(yōu)先順序是隨機(jī)選擇的。.SLBM、MSLBM和和ASBMl若源節(jié)點在出錯的n維立方中是安全的，那么由SLBM, MSLBM或ASBM產(chǎn)生的組播一定是時間最優(yōu)的。l當(dāng)源節(jié)點不安全并且出錯節(jié)點的個數(shù)不超過n-1時，從源節(jié)點到一個目標(biāo)的路徑的長度l或者等于相應(yīng)的海明距離，或者比相應(yīng)的海明距離多2。l若源和任一目標(biāo)間的相對距離不超過源的安全等級，那么由SLBM, MSLBM或ASBM產(chǎn)生的組播一定是時間最優(yōu)的。.算法舉例算法舉例l下圖顯示了一個有四個出錯節(jié)點的Q4 ，出錯節(jié)點為黑色節(jié)點：1100, 0110, 0011和0001.算法舉例：算法舉例：計算安全等級計算安全等級l開始，所有

29、非出錯節(jié)點都是4-安全的，即安全的l第一輪鄰居間交換過信息后節(jié)點0010, 0111, 0100和1110 因有兩個或兩個以上的出錯鄰居，都從4-安全變?yōu)?-安全狀態(tài)其他節(jié)點的狀態(tài)保持不變。.算法舉例：算法舉例：計算安全等級（計算安全等級（contd）l在第二輪之后，節(jié)點0000 和0101 的狀態(tài)變?yōu)?-安全，這是因為它們有兩個1-安全的節(jié)點和一個2-安全的節(jié)點。l兩輪之后，每個節(jié)點的安全等級達(dá)到穩(wěn)定。l圖中節(jié)點中的數(shù)字即代表該節(jié)點最終的安全等級.算法舉例：算法舉例：計算相對地址和地址總和計算相對地址和地址總和l假定圖中源節(jié)點是安全節(jié)點1000 ，組播集合u=u1, u2, u3, u4, u5, u6=0000, 0010, 0100, 0101, 0111, 1001源和目標(biāo)之間的相對地址集合為R=r1, r2, r3, r4, r5, r6=1000, 1010, 1100, 1101, 1111, 0001因此，地址總和as=5323.算法舉例：算法舉例：使用使用SLBMlSLBM方法僅使用鄰居維度序列（ds）所代表的鄰居的安全等級來確定鄰居節(jié)點間的優(yōu)先級。l本例中，維度2具有最高的優(yōu)先級，其次是維度1和維度4；維度3具有最低的優(yōu)先級。l因為r2和r5的第二位是1，所以r2(2)和r5(2)和組播消息一起將被發(fā)往節(jié)點1010（1000 沿著維度2 的鄰居）。l假定組