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

1、.高級(jí)操作系統(tǒng)高級(jí)操作系統(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)和無(wú)死鎖路由算法l幾個(gè)自適應(yīng)和無(wú)死鎖路由算法 l容錯(cuò)單播的一般方法 l網(wǎng)格和圓環(huán)中的容錯(cuò)單播算法l超立方中的容錯(cuò)單播算法l容錯(cuò)組播算法.4.10 超立方中的容錯(cuò)單播超立方中的容錯(cuò)單播 l按照使用的錯(cuò)誤信息類型對(duì)超立方中的容錯(cuò)單播路由進(jìn)行分類：l基于局部信息的l基于有限全局信息的l基于擴(kuò)展安全等級(jí)模型的.4.10.1 基于

2、局部信息的模型基于局部信息的模型l已經(jīng)證明，l對(duì)n維立方中的任何兩點(diǎn)u和w，如果H(u,w)=k，那么從u到w恰好有n條點(diǎn)分離路徑。其中，l有k條長(zhǎng)度為k的路徑和(n-k)條長(zhǎng)度為k+2的路徑l若出錯(cuò)組件的數(shù)目L小于n，那么用多條路徑進(jìn)行路由的方法是很直接的。l消息沿著n條點(diǎn)分離路徑進(jìn)行傳送，并且其中至少有一條是好的。l這樣，就可通過(guò)那條路徑到達(dá)目標(biāo)，路徑最大長(zhǎng)度是k+2.4.10.1 基于局部信息的模型基于局部信息的模型lchen和shin給出了下面四種容錯(cuò)路由算法: l出錯(cuò)組件小于n-1，不確保有最優(yōu)路徑。l出錯(cuò)組件小于n-1，確保有最優(yōu)路徑。l出錯(cuò)組件無(wú)限制，不確保有最優(yōu)路徑。l出錯(cuò)組件

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

4、 目標(biāo)節(jié)點(diǎn)：0 1 1 1等位序列是1,3.4.10.1 基于局部信息的模型基于局部信息的模型消息的表示消息的表示l每個(gè)消息都有一個(gè)n位的向量標(biāo)志，用以保存“空余維度(spare dimensions)”。l可以用這些維度來(lái)繞過(guò)出錯(cuò)組件。l注意：空余維度就是那些沒(méi)有在最初的等位序列中出現(xiàn)的維度l源節(jié)點(diǎn)發(fā)起路由時(shí)，標(biāo)志中的所有位都將清零。l消息的表示：(k, d1, d2, , dk, 消息, 標(biāo)記)。lk為剩余路徑長(zhǎng)度， k會(huì)在消息的發(fā)往過(guò)程中不斷更新l當(dāng)k變?yōu)?時(shí)，消息就到達(dá)目標(biāo)了。.4.10.1 基于局部信息的模型基于局部信息的模型算法描述算法描述l當(dāng)節(jié)點(diǎn)收到一個(gè)消息時(shí)，檢查k的值以判斷自

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

6、算法，l節(jié)點(diǎn)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)錯(cuò)誤，節(jié)點(diǎn)0101將發(fā)送(1, 3, m, 0000)到01014=1101。l然而，由于1101的第3維的鏈接出現(xiàn)錯(cuò)誤，節(jié)點(diǎn)1101將使用第1維（標(biāo)記=0100，標(biāo)記記下了要繞道時(shí)的首選維度），并發(fā)送消息(2, 3, 1 , m, 0101)到1100。.4.10.1 基于局部信息的模型基于局部信息的模型算法舉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、掉一個(gè)邊以便打破回路，沿著維度n增加兩個(gè)邊從而把兩個(gè)打破的回路連接起來(lái)。l連接剩下的兩個(gè)哈密爾頓回路，從而形成n維立方中的另一個(gè)哈密爾頓回路。l在n維立方中建立兩個(gè)邊分離的哈密爾頓路徑。1.從n維立方的兩個(gè)邊分離的哈密爾頓回路中去掉兩個(gè)鄰邊，就得到了兩個(gè)連續(xù)的哈密爾頓路徑。.4.11.3 使用安全等級(jí)在超立方中使用安全等級(jí)在超立方中進(jìn)行組播進(jìn)行組播l組播的關(guān)鍵問(wèn)題是：l每個(gè)中間節(jié)點(diǎn)u（包括源節(jié)點(diǎn)s）向它的合適的鄰居節(jié)點(diǎn)發(fā)送一個(gè)目標(biāo)節(jié)點(diǎn)集合u1, u2, um。l例如，l若一個(gè)目標(biāo)節(jié)點(diǎn)集合u1, u2, u3=0101, 1001, 0000并且節(jié)點(diǎn)u=1010.相對(duì)地址相對(duì)地址l本節(jié)介紹的算法

22、中涉及如下的定義：l相對(duì)地址ri：取節(jié)點(diǎn)u與目標(biāo)節(jié)點(diǎn)ui的地址值的異或值l上例中，u=1010；u1=0101則相對(duì)地址r1=u u1=1010 0101=1111l相對(duì)地址的某一位為1，表示在相應(yīng)的維度上必須進(jìn)行一次跳步l因此可以用目標(biāo)節(jié)點(diǎn)關(guān)于節(jié)點(diǎn)u的相對(duì)地址來(lái)代表目標(biāo)節(jié)點(diǎn)l使用相對(duì)地址的集合表示目標(biāo)節(jié)點(diǎn)的集合，用R表示：R=ri ，其中ri=u ui, 1im。l上例中： u=1010； u1, u2, u3= 0101, 1001, 0000 則R=r1, r2, r3= 1111, 0111, 1010.節(jié)點(diǎn)間的距離、地址總和節(jié)點(diǎn)間的距離、地址總和l由于相對(duì)地址中的1代表了一個(gè)必須的跳

