【正文】 可以將消息路由到一個(gè)更長(zhǎng)的路徑從而避免擁塞。 確定型路由和適應(yīng)型路由 ? 確定型路徑算法 ? 路由路徑只在網(wǎng)絡(luò)的拓?fù)浒l(fā)生改變時(shí)才發(fā)生變化， ? 而且它不使用任何有關(guān)網(wǎng)絡(luò)狀態(tài)的消息。 容錯(cuò)型路由和非容錯(cuò)型路由 ? 容錯(cuò)型路由算法 ? 即使出現(xiàn)錯(cuò)誤，被路由消息也能保證送到。 冗余型路由和非冗余路由 ? 冗余型路由算法 ? 用幾個(gè)邊分離（或節(jié)點(diǎn)分離）的路徑向同一個(gè)目標(biāo)發(fā)送多個(gè)拷貝。 ? 必須保證有且只有一個(gè)拷貝被接收 ? 非冗余型路由算法 ? 對(duì)每個(gè)目標(biāo)只需轉(zhuǎn)發(fā)消息的一個(gè)拷貝。 ? 非死鎖避免型路由算法 ? 沒(méi)有特別的措施來(lái)預(yù)防或避免死鎖。 路由函數(shù) ? 路由函數(shù) ? 定義一個(gè)消息如何從源節(jié)點(diǎn)路由到目標(biāo)節(jié)點(diǎn)。 ? 右圖顯示了一個(gè)分布式系 統(tǒng)的例子 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法 ? 第一種類型的算法以集中式的風(fēng)格進(jìn)行路由 ? Dijkstra集中式算法可以發(fā)現(xiàn)一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。 Dijkstra集中式算法： 算法描述 設(shè) D(v)是從源 s到節(jié)點(diǎn) v的距離（沿給定路徑的鏈接的代價(jià)的和） l(v,w)是節(jié)點(diǎn) v和 w之間的代價(jià) Dijkstra算法 如下： 1. 設(shè) N={s}； 對(duì)不在 N中的每一個(gè)節(jié)點(diǎn) v，令 D(v)=l(s,v)。 2. 找到不在 N中的一個(gè)節(jié)點(diǎn) w，使 D(w)最小并將 w加入 N； 然后對(duì)所有不在 N中的其它節(jié)點(diǎn)計(jì)算并更新 D(v)： D(v) := min[D(v), D(w)+l(w,v)] 重復(fù)步驟 2，直到所有節(jié)點(diǎn)都在 N中 Dijkstra集中式算法： 算法舉例 ? 上述算法作用于如圖所示的網(wǎng)絡(luò)： 以 P5為源節(jié)點(diǎn) 1. 集合 N只包含源節(jié)點(diǎn) P5即 N= { P5}。d） 2. 取 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)=min{D(1),D(4)+l(4,1)} =min{∞,2+∞}=∞, D(2)=min{D(2),D(4)+l(4,2)} =min{∞,2+1}=3, D(3)=min{D(3),D(4)+l(4,3)} =min{20,2+2}=4。d） 3. 取 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)=min{D(1),D(2)+l(2,1)} =min{∞,3+4}=7 D(3)=min{D(3),D(2)+l(2,3)} =min{4, 3+3}=4。d） 5. 取 D(1)中具有最小值的對(duì)應(yīng)節(jié)點(diǎn) P1加入到集合 N中 , N= { P5,P4,P2,P3,P1}, 此時(shí)，節(jié)點(diǎn)都在 N中，算法結(jié)束。d） ? Ford分布式算法也包括兩個(gè)部分： ? 一個(gè)初始步驟 ? 一個(gè)最短距離計(jì)算的步驟 ? 這里，最短距離指一個(gè)給定節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離 ? 當(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é)束。 ? D(v)代表該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短距離的當(dāng)前值； ? n是截至目前得到的最短路徑的下一個(gè)節(jié)點(diǎn)。 令 D(d)=0，將所有其它節(jié)點(diǎn)標(biāo)記為 (.,∞) Ford分布式算法： 算法描述（ cont39。 對(duì)每個(gè)節(jié)點(diǎn)重復(fù)上述操作，直到不再有改變 Ford分布式算法： 舉例 ? 上述算法作用于如圖所示的網(wǎng)絡(luò)： 以 P5為目標(biāo)節(jié)點(diǎn) ? 初始： 令 D(5) = 0，將其他節(jié)點(diǎn) P1,P2,P3,P4都標(biāo)記為 (.,∞) P 1P 2P 3P 4 P 54531222 0( . , 0 )( . , ∞ )( . , ∞ )( . , ∞ )( . , ∞ ) Ford分布式算法： 舉例：第一輪 ? 對(duì)于 P1， ? 鄰節(jié)點(diǎn)為 P2,P3，由當(dāng)前標(biāo)記可知 P2,P3距離 P5都為 ∞，則 P1不能通過(guò)任何節(jié)點(diǎn)到達(dá) P5， P1仍標(biāo)記為 (.,∞) ? 同理， P2仍標(biāo)記為 (.,∞) ? 對(duì)于 P3， ? 鄰節(jié)點(diǎn)為 P1,P2,P4,P5，其中 D(1)= D(2)=D(4)=∞,D(5)=0 ? 由于 P3到 P5的距離 20+D(5)為 20 小于當(dāng)前 D(3)= ∞, 表明 P3經(jīng) P5有最短路徑可達(dá) P5 ? 故 P3標(biāo)記為 (P5, 20) ? 同理， P4標(biāo)記為 (P5, 2)。 P 1P 2P 3P 4 P 54531222 0( . , 0 )( P5, 2 )( P4, 4 )( P4, 3 )( P3, 2 5 )( P5, 2 )( P4, 4 )( P4, 3 )( P2, 7 ) Ford分布式算法： 舉例小結(jié) P 1P 2P 3P 4 P 54531222 0 Ford分布式算法（ cont’d） ? 上例中，所有節(jié)點(diǎn)的行為在經(jīng)過(guò)幾輪之后都被同步了 ? 上述同步方法僅僅是為了便于演示 ? 同步方法是指所有節(jié)點(diǎn)在每一輪中都更新一次標(biāo)記 ? Ford算法也適用于異步系統(tǒng)， ? 其中每個(gè)節(jié)點(diǎn)以隨機(jī)的速率更新其 D(v)值。 ? 與 Ford算法比較相似 ? 不同的是 ? 算法中的節(jié)點(diǎn)都維護(hù)一個(gè)一般化的路由表，以便記錄通過(guò)不同鄰接節(jié)點(diǎn)的最短路徑。 ? 每隔固定的時(shí)間間隔，路由表就被傳送到它的所有鄰接節(jié)點(diǎn)，直到最小延遲表在某一點(diǎn)達(dá)到穩(wěn)定為止。d） ? 假設(shè) 0時(shí)刻， P4與 P5之間鏈接失效，則它更新它的路由延遲表，并傳輸給 P4的所有鄰節(jié)點(diǎn)，從而使那些節(jié)點(diǎn)的路由延遲表發(fā)生變化，直到產(chǎn)生一個(gè)新的穩(wěn)定點(diǎn) P 1P 2P 3P 4 P 54531222 0P2 7 P3 9 P1 11 P3 7 P8 3 P1 12 P2 6 P4 4 P5 20 P2 4 P3 6 P5 2?∞ ? ARPA路由算法： 舉例（ cont39。d） ? 上述過(guò)程一直持續(xù)到達(dá)到一個(gè)新的穩(wěn)定點(diǎn)， P1， P2， P3， P4分別用了 20， 19， 17， 20個(gè)時(shí)間間隔，如下圖所示。d） ? ARPA路由算法中 每個(gè)節(jié)點(diǎn)對(duì)所有鄰居都發(fā)送相同消息，對(duì)接收節(jié)點(diǎn)不做任何標(biāo)識(shí)。 ? 在鏈接節(jié)點(diǎn)失效時(shí)候，這些消息會(huì)導(dǎo)致我們不期望的循環(huán)。 ? 然而，它的效率較低，因?yàn)樗念~外開(kāi)銷太大。但是， ? 每個(gè)節(jié)點(diǎn)需要維持路由延遲表，而且 ? 不適用于特殊類型的網(wǎng)絡(luò)，原因是效率太低。 ? 一個(gè)消息通過(guò)幾個(gè)中間節(jié)點(diǎn)按照順時(shí)針或逆時(shí)針?lè)较騻鬟f，直到到達(dá)目標(biāo)節(jié)點(diǎn)。d ） ? 雙向環(huán)上的單播路由算法可以使用兩條路徑： ? 一條沿著順時(shí)針， ? 另一條沿著逆時(shí)針。 雙向環(huán)單播路由算法： 算法一般化 ? 雙向環(huán)是 k元 1維立方，即只有一維度。d ） ? 環(huán)形路由方法可用于在一個(gè)維度中對(duì)消息進(jìn)行路由。 ? 當(dāng)消息到達(dá)每個(gè)維度的對(duì)等者時(shí)，就使用下一個(gè)維度。 ? 但這種方法適應(yīng)性差。 ? 圓環(huán)有周邊鄰接， ? 網(wǎng)格沒(méi)有周邊連接。 網(wǎng)格和圓環(huán)單播路由算法： 2維網(wǎng)格的 XY路由 ? 在 2維網(wǎng)格中，有序維度路由叫 XY路由。 ? 消息首先沿著 X維度轉(zhuǎn)發(fā)，然后沿