第五章 路由算法

1、第五章第五章 路由算法路由算法5.1 路由算法概述路由算法概述 網(wǎng)絡(luò)層的任務(wù)網(wǎng)絡(luò)層的任務(wù) 建立、維持、中止網(wǎng)絡(luò)的連接建立、維持、中止網(wǎng)絡(luò)的連接 網(wǎng)絡(luò)層的核心：路由算法網(wǎng)絡(luò)層的核心：路由算法 路由算法的功能：指引分組通過通信子網(wǎng)到達目的節(jié)路由算法的功能：指引分組通過通信子網(wǎng)到達目的節(jié)點點 為源節(jié)點和目的節(jié)點對選擇傳輸路徑；為源節(jié)點和目的節(jié)點對選擇傳輸路徑； 將分組正確地送到目的節(jié)點。將分組正確地送到目的節(jié)點。5.1 路由算法概述路由算法概述5.1 路由算法概述路由算法概述 路由選擇的優(yōu)劣將直接影響網(wǎng)絡(luò)的性能路由選擇的優(yōu)劣將直接影響網(wǎng)絡(luò)的性能1.1.源節(jié)點源節(jié)點 1 1、2 2的輸入業(yè)務(wù)的輸入業(yè)務(wù)

2、量分別為量分別為 5 5個單位個單位2.2.源節(jié)點源節(jié)點 1 1的輸入業(yè)務(wù)量的輸入業(yè)務(wù)量分別為分別為 5 5個單位；源節(jié)個單位；源節(jié)點點 2 2的輸入業(yè)務(wù)量分別的輸入業(yè)務(wù)量分別為為 1515個單位；個單位； 輕負荷條件下，減少時延輕負荷條件下，減少時延 高負荷條件下，保證時延高負荷條件下，保證時延的前提下，增加網(wǎng)絡(luò)通過的前提下，增加網(wǎng)絡(luò)通過量量5.1.1 路由選擇算法的分類路由選擇算法的分類 決策地點決策地點 集中式集中式 分布式分布式 決策時間決策時間 分組（數(shù)據(jù)報）分組（數(shù)據(jù)報） 會話（虛電路）會話（虛電路） 性能評價準則性能評價準則 吞吐量吞吐量 時延時延 鏈路數(shù)鏈路數(shù) 設(shè)施代價設(shè)施代價

3、 路由選擇所基于的信息源路由選擇所基于的信息源 本地本地 相鄰節(jié)點相鄰節(jié)點 路徑上的節(jié)點路徑上的節(jié)點 所有節(jié)點所有節(jié)點 路由選擇對網(wǎng)絡(luò)的適應(yīng)性路由選擇對網(wǎng)絡(luò)的適應(yīng)性 靜態(tài)靜態(tài) 自適應(yīng)自適應(yīng) 根據(jù)負載、拓撲結(jié)構(gòu)的變化自適應(yīng)地調(diào)整根據(jù)負載、拓撲結(jié)構(gòu)的變化自適應(yīng)地調(diào)整路由路由5.1.2 對路由選擇算法的要求對路由選擇算法的要求 正確性正確性 到達目的地；交付給目的地，不再轉(zhuǎn)發(fā)到達目的地；交付給目的地，不再轉(zhuǎn)發(fā) 計算簡單計算簡單 運算量??；路由計算所需信息的獲取過程占用帶寬少運算量小；路由計算所需信息的獲取過程占用帶寬少 自適應(yīng)性自適應(yīng)性 業(yè)務(wù)量；拓撲業(yè)務(wù)量；拓撲 穩(wěn)定性穩(wěn)定性 震蕩少震蕩少 公平性公

4、平性用戶用戶 最優(yōu)性最優(yōu)性 基于某項性能準則基于某項性能準則 上述要求之間存在矛盾上述要求之間存在矛盾5.1.3 路由算法的實現(xiàn)路由算法的實現(xiàn) 路由表路由表 路由表：存儲了分組的傳送路徑路由表：存儲了分組的傳送路徑(下一跳下一跳)5.1.3 路由算法的實現(xiàn)路由算法的實現(xiàn) 路由表路由表 路由環(huán)路問題路由環(huán)路問題 路由表中的附加信息路由表中的附加信息5.1.4 路由算法與流量控制的關(guān)系路由算法與流量控制的關(guān)系 “流量控制流量控制”根據(jù)時延調(diào)整負載進入網(wǎng)絡(luò)的吞吐量；根據(jù)時延調(diào)整負載進入網(wǎng)絡(luò)的吞吐量； 路由算法影響分組的傳輸時延；路由算法影響分組的傳輸時延；5.2 常用路由算法常用路由算法 網(wǎng)內(nèi)路由網(wǎng)

5、內(nèi)路由 網(wǎng)際路由網(wǎng)際路由5.2.1 廣域網(wǎng)中的路由算法廣域網(wǎng)中的路由算法1. 廣播廣播接收節(jié)點常常是全網(wǎng)所有成員接收節(jié)點常常是全網(wǎng)所有成員傳播公共信息、拓撲變化信息（節(jié)點移動，節(jié)電傳播公共信息、拓撲變化信息（節(jié)點移動，節(jié)電開關(guān)、鏈路故障）開關(guān)、鏈路故障）路由算法路由算法洪泛洪泛生成樹生成樹單播單播Delivery: Broadcast RoutingSOURCEDATA洪泛算法洪泛算法Delivery: Broadcast RoutingSOURCEDelivery: Broadcast RoutingSOURCE5.2.1 廣域網(wǎng)中的路由算法廣域網(wǎng)中的路由算法 洪泛算法的問題洪泛算法的問題

6、分組的傳輸次數(shù)多分組的傳輸次數(shù)多 附加規(guī)則附加規(guī)則 不重復(fù)轉(zhuǎn)發(fā)，用節(jié)點標識符和序號來保證不重復(fù)轉(zhuǎn)發(fā)，用節(jié)點標識符和序號來保證 不回傳不回傳5.2.1 廣域網(wǎng)中的路由算法廣域網(wǎng)中的路由算法2. 最短路由最短路由3. 最佳路由最佳路由最短路由：一對節(jié)點之間的路徑最優(yōu)；最短路由：一對節(jié)點之間的路徑最優(yōu)；限制了網(wǎng)絡(luò)的通過量；限制了網(wǎng)絡(luò)的通過量；為避免震蕩，適應(yīng)業(yè)務(wù)變化的能力受限。為避免震蕩，適應(yīng)業(yè)務(wù)變化的能力受限。最佳路由基于平均指標的最優(yōu)化，在全網(wǎng)搜索可最佳路由基于平均指標的最優(yōu)化，在全網(wǎng)搜索可能的路徑，可將流量分配在多條路徑上。能的路徑，可將流量分配在多條路徑上。5.2.2 互連網(wǎng)中的路由算法互連

7、網(wǎng)中的路由算法 網(wǎng)關(guān)網(wǎng)關(guān) WAN與與WAN之間之間 協(xié)議轉(zhuǎn)換、路由協(xié)議轉(zhuǎn)換、路由 網(wǎng)橋網(wǎng)橋 LAN與與LAN之間之間 Translate a packet from one format into another, e.g., ethernet to optical (FDDI) MAC層協(xié)議層協(xié)議 路由器路由器 connect and route between two networks 網(wǎng)絡(luò)層網(wǎng)絡(luò)層 網(wǎng)絡(luò)規(guī)模擴大與路由器內(nèi)存有限之間的矛盾網(wǎng)絡(luò)規(guī)模擴大與路由器內(nèi)存有限之間的矛盾 分級分級5.2.2 自組織網(wǎng)絡(luò)中的路由算法自組織網(wǎng)絡(luò)中的路由算法 自組織網(wǎng)絡(luò)？自組織網(wǎng)絡(luò)？ 路由算法分類路由算法分

