第8章分布式系統(tǒng)中的路由算法ppt課件

1、 分布式路由算法分布式路由算法 主要內(nèi)容（主要內(nèi)容（ contd ）l一般類型網(wǎng)絡(luò)的分布式路由算法l自適應(yīng)和無(wú)死鎖路由算法 l網(wǎng)格和圓環(huán)中的容錯(cuò)單播算法l超立方中的容錯(cuò)單播算法l容錯(cuò)組播算法 進(jìn)程間通信類型進(jìn)程間通信類型l有效的進(jìn)程間通信對(duì)分布式系統(tǒng)的性能很重要l根據(jù)目標(biāo)個(gè)數(shù)的不同，進(jìn)程間通信的類型有：l一對(duì)一單播）l一對(duì)多組播）l一對(duì)所有廣播） 通信延遲及其原因通信延遲及其原因l在基于消息傳遞的分布式系統(tǒng)中，消息一般在到達(dá)目標(biāo)節(jié)點(diǎn)之前可能要通過(guò)一個(gè)或多個(gè)中間節(jié)點(diǎn)，故存在通信延遲。l分布式系統(tǒng)中的通信延遲依賴于如下四個(gè)因素：l網(wǎng)絡(luò)拓?fù)洌簂通常用圖表示l定義處理單元PE之間是如何連接的l路由l決

2、定如何選擇路徑以便將消息傳遞到目的地。 通信延遲及其原因通信延遲及其原因contd）l流量控制l流量控制決定在消息沿路徑傳遞時(shí)如何分配網(wǎng)絡(luò)資源，包括：l信道l緩沖區(qū)l交換l這是一個(gè)實(shí)際的機(jī)制，它決定消息如何從一個(gè)輸入信道轉(zhuǎn)到一個(gè)輸出信道。 路由算法類型路由算法類型l路由算法類型包括：l特殊 vs. 普通l最短 vs. 非最短l確定型 vs. 適應(yīng)型l源路由 vs. 目標(biāo)路由l容錯(cuò)型 vs. 非容錯(cuò)型l冗余型 vs. 非冗余型l死鎖避免型 vs. 非死鎖避免型 一般型路由和特殊型路由一般型路由和特殊型路由l 一般型路由算法l適合于所有類型的網(wǎng)絡(luò)l但是對(duì)于某種特定網(wǎng)絡(luò)不是很有效l特殊型路由算法l只

3、對(duì)特定的網(wǎng)絡(luò)類型有效，如超立方、網(wǎng)格等l這些算法由于利用了特定網(wǎng)絡(luò)的拓?fù)鋵傩?，所以效率往往較高。最短路由算法和非最短路由算法最短路由算法和非最短路由算法l最短路徑算法l對(duì)給定的源-目標(biāo)對(duì)給出一個(gè)代價(jià)最小的路徑l路徑的代價(jià)l所有跳步銜接代價(jià)的線性和。l缺陷：可能會(huì)導(dǎo)致網(wǎng)絡(luò)某一部分的擁塞l非最短路由算法l可以將消息路由到一個(gè)更長(zhǎng)的路徑從而避免擁塞。l在某些情況下，隨機(jī)路由可能是有效的。 確定型路由和適應(yīng)型路由確定型路由和適應(yīng)型路由l確定型路徑算法l路由路徑只在網(wǎng)絡(luò)的拓?fù)浒l(fā)生改變時(shí)才發(fā)生變化，l而且它不使用任何有關(guān)網(wǎng)絡(luò)狀態(tài)的消息。l適應(yīng)型路由算法l路徑根據(jù)網(wǎng)絡(luò)流量而改變。 容錯(cuò)型路由和非容錯(cuò)型路由容

4、錯(cuò)型路由和非容錯(cuò)型路由l容錯(cuò)型路由算法l即使出現(xiàn)錯(cuò)誤，被路由消息也能保證送到。l非容錯(cuò)型路由算法l假定路由不會(huì)出錯(cuò)l路由算法不必動(dòng)態(tài)調(diào)整自己的活動(dòng)。 冗余型路由和非冗余路由冗余型路由和非冗余路由l冗余型路由算法l用幾個(gè)邊分離或節(jié)點(diǎn)分離的路徑向同一個(gè)目標(biāo)發(fā)送多個(gè)拷貝。l只要這些路徑中的一個(gè)是好的，那么就會(huì)至少有一個(gè)消息拷貝到達(dá)目標(biāo)。l必須保證有且只有一個(gè)拷貝被接收l(shuí)非冗余型路由算法l對(duì)每個(gè)目標(biāo)只需轉(zhuǎn)發(fā)消息的一個(gè)拷貝。 死鎖避免型路由和死鎖避免型路由和 非死鎖避免型路由非死鎖避免型路由l死鎖避免型路由算法l通過(guò)仔細(xì)設(shè)計(jì)的路由算法，保證不發(fā)生死鎖。l非死鎖避免型路由算法l沒(méi)有特別的措施來(lái)預(yù)防或避免死

5、鎖。l可能發(fā)生死鎖，也可能不發(fā)生死鎖。 路由函數(shù)路由函數(shù)l路由函數(shù)l定義一個(gè)消息如何從源節(jié)點(diǎn)路由到目標(biāo)節(jié)點(diǎn)。l每個(gè)PE在收到一個(gè)消息以后，都將決定：1把這條消息傳送到本地存儲(chǔ)器，還是2轉(zhuǎn)發(fā)到一個(gè)鄰接的PEl有許多不同的路由函數(shù)的定義，例如l依賴于目標(biāo)的、依賴于輸入的、依賴于源的、依賴于路徑的等等l本章僅使用依賴于目標(biāo)的路由函數(shù) 路由函數(shù)類型路由函數(shù)類型l依賴于源的：依賴于源節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)l依賴于目標(biāo)的：僅僅依賴于當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)l依賴于輸入的：依賴于當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)以及鄰近的鏈接l依賴于路徑的：依賴于目標(biāo)節(jié)點(diǎn)和從源節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的路徑 一般類型網(wǎng)絡(luò)的最短路徑路由算一般類型網(wǎng)絡(luò)的