23、步，因此相對(duì)地址中1的個(gè)數(shù)|ri|=1jnri(j)代表節(jié)點(diǎn)u和ui的最短距離l如上例中：|r1|=4, |r2|=3, |r3|=2l地址總和：表示集合中目標(biāo)節(jié)點(diǎn)在不同維度的分布，使用as表示l由于相對(duì)地址的每一位對(duì)應(yīng)于一個(gè)維度，取所有相對(duì)地址在某一維的值之和（1的個(gè)數(shù)），就是所有目標(biāo)節(jié)點(diǎn)在該維度的分布情況l因此，地址總和as=riRril如上例中， R=r1, r2, r3= 1111, 0111, 1010，因此as = 2232.相對(duì)地址的更新相對(duì)地址的更新l為避免重復(fù)計(jì)算相對(duì)地址，僅在源節(jié)點(diǎn)計(jì)算相對(duì)地址。l每當(dāng)具有相對(duì)地址r的目標(biāo)節(jié)點(diǎn)被沿著維度d發(fā)送到下一個(gè)節(jié)點(diǎn)，r的第d位就被置為0

24、。即這個(gè)目標(biāo)節(jié)點(diǎn)的新的相對(duì)地址是r(d)。l上例u=1010，u1=0101，相對(duì)地址r1=1111，假如u1沿著第2維被送到鄰居1000處，則在新的中間節(jié)點(diǎn)（1000）上，具有新的相對(duì)地址為1101，正好為r1(2)l為避免在新的中間節(jié)點(diǎn)1000上重新計(jì)算相對(duì)地址，只需要在發(fā)送消息時(shí)將目標(biāo)地址的相應(yīng)位置0即可（即r(d)操作）.基于相對(duì)地址路由的基本描述基于相對(duì)地址路由的基本描述l為保證時(shí)間最優(yōu)，使用下面的簡(jiǎn)單策略：l當(dāng)目標(biāo)節(jié)點(diǎn)ui關(guān)于中間節(jié)點(diǎn)u的相對(duì)地址ri的第d位等于1 時(shí)，ri(d)將沿著d維度發(fā)送到u的鄰居u(d)。l當(dāng)目標(biāo)節(jié)點(diǎn)ui的相對(duì)地址ri在不同的位（維度）有超過(guò)一個(gè)的1值時(shí)，

25、相對(duì)地址ri可以被轉(zhuǎn)發(fā)到任意一個(gè)維度。l此時(shí)，需要在n維中確定一個(gè)優(yōu)先級(jí)順序。這個(gè)優(yōu)先級(jí)順序的信息決定了組播的結(jié)果。l優(yōu)先級(jí)順序的定義應(yīng)該能夠?qū)崿F(xiàn)對(duì)路徑的最大限度的共享從而使流量最小.使用安全等級(jí)的原因使用安全等級(jí)的原因l在組播中，組播消息不應(yīng)到達(dá)死端（dead end）l當(dāng)一個(gè)特定目標(biāo)節(jié)點(diǎn)的所有海明距離路徑都被出錯(cuò)鄰居阻塞時(shí)，死端就會(huì)出現(xiàn)在中間節(jié)點(diǎn)。l在這種情況下，為了到達(dá)那個(gè)目標(biāo)必須繞道或回退。l為了避免盡頭的出現(xiàn)，應(yīng)該限制向附近有出錯(cuò)節(jié)點(diǎn)的鄰居發(fā)送的目標(biāo)的數(shù)目。l這就是在維度有限決策時(shí)使用安全等級(jí)的原因。.基于安全等級(jí)的組播基于安全等級(jí)的組播l介紹三個(gè)方法l基于安全等級(jí)的組播SLBM；l

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

27、有相同的最大值時(shí)，選擇是隨機(jī)的。l下一個(gè)優(yōu)先級(jí)的選擇使用同樣的方法，只不過(guò)此時(shí)要根據(jù)更新的目標(biāo)節(jié)點(diǎn)集，即去掉上述被轉(zhuǎn)發(fā)到高優(yōu)先級(jí)維度的節(jié)點(diǎn).ASBMlASBM中，維度優(yōu)先級(jí)主要依賴于地址總和中的位值l若在一個(gè)維度上的鄰居節(jié)點(diǎn)能承受最大數(shù)目的節(jié)點(diǎn)，那這個(gè)維度就具有最高優(yōu)先級(jí)。l為保證時(shí)間最優(yōu)，只有與選定的鄰居的海明距離不超過(guò)k（k為該鄰居的安全等級(jí)）的目標(biāo)節(jié)點(diǎn)才能被包括進(jìn)來(lái)。l在這種情況下，所有鄰居的安全等級(jí)和目標(biāo)節(jié)點(diǎn)的相對(duì)距離都在決策中體現(xiàn)出來(lái)了。l當(dāng)存在一個(gè)以上的能承載同樣最大數(shù)目的目標(biāo)節(jié)點(diǎn)的鄰居時(shí)l可以使用一種修正的ASBM正如MSLBM那樣，這些鄰居的優(yōu)先級(jí)根據(jù)其安全等級(jí)確定1.在ASB

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

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