8、類5.3 最短路由算法最短路由算法 圖論基本概念圖論基本概念 圖：圖：定義成空間中一些定義成空間中一些節(jié)點節(jié)點（頂點）和連接這些節(jié)點（頂點）和連接這些節(jié)點的的鏈路鏈路（邊）的（邊）的集合集合。 無向圖：無向圖：鏈路無方向鏈路無方向 有向圖：有向圖：鏈路有方向鏈路有方向 關(guān)聯(lián)：關(guān)聯(lián)：如果節(jié)點是鏈路如果節(jié)點是鏈路e的一個端點，則稱邊的一個端點，則稱邊e和頂和頂點節(jié)點相點節(jié)點相關(guān)聯(lián)關(guān)聯(lián) 方向性行走：方向性行走：指一個節(jié)點序列指一個節(jié)點序列 與該與該序列相關(guān)聯(lián)的鏈路序列相關(guān)聯(lián)的鏈路 為為G中中的鏈路的鏈路 方向性路徑方向性路徑（path）：無重復(fù)節(jié)點的方向性行走）：無重復(fù)節(jié)點的方向性行走12( ,)l

9、n nn1( ,),11iiln nnil 5.3 最短路由算法最短路由算法 圖論基本概念（圖論基本概念（2） 方向性環(huán)：源節(jié)點與目的節(jié)點相同的方向性路徑方向性環(huán)：源節(jié)點與目的節(jié)點相同的方向性路徑 強連通方向圖：圖中的每一對節(jié)點強連通方向圖：圖中的每一對節(jié)點i,j都有一條方向性都有一條方向性路徑路徑 連通方向圖：方向圖對應(yīng)的無方向圖是連通的。連通方向圖：方向圖對應(yīng)的無方向圖是連通的。5.3 最短路由算法最短路由算法 最短路徑：最短路徑： 給每條鏈路給每條鏈路 指定一個實數(shù)作為其長度指定一個實數(shù)作為其長度 一條方向性路徑一條方向性路徑 的長度為的長度為 最短路徑問題就是尋找從最短路徑問題就是尋找

10、從i到到m的最小長度方向性的最小長度方向性路徑路徑 鏈路長度可以是成本、時延、可靠性。鏈路長度可以是成本、時延、可靠性。( , )i jijdijjklmddd( , , , ,)pi j kl m5.3 最短路由算法最短路由算法 集中式最短路徑算法集中式最短路徑算法 Bellman-Ford算法算法 點對多點點對多點 Dijkstra算法算法 點對多點點對多點 Floyd-Warshall算法。算法。 多點對多點多點對多點 尋找網(wǎng)絡(luò)中一個節(jié)點到其它尋找網(wǎng)絡(luò)中一個節(jié)點到其它所有節(jié)點所有節(jié)點的的最短路由最短路由。 定義：最短（定義：最短（ ）行走（）行走（Walk）是指在下列約束條件下從）是指在

11、下列約束條件下從給定節(jié)點給定節(jié)點i到目的節(jié)點到目的節(jié)點1的最短的最短Walk。 該行走（該行走（Walk）中最多包括）中最多包括h條鏈路，即條鏈路，即Walk中包含的中包含的鏈路數(shù)至多為鏈路數(shù)至多為h條。條。 該行走（該行走（Walk）僅經(jīng)過目的節(jié)點）僅經(jīng)過目的節(jié)點1一次。一次。 最短行走最短行走Walk長度用長度用 表示。節(jié)點表示。節(jié)點i經(jīng)過條鏈路到達目經(jīng)過條鏈路到達目的節(jié)點的節(jié)點1的行走長度的行走長度 對所有的對所有的h，令，令 。 B-F算法的核心思想是通過下面的算法的核心思想是通過下面的公式進行迭代，即公式進行迭代，即Bellman-Ford算法算法hhiD01hDmin1hjijjh

12、DdDi1iBellman-Ford算法算法第一步：初始化。即對所有第一步：初始化。即對所有i （ ）令）令 。第二步：對所有的節(jié)點第二步：對所有的節(jié)點j（ ），先找出一條鏈路的最），先找出一條鏈路的最短（短（ ）的）的Walk長度；長度；第三步：對所有的節(jié)點第三步：對所有的節(jié)點j（ ），再找出經(jīng)兩條鏈路的），再找出經(jīng)兩條鏈路的最短（最短（ ）的）的Walk長度；長度；依次類推：如果對所有依次類推：如果對所有i有：有： （即繼續(xù)迭代下去以（即繼續(xù)迭代下去以后不會再有變化），則算法在后不會再有變化），則算法在h次迭代后結(jié)束。次迭代后結(jié)束。0iDmin01jijjDdDimin12jijjDdDi

13、1hihiDDmin1hjijjhDdDi最短最短Walk長度等于最短路徑長度的充分必要條件長度等于最短路徑長度的充分必要條件定理定理1：對于：對于B-F算法算法初始條件：對所有初始條件：對所有 ，有，有有：有： 由該算法產(chǎn)生的由該算法產(chǎn)生的 等于最短（等于最短（ ）Walk長度長度 當且僅當所有不包括節(jié)點當且僅當所有不包括節(jié)點1的環(huán)具有非負的長度，算的環(huán)具有非負的長度，算法在有限次迭代后結(jié)束。法在有限次迭代后結(jié)束。此外，如果算法在最多此外，如果算法在最多 次迭代后結(jié)束，則結(jié)束次迭代后結(jié)束，則結(jié)束時時 就是從就是從到到1的最短路徑長度。的最短路徑長度。1i 0iD hiDhkNhiD定理定理1

14、 1中中闡明了與最短（闡明了與最短（ ）WalkWalk的關(guān)系。的關(guān)系。闡闡明了算法何時結(jié)束，結(jié)束時所得的結(jié)果是否是最短路徑。明了算法何時結(jié)束，結(jié)束時所得的結(jié)果是否是最短路徑。hiDh最短最短Walk長度等于最短路徑長度的充分必要條件長度等于最短路徑長度的充分必要條件證明證明：我們采用歸納法證明（：我們采用歸納法證明（1）。）。 因為因為 ，所以顯然有，所以顯然有 等于最短（等于最短（ ）的）的Walk長度；長度； 假定假定 是等于最短（是等于最短（ ）的）的Walk長度，求證長度，求證 是等于最短（是等于最短（ ）的）的Walk長度。長度。h11iiDd1iD1hiDh1hiD1h證明證明：

15、從從i到到1的最短（的最短（ ）Walk包含的鏈路數(shù)有兩種情況：包含的鏈路數(shù)有兩種情況：一種情況是鏈路數(shù)小于一種情況是鏈路數(shù)小于h+1，在此情況下，有，在此情況下，有Walk長度長度等于等于 ；另一種情況是鏈路數(shù)等于另一種情況是鏈路數(shù)等于h+1。在后一種情況下，有最。在后一種情況下，有最短（短（ ）Walk長度長度 根據(jù)根據(jù) 等于最短（等于最短（ ）Walk的假設(shè)，對所有的有的假設(shè)，對所有的有 因此有因此有 最短（最短（ ）Walk長度長度 1hhiD1h11min,min,minhhhhiiiijjjDDDdDhiDhkh1kkjjDD11minminhhhhiijjijjijjDdDdDD

