【正文】 高級操作系統(tǒng) Advanced Operating System 陳香蘭（代） 0551_360686483 中國科學技術大學計算機系 第四章 分布式路由算法 主要內(nèi)容 ? 分布式路由算法導論 ? 一般類型網(wǎng)絡的最短路徑路由算法 ? 特殊類型網(wǎng)絡的單播算法 ? 特殊類型網(wǎng)絡中的多播算法 ? 虛信道和虛網(wǎng)絡 ? 完全自適應和無死鎖路由算法 第四章 分布式路由算法 主要內(nèi)容（ cont39。d ） ? 幾個自適應和無死鎖路由算法 ? 容錯單播的一般方法 ? 網(wǎng)格和圓環(huán)中的容錯單播算法 ? 超立方中的容錯單播算法 ? 容錯組播算法 進程間通信類型 ? 有效的進程間通信對分布式系統(tǒng)的性能很重要 ? 根據(jù)目標個數(shù)的不同， 進程間通信的類型 有： ? 一對一（單播） ? 一對多（組播） ? 一對所有（廣播） ： 通信延遲及其原因 ? 在基于消息傳遞的分布式系統(tǒng)中，消息一般在到達目標節(jié)點之前可能要通過一個或多個中間節(jié)點，故 存在通信延遲 。 ? 分布式系統(tǒng)中的通信延遲依賴于如下四個因素： ? 網(wǎng)絡拓撲 ： ? 通常用圖表示 ? 定義處理單元（ PE）之間是如何連接的 ? 路由 ? 決定如何選擇路徑以便將消息傳遞到目的地。 ： 通信延遲及其原因（ cont39。d） ? 流量控制 ? 流量控制決定在消息沿路徑傳遞時如何分配網(wǎng)絡資源，包括： ? 信道 ? 緩沖區(qū) ? 交換 ? 這是一個實際的機制，它決定消息如何從一個輸入信道轉(zhuǎn)到一個輸出信道。 ： 路由算法類型 ? 路由算法類型 包括： 1）特殊 vs. 一般 2）最短 vs. 非最短 3）確定型 vs. 適應型 4）源路由 vs. 目標路由 5）容錯型 vs. 非容錯型 6）冗余型 vs. 非冗余型 7）死鎖避免型 vs. 非死鎖避免型 1）一般型路由和特殊型路由 ? 一般型路由算法 ? 適合于所有類型的網(wǎng)絡 ? 但是對于某種特定網(wǎng)絡不是很有效 ? 特殊型路由算法 ? 只對特定的網(wǎng)絡類型有效，如超立方、網(wǎng)格等 ? 這些算法由于 利用了特定網(wǎng)絡的拓撲屬性 ，所以效率往往較高。 2）最短路由算法和非最短路由算法 ? 最短路徑算法 ? 對給定的源 目標對給出一個代價最小的路徑 ? 路徑的代價 ? 所有跳步（連接）代價的線性和。 ? 缺點：可能會導致網(wǎng)絡某一部分的擁塞 ? 非最短路由算法 ? 可以將消息路由到一個更長的路徑從而避免擁塞。 ? 在某些情況下，隨機路由可能是有效的。 3）確定型路由和適應型路由 ? 確定型路徑算法 ? 路由路徑只在網(wǎng)絡的拓撲發(fā)生改變時才發(fā)生變化， ? 而且它不使用任何有關網(wǎng)絡狀態(tài)的消息。 ? 適應型路由算法 ? 路徑根據(jù)網(wǎng)絡流量而改變。 5）容錯型路由和非容錯型路由 ? 容錯型路由算法 ? 即使出現(xiàn)錯誤，被路由消息也能保證送到。 ? 非容錯型路由算法 ? 假定路由不會出錯 ? 路由算法不必動態(tài)調(diào)整自己的活動。 6）冗余型路由和非冗余路由 ? 冗余型路由算法 ? 用幾個邊分離（或節(jié)點分離）的路徑向同一個目標發(fā)送多個拷貝。 ? 只要這些路徑中的一個是好的，那么就會至少有一個消息拷貝到達目標。 ? 必須保證有且只有一個拷貝被接收 ? 非冗余型路由算法 ? 對每個目標只需轉(zhuǎn)發(fā)消息的一個拷貝。 7）死鎖避免型路由和非死鎖避免型路由 ? 死鎖避免型路由算法 ? 通過仔細設計的路由算法，保證不發(fā)生死鎖。 ? 非死鎖避免型路由算法 ? 沒有特別的設施來預防或避免死鎖。 ? 可能發(fā)生死鎖，也可能不發(fā)生死鎖。 ： 路由函數(shù) ? 路由函數(shù) ? 定義一個消息如何從源節(jié)點路由到目標節(jié)點。 ? 每個 PE在收到一個消息以后，都將決定： 1）把這條消息傳送到本地存儲器，還是 2）轉(zhuǎn)發(fā)到一個鄰接的 PE ? 有許多不同的路由函數(shù)的定義，例如 ? 依賴于目標的、依賴于輸入的、依賴于源的、依賴于路徑的等等 ? 本章僅使用 依賴于目標的路由函數(shù) 一般類型網(wǎng)絡的最短路徑路由算法 ? 許多分組交換網(wǎng)，如法國的 Transpac或美國的ARPA都使用最短路徑路由 ? 本節(jié)介紹三個一般類型網(wǎng)絡的 最短路徑路由算法： ? Dijkstra集中式算法 ? Ford分布式算法 ? ARPA路由算法 一般類型網(wǎng)絡的最短路徑路由算法： 分布式系統(tǒng)圖示 ? 一般地，一個分布式系統(tǒng)可以用圖來表示： ? 節(jié)點 代表 PE（處理單元）； ? 邊 代表通信鏈接； ? 每個鏈接的 數(shù)字 代表鏈接代價。 P 1P 2P 3P 4 P 54531222 0一個分布式系 統(tǒng)的例子 Dijkstra集中式算法 ? 第一種類型的算法以集中式的風格進行路由 ? Dijkstra集中式算法可以 發(fā)現(xiàn)一個源節(jié)點到所有其他節(jié)點的最短路徑。 ? 算法需求： ? 需要了解給定網(wǎng)絡的全局拓撲消息，即： 1）網(wǎng)絡中所有其他節(jié)點的列表； 2）節(jié)點之間的所有鏈接； 3）每個鏈接的代價。 Dijkstra集中式算法： 算法描述 設： D(v)是從源 s到節(jié)點 v的距離； l(v,w)是節(jié)點 v和 w之間的鏈接代價 Dijkstra算法 如下： 1） 設 N={s}； 對不在 N中的每一個節(jié)點 v，若 v與 s相連，則令 D(v)=l(s, v)。否則， D(v)為 ∞。 2） 找到不在 N中的一個節(jié)點 w，并且 D(w)最小，將 w加入 N； 然后對所有不在 N中的其它節(jié)點計算并更新 D(v)： D(v) := min[D(v), D(w)+l(w,v)] 重復步驟 2，直到所有節(jié)點都在 N中 沿給定路徑的鏈接 的代價的和 Dijkstra集中式算法： 算法舉例 ? 上述算法作用于如圖所示的網(wǎng)絡： 以 P5為源節(jié)點 1）一開始，集合 N只包含源節(jié)點 P5即 N= { P5}。 對不在 N中的節(jié)點 P1,P2,P3,P4計算： D(1)=D(2)=∞； （由于 P1和 P2不與 P5直接相連） D(3)=l(P5 ,P3) =20 D(4)=l(P5,P4)=2 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont39。d） 2）取 D(1),D(2),D(3),D(4)中具最小值的對應節(jié)點 P4加入到集合 N中 , N= { P5,P4}, 對不在 N中的其它節(jié)點 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。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont39。d） 3）取 D(1),D(2),D(3)中具最小值的對應節(jié)點 P2加入到集合 N中，N={P5,P4,P2}, 對不在 N中的其它節(jié)點 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。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont‘d） 4）取 D(1),D(3)中具最小值的對應節(jié)點 P3加入到集合 N中 , N= { P5,P4,P2,P3} 對不在 N中的其它節(jié)點 P1更新 D(1)=min{D(1),D(3)+l(3,1)} =min{7,4+5}=7 P 1P 2P 3P 4 P 54531222 0 Di