【正文】 P5距離 P2為 ∞，距離 P3為20，則 P1通過 P3有最短路徑到達(dá) P5， D(1)為 P1到 P3的距離與 P3到 P5的距離之和為 5+20=25，故 P1標(biāo)記為 (P3,25)； ? 對于 P2， ? 鄰節(jié)點(diǎn)為 P1,P3,P4，計(jì)算 P2到 Pi (i = 1,3,4)的距離與當(dāng)前 D(i)之 和，并取最小值，可見計(jì)算 P2到 P4的距離與當(dāng)前 D(4)之和最小為 3，說明 P2經(jīng) P4有最短路徑到達(dá) P5，故 P2標(biāo)記更新為 (P4,3)； ? 同理，更新 P3和 P4的標(biāo)記為 (P4,4)， (P5,2) P 1P 2P 3P 4 P 54531222 0( . , 0 )( P5, 2 )( P4, 4 )( . , ∞ )( P5, 2 0 )( . , ∞ )( P4, 3 )( P3, 2 5 ) ( P5, 2 ) Ford分布式算法： 舉例：第三輪 ? 按同樣方法更新 P1,P2,P3,P4的標(biāo)記為： (P2,7),(P4,3),(P4,4),(P5,2)； ? 由于此后再重復(fù)以上算法試圖更新 每一個節(jié)點(diǎn)的標(biāo)記都不會改變其 標(biāo)記，算法結(jié)束。d） 2. 最短距離計(jì)算步驟： 對所有節(jié)點(diǎn)的最短路徑做標(biāo)記： 對每個節(jié)點(diǎn) v≠d： 使用 v的每個鄰節(jié)點(diǎn) w的當(dāng)前 D(w) 計(jì)算 D(w)+l(w, v)，使得 D(v):=min{D(v),D(w)+l(w,v)} 更新 v的標(biāo)記：用使上述表達(dá)式取值最小的鄰接節(jié)點(diǎn)代替 n，并用新值代替 D(v)。 1. 初始步驟： 設(shè) d是目標(biāo)節(jié)點(diǎn)。 Ford分布式算法： 算法描述 ? 每個節(jié)點(diǎn) v，都有 (n,D(v))的標(biāo)記。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 連續(xù)的步驟，如下表： P 1P 2P 3P 4 P 54531222 0 Ford分布式算法 ? 第二種類型的路由算法采用分散式的方法進(jìn)行路由 ? 分布式算法 ? 每個節(jié)點(diǎn)在交互式的基礎(chǔ)上和其鄰節(jié)點(diǎn)交換代價和路由信息，直到這些節(jié)點(diǎn)的路由表到達(dá)最短路徑的要求為止 Ford分布式算法（ cont39。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont‘d） 4. 取 D(1),D(3)中具最小值的對應(yīng)節(jié)點(diǎn) P3加入到集合 N中 , N= { P5,P4,P2,P3} 對不在 N中的其它節(jié)點(diǎn) P1更新 D(1)=min{D(1),D(3)+l(3,1)} =min{7,4+5}=7 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont39。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 算法舉例（ cont39。 對不在 N中的節(jié)點(diǎn) P1,P2,P3,P4計(jì)算： 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。 對那些沒有連接到 s的節(jié)點(diǎn)賦值為 ∞。 ? Dijkstra集中式算法需求： ? 需要了解給定網(wǎng)絡(luò)的全局拓?fù)湎?，即? 網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的列表； 節(jié)點(diǎn)之間的所有鏈接； 每個鏈接的代價。 ? 每個 PE在收到一個消息以后，都將決定： 1）把這條消息傳送到本地存儲器，還是 2）轉(zhuǎn)發(fā)到一個鄰接的 PE ? 有許多不同的路由函數(shù)的定義，例如 ? 依賴于目標(biāo)的、依賴于輸入的、依賴于源的、依賴于路徑的等等 ? 本章僅使用依賴于目標(biāo)的路由函數(shù) 路由函數(shù)類型 ? 依賴于源的：依賴于源節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn) ? 依賴于目標(biāo)的：僅僅依賴于當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn) ? 依賴于輸入的：依賴于當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)以及鄰近的鏈接 ? 依賴于路徑的：依賴于目標(biāo)節(jié)點(diǎn)和從源節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的路徑 一般類型網(wǎng)絡(luò)的最短路徑路由算法 ? 許多分組交換網(wǎng)，如法國的 Transpac或美國的ARPA都使用最短路徑路由 ? 本節(jié)介紹三個一般類型網(wǎng)絡(luò)的 最短路徑路由算法： ? Dijkstra集中式算法 ? Ford分布式算法 ? ARPA路由算法 一般類型網(wǎng)絡(luò)的最短路徑路由算法： 分布式系統(tǒng)圖示 ? 一般地，一個分布式系統(tǒng)可以用圖來表示： 節(jié)點(diǎn) 代表 PE（處理單元）； 邊 代表通信鏈接； 每個鏈接的 數(shù)字 代表鏈接代價。 ? 可能發(fā)生死鎖，也可能不發(fā)生死鎖。 死鎖避免型路由和 非死鎖避免型路由 ? 死鎖避免型路由算法 ? 通過仔細(xì)設(shè)計(jì)的路由算法，保證不發(fā)生死鎖。 ? 只要這些路徑中的一個是好的，那么就會至少有一個消息拷貝到達(dá)目標(biāo)。 ? 非容錯型路由算法 ? 假定路由不會出錯 ? 路由算法不必動態(tài)調(diào)整自己的活動。 ? 適應(yīng)型路由算法 ? 路徑根據(jù)網(wǎng)絡(luò)流量而改變。 ? 在某些情況下，隨機(jī)路由可能是有效的。 最短路由算法和非最短路由算法 ? 最短路徑算法 ? 對給定的源 目標(biāo)對給出一個代價最小的路徑 ? 路徑的代價 ? 所有跳步（連接）代價的線性和。d） ? 流量控制 ? 流量控制決定在消息沿路徑傳遞時如何分配網(wǎng)絡(luò)資源，包括： ? 信道 ? 緩沖區(qū) ? 交換 ? 這是一個實(shí)際的機(jī)制，它決定消息如何從一個輸入信道轉(zhuǎn)到一個輸出信道。 ? 分布式系統(tǒng)中的通信延遲依賴于如下四個因素： ? 網(wǎng)絡(luò)拓?fù)?： ? 通常用圖表示 ? 定義處理單元（ PE）之間是如何連接的 ? 路由 ? 決定如何選擇路徑以便將消息傳遞到目的地。 分布式路由算法 主要內(nèi)容（ cont39。d ） ? 一般類型網(wǎng)絡(luò)的分布式路由算法 ? 自適應(yīng)和無死鎖路由算法 ? 網(wǎng)格和圓環(huán)中的容錯單播算法 ? 超立方中的容錯單播算法 ? 容錯組播算法 進(jìn)程間通信類型 ? 有效的進(jìn)程間通信對分布式系統(tǒng)的性能很重要 ? 根據(jù)目標(biāo)個數(shù)的不同， 進(jìn)程間通信的類型 有： ? 一對一（單播） ? 一對多（組播） ? 一對所有（廣播） 通信延遲及其原因 ? 在基于消息傳遞的分布式系統(tǒng)中，消息一般在到達(dá)目標(biāo)節(jié)點(diǎn)之前可能要通過一個或多個中間節(jié)點(diǎn)，故存在通信延遲。 通信延遲及其原因（ cont39。 路由算法類型 ? 路由算法類型 包括： ? 特殊 vs. 一般 ? 最短 vs. 非最短 ? 確定型 vs. 適應(yīng)型 ? 源路由 vs. 目標(biāo)路由 ? 容錯型 vs. 非容錯型 ? 冗余型 vs. 非冗余型 ? 死鎖避免型 vs. 非死鎖避免型 一般型路由和特殊型路由 ? 一般型路由算法 ? 適合于所有類型的網(wǎng)絡(luò) ? 但是對于某種特定網(wǎng)絡(luò)不是很有效 ? 特殊型路由算法 ? 只對特定的網(wǎng)絡(luò)類型有效 ，如超立方、網(wǎng)格等 ? 這些算法由于利用了特定網(wǎng)絡(luò)的拓?fù)鋵傩?，所以效率往往較高。 ? 缺點(diǎn)：可能會導(dǎo)致網(wǎng)絡(luò)某一部分的擁塞 ? 非最短路由算法 ?