16、1h1hiD證明證明：（2）如果）如果B-F算法在算法在h次迭代后結(jié)束，即有次迭代后結(jié)束，即有 對所有對所有i和和 則我們不可能通過添加更多的鏈路來減少最短的則我們不可能通過添加更多的鏈路來減少最短的Walk長長度。（否則，算法沒有結(jié)束。）度。（否則，算法沒有結(jié)束。）也就是不可能存在一個負長度的（不包括目的節(jié)點）環(huán)。也就是不可能存在一個負長度的（不包括目的節(jié)點）環(huán)。因為這樣的負長度的任意大次數(shù)的重復(fù)將使因為這樣的負長度的任意大次數(shù)的重復(fù)將使Walk的長度的長度任意的小，這與上式相矛盾。任意的小，這與上式相矛盾。khiiDDkh證明證明：相反，假定所有的不包括相反，假定所有的不包括1的環(huán)具有非負

17、的長度。從最短的環(huán)具有非負的長度。從最短（ ）Walk中刪除這些環(huán)，我們會得到長度相同或中刪除這些環(huán)，我們會得到長度相同或更短的路徑。因此，對每一個更短的路徑。因此，對每一個i和和h，總存在一條從，總存在一條從i到到1的的最短（最短（ ）Walk，其相應(yīng)的最短的路徑長度等于，其相應(yīng)的最短的路徑長度等于 。由于路徑中沒有環(huán)，路徑可能包括。由于路徑中沒有環(huán)，路徑可能包括最多最多N-1條鏈路。因此條鏈路。因此 ，對所有，對所有i成立。即成立。即算法在最多算法在最多N次迭代后結(jié)束。次迭代后結(jié)束。 hhhiD1NNiiDD直接來構(gòu)造最短的路徑直接來構(gòu)造最短的路徑 假定所有不包括節(jié)點假定所有不包括節(jié)點1的

18、環(huán)具有非負的長度，用的環(huán)具有非負的長度，用Di表示從表示從節(jié)點節(jié)點i到達目的節(jié)點到達目的節(jié)點1的最短路徑長度。根據(jù)前面的討論，的最短路徑長度。根據(jù)前面的討論，當當B-F算法結(jié)束時，有算法結(jié)束時，有該式稱為該式稱為Bellman方程方程 。它表明從節(jié)點。它表明從節(jié)點i到達目的節(jié)點到達目的節(jié)點1的最短路徑長度，等于的最短路徑長度，等于i到達該路徑上第一個節(jié)點到達該路徑上第一個節(jié)點j的鏈路的鏈路長度，加上該節(jié)點長度，加上該節(jié)點j到達目的節(jié)點到達目的節(jié)點1的最短路徑長度。從的最短路徑長度。從該方程出發(fā)，只要所有不包括該方程出發(fā)，只要所有不包括1的環(huán)具有正的長度（而不的環(huán)具有正的長度（而不是是0長度）的

19、情況下，我們就可以很容易地找到最短路徑長度）的情況下，我們就可以很容易地找到最短路徑（而不是最短路徑長度）。（而不是最短路徑長度）。 miniijjjDdD1i 10D 具體方法如下具體方法如下 ：對于每一個節(jié)點對于每一個節(jié)點 ，選擇一條滿足，選擇一條滿足 的最小值的鏈路的最小值的鏈路 ，利用這些，利用這些N-1條鏈路組成一個子條鏈路組成一個子圖，則圖，則i沿該子圖到達目的節(jié)點沿該子圖到達目的節(jié)點1的路徑即為最短路徑。的路徑即為最短路徑。 1i miniijjjDdD( ,)ii j利用上面的構(gòu)造方法，可以證明：如果沒有利用上面的構(gòu)造方法，可以證明：如果沒有0長度（或負長度（或負長度）的環(huán)，則

20、長度）的環(huán)，則Bellman方程式有惟一解。方程式有惟一解。如果有不包括節(jié)點如果有不包括節(jié)點1的環(huán)的長度為的環(huán)的長度為0，則，則Bellman方程不方程不再具有惟一解。再具有惟一解。路徑長度惟一，并不意味著路徑惟一。路徑長度惟一，并不意味著路徑惟一。利用該結(jié)論，可以證明：即使初始條件利用該結(jié)論，可以證明：即使初始條件 ， 是任意是任意數(shù)（而不是數(shù)（而不是 ），），B-F算法都能正確工作，對于不算法都能正確工作，對于不同的節(jié)點，迭代的過程可以以任意順序并行進行。同的節(jié)點，迭代的過程可以以任意順序并行進行。 0iD1i 0iD B-F算法的運算量算法的運算量 設(shè)有設(shè)有N個節(jié)點，個節(jié)點， B-F算法

21、最多循環(huán)算法最多循環(huán)N次次 每次循環(huán)處理每次循環(huán)處理N-1個節(jié)點個節(jié)點 對每個節(jié)點求最小路徑，有對每個節(jié)點求最小路徑，有N-1種選擇種選擇 最壞情況下計算量為最壞情況下計算量為 ，表示為，表示為3N3()O N2 Dijkstra算法算法 Dijkstra算法算法也是一種典型的也是一種典型的點對多點點對多點的路由選的路由選擇算法，即通過迭代，尋找某一節(jié)點到網(wǎng)絡(luò)中其擇算法，即通過迭代，尋找某一節(jié)點到網(wǎng)絡(luò)中其它所有節(jié)點的最短路徑。它所有節(jié)點的最短路徑。假定所有鏈路的長度均為非負。假定所有鏈路的長度均為非負。Dijkstra算法算法思路思路顯然有：節(jié)點顯然有：節(jié)點1的最近的鄰節(jié)點通過單條鏈路到的最近

22、的鄰節(jié)點通過單條鏈路到達目的節(jié)點達目的節(jié)點1是最短路徑中最短的。由于鏈路長是最短路徑中最短的。由于鏈路長度非負，所以任何多條鏈路組成的路徑的長度都度非負，所以任何多條鏈路組成的路徑的長度都不可能短于第一條鏈路的長度。不可能短于第一條鏈路的長度。下一個最短的肯定是節(jié)點下一個最短的肯定是節(jié)點1的次最近的鄰節(jié)點所的次最近的鄰節(jié)點所對應(yīng)的單條鏈路，或者是通過前面選定的節(jié)點的對應(yīng)的單條鏈路，或者是通過前面選定的節(jié)點的有兩條鏈路組成的路徑，依次類推。有兩條鏈路組成的路徑，依次類推。Dijkstra算法算法Dijkstra算法算法Di為每個節(jié)點為每個節(jié)點i到達目的節(jié)點到達目的節(jié)點1的最短路徑長度的預(yù)估值的最

23、短路徑長度的預(yù)估值如果在迭代的過程中，如果在迭代的過程中，Di已變成一個確定的值，稱節(jié)點已變成一個確定的值，稱節(jié)點i為永久標定的節(jié)點，這些永久標定的節(jié)點的集合用為永久標定的節(jié)點，這些永久標定的節(jié)點的集合用P表示。表示。在算法的每一步中，在在算法的每一步中，在P以外的節(jié)點中，選擇與目的節(jié)點以外的節(jié)點中，選擇與目的節(jié)點1最近的節(jié)點加入到集合最近的節(jié)點加入到集合P中。中。 1. 初始化，初始化，如果如果 ，則，則 。2. 尋找下一個與目的節(jié)點最近的節(jié)點，尋找下一個與目的節(jié)點最近的節(jié)點， 置置 如果如果P包括了所有的節(jié)點，則算法結(jié)束。包括了所有的節(jié)點，則算法結(jié)束。3. 更改標定值，即對所有的更改標定值

