【導(dǎo)讀】分布式路由算法導(dǎo)論。一般類型網(wǎng)絡(luò)的最短路徑路由算法。完全自適應(yīng)和無死鎖路由算法。網(wǎng)格和圓環(huán)中的容錯單播算法。有效的進(jìn)程間通信對分布式系統(tǒng)的性能很重要。根據(jù)目標(biāo)個數(shù)的不同，進(jìn)程間通信的類型有：。一對所有（廣播）。節(jié)點(diǎn)，故存在通信延遲。定義處理單元之間是如何連接的。決定如何選擇路徑以便將消息傳遞到目的地。這是一個實際的機(jī)制，它決定消息如何從一個輸入信道。轉(zhuǎn)到一個輸出信道。這些算法由于利用了特定網(wǎng)絡(luò)的拓?fù)鋵傩裕孕?。對給定的源-目標(biāo)對給出一個代價最小的路徑?？梢詫⑾⒙酚傻揭粋€更長的路徑從而避免擁塞。在某些情況下，隨機(jī)路由可能是有效的。假定路由不會出錯。路由算法不必動態(tài)調(diào)整自己的活動。對每個目標(biāo)只需轉(zhuǎn)發(fā)消息的一個拷貝。通過仔細(xì)設(shè)計的路由算法，保證不發(fā)生死鎖。沒有特別的設(shè)施來預(yù)防或避免死鎖。本章僅使用依賴于目標(biāo)的路由函數(shù)。許多分組交換網(wǎng)，如法國的Transpac或美國的。每個鏈接的數(shù)字代表鏈接代價。

　　