6、最短路徑路由算法法l許多分組交換網(wǎng)，如法國(guó)的Transpac或美國(guó)的ARPAnet都使用最短路徑路由l本節(jié)介紹三個(gè)一般類型網(wǎng)絡(luò)的最短路徑路由算法：lDijkstra集中式算法lFord分布式算法lARPAnet路由算法 一般類型網(wǎng)絡(luò)的最短路徑路由算法：一般類型網(wǎng)絡(luò)的最短路徑路由算法： 分布式系統(tǒng)圖示分布式系統(tǒng)圖示l一般地，一個(gè)分布式系統(tǒng)可以用圖來(lái)表示：節(jié)點(diǎn)代表PE處理單元）；邊代表通信鏈接；每個(gè)鏈接的數(shù)字代表鏈接代價(jià)。l右圖顯示了一個(gè)分布式系統(tǒng)的例子 Dijkstra集中式算法集中式算法l第一種類型的算法以集中式的風(fēng)格進(jìn)行路由lDijkstra集中式算法可以發(fā)現(xiàn)一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路

7、徑。lDijkstra集中式算法需求：l需要了解給定網(wǎng)絡(luò)的全局拓?fù)湎?，即?網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的列表； 節(jié)點(diǎn)之間的所有鏈接； 每個(gè)鏈接的代價(jià)。 Dijkstra集中式算法：集中式算法： 算法描述算法描述設(shè)D(v)是從源s到節(jié)點(diǎn)v的距離沿給定路徑的鏈接的代價(jià)的和）l(v,w)是節(jié)點(diǎn)v和w之間的代價(jià)Dijkstra算法如下：設(shè)N=s；對(duì)不在N中的每一個(gè)節(jié)點(diǎn)v，令D(v)=l(s,v)。對(duì)那些沒(méi)有連接到s的節(jié)點(diǎn)賦值為。 找到不在N中的一個(gè)節(jié)點(diǎn)w，使D(w)最小并將w加入N；然后對(duì)所有不在N中的其它節(jié)點(diǎn)計(jì)算并更新D(v)： D(v) := minD(v), D(w)+l(w,v) 重復(fù)步驟2，直到所

8、有節(jié)點(diǎn)都在N中 Dijkstra集中式算法：集中式算法： 算法舉例算法舉例l上述算法作用于如圖所示的網(wǎng)絡(luò)：以P5為源節(jié)點(diǎn)l集合N只包含源節(jié)點(diǎn)P5即N= P5。對(duì)不在N中的節(jié)點(diǎn)P1,P2,P3,P4計(jì)算：D(1)=D(2)=；（由于P1和P2不與P5直接相連）D(3)=l(P5 ,P3) =20D(4)=l(P5,P4)=2 Dijkstra集中式算法：集中式算法： 算法舉例算法舉例contd）l取D(1),D(2),D(3),D(4)中具最小值的對(duì)應(yīng)節(jié)點(diǎn)P4加入到集合N中, N= P5,P4,對(duì)不在N中的其它節(jié)點(diǎn)P3,P2,P1更新D(1)=minD(1),D(4)+l(4,1)=min,2+

9、=,D(2)=minD(2),D(4)+l(4,2)=min,2+1=3,D(3)=minD(3),D(4)+l(4,3)=min20,2+2=4。 Dijkstra集中式算法：集中式算法： 算法舉例算法舉例contd）l取D(1),D(2),D(3)中具最小值的對(duì)應(yīng)節(jié)點(diǎn)P2加入到集合N中，N=P5,P4,P2,對(duì)不在N中的其它節(jié)點(diǎn)P3,P1更新D(1)=minD(1),D(2)+l(2,1)=min,3+4=7D(3)=minD(3),D(2)+l(2,3)=min4, 3+3=4。 Dijkstra集中式算法：集中式算法： 算法舉例算法舉例contd）l取D(1),D(3)中具最小值的對(duì)應(yīng)

10、節(jié)點(diǎn)P3加入到集合N中, N= P5,P4,P2,P3對(duì)不在N中的其它節(jié)點(diǎn)P1更新D(1)=minD(1),D(3)+l(3,1)=min7,4+5=7 Dijkstra集中式算法：集中式算法： 算法舉例算法舉例contd）l取D(1)中具有最小值的對(duì)應(yīng)節(jié)點(diǎn)P1加入到集合N中, N= P5,P4,P2,P3,P1, 此時(shí)，節(jié)點(diǎn)都在N中，算法結(jié)束。 Dijkstra集中式算法：集中式算法： 連續(xù)的步驟，如下表：連續(xù)的步驟，如下表： Ford分布式算法分布式算法l第二種類型的路由算法采用分散式的方法進(jìn)行路由l分布式算法l每個(gè)節(jié)點(diǎn)在交互式的基礎(chǔ)上和其鄰節(jié)點(diǎn)交換代價(jià)和路由信息，直到這些節(jié)點(diǎn)的路由表到達(dá)