24、，即對所有的 ，置，置 返回第返回第步。步。1P 10D 1jjDd1j ( ,1)jA1 jd iPminijj PDD PPijPmin,jjjiiiDD dDDijkstra算法算法Dijkstra算法運算量算法運算量有有N個節(jié)點，則有個節(jié)點，則有N-1次疊代，即次疊代，即N-1 個節(jié)點均成為永久節(jié)點；個節(jié)點均成為永久節(jié)點；每次疊代中，更改標定值，最多每次疊代中，更改標定值，最多N-1個點個點在最壞的情況下，在最壞的情況下，Dijkstra算法的復(fù)雜度為算法的復(fù)雜度為 ，B-F算法的復(fù)雜度為算法的復(fù)雜度為 。即。即Dijkstra算法的復(fù)雜度要低于算法的復(fù)雜度要低于B-F我們可以看到：我

25、們可以看到： ，對所有，對所有 。 對于每一個節(jié)點對于每一個節(jié)點j，Dj是從是從j到目的節(jié)點到目的節(jié)點1的最短距離。該路徑使用的最短距離。該路徑使用的所有節(jié)點（除的所有節(jié)點（除j以外）都屬于以外）都屬于P。2()O N3()O NijDD,iP jP3 Floyd-Warshall算法（算法（F-W算法）算法） B-F算法和算法和Dijkstra算法都是求解所有節(jié)點到一個特算法都是求解所有節(jié)點到一個特定的目的節(jié)點之間的最短路徑，定的目的節(jié)點之間的最短路徑， F-W算法則是多點對多點的路由選擇算法。算法則是多點對多點的路由選擇算法。 假設(shè)：假設(shè)： 鏈路的長度可正可負；鏈路的長度可正可負； 不存在

26、負長度的環(huán)；不存在負長度的環(huán)；3 Floyd-Warshall算法（算法（F-W算法）算法） 基本思想：基本思想：是在是在 的路徑之間通過添加中間節(jié)點來減小路的路徑之間通過添加中間節(jié)點來減小路徑長度。徑長度。 以單鏈路（無中間節(jié)點）的距離作為最短路徑的初始以單鏈路（無中間節(jié)點）的距離作為最短路徑的初始估計。估計。然后，在僅允許節(jié)點然后，在僅允許節(jié)點1作為中間節(jié)點的情況下，計算最作為中間節(jié)點的情況下，計算最短路徑，短路徑，接著，在允許節(jié)點接著，在允許節(jié)點1和節(jié)點和節(jié)點2作為中間節(jié)點的情況下計作為中間節(jié)點的情況下計算最短距離，算最短距離，依次類推。依次類推。 ij3 Floyd-Warshall算

27、法（算法（F-W算法）算法）具體算法描述如下：具體算法描述如下： 令令 是可以用是可以用1、2n作為中間節(jié)點的從作為中間節(jié)點的從i到到j(luò)的最短的最短路徑長度，路徑長度，算法開始時算法開始時 ，對所有，對所有i，j， 。對于對于 ，有，有上式假設(shè)上式假設(shè)i到到j(luò)的最短路徑的最短路徑 （以（以1，2n作為中間節(jié)點）作為中間節(jié)點）的條件，給出了計算在的條件，給出了計算在i到到j(luò)的最短路徑上可添加節(jié)點的最短路徑上可添加節(jié)點n+1后的最短路徑長度。后的最短路徑長度。 復(fù)雜度為復(fù)雜度為 。N個節(jié)點，每個節(jié)點疊代個節(jié)點，每個節(jié)點疊代N-1次，次，nijD0ijijDdij0,1,.,1nN1(1)(1)mi

28、n,nnnnijiji nnjDDDDijnijD3()O N 前面討論的三種最短路由算法的構(gòu)造方法，都是通過迭代的前面討論的三種最短路由算法的構(gòu)造方法，都是通過迭代的過程求得最終結(jié)果。但其主要差別是迭代的內(nèi)容不同。過程求得最終結(jié)果。但其主要差別是迭代的內(nèi)容不同。 在在B-F算法中，迭代的是路徑中的鏈路數(shù)，即使用一條，兩算法中，迭代的是路徑中的鏈路數(shù)，即使用一條，兩條，條，直到，直到N-1條鏈路。條鏈路。 在在Dijkstra算法中迭代的是路徑的長度，即最短長度，次短長算法中迭代的是路徑的長度，即最短長度，次短長度，度，。 而在而在F-W算法中，是對路徑的中間節(jié)點進行的迭代，即一個中算法中，是

29、對路徑的中間節(jié)點進行的迭代，即一個中間節(jié)點，兩個中間節(jié)點，間節(jié)點，兩個中間節(jié)點，。分布式最短路徑算法分布式最短路徑算法 集中式集中式路由算法是指網(wǎng)絡(luò)的路由是由路由算法是指網(wǎng)絡(luò)的路由是由路由控制中心路由控制中心計計算的，該中心周期性收集各鏈路的狀態(tài)，經(jīng)過路由計算的，該中心周期性收集各鏈路的狀態(tài)，經(jīng)過路由計算后周期性地向各網(wǎng)絡(luò)節(jié)點提供路由表。算后周期性地向各網(wǎng)絡(luò)節(jié)點提供路由表。 分布式分布式路由是指網(wǎng)絡(luò)中所有節(jié)點通過相互交換路由信路由是指網(wǎng)絡(luò)中所有節(jié)點通過相互交換路由信息，獨立地計算到達各節(jié)點的路由。息，獨立地計算到達各節(jié)點的路由。5.3.2 分布式最短路徑算法分布式最短路徑算法 分布式路由算法的

