【正文】 于某種特定網(wǎng)絡(luò)不是很有效 ? 特殊型路由算法 ? 只對(duì)特定的網(wǎng)絡(luò)類型有效，如超立方、網(wǎng)格等 ? 這些算法由于 利用了特定網(wǎng)絡(luò)的拓?fù)鋵傩?，所以效率往往較高。 3）確定型路由和適應(yīng)型路由 ? 確定型路徑算法 ? 路由路徑只在網(wǎng)絡(luò)的拓?fù)浒l(fā)生改變時(shí)才發(fā)生變化， ? 而且它不使用任何有關(guān)網(wǎng)絡(luò)狀態(tài)的消息。 6）冗余型路由和非冗余路由 ? 冗余型路由算法 ? 用幾個(gè)邊分離（或節(jié)點(diǎn)分離）的路徑向同一個(gè)目標(biāo)發(fā)送多個(gè)拷貝。 ? 非死鎖避免型路由算法 ? 沒有特別的設(shè)施來預(yù)防或避免死鎖。 P 1P 2P 3P 4 P 54531222 0一個(gè)分布式系 統(tǒng)的例子 Dijkstra集中式算法 ? 第一種類型的算法以集中式的風(fēng)格進(jìn)行路由 ? Dijkstra集中式算法可以 發(fā)現(xiàn)一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。 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中 沿給定路徑的鏈接 的代價(jià)的和 Dijkstra集中式算法： 算法舉例 ? 上述算法作用于如圖所示的網(wǎng)絡(luò)： 以 P5為源節(jié)點(diǎn) 1）一開始，集合 N只包含源節(jié)點(diǎn) P5即 N= { P5}。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(v)代表該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短距離的當(dāng)前值； ? next是截至目前得到的最短路徑的下一個(gè)節(jié)點(diǎn)。 對(duì)每個(gè)節(jié)點(diǎn)重復(fù)上述操作，直到不再有改變 ： 舉例 ? 上述算法作用于如圖所示的網(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 )( . , ∞ )( . , ∞ )( . , ∞ )( . , ∞ )： 舉例：第一輪 ? 對(duì)于 P1， ? 鄰節(jié)點(diǎn)為 P2,P3，由當(dāng)前標(biāo)記可知 P2,P3距離 P5都為 ∞，則 P1不能通過任何節(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) ? 同理， P４ 標(biāo)記為 (P5, 2)。 ? 與 Ford算法比較相似 ? 不同的是 ? 算法中的節(jié)點(diǎn)都維護(hù)一個(gè)一般化的路由表，以便 記錄通過所有不同鄰接節(jié)點(diǎ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 P4 3 P1 12 P2 6 P4 4 P5 20 P2 4 P3 6 P5 2?∞ ? ARPA路由算法： 舉例（ cont39。d） ? ARPA路由算法 中 每個(gè)節(jié)點(diǎn)對(duì)所有鄰居都發(fā)送相同消息，對(duì)接收節(jié)點(diǎn)不做任何標(biāo)識(shí)。 ? 然而，它的效率較底，因?yàn)樗念~外開銷太大。 ? 一個(gè)消息通過幾個(gè)中間節(jié)點(diǎn)按照順時(shí)針或逆時(shí)針方向傳遞，直到到達(dá)目標(biāo)節(jié)點(diǎn)。 雙向環(huán)單播路由算法： 算法一般化 ? 雙向環(huán)是 k元 1維立方，即只有一維度。 ? 當(dāng)消息到達(dá)每個(gè)維度的對(duì)等者時(shí)，就使用下一個(gè)維度。 ? 圓環(huán)有周邊鄰接， ? 網(wǎng)格沒有周邊連接。 ? 消息首先沿著 X維度轉(zhuǎn)發(fā)，然后沿著 Y維度路由。 ? 顯然， XY路由是最不靈活的一個(gè)。 消息將沿著直線 L 路由，但仍在矩 形內(nèi)部。 ? 特別，對(duì)一個(gè) n為偶數(shù)的 n n的圓環(huán)，存在一個(gè)具有四個(gè)合格鄰居的節(jié)點(diǎn)。 ? 基于最大最短路徑的路由算法是一個(gè)對(duì) 2維網(wǎng)格和 M維立方都是最優(yōu)的路由算法。 ? 一般地，設(shè) k(k≤4)是源和目 標(biāo)節(jié)點(diǎn)所具有的最小的鄰居 的數(shù)目，那么，在源和目標(biāo) 之間就存在 k個(gè)邊（點(diǎn)）分離 的路徑。 ? u和 w間的異或操作 u⊕ w＝ rn rn1 …. r 1定義為： 如果 ui＝ wi，則 ri＝ 0。 超立方單播路由算法： 超立方路由 ? 在超立方路由中， ? 當(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) )的消息一起傳送。 超立方單播路由算法： 超立方路由（ cont39。 ? 例如，維的順序遵循升序：首先是 1維，然后 2維，等等。 ? 000和 110之間的距離 |000⊕ 110|＝ 2。 一般的多播路由算法 ? 兩個(gè)主要的多播路由參數(shù)是通信量和時(shí)間。 ? 通信量可以通過不同的目標(biāo)共享鏈接來降低。d ） 3） steiner樹優(yōu)化問題 ? 一個(gè)包含所有目標(biāo)節(jié)點(diǎn)的給定拓?fù)涞囊粋€(gè)子樹 ? 最小 steiner樹具有最小的總長度 ? 注意：不一定每個(gè)通向目標(biāo)的路徑長度都是最短的。因此，一般使用啟發(fā)式多播算法。 ? 如果有一個(gè)鄰居位于目標(biāo)前面，但距離目標(biāo)更近，那么就可以抄近路 。 ： 主要步驟 1. 在給定的網(wǎng)格或超立方上 建立哈密爾頓回路 ； 2. 將哈密爾頓回路上的節(jié)點(diǎn) 排序 。 這個(gè)鄰居必須在當(dāng)前節(jié)點(diǎn)之前（按順序 )，離下一個(gè)目標(biāo)最近，且仍在這個(gè)目標(biāo)之前 (或就是這個(gè)目標(biāo) )。 ? 在兩個(gè)子網(wǎng)中，除了哈密爾頓路徑上的鏈接以外，其它鏈接也包含在其中。 ? 假定使用高信道網(wǎng)絡(luò)。d ） ? 顯然，轉(zhuǎn)發(fā)消息到節(jié)點(diǎn) 0和 2時(shí)，應(yīng)該使用低信道網(wǎng)絡(luò)。 ： 根據(jù)維度順序進(jìn)行轉(zhuǎn)發(fā) ? 維度順序由目標(biāo)節(jié)點(diǎn)的 相對(duì)地址 來決定 ? n位地址的每一位都有一個(gè)計(jì)數(shù)器。 ? 當(dāng)剩余的多播集合為空時(shí)，這一過程就結(jié)束。即節(jié)點(diǎn)0000成為下一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，發(fā)往節(jié)點(diǎn) 0000的消息包含子集 (0000， 0001， 1001， 1100)。 ? 以單端口模型下的 2維網(wǎng)格 為例來說明McKinIey等人提出的 u網(wǎng)格算法。源節(jié)點(diǎn)將多播消息發(fā)往第二個(gè)子列表的第一個(gè)節(jié)點(diǎn)。d ） ? 在每個(gè)子列表上重復(fù)上述過程，有： 0 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 30 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3本課小結(jié) ? 本課主要內(nèi)容（ 4小節(jié)） ? 分布式路由算法導(dǎo)論 ? 進(jìn)程間通信類型 ? 通信延遲及其原因 ? 路由算法分類 ? 路由函數(shù)定義 ? 一般類型網(wǎng)絡(luò)的最短路徑路由算法 ? Dijkstra集中式算法 ? Ford分布式算法 ? ARPA的路由算法 ? 特殊類型網(wǎng)絡(luò)的單播算法 ? 雙向環(huán)上的單播算法及其一般化 ? 網(wǎng)格和圓環(huán)上的單播算法 ? 2維網(wǎng)格的 XY路由、適應(yīng)性路由、折線路由等 ? 超立方 ? 基于海明距離的一種簡單的路由算法 ? 特殊類型網(wǎng)絡(luò)中的多播算法 ? 基于（哈密爾頓）路徑 ? 基于樹的多播 ? 應(yīng)用于超立方的 Lan的貪婪多播算法 ? U網(wǎng)格算法