11、最短路徑的要求為止 Ford分布式算法分布式算法contd）lFord分布式算法也包括兩個(gè)部分：l一個(gè)初始步驟l一個(gè)最短距離計(jì)算的步驟l這里，最短距離指一個(gè)給定節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離l當(dāng)所有節(jié)點(diǎn)都帶有1一個(gè)表示它們到目標(biāo)節(jié)點(diǎn)距離的標(biāo)記以及2沿著最短路徑到達(dá)目標(biāo)節(jié)點(diǎn)要經(jīng)過(guò)的下一個(gè)節(jié) 點(diǎn)的標(biāo)記時(shí)，算法結(jié)束。 Ford分布式算法：分布式算法： 算法描述算法描述l每個(gè)節(jié)點(diǎn)v，都有(n,D(v)的標(biāo)記。lD(v)代表該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短距離的當(dāng)前值；ln是截至目前得到的最短路徑的下一個(gè)節(jié)點(diǎn)。l初始步驟：l設(shè)d是目標(biāo)節(jié)點(diǎn)。l令D(d)=0，將所有其它節(jié)點(diǎn)標(biāo)記為(.,) Ford分布式算法：分布式算法：

12、 算法描述算法描述contd）l最短距離計(jì)算步驟：l對(duì)所有節(jié)點(diǎn)的最短路徑做標(biāo)記：對(duì)每個(gè)節(jié)點(diǎn)vd： 使用v的每個(gè)鄰節(jié)點(diǎn)w的當(dāng)前D(w) 計(jì)算D(w)+l(w, v)，使得D(v):=minD(v),D(w)+l(w,v) 更新v的標(biāo)記：用使上述表達(dá)式取值最小的鄰接節(jié)點(diǎn)代替n，并用新值代替D(v)。 對(duì)每個(gè)節(jié)點(diǎn)重復(fù)上述操作，直到不再有改變 Ford分布式算法：分布式算法： 舉例舉例l上述算法作用于如圖所示的網(wǎng)絡(luò)：以P5為目標(biāo)節(jié)點(diǎn)l初始：令D(5) = 0，將其他節(jié)點(diǎn)P1,P2,P3,P4都標(biāo)記為(.,) Ford分布式算法：分布式算法：舉例：第一輪舉例：第一輪l對(duì)于P1，l鄰節(jié)點(diǎn)為P2,P3，由當(dāng)

13、前標(biāo)記可知P2,P3距離P5都為，則P1不能通過(guò)任何節(jié)點(diǎn)到達(dá)P5，P1仍標(biāo)記為(.,)l同理，P2仍標(biāo)記為(.,)l對(duì)于P3，l鄰節(jié)點(diǎn)為P1,P2,P4,P5，其中D(1)= D(2)=D(4)=,D(5)=0l由于P3到P5的距離20+D(5)為20小于當(dāng)前D(3)= ,表明P3經(jīng)P5有最短路徑可達(dá)P5l故P3標(biāo)記為(P5, 20)l同理，P4標(biāo)記為(P5, 2)。 Ford分布式算法：分布式算法：舉例：第二輪舉例：第二輪l對(duì)于P1，l鄰節(jié)點(diǎn)為P2,P3，由當(dāng)前標(biāo)記可知P5距離P2為，距離P3為20，則P1通過(guò)P3有最短路徑到達(dá)P5，D(1)為P1到P3的距離與P3到P5的距離之和為5+20

14、=25，故P1標(biāo)記為(P3,25)；l對(duì)于P2，l鄰節(jié)點(diǎn)為P1,P3,P4，計(jì)算P2到Pi (i = 1,3,4)的距離與當(dāng)前D(i)之和，并取最小值，可見(jiàn)計(jì)算P2到P4的距離與當(dāng)前D(4)之和最小為3，說(shuō)明P2經(jīng)P4有最短路徑到達(dá)P5，故P2標(biāo)記更新為(P4,3)；l同理，更新P3和P4的標(biāo)記為(P4,4)，(P5,2) Ford分布式算法：分布式算法：舉例：第三輪舉例：第三輪l按同樣方法更新P1,P2,P3,P4的標(biāo)記為： (P2,7),(P4,3),(P4,4),(P5,2)；l由于此后再重復(fù)以上算法試圖更新每一個(gè)節(jié)點(diǎn)的標(biāo)記都不會(huì)改變其標(biāo)志，算法結(jié)束。 Ford分布式算法：分布式算法：舉

15、例小結(jié)舉例小結(jié) Ford分布式算法分布式算法contd）l上例中，所有節(jié)點(diǎn)的行為在經(jīng)過(guò)幾輪之后都被同步了l上述同步方法僅僅是為了便于演示l同步方法是指所有節(jié)點(diǎn)在每一輪中都更新一次標(biāo)記lFord算法也適用于異步系統(tǒng)，l其中每個(gè)節(jié)點(diǎn)以隨機(jī)的速率更新其D(v)值。ARPAnet路由算法路由算法lARPAnet的路由算法是一個(gè)可靠、實(shí)用的分布式路由算法，也是今天流行的Internet 路由算法的前身。l與Ford算法比較相似l不同的是l算法中的節(jié)點(diǎn)都維護(hù)一個(gè)一般化的路由表，以便記錄通過(guò)不同鄰接節(jié)點(diǎn)的最短路徑。l這個(gè)路由表包含從這個(gè)節(jié)點(diǎn)到所有其它節(jié)點(diǎn)的最優(yōu)路徑的延遲。l每隔固定的時(shí)間間隔，路由表就被傳送

16、到它的所有鄰接節(jié)點(diǎn)，直到最小延遲表在某一點(diǎn)達(dá)到穩(wěn)定為止。ARPAnet路由算法：路由算法：舉例舉例l舉例說(shuō)明：用ARPAnet路由算法時(shí)，P1，P2，P3，P4的一般路由表，仍以P5為目標(biāo)節(jié)點(diǎn)l每個(gè)表格都包含通過(guò)每個(gè)鄰居到達(dá)P5的最短距離l假設(shè)在時(shí)刻0前已經(jīng)達(dá)到了一個(gè)穩(wěn)定點(diǎn)l即網(wǎng)絡(luò)延遲表如右圖P27P39P111P37P43P112P26P44P520P24P36P52ARPAnet路由算法：路由算法：舉例舉例contd）l假設(shè)0時(shí)刻，P4與P5之間鏈接失效，則它更新它的路由延遲表，并傳輸給P4的所有鄰節(jié)點(diǎn)，從而使那些節(jié)點(diǎn)的路由延遲表發(fā)生變化，直到產(chǎn)生一個(gè)新的穩(wěn)定點(diǎn)P27P39P111P37P

17、83P112P26P44P520P24P36P52 ARPAnet路由算法：路由算法：舉例舉例contd）P27P39P111P37P435P112P26P446P520P24P36P5P279P3911P111P379P45P112P268P46P520P246P368P5ARPAnet路由算法：路由算法：舉例舉例contd）l上述過(guò)程一直持續(xù)到達(dá)到一個(gè)新的穩(wěn)定點(diǎn)，P1，P2，P3，P4分別用了20，19，17，20個(gè)時(shí)間間隔，如下圖所示。ARPAnet路由算法路由算法contd）lARPAnet路由算法中 每個(gè)節(jié)點(diǎn)對(duì)所有鄰居都發(fā)送相同消息，對(duì)接收節(jié)點(diǎn)不做任何標(biāo)識(shí)。l這樣，某些節(jié)點(diǎn)就會(huì)接收無(wú)

18、用消息。l在鏈接節(jié)點(diǎn)失效時(shí)候，這些消息會(huì)導(dǎo)致我們不期望的循環(huán)。l例如ARPAnet路由算法：路由算法：不期望的循環(huán)，舉例不期望的循環(huán)，舉例l例如，P4和P5鏈接失效時(shí)，P4的最短路徑為4，但是這個(gè)4來(lái)自于P2，而P2到P5的最短路徑原來(lái)就依賴于P4與P5的鏈接，由于P4使用P2的信息時(shí)，P2的信息尚未得到更新，導(dǎo)致出現(xiàn)不期望的循環(huán)：P4P2P4P27P39P111P37P43P112P26P44P520P24P36P52ARPAnet路由算法：路由算法：不期望循環(huán)的消除不期望循環(huán)的消除l循環(huán)的消除是在路由消息中包含路徑的所有節(jié)點(diǎn)，并把這些消息發(fā)給鄰居節(jié)點(diǎn)。l然而，它的效率較低，因?yàn)樗念~外開(kāi)銷