30、特點分布式路由算法的特點 節(jié)點用于存儲網(wǎng)絡(luò)拓撲結(jié)構(gòu)的空間較少；節(jié)點用于存儲網(wǎng)絡(luò)拓撲結(jié)構(gòu)的空間較少； 每個節(jié)點每個節(jié)點周期性周期性的從相鄰的節(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息，同時的從相鄰的節(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息，同時也將本節(jié)點做出的決定周期性的通知周圍的各節(jié)點，以使也將本節(jié)點做出的決定周期性的通知周圍的各節(jié)點，以使這些節(jié)點不斷的根據(jù)網(wǎng)絡(luò)新的狀態(tài)更新其路由選擇。這些節(jié)點不斷的根據(jù)網(wǎng)絡(luò)新的狀態(tài)更新其路由選擇。 各個節(jié)點的路由表相互作用；各個節(jié)點的路由表相互作用； 整個網(wǎng)絡(luò)的路由經(jīng)常處于一種整個網(wǎng)絡(luò)的路由經(jīng)常處于一種動態(tài)變化動態(tài)變化的狀態(tài)。當網(wǎng)絡(luò)狀的狀態(tài)。當網(wǎng)絡(luò)狀態(tài)發(fā)生變化時，會影響到許多節(jié)點的路由表。要經(jīng)過一定態(tài)

31、發(fā)生變化時，會影響到許多節(jié)點的路由表。要經(jīng)過一定的時間以后，各路由表中的數(shù)據(jù)才能達到穩(wěn)定的數(shù)值。的時間以后，各路由表中的數(shù)據(jù)才能達到穩(wěn)定的數(shù)值。 分布式路由選擇算法的核心思想是各個節(jié)點獨立的計算最分布式路由選擇算法的核心思想是各個節(jié)點獨立的計算最短路徑。短路徑。 典型的分布式最短路徑選擇算法有典型的分布式最短路徑選擇算法有距離矢量路由算法距離矢量路由算法和和鏈路鏈路狀態(tài)路由算法狀態(tài)路由算法。一一 距離矢量路由算法距離矢量路由算法 距離矢量路由算法距離矢量路由算法（Distance Vector Routing）算）算法法分布式分布式B-F算法算法的具體實現(xiàn)。的具體實現(xiàn)。 路由表結(jié)構(gòu)路由表結(jié)構(gòu)

32、在距離矢量路由表中，每個在距離矢量路由表中，每個路由器路由器維護一張維護一張路由路由表表，該表中記錄了到網(wǎng)絡(luò)中其它所有目的節(jié)點的，該表中記錄了到網(wǎng)絡(luò)中其它所有目的節(jié)點的路由信息。包括到該目的節(jié)點的路由信息。包括到該目的節(jié)點的下一跳節(jié)點下一跳節(jié)點（即（即本節(jié)點通過哪個鄰節(jié)點到達指定的目的節(jié)點），本節(jié)點通過哪個鄰節(jié)點到達指定的目的節(jié)點），和到達該目的節(jié)點所需的和到達該目的節(jié)點所需的“距離距離”的估計值。的估計值。一一 距離矢量路由算法距離矢量路由算法 算法：算法： 初始化初始化 每當收到鄰節(jié)點路由信息每當收到鄰節(jié)點路由信息 ，按下式更新路，按下式更新路由表由表 為節(jié)點為節(jié)點i 的鄰居節(jié)點集合的鄰居

33、節(jié)點集合 將更新的路由表通知其臨界點將更新的路由表通知其臨界點1i 0iD 010D ( )miniijjj N iDdDjD( )N i( )miniijjj N iDdD一一 距離矢量路由算法距離矢量路由算法 在表中使用的距離量度可以是在表中使用的距離量度可以是跳數(shù)、時延、某一路徑排隊的跳數(shù)、時延、某一路徑排隊的總分組數(shù)或者其它類似的量度總分組數(shù)或者其它類似的量度。每一個節(jié)點都確知它的每一。每一個節(jié)點都確知它的每一個鄰節(jié)點的距離。個鄰節(jié)點的距離。 如果采用時延作為距離的量度，每個節(jié)點應(yīng)當能夠利用一個如果采用時延作為距離的量度，每個節(jié)點應(yīng)當能夠利用一個特殊的特殊的“回聲回聲”（ECHO）分組

34、來直接測量該時延。接收節(jié)點）分組來直接測量該時延。接收節(jié)點收到收到“回聲回聲”分組后，只對它加上時間標記后就立即送回。分組后，只對它加上時間標記后就立即送回。 以時延作為距離的量度。每隔以時延作為距離的量度。每隔T秒，每個節(jié)點向它的每個鄰節(jié)秒，每個節(jié)點向它的每個鄰節(jié)點發(fā)送一個路由信息分組，該分組包括了發(fā)送節(jié)點已知的目點發(fā)送一個路由信息分組，該分組包括了發(fā)送節(jié)點已知的目的節(jié)點的下一跳節(jié)點和時延估計值。同樣，每一個節(jié)點都會的節(jié)點的下一跳節(jié)點和時延估計值。同樣，每一個節(jié)點都會收到它所有的鄰節(jié)點發(fā)送來的路由信息分組。收到它所有的鄰節(jié)點發(fā)送來的路由信息分組。一一 距離矢量路由算法距離矢量路由算法計數(shù)至無

35、窮問題（對鏈路故障反應(yīng)較慢）計數(shù)至無窮問題（對鏈路故障反應(yīng)較慢）它對好消息的反應(yīng)迅速，但對壞消息卻反應(yīng)遲鈍它對好消息的反應(yīng)迅速，但對壞消息卻反應(yīng)遲鈍 討論壞消息的傳播速度。討論壞消息的傳播速度。 在實際系統(tǒng)中，我們可以將無窮大設(shè)置為網(wǎng)絡(luò)的在實際系統(tǒng)中，我們可以將無窮大設(shè)置為網(wǎng)絡(luò)的最大跳數(shù)加最大跳數(shù)加1。但是當采用時延作為距離的長度時，。但是當采用時延作為距離的長度時，將很難定義一個合適的時延上界。該時延的上界將很難定義一個合適的時延上界。該時延的上界應(yīng)足夠大，以避免將長時延的路徑認為是故障的應(yīng)足夠大，以避免將長時延的路徑認為是故障的鏈路。鏈路。 2 水平分裂算法水平分裂算法 水平分裂算法與距離

36、矢量算法的工作過程基本一樣，不同之水平分裂算法與距離矢量算法的工作過程基本一樣，不同之處在于如果節(jié)點處在于如果節(jié)點I到達某一目的節(jié)點到達某一目的節(jié)點J的距離是通過節(jié)點的距離是通過節(jié)點X得到得到的，則節(jié)點的，則節(jié)點I將不會向節(jié)點將不會向節(jié)點X報告有關(guān)節(jié)點報告有關(guān)節(jié)點J的信息（即節(jié)點的信息（即節(jié)點I向向節(jié)點節(jié)點X報告的到達節(jié)點報告的到達節(jié)點J的距離為無窮大）。的距離為無窮大）。 平分割法雖然能夠解決一些計數(shù)平分割法雖然能夠解決一些計數(shù)至無窮問題，但有時候也不能正至無窮問題，但有時候也不能正常工作。常工作。IXJ二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 在在1979年之前，年之前，ARPANET都是采

37、用的距離矢量路由都是采用的距離矢量路由算法。之后，就用鏈路狀態(tài)路由算法（算法。之后，就用鏈路狀態(tài)路由算法（Link State Routing）取代了距離矢量路由算法。）取代了距離矢量路由算法。 其主要原因有兩個。其主要原因有兩個。 第一，因為在距離矢量算法中，時延的度量是僅第一，因為在距離矢量算法中，時延的度量是僅僅是隊列的長度，而并沒有考慮后來鏈路帶寬的僅是隊列的長度，而并沒有考慮后來鏈路帶寬的增長；增長； 第二，距離矢量算法的收斂速度比較慢，即使是第二，距離矢量算法的收斂速度比較慢，即使是采用了類似于水平分割這樣的技術(shù)，也需要耗費采用了類似于水平分割這樣的技術(shù)，也需要耗費過多的時間用于記

38、錄信息。過多的時間用于記錄信息。 路由計算采用路由計算采用Dijkstra算法算法二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 鏈路狀態(tài)路由算法的思想非常簡單，它包括以下五個部分：鏈路狀態(tài)路由算法的思想非常簡單，它包括以下五個部分： 發(fā)現(xiàn)鄰節(jié)點，并獲取它們的地址；發(fā)現(xiàn)鄰節(jié)點，并獲取它們的地址； 測量到達每一個鄰節(jié)點的時延或成本；測量到達每一個鄰節(jié)點的時延或成本； 構(gòu)造一個分組來通告它所知道的所有路由信息；構(gòu)造一個分組來通告它所知道的所有路由信息； 發(fā)送該分組到所有其它節(jié)點；發(fā)送該分組到所有其它節(jié)點； 計算到所有其它節(jié)點的最短路徑。計算到所有其它節(jié)點的最短路徑。 事實上，完整的拓撲結(jié)構(gòu)和所有的時延都已

39、經(jīng)分發(fā)到網(wǎng)絡(luò)中事實上，完整的拓撲結(jié)構(gòu)和所有的時延都已經(jīng)分發(fā)到網(wǎng)絡(luò)中的每一個節(jié)點。隨后，每個節(jié)點都可以用的每一個節(jié)點。隨后，每個節(jié)點都可以用DijkstraDijkstra算法來求算法來求得到其它所有節(jié)點的最短路徑。得到其它所有節(jié)點的最短路徑。二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 發(fā)現(xiàn)鄰節(jié)點發(fā)現(xiàn)鄰節(jié)點 當一個路由器啟動以后，它的第一個任務(wù)就是要知道當一個路由器啟動以后，它的第一個任務(wù)就是要知道它的鄰節(jié)點是誰。具體實現(xiàn)的方法是：該路由器在每它的鄰節(jié)點是誰。具體實現(xiàn)的方法是：該路由器在每一個輸出鏈路上廣播一個特殊的一個輸出鏈路上廣播一個特殊的Hello分組，在這些分組，在這些鏈路另一端的路由器將會

40、發(fā)送回一個應(yīng)答分組，告知鏈路另一端的路由器將會發(fā)送回一個應(yīng)答分組，告知它是誰。所有路由器的名字（地址）必須是全球唯一它是誰。所有路由器的名字（地址）必須是全球唯一的。的。 二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 當兩個或多個路由器通過當兩個或多個路由器通過LAN互連時，如圖互連時，如圖5-14（a）所）所示，這時我們把示，這時我們把LAN看成一個虛擬的節(jié)點看成一個虛擬的節(jié)點N，如圖，如圖5-14（b）所示。這時所示。這時A到到C的路由就可以看成是的路由就可以看成是ANC。 二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 測量鏈路時延或成本測量鏈路時延或成本鏈路狀態(tài)路由算法要求每個路由器確知到達每一個鄰

41、節(jié)點鏈路狀態(tài)路由算法要求每個路由器確知到達每一個鄰節(jié)點的時延或?qū)υ摃r延有一個合理的估計。確定該時延的最直的時延或?qū)υ摃r延有一個合理的估計。確定該時延的最直接的方法是發(fā)送一個特殊的接的方法是發(fā)送一個特殊的ECHOECHO分組給每個鄰節(jié)點，并要分組給每個鄰節(jié)點，并要求每個鄰節(jié)點立即發(fā)回該分組。將測量的來回時延除以求每個鄰節(jié)點立即發(fā)回該分組。將測量的來回時延除以2 2就就可以得到該鏈路時延的估計。為了得到較好的結(jié)果，可測可以得到該鏈路時延的估計。為了得到較好的結(jié)果，可測量多次后取平均。量多次后取平均。在測量鏈路時延時，既可以考慮排隊的時延（鏈路的負在測量鏈路時延時，既可以考慮排隊的時延（鏈路的負荷）