【正文】 以外，其它鏈接也包含在其中。 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 , 3xy01237654891 01 11 51 41 31 20 , 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 , 3xy01237654891 01 11 51 41 31 2： 最短路徑路由函數(shù) ? 目標(biāo)依據(jù)它們與源的相對位置也分為兩個子集。 ? 一個子集將沿著高信道網(wǎng)絡(luò)傳送， ? 另外一個將沿著低信道網(wǎng)絡(luò)傳送。 ? 為了將消息沿著最短路徑傳送，定義如下路由函數(shù)。 ? 假定使用高信道網(wǎng)絡(luò)。 ? v和 d（ r(v)r(d)）分別是中間節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。 ? 若 d是 v的一個鄰居，那么消息將直接轉(zhuǎn)發(fā)到 d； ? 否則，選擇一個滿足下式的 v的鄰居 u： ： 舉例 ? 下圖顯示了一個在 4X4網(wǎng)格中進(jìn)行多播的例子 ? 哈密爾頓路徑連接了那些 r值依次遞增的節(jié)點(diǎn) ? 假定節(jié)點(diǎn) 6(地址為 (1,1))為源節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)為 0、 13和 14。 紫色：源節(jié)點(diǎn)； 藍(lán)色：目標(biāo)節(jié)點(diǎn) 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 , 3xy01237654891 01 11 51 41 31 2： 舉例（ cont39。d ） ? 顯然，轉(zhuǎn)發(fā)消息到節(jié)點(diǎn) 0和 2時，應(yīng)該使用低信道網(wǎng)絡(luò)。 ? 依據(jù)路由函數(shù)，可以得到如下路徑： ? 同樣，轉(zhuǎn)發(fā)消息到節(jié)點(diǎn) 10， 13和 14時應(yīng)使用高信道網(wǎng)絡(luò) 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 , 3xy01237654891 01 11 51 41 31 2紅色：低信道網(wǎng)絡(luò)路徑和 具有最小 r值的鄰居 深紫色：高信道網(wǎng)絡(luò)路徑和 具有最大 r值的鄰居 ? Lan的貪婪多播算法可以應(yīng)用于 超立方 。在這個算法中， ? 每個節(jié)點(diǎn) (包括源節(jié)點(diǎn) )在收到包含目標(biāo)節(jié)點(diǎn)地址列表的消息后，就把自己的地址和目標(biāo)節(jié)點(diǎn)的地址相比較。 ? 若發(fā)現(xiàn)匹配，消息的一個拷貝將被送往本地的處理器 ? 若多播集合非空，當(dāng)前節(jié)點(diǎn)將決定把目標(biāo)列表中的地址轉(zhuǎn)發(fā)到哪些鄰居。 ： 根據(jù)維度順序進(jìn)行轉(zhuǎn)發(fā) ? 維度順序由目標(biāo)節(jié)點(diǎn)的 相對地址 來決定 ? n位地址的每一位都有一個計數(shù)器。 ? 計數(shù)器的內(nèi)容代表相應(yīng)維度的信息。 ? 具有最大計數(shù)值的那一維將被選中。 ? 所有在這一位為 1的目標(biāo)將被轉(zhuǎn)發(fā)到這一維上的那個鄰居 ? 在剩余的目標(biāo)中，將利用下一個被選中的維度重復(fù)上述步驟。 ? 當(dāng)剩余的多播集合為空時，這一過程就結(jié)束。 ： 4維立方中的多播例子 ? 考慮一個 4維立方體（目標(biāo)用藍(lán)色節(jié)點(diǎn)代表） ? 節(jié)點(diǎn) 0010打算向組播集 {0000， 0001， 1001， 1100， 1110} 中的每個節(jié)點(diǎn)發(fā)送消息 ? 所有目標(biāo)節(jié)點(diǎn)的實際地址和源節(jié)點(diǎn) 0010 的實際地址做異或操作，得到 多播集合的相對地址 {0010， 0011， 1011， 1110， 1100}。 ? 每一列的 1的數(shù)目組成 了一個稱為列總和的 向量 (3, 2, 4, 2) 0 1 1 0 0 1 1 10 1 0 0 0 1 0 10 0 1 0 0 0 1 10 0 0 0 0 0 0 11 1 1 0 1 1 1 11 1 0 0 1 1 0 11 0 1 0 1 0 1 11 0 0 0 1 0 0 1： 4維立方中多播例子（ cont39。d ） ? 沿著第 2維的鄰居擁有最受歡迎的維度。即節(jié)點(diǎn)0000成為下一個轉(zhuǎn)發(fā)節(jié)點(diǎn)，發(fā)往節(jié)點(diǎn) 0000的消息包含子集 (0000， 0001， 1001， 1100)。 ? 只有節(jié)點(diǎn) 1110被剩下了，這個節(jié)點(diǎn)可以通過第 3維的鄰居轉(zhuǎn)發(fā)，也可以通過第 4維的鄰居轉(zhuǎn)發(fā)。 ? 上述過程將在每個轉(zhuǎn)發(fā)節(jié)點(diǎn)重復(fù)操作。 ? 每個多播樹的分支都將繼續(xù)到剩余的 多播集合變空為止 ： 基于遞歸倍增的啟發(fā)式算法 ? 當(dāng)使用分割 通過網(wǎng)絡(luò)時，可以使用遞歸倍增方法構(gòu)造啟發(fā)式算法。 ? 以單端口模型下的 2維網(wǎng)格 為例來說明McKinIey等人提出的 u網(wǎng)格算法。 ? 先為 2維網(wǎng)格的節(jié)點(diǎn)地址定義一個字典序 (t)，即 若 x1tx2或者 x1=x2,但 y1ty2，則有 (x1,y1)(x2,y2)。 ? 邊分離性質(zhì) ： ? 假定 P(n1,n2)是 n1和 n2間最短路徑，易知， 若 n1tn2tn3tn4， 則 P(n1,n2)和 P(n3,n4)邊分離 ： 基于遞歸倍增的啟發(fā)式算法 ? 利用邊分離性質(zhì)，可建立下面避免競爭且具有最少步數(shù)的多播算法 ? 假定源節(jié)點(diǎn)是 (0,0)，按照字典順序重新排列目標(biāo)節(jié)點(diǎn)、并將源節(jié)點(diǎn)放在前面。 ? 將列表分成兩個相等的子列表。源節(jié)點(diǎn)將多播消息發(fā)往第二個子列表的第一個節(jié)點(diǎn)。 ? 重復(fù)上述分割步驟直到每個子列表中只有一個節(jié)點(diǎn)； ? 若源節(jié)點(diǎn)不是 (0,0)，可重新定義排列順序以便源節(jié)點(diǎn)成為第一個節(jié)點(diǎn) ： 舉例 ? 考慮一個 4 4網(wǎng)格， (0,0)是源節(jié)點(diǎn)，(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和 (3,2)是目標(biāo)節(jié)點(diǎn)。 ? 源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的字典順序是：(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2) 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 , 3： 舉例（ cont39。d ） ? 第一步，這個列表被分成兩個子列表{(0,0),(1,0),(1,1),(1,2)}和{(1,3),(2,0),(2,1),(3,2)} ? 源 (0,0)將信息發(fā)送到第二個子列表的第一個節(jié)點(diǎn) (1,3) ? 使用 XY路由建立 (0,0)到 (1,3)的路由路徑 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 , 3： 舉例（ cont39。d ） ? 在每個子列表上重復(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)格算法