19、太大。lShin和Chou，提出了一個(gè)避免循環(huán)算法：只需在路由消息中存儲(chǔ)路徑中最近的l個(gè)節(jié)點(diǎn)，l與相應(yīng)網(wǎng)絡(luò)中循環(huán)的最大長(zhǎng)度有關(guān)特殊類型網(wǎng)絡(luò)的單播路由算法特殊類型網(wǎng)絡(luò)的單播路由算法l一般類型網(wǎng)絡(luò)的路由算法適用于所有拓?fù)漕愋偷木W(wǎng)絡(luò)。但是，l每個(gè)節(jié)點(diǎn)需要維持路由延遲表，而且l不適用于特殊類型的網(wǎng)絡(luò)，原因是效率太低。l得益于特殊網(wǎng)絡(luò)的拓?fù)涮匦裕梢圆皇褂寐酚裳舆t表而構(gòu)造最短路徑路由算法l本節(jié)介紹三種特殊網(wǎng)絡(luò)的單播路由算法：l雙向環(huán)單播路由算法l網(wǎng)格和圓環(huán)單播路由算法l超立方單播路由算法雙向環(huán)單播路由算法雙向環(huán)單播路由算法l在雙向環(huán)上進(jìn)行決定型單播路由非常簡(jiǎn)單：l消息沿著一個(gè)方向被轉(zhuǎn)發(fā)：順時(shí)針或者逆時(shí)針

20、l由于消息可以沿兩個(gè)方向發(fā)送，所以由源節(jié)點(diǎn)根據(jù)目標(biāo)節(jié)點(diǎn)的位置決定發(fā)送方向：l如果目標(biāo)離順時(shí)針?lè)较蚪?，則用順時(shí)針?lè)较?；l否則選擇逆時(shí)針?lè)较?。l一個(gè)消息通過(guò)幾個(gè)中間節(jié)點(diǎn)按照順時(shí)針或逆時(shí)針?lè)较騻鬟f，直到到達(dá)目標(biāo)節(jié)點(diǎn)。雙向環(huán)單播路由算法（雙向環(huán)單播路由算法（ contd ）l雙向環(huán)上的單播路由算法可以使用兩條路徑：l一條沿著順時(shí)針，l另一條沿著逆時(shí)針。l音訊l也可以被復(fù)制，然后每個(gè)方向發(fā)一個(gè)拷貝；l也可以分成兩半，每半轉(zhuǎn)發(fā)到一個(gè)方向。雙向環(huán)單播路由算法：雙向環(huán)單播路由算法：算法一般化算法一般化l雙向環(huán)是k元1維立方，即只有一維度。l若維度大于1，例如網(wǎng)格和超立方，就用有序維度路由l每次將每個(gè)消息向一個(gè)