42、，也可以不考慮排隊的時延?？紤]排隊時延（鏈路負荷），也可以不考慮排隊的時延。考慮排隊時延（鏈路負荷）的優(yōu)點是可以獲得較好的性能，但是可能會引起路由荷）的優(yōu)點是可以獲得較好的性能，但是可能會引起路由的振蕩。的振蕩。二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 構(gòu)造鏈路狀態(tài)分組構(gòu)造鏈路狀態(tài)分組 每個節(jié)點都構(gòu)造一個自己的鏈路狀態(tài)分組，它包括發(fā)送節(jié)每個節(jié)點都構(gòu)造一個自己的鏈路狀態(tài)分組，它包括發(fā)送節(jié)點的標號、該分組的序號和壽命，以及發(fā)送節(jié)點的鄰節(jié)點點的標號、該分組的序號和壽命，以及發(fā)送節(jié)點的鄰節(jié)點列表及發(fā)送節(jié)點到這些鄰節(jié)點的鏈路時延。列表及發(fā)送節(jié)點到這些鄰節(jié)點的鏈路時延。 何時構(gòu)造這些分組。何時構(gòu)造這些分組。

43、 一種方法是周期性地構(gòu)造這些分組；一種方法是周期性地構(gòu)造這些分組； 另一種方法是在鏈路狀態(tài)變化（如故障、恢復(fù)工作或特另一種方法是在鏈路狀態(tài)變化（如故障、恢復(fù)工作或特性改變）時才構(gòu)造這些分組。性改變）時才構(gòu)造這些分組。 二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 分發(fā)鏈路狀態(tài)分組分發(fā)鏈路狀態(tài)分組該算法的中最具技巧性的部分就是如何可靠的分發(fā)鏈路狀態(tài)分組。當該算法的中最具技巧性的部分就是如何可靠的分發(fā)鏈路狀態(tài)分組。當鏈路狀態(tài)分組被發(fā)布后，首先得到該分組的路由器將改變其路由選擇。鏈路狀態(tài)分組被發(fā)布后，首先得到該分組的路由器將改變其路由選擇。同時，別的路由器可能還在使用

44、不同的舊版本的鏈路信息，這樣將導(dǎo)同時，別的路由器可能還在使用不同的舊版本的鏈路信息，這樣將導(dǎo)致各節(jié)點對當前網(wǎng)絡(luò)拓撲的看法不一致性，從而計算出的路由可能出致各節(jié)點對當前網(wǎng)絡(luò)拓撲的看法不一致性，從而計算出的路由可能出現(xiàn)死循環(huán)、不可達或其它問題?，F(xiàn)死循環(huán)、不可達或其它問題。鏈路狀態(tài)分組分發(fā)的最基本方法是采用泛洪（鏈路狀態(tài)分組分發(fā)的最基本方法是采用泛洪（FloodingFlooding）方式。為防）方式。為防止每個節(jié)點處理和中轉(zhuǎn)過時的鏈路狀態(tài)分組，在這些分組中引入了序止每個節(jié)點處理和中轉(zhuǎn)過時的鏈路狀態(tài)分組，在這些分組中引入了序號。每個節(jié)點僅中轉(zhuǎn)序號大于已記錄的最大序號的分組，為了防止序號。每個節(jié)點僅中

45、轉(zhuǎn)序號大于已記錄的最大序號的分組，為了防止序號出錯，在分組中還引入了壽命，壽命每秒遞減一次，如果壽命為號出錯，在分組中還引入了壽命，壽命每秒遞減一次，如果壽命為0 0，則該分組將被丟棄。則該分組將被丟棄。二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 為了提高傳輸?shù)目煽啃?，所有鏈路狀態(tài)分組都需為了提高傳輸?shù)目煽啃?，所有鏈路狀態(tài)分組都需要應(yīng)答。為了處理鏈路狀態(tài)分組在泛洪中需要發(fā)要應(yīng)答。為了處理鏈路狀態(tài)分組在泛洪中需要發(fā)往哪些鄰節(jié)點、需要對哪條鏈路的分組進行應(yīng)答往哪些鄰節(jié)點、需要對哪條鏈路的分組進行應(yīng)答的問題，每個節(jié)點需構(gòu)造一個分組存儲數(shù)據(jù)結(jié)構(gòu)。的問題，每個節(jié)點需構(gòu)造一個分組存儲數(shù)據(jù)結(jié)構(gòu)。該圖是圖該圖是圖

46、5-15拓撲中節(jié)點拓撲中節(jié)點B的數(shù)據(jù)結(jié)構(gòu)。圖中每一的數(shù)據(jù)結(jié)構(gòu)。圖中每一行對應(yīng)剛剛到達，但還沒有完全處理的鏈路狀態(tài)行對應(yīng)剛剛到達，但還沒有完全處理的鏈路狀態(tài)分組。由于節(jié)點分組。由于節(jié)點B有三個鄰節(jié)點有三個鄰節(jié)點A、C和和F，所以發(fā)，所以發(fā)送標志指明應(yīng)當發(fā)送給哪個鄰節(jié)點，應(yīng)答標志指送標志指明應(yīng)當發(fā)送給哪個鄰節(jié)點，應(yīng)答標志指明應(yīng)答哪個鄰節(jié)點。明應(yīng)答哪個鄰節(jié)點。 二二 鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法 計算新的路由計算新的路由 當每個節(jié)點獲得所有的鏈路狀態(tài)分組以后，它可以構(gòu)造一當每個節(jié)點獲得所有的鏈路狀態(tài)分組以后，它可以構(gòu)造一個完整的網(wǎng)絡(luò)拓撲，此時每個節(jié)點就可以運行個完整的網(wǎng)絡(luò)拓撲，此時每個節(jié)點就可以

47、運行Dijkstra算法算法來構(gòu)造到達所有目的的節(jié)點的最短路由。來構(gòu)造到達所有目的的節(jié)點的最短路由。 鏈路狀態(tài)路由算法已廣泛用于多種實際網(wǎng)絡(luò)中，例如鏈路狀態(tài)路由算法已廣泛用于多種實際網(wǎng)絡(luò)中，例如Internet中的中的OSPF采用了該算法，采用了該算法，ISO的無連接網(wǎng)絡(luò)層協(xié)議（的無連接網(wǎng)絡(luò)層協(xié)議（CLNP）使用的使用的IS-IS（Intermediate System-to-Intermediate System）協(xié)議也是采用該算法。）協(xié)議也是采用該算法。IS-IS中交換的信息是用于計中交換的信息是用于計算最短路由的網(wǎng)絡(luò)拓撲圖（而不僅僅是鏈路狀態(tài)分組），它算最短路由的網(wǎng)絡(luò)拓撲圖（而不僅僅是鏈

48、路狀態(tài)分組），它還可以支持多種網(wǎng)絡(luò)協(xié)議（如還可以支持多種網(wǎng)絡(luò)協(xié)議（如IP，IPX，AppleTalk等）。等）。5.4 自適應(yīng)最短路由的穩(wěn)定性分析自適應(yīng)最短路由的穩(wěn)定性分析自適應(yīng)最短路由的穩(wěn)定性分析自適應(yīng)最短路由的穩(wěn)定性分析 路由算法分類路由算法分類 確定型策略（確定型策略（Deterministic Algorithm） 基于網(wǎng)絡(luò)拓撲和平均分組時延要求，以某一準則來選擇基于網(wǎng)絡(luò)拓撲和平均分組時延要求，以某一準則來選擇分組的路徑。這類策略包括：擴散式路由算法，隨機式分組的路徑。這類策略包括：擴散式路由算法，隨機式路由算法，固定式最佳路由算法等。路由算法，固定式最佳路由算法等。 自適應(yīng)型策略（自

49、適應(yīng)型策略（Adaptive Algorithm）。）。 基于某一準則來確定在某一段時間內(nèi)有效的路由，目的基于某一準則來確定在某一段時間內(nèi)有效的路由，目的是為了適應(yīng)業(yè)務(wù)和拓撲的變化。這類策略又可細分為：是為了適應(yīng)業(yè)務(wù)和拓撲的變化。這類策略又可細分為：集中式自適應(yīng)路由、分布式自適應(yīng)路由算法。集中式自適應(yīng)路由、分布式自適應(yīng)路由算法。 如果在一段時間之后，算法最終是否可以有一個穩(wěn)定的如果在一段時間之后，算法最終是否可以有一個穩(wěn)定的解，會不會振蕩？這就是我們要討論的算法穩(wěn)定性問題。解，會不會振蕩？這就是我們要討論的算法穩(wěn)定性問題。 下面我們針對以鏈路長度最短為路由選擇原則的自適下面我們針對以鏈路長度最

50、短為路由選擇原則的自適應(yīng)路由算法來分析其穩(wěn)定性問題。這里，我們討論一應(yīng)路由算法來分析其穩(wěn)定性問題。這里，我們討論一種典型的情況，即鏈路的長度隨著該鏈路的業(yè)務(wù)情況種典型的情況，即鏈路的長度隨著該鏈路的業(yè)務(wù)情況變化而變化。很顯然，業(yè)務(wù)量比較重的鏈路將會被指變化而變化。很顯然，業(yè)務(wù)量比較重的鏈路將會被指定較大的鏈路長度。定較大的鏈路長度。 下面我們通過實例來看看數(shù)據(jù)報網(wǎng)絡(luò)和虛電路網(wǎng)絡(luò)的下面我們通過實例來看看數(shù)據(jù)報網(wǎng)絡(luò)和虛電路網(wǎng)絡(luò)的穩(wěn)定性問題。穩(wěn)定性問題。 1 數(shù)據(jù)報網(wǎng)絡(luò)的穩(wěn)定性數(shù)據(jù)報網(wǎng)絡(luò)的穩(wěn)定性 假定有一個網(wǎng)絡(luò)如圖假定有一個網(wǎng)絡(luò)如圖5-17所所示，它由示，它由16個節(jié)點組成，其個節(jié)點組成，其中節(jié)點中

51、節(jié)點16是惟一一個目的節(jié)是惟一一個目的節(jié)點。點。 網(wǎng)絡(luò)中的每一個節(jié)點都可能有兩條路徑到達目的節(jié)點：一條網(wǎng)絡(luò)中的每一個節(jié)點都可能有兩條路徑到達目的節(jié)點：一條是順時針方向到達目的節(jié)點，另一條是逆時針方向到達目的是順時針方向到達目的節(jié)點，另一條是逆時針方向到達目的節(jié)點。設(shè)鏈路節(jié)點。設(shè)鏈路 的長度的長度dij與鏈路上的流量與鏈路上的流量Fij成正比，這成正比，這里取里取 ，采用自適應(yīng)最短路由準則。，采用自適應(yīng)最短路由準則。 設(shè)節(jié)點設(shè)節(jié)點17、915輸入的業(yè)務(wù)量為輸入的業(yè)務(wù)量為1個單位，節(jié)點個單位，節(jié)點8輸入的業(yè)輸入的業(yè)務(wù)量為務(wù)量為 （ 是一個非常小的正數(shù)），網(wǎng)絡(luò)每隔是一個非常小的正數(shù)），網(wǎng)絡(luò)每隔T秒更