21、維度路由l圓環(huán)：在一個(gè)維度中的各點(diǎn)以環(huán)的方式連接起來(lái)，帶有周邊連接l網(wǎng)格：一個(gè)維度中的各點(diǎn)以線性排列的形式連接起來(lái)，沒(méi)有周邊連接雙向環(huán)單播路由算法：雙向環(huán)單播路由算法：算法一般化（算法一般化（ contd ）l環(huán)形路由方法可用于在一個(gè)維度中對(duì)消息進(jìn)行路由。l沿著一個(gè)線性排列路由是很簡(jiǎn)單的。l當(dāng)消息到達(dá)每個(gè)維度的對(duì)等者時(shí)，就使用下一個(gè)維度。l通過(guò)使經(jīng)過(guò)的各個(gè)維度保持一個(gè)單調(diào)的順序，就可以保證不會(huì)發(fā)生死鎖。l但這種方法適應(yīng)性差。網(wǎng)格和圓環(huán)單播路由算法網(wǎng)格和圓環(huán)單播路由算法l網(wǎng)格和圓環(huán)是k元2維立方。l圓環(huán)有周邊鄰接，l網(wǎng)格沒(méi)有周邊連接。l類似地，3維網(wǎng)格和圓環(huán)是k元3維立方。網(wǎng)格和圓環(huán)單播路由算法

22、：網(wǎng)格和圓環(huán)單播路由算法：2維網(wǎng)格的維網(wǎng)格的XY路由路由l在2維網(wǎng)格中，有序維度路由叫XY路由。l每個(gè)節(jié)點(diǎn)的地址為(x,y)。l消息首先沿著X維度轉(zhuǎn)發(fā)，然后沿著Y維度路由。l特別地，若源和目標(biāo)分別為(sx,sy)和(dx,dy)，則路由消息將在X維度上走|dx sx| 步，然后在Y維度上走|dy sy|步網(wǎng)格和圓環(huán)單播路由算法：網(wǎng)格和圓環(huán)單播路由算法：最短且完全適應(yīng)路由最短且完全適應(yīng)路由l在最短且完全適應(yīng)路由中，l每個(gè)中間節(jié)點(diǎn)，包括源節(jié)點(diǎn)，都要充分利用所有可行的最短路徑。l在2維網(wǎng)格中，l只要dxsx0且dysy0，每個(gè)節(jié)點(diǎn)在選擇鄰居時(shí)總有兩個(gè)選擇。l一個(gè)好的適應(yīng)性路由算法應(yīng)該能選擇任意個(gè)鄰居

23、并能盡可能地保持dx sx0且dysy0的情況。l顯然,XY路由是最不靈活的一個(gè)。 網(wǎng)格和圓環(huán)單播路由算法：網(wǎng)格和圓環(huán)單播路由算法：適應(yīng)性路由圖示適應(yīng)性路由圖示只要dxsx0且dysy0，每個(gè)節(jié)點(diǎn)在選擇鄰居時(shí)總有兩個(gè)選擇：X方向或者Y方向網(wǎng)格和圓環(huán)單播路由算法網(wǎng)格和圓環(huán)單播路由算法（ contd ）l如果每個(gè)鏈接信道擁塞的概率是一樣的，那么在最短路由的限制下，哪一個(gè)是最好的路由方法呢？l這里的最好是指在這種路由方法下，消息到達(dá)目標(biāo)的延遲最小。網(wǎng)格和圓環(huán)單播路由算法：網(wǎng)格和圓環(huán)單播路由算法：折線路由折線路由lBadr和Podar提出了一個(gè)2維網(wǎng)格的折線路由方法l首先建立一個(gè)包含源和目標(biāo)的矩形l源

24、s=(sx,sy)和目標(biāo)d=(dx,dy)分別位于矩形的兩個(gè)對(duì)角l從端點(diǎn)d=(dx,dy)引出一條線L，這條線將平分經(jīng)過(guò)點(diǎn)d的矩形的兩邊所組成的角。消息將沿著直線L 路由，但仍在矩形內(nèi)部。即所有的中間節(jié)點(diǎn)都是依照它們到L的距離來(lái)選擇的在所有合格的節(jié)點(diǎn)中，總是選擇距離L 最近的一個(gè)。直線L網(wǎng)格和圓環(huán)單播路由算法：網(wǎng)格和圓環(huán)單播路由算法：折線路由（折線路由（ contd ）l在2維圓環(huán)中，折線路由可能不是最優(yōu)的，因?yàn)橐粋€(gè)中間節(jié)點(diǎn)可能有多于兩個(gè)的合格鄰居。l特別，對(duì)一個(gè)n為偶數(shù)的nxn的圓環(huán)，存在一個(gè)具有四個(gè)合格鄰居的節(jié)點(diǎn)。而且，有2(n-2)個(gè)節(jié)點(diǎn)，它們和源的距離為n2個(gè)行或列，因此，在最短路徑上

25、就有三個(gè)方向。網(wǎng)格和圓環(huán)單播路由算法網(wǎng)格和圓環(huán)單播路由算法（ contd ）l對(duì)于最優(yōu)解，Wu在k元M維立方的最短路徑路由算法的基礎(chǔ)上提出了一個(gè)最大最短路徑(MP)路由算法：l路由消息總是被轉(zhuǎn)發(fā)到與目標(biāo)節(jié)點(diǎn)存在最大個(gè)數(shù)的最短路徑的那個(gè)鄰居節(jié)點(diǎn)。l基于最大最短路徑的路由算法是一個(gè)對(duì)2維網(wǎng)格和M維立方都是最優(yōu)的路由算法。l然而，關(guān)于最大最短路徑對(duì)2維圓環(huán)是不是最優(yōu)的仍然是一個(gè)未決的問(wèn)題。 網(wǎng)格和圓環(huán)單播路由算法網(wǎng)格和圓環(huán)單播路由算法（ contd ）l若源和目標(biāo)都有四個(gè)鄰居，那么很容易在它們之間建立四個(gè)邊(或點(diǎn))分離的路徑，如圖。l一般地，設(shè)k(k=8)是源和目標(biāo)節(jié)點(diǎn)所具有的最小的鄰居的數(shù)目，那么

26、，在源和目標(biāo)之間就存在k個(gè)邊點(diǎn)分別的路徑。超立方單播路由算法超立方單播路由算法l對(duì)超立方的單播路由可采用一種相對(duì)簡(jiǎn)單的方法，不必在每個(gè)節(jié)點(diǎn)中存儲(chǔ)路由延遲表。l一個(gè)n維超立方n-cube可定義為：lQ0，是一個(gè)只有一個(gè)節(jié)點(diǎn)的退化圖lQnK2xQn-1，這里：K2是具有兩個(gè)節(jié)點(diǎn)的完全圖；x是兩個(gè)圖的笛卡爾乘積。lQn中的一個(gè)節(jié)點(diǎn)的地址可以表示為u=unun-1u1ui0或1，1=i=n）超立方單播路由算法：超立方單播路由算法：海明距離海明距離l兩個(gè)節(jié)點(diǎn)u=unun-1u1和w =wnwn-1w1間最短路徑長(zhǎng)度就是u和w間的海明距離，表示為H(u,w)。lu和w間的異或操作u wrn rn-1 .

27、r1定義為：l如果uiwi，則ri0;如果uiwi，則ri1,1=i=n。l顯然，H(u,w)等于u w中1的個(gè)數(shù)。lu(i)表示改變u的第i位(也叫維)例如1101(3)=1001。 超立方單播路由算法：超立方單播路由算法：超立方路由超立方路由l在超立方路由中，l當(dāng)前節(jié)點(diǎn)u和目標(biāo)節(jié)點(diǎn)w的相對(duì)地址為u w，它和將要發(fā)送到下一個(gè)節(jié)點(diǎn)(這個(gè)節(jié)點(diǎn)也叫轉(zhuǎn)發(fā)節(jié)點(diǎn))的消息一起傳送。l在每個(gè)跳步，相對(duì)距離都會(huì)通過(guò)將u w中的一個(gè)1替換而進(jìn)行更新。超立方單播路由算法：超立方單播路由算法：超立方路由（超立方路由（ contd ）l在下面的算法中，節(jié)點(diǎn)u是當(dāng)前節(jié)點(diǎn)(可以是源節(jié)點(diǎn))，節(jié)點(diǎn)w是目標(biāo)節(jié)點(diǎn)。超立方單播路由

28、算法：超立方單播路由算法：超立方路由（超立方路由（ contd ）l在上述算法中，i的選擇是隨機(jī)的，這意味著可能有不止一條最短路徑。l實(shí)際上，最短邊分離的個(gè)數(shù)等于源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的海明距離。l如果遵循一個(gè)預(yù)定的順序，這種算法就是決定性的，叫做e立方路由。l例如，維的順序遵循升序：首先是1維，然后2維，等等。n維在最后；超立方單播路由算法：超立方單播路由算法：一個(gè)一個(gè)3維立方路由的例子維立方路由的例子l例中：源節(jié)點(diǎn)u=000目標(biāo)節(jié)點(diǎn)w110。從點(diǎn)000到點(diǎn)110有下列三個(gè)點(diǎn)分離路徑：l路徑1紅色）：000100110l路徑2藍(lán)色）：000010110l路徑3綠色）：000001011111110

29、超立方單播路由算法：超立方單播路由算法：超立方多路徑路由的性質(zhì)超立方多路徑路由的性質(zhì)l超立方多路徑路由具有如下性質(zhì)：l若兩個(gè)節(jié)點(diǎn)u和w在n維立方中的海明距離是k那么，在u和w之間就有n個(gè)點(diǎn)分離路徑。在這n條路徑中，有k個(gè)路徑長(zhǎng)度為k，其余n-k個(gè)路徑長(zhǎng)度為k+2。 l000和110之間的距離|000 110|2。因此，上述路徑中有兩條長(zhǎng)度為2，一條長(zhǎng)度為4l路徑1紅色）：000100110l路徑2藍(lán)色）：000010110l路徑3綠色）：000001011111110超立方單播路由算法：超立方單播路由算法：超立方多路徑路由的性質(zhì)超立方多路徑路由的性質(zhì)l類似地000和100之間的三條點(diǎn)分離路徑為

30、：l路徑1紅色）：000100l路徑2綠色）：000001101100l路徑3藍(lán)色）：000010110100l000和100之間的海明距離|000 100|=1特殊類型網(wǎng)絡(luò)的多播路由算法特殊類型網(wǎng)絡(luò)的多播路由算法l多播一到多是指從一個(gè)源向任意多個(gè)目標(biāo)節(jié)點(diǎn)傳送同樣的消息。l只有一個(gè)目標(biāo)的單播和以網(wǎng)絡(luò)中的所有節(jié)點(diǎn)為目標(biāo)的廣播都是多播的特例。l多播在數(shù)據(jù)并行編程操作中有一些應(yīng)用，例如l復(fù)制，障礙同步，對(duì)共享存儲(chǔ)器失效以及分布式共享內(nèi)存系統(tǒng)更新的支持等。一般的多播路由算法一般的多播路由算法l兩個(gè)主要的多播路由參數(shù)是通信量和時(shí)間。l通信量是以將消息發(fā)送到所有的目標(biāo)所需的通信鏈接的數(shù)目來(lái)衡量的。l時(shí)間就

31、是消息傳送的時(shí)間。l當(dāng)兩個(gè)多播路由算法有相同的時(shí)間步數(shù)時(shí)，應(yīng)該選擇具有較小的通信量步數(shù)的那一個(gè)。l通信量可以通過(guò)不同的目標(biāo)共享鏈接來(lái)降低。一般的多播路由算法：一般的多播路由算法：多播優(yōu)化問(wèn)題多播優(yōu)化問(wèn)題l通常，多播存在下列四個(gè)優(yōu)化問(wèn)題： l多播路徑優(yōu)化問(wèn)題l一個(gè)最優(yōu)的多播路徑是一個(gè)包括所有目標(biāo)的最短路徑。l多播回路優(yōu)化問(wèn)題l最優(yōu)多播回路是包含所有目標(biāo)的最短長(zhǎng)度的回路。一般的多播路由算法：一般的多播路由算法：多播優(yōu)化問(wèn)題（多播優(yōu)化問(wèn)題（ contd ）lsteiner樹(shù)優(yōu)化問(wèn)題l一個(gè)包含所有目標(biāo)節(jié)點(diǎn)的給定拓?fù)涞囊粋€(gè)子樹(shù)l最小steiner樹(shù)具有最小的總長(zhǎng)度l留意：不一定每個(gè)通向目標(biāo)的路徑長(zhǎng)度都是

32、最短的。l多播樹(shù)優(yōu)化問(wèn)題l一個(gè)包含所有目標(biāo)的給定拓?fù)涞淖訕?shù)，且樹(shù)中每個(gè)通向目標(biāo)的路徑的長(zhǎng)度對(duì)于給定的拓?fù)涫亲钚〉?。l一個(gè)最優(yōu)的多播樹(shù)具有最小的通信量 一般的多播路由算法：一般的多播路由算法：多播優(yōu)化問(wèn)題（多播優(yōu)化問(wèn)題（ contd）l網(wǎng)格和超立方的多播優(yōu)化問(wèn)題都是NP完全問(wèn)題。因此，一般使用啟發(fā)式多播算法。l目前，已有人給出了在使用分割-通過(guò)路由技術(shù)(如蟲(chóng)孔路由)的網(wǎng)絡(luò)中進(jìn)行最優(yōu)化多播通信的充分條件。l本節(jié)考慮兩種算法：一個(gè)是基于路徑的；另一個(gè)是基于樹(shù)的。 基于路徑的多播路由算法基于路徑的多播路由算法l基本思想：l首先建立一個(gè)哈密爾頓回路，l然后根據(jù)這個(gè)回路把多播集合轉(zhuǎn)發(fā)出去。l如果有一個(gè)鄰居

33、位于目標(biāo)前面，但距離目標(biāo)更近，那么就可以抄近路。1895年，愛(ài)爾蘭數(shù)學(xué)家哈密爾頓首先提出“環(huán)球周游問(wèn)題。他用一個(gè)正十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，要求旅游者能否找到沿著正十二面體的 棱，從某一個(gè)頂點(diǎn)即城市出發(fā)，經(jīng)過(guò)每一個(gè)頂點(diǎn)即每一座城市恰好一次，然后回到出發(fā)頂點(diǎn)？這便是著名的哈密爾頓問(wèn)題。它的解稱為哈密爾頓回路。 基于路徑的多播路由算法：基于路徑的多播路由算法：主要步驟主要步驟l在給定的網(wǎng)格或超立方上建立哈密爾頓回路；l將哈密爾頓回路上的節(jié)點(diǎn)排序。l這個(gè)順序起始于源節(jié)點(diǎn)，并包括所有目標(biāo)節(jié)點(diǎn)。l這樣哈密爾頓回路就被分割成了哈密爾頓路徑；l對(duì)每個(gè)中間節(jié)點(diǎn)，l若它是一個(gè)目標(biāo)節(jié)點(diǎn)，l保留消息

34、的一個(gè)拷貝，刪除該目標(biāo)節(jié)點(diǎn)的地址。l將消息和目標(biāo)列表傳給一個(gè)鄰居。l這個(gè)鄰居必須在當(dāng)前節(jié)點(diǎn)之前按順序)，離下一個(gè)目標(biāo)最近，且仍在這個(gè)目標(biāo)之前(或就是這個(gè)目標(biāo))。基于路徑的多播路由算法：基于路徑的多播路由算法：哈密爾頓路徑哈密爾頓路徑l若使用雙向鏈接，則只需一個(gè)哈密爾頓路徑(而不是哈密爾頓回路)即可。l哈密爾頓路徑為系統(tǒng)中的所有節(jié)點(diǎn)定義了一個(gè)順序。l在整個(gè)順序中，每個(gè)節(jié)點(diǎn)(x,y)都被賦予一個(gè)數(shù)字r：基于路徑的多播路由算法：基于路徑的多播路由算法：哈密爾頓路徑舉例哈密爾頓路徑舉例l例如，一個(gè)4X4的網(wǎng)格上每個(gè)節(jié)點(diǎn)具有的r值如圖所示：ln=4l若y是偶數(shù)，r值沿X方向遞增lr(x,y)=yn+xl

35、若y是奇數(shù)，r值沿X方向遞減lr(x,y)=yn+n-x-1=yn+(n-1)-x基于路徑的多播路由算法：基于路徑的多播路由算法：哈密爾頓路徑定義哈密爾頓路徑定義l哈密爾頓路徑定義l兩個(gè)節(jié)點(diǎn)在路徑中相鄰當(dāng)且僅當(dāng)|r(v)-r(u)|=1l例如：l4X4網(wǎng)格中，使用粗線連接兩個(gè)相鄰節(jié)點(diǎn)基于路徑的多播路由算法：基于路徑的多播路由算法：低信道網(wǎng)絡(luò)和高信道網(wǎng)絡(luò)低信道網(wǎng)絡(luò)和高信道網(wǎng)絡(luò)l使用順序定義，整個(gè)網(wǎng)格可以分成兩個(gè)子網(wǎng)：l一個(gè)包括從低序節(jié)點(diǎn)到高序節(jié)點(diǎn)的鏈接；l另一個(gè)包括從高序節(jié)點(diǎn)到低序節(jié)點(diǎn)的鏈接。l在兩個(gè)子網(wǎng)中，除了哈密爾頓路徑上的鏈接以外，其它鏈接也包含在其中。基于路徑的多播路由算法：基于路徑的多

36、播路由算法：最短路徑路由函數(shù)最短路徑路由函數(shù)l目標(biāo)依據(jù)它們與源的相對(duì)位置也分為兩個(gè)子集。l一個(gè)子集將沿著高信道網(wǎng)絡(luò)傳送，l另外一個(gè)將沿著低信道網(wǎng)絡(luò)傳送。l為了將消息沿著最短路徑傳送，定義如下路由函數(shù)。l假定使用高信道網(wǎng)絡(luò)。lv和dr(v)r(d)）分別是中間節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。l若d是v的一個(gè)鄰居，那么消息將直接轉(zhuǎn)發(fā)到d；l否則，選擇一個(gè)滿足下式的v的鄰居u：基于路徑的多播路由算法：基于路徑的多播路由算法：舉例舉例l下圖顯示了一個(gè)在4X4網(wǎng)格中進(jìn)行多播的例子l哈密爾頓路徑連接了那些r值依次遞增的節(jié)點(diǎn)l假定節(jié)點(diǎn)6(地址為(1,1)為源節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)為0、2、10、13和14。紫色：源節(jié)點(diǎn)；藍(lán)色：目標(biāo)

37、節(jié)點(diǎn)基于路徑的多播路由算法：基于路徑的多播路由算法：舉例（舉例（ contd ）l顯然，轉(zhuǎn)發(fā)消息到節(jié)點(diǎn)0和2時(shí)，應(yīng)該使用低信道網(wǎng)絡(luò)。l依據(jù)路由函數(shù)，可以得到如下路徑：l同樣，轉(zhuǎn)發(fā)消息到節(jié)點(diǎn)10，13和18時(shí)應(yīng)使用高信道網(wǎng)絡(luò)紅色：低信道網(wǎng)絡(luò)路徑和 具有最小r值的鄰居深紫色：高信道網(wǎng)絡(luò)路徑和 具有最大r值的鄰居基于樹(shù)的多播路由算法基于樹(shù)的多播路由算法lLan的貪婪多播算法可以應(yīng)用于超立方。在這個(gè)算法中，l每個(gè)節(jié)點(diǎn)(包括源節(jié)點(diǎn))在收到包含目標(biāo)節(jié)點(diǎn)地址列表的消息后，就把自己的地址和目標(biāo)節(jié)點(diǎn)的地址相比較。l若發(fā)現(xiàn)匹配，消息的一個(gè)拷貝將被送往本地的處理器l若多播集合非空，當(dāng)前節(jié)點(diǎn)將決定把目標(biāo)列表中的地址轉(zhuǎn)

38、發(fā)到哪些鄰居?；跇?shù)的多播路由算法：基于樹(shù)的多播路由算法：根據(jù)維度順序進(jìn)行轉(zhuǎn)發(fā)根據(jù)維度順序進(jìn)行轉(zhuǎn)發(fā)l維度順序由目標(biāo)節(jié)點(diǎn)的相對(duì)二進(jìn)制地址來(lái)決定ln位地址的每一位都有一個(gè)計(jì)數(shù)器。l計(jì)數(shù)器的內(nèi)容代表相應(yīng)維度的信息。l具有最大計(jì)數(shù)值的那一維將被選中。l所有在這一位為1的目標(biāo)將被轉(zhuǎn)發(fā)到這一維上的那個(gè)鄰居l在剩余的目標(biāo)中，將利用下一個(gè)被選中的維度重復(fù)上述步驟。l當(dāng)剩余的多播集合為空時(shí)，這一過(guò)程就結(jié)束?；跇?shù)的多播路由算法：基于樹(shù)的多播路由算法：4維立方中的多播例子維立方中的多播例子l考慮一個(gè)4維立方體(目標(biāo)用藍(lán)色節(jié)點(diǎn)代表)l節(jié)點(diǎn)0010打算向組播集0000，0001，1001，1100，1110中的每個(gè)節(jié)點(diǎn)發(fā)送消息l所有目標(biāo)節(jié)點(diǎn)的實(shí)際地址和源節(jié)點(diǎn)0010的實(shí)際地址做異或操作，得到多播集合的相對(duì)地址0010，0011，1011，1110，1100。l每一列的1的數(shù)目組成了一個(gè)稱為列總和的向量(3, 2, 4, 2) 基