52、秒更新一次最短路由，即每個節(jié)點用前一個新一次最短路由，即每個節(jié)點用前一個T內(nèi)的內(nèi)的Fij決定當前決定當前T秒秒的路由。的路由。 ( , )i jijijdF0 出現(xiàn)上述振蕩的原因是各鏈路的長度（流量）取決于路由的出現(xiàn)上述振蕩的原因是各鏈路的長度（流量）取決于路由的選擇，而路由的選擇又取決于各鏈路的流量，這樣就構(gòu)成了選擇，而路由的選擇又取決于各鏈路的流量，這樣就構(gòu)成了反饋效應(yīng)。在一般情況下，只要鏈路長度反饋效應(yīng)。在一般情況下，只要鏈路長度dij是隨著鏈路流量是隨著鏈路流量Fij的增加而單調(diào)增長，且當?shù)脑黾佣鴨握{(diào)增長，且當 時有，都會出現(xiàn)上述不穩(wěn)定時有，都會出現(xiàn)上述不穩(wěn)定的振蕩現(xiàn)象。的振蕩現(xiàn)象。

53、0ijF 為了消除或減緩上述振蕩，一種方法是給每條鏈路的長度都為了消除或減緩上述振蕩，一種方法是給每條鏈路的長度都增加一個正的常量增加一個正的常量 （ 稱為偏置因子）。當稱為偏置因子）。當 時時有有 。此時。此時 的選擇就對路由的穩(wěn)定性起著決定性的選擇就對路由的穩(wěn)定性起著決定性的作用。如果的作用。如果 相對于可能的鏈路長度足夠大，則基本上是一相對于可能的鏈路長度足夠大，則基本上是一個靜態(tài)路由，且上述自適應(yīng)最短路由就變成了一個最小跳數(shù)個靜態(tài)路由，且上述自適應(yīng)最短路由就變成了一個最小跳數(shù)的路由。此時，網(wǎng)絡(luò)振蕩的可能性很小，但網(wǎng)絡(luò)對鏈路的阻的路由。此時，網(wǎng)絡(luò)振蕩的可能性很小，但網(wǎng)絡(luò)對鏈路的阻塞將不敏

54、感。塞將不敏感。 另一種方法是引入一種機制，將鏈路長度在多個最短路由更另一種方法是引入一種機制，將鏈路長度在多個最短路由更新周期上平均，這樣將改進路由算法的穩(wěn)定性，但也降低了新周期上平均，這樣將改進路由算法的穩(wěn)定性，但也降低了網(wǎng)絡(luò)對鏈路阻塞的敏感程度。網(wǎng)絡(luò)對鏈路阻塞的敏感程度。 0ijF 0ijd5.5 路由信息的廣播路由信息的廣播路由信息的廣播路由信息的廣播 路由信息的交換是路由算法的基礎(chǔ)。路由信息的交換是路由算法的基礎(chǔ)。 在正常情況下，在正常情況下， 收集節(jié)點：收集網(wǎng)絡(luò)路由信息的節(jié)點；收集節(jié)點：收集網(wǎng)絡(luò)路由信息的節(jié)點； 路由信息廣播：收集節(jié)點將路由信息發(fā)送到需要該信息的路由信息廣播：收集節(jié)

55、點將路由信息發(fā)送到需要該信息的節(jié)點。節(jié)點。 分組的廣播是一個難點問題。分組的廣播是一個難點問題。這些困難主要體現(xiàn)在以下幾個方面：這些困難主要體現(xiàn)在以下幾個方面：1. 網(wǎng)絡(luò)的拓撲信息必須通過鏈路來傳輸，而鏈路本網(wǎng)絡(luò)的拓撲信息必須通過鏈路來傳輸，而鏈路本身可能有故障。在有中心的網(wǎng)絡(luò)中，這個問題尤身可能有故障。在有中心的網(wǎng)絡(luò)中，這個問題尤為嚴重。因為，當網(wǎng)絡(luò)的部分節(jié)點通過一條可能為嚴重。因為，當網(wǎng)絡(luò)的部分節(jié)點通過一條可能會故障的鏈路與網(wǎng)絡(luò)中心相連時，如果該鏈路發(fā)會故障的鏈路與網(wǎng)絡(luò)中心相連時，如果該鏈路發(fā)生了故障，則網(wǎng)絡(luò)中的部分節(jié)點將會與網(wǎng)絡(luò)中心生了故障，則網(wǎng)絡(luò)中的部分節(jié)點將會與網(wǎng)絡(luò)中心失去聯(lián)系，從而

56、導(dǎo)致這些節(jié)點無法獲知網(wǎng)絡(luò)的拓失去聯(lián)系，從而導(dǎo)致這些節(jié)點無法獲知網(wǎng)絡(luò)的拓撲信息。撲信息。 2. 網(wǎng)絡(luò)中會存在多次拓撲變化（如鏈路斷開后，又網(wǎng)絡(luò)中會存在多次拓撲變化（如鏈路斷開后，又在短時間內(nèi)恢復(fù)正常），這就意味著們必須對舊在短時間內(nèi)恢復(fù)正常），這就意味著們必須對舊的路由信息和新的路由信息加以區(qū)分。的路由信息和新的路由信息加以區(qū)分。如果網(wǎng)絡(luò)采用泛洪的方式來廣播拓撲變化信息，如果網(wǎng)絡(luò)采用泛洪的方式來廣播拓撲變化信息，當網(wǎng)絡(luò)僅有一次拓撲變化時，泛洪方式可以正當網(wǎng)絡(luò)僅有一次拓撲變化時，泛洪方式可以正常工作，但當網(wǎng)絡(luò)有多次拓撲變化時，泛洪的常工作，但當網(wǎng)絡(luò)有多次拓撲變化時，泛洪的方法將不能正常工作。方法將

57、不能正常工作。 鏈路鏈路n UPn UP鏈路鏈路n DOWNn DOWNCBA A (DOWN)CBA A (DOWN)鏈路鏈路n UPn UPCBA A (UP)CBA A (UP) CA A (DOWN) CA A (DOWN)鏈路鏈路CA DOWNCA DOWN過時的信息被當作新信息！過時的信息被當作新信息！3. 當正在執(zhí)行最短路由算法時，新的拓撲信息到達，當正在執(zhí)行最短路由算法時，新的拓撲信息到達，這時，要么路由算法能夠處理拓撲變化帶來的問這時，要么路由算法能夠處理拓撲變化帶來的問題，要么中止剛才進行的計算，開始重新計算路題，要么中止剛才進行的計算，開始重新計算路由。由。4. 當一條鏈

58、路修復(fù)之后，它可能會引起分離的網(wǎng)絡(luò)當一條鏈路修復(fù)之后，它可能會引起分離的網(wǎng)絡(luò)重新連接，這時每一個分離的部分都可能會有另重新連接，這時每一個分離的部分都可能會有另外一部分的過時拓撲信息。路由算法必須讓這兩外一部分的過時拓撲信息。路由算法必須讓這兩部分最終認識到正確的網(wǎng)絡(luò)拓撲。部分最終認識到正確的網(wǎng)絡(luò)拓撲。 前面的討論告訴我們，網(wǎng)絡(luò)中的每一個節(jié)點要在所有的時間前面的討論告訴我們，網(wǎng)絡(luò)中的每一個節(jié)點要在所有的時間內(nèi)都得到正確的網(wǎng)絡(luò)拓撲是不可能的。所以我們期望的最佳內(nèi)都得到正確的網(wǎng)絡(luò)拓撲是不可能的。所以我們期望的最佳值是：算法能夠在有限的時間內(nèi)處理有限次的拓撲變化。值是：算法能夠在有限的時間內(nèi)處理有限

59、次的拓撲變化。 為了便于討論，我們作如下假設(shè)，這些假設(shè)可以保證拓撲變?yōu)榱吮阌谟懻?，我們作如下假設(shè)，這些假設(shè)可以保證拓撲變化能夠被正確的檢測到?；軌虮徽_的檢測到。 網(wǎng)絡(luò)的鏈路能維持傳輸?shù)捻樞蛐院驼_性。此外，各節(jié)網(wǎng)絡(luò)的鏈路能維持傳輸?shù)捻樞蛐院驼_性。此外，各節(jié)點能夠維持其存儲器中數(shù)據(jù)的完整性。點能夠維持其存儲器中數(shù)據(jù)的完整性。 鏈路的故障是由鏈路的兩個端點檢測的，但不一定要同鏈路的故障是由鏈路的兩個端點檢測的，但不一定要同時檢測到。這就意味著鏈路的一個端點認為鏈路斷開后，時檢測到。這就意味著鏈路的一個端點認為鏈路斷開后，另一個端點最終也會認為鏈路斷開。必須注意的是，另一另一個端點最終也會認為

60、鏈路斷開。必須注意的是，另一個端點認為鏈路斷開必須在第一個點認為鏈路恢復(fù)之前。個端點認為鏈路斷開必須在第一個點認為鏈路恢復(fù)之前。 有完善的數(shù)據(jù)鏈路層協(xié)議，能夠識別鏈路何時再次工作。有完善的數(shù)據(jù)鏈路層協(xié)議，能夠識別鏈路何時再次工作。如果鏈路的一個端點宣布鏈路恢復(fù)（如果鏈路的一個端點宣布鏈路恢復(fù)（UP），則在有限的時），則在有限的時間內(nèi)，另一個端點要么宣布鏈路恢復(fù)，要么首先再次宣布間內(nèi)，另一個端點要么宣布鏈路恢復(fù)，要么首先再次宣布鏈路故障（鏈路故障（DOWN）。）。 節(jié)點可以有故障。這種情況下，與它關(guān)聯(lián)的每一條鏈路節(jié)點可以有故障。這種情況下，與它關(guān)聯(lián)的每一條鏈路的另一個端點在有限的時間內(nèi)必須宣布鏈