吉大計算機網(wǎng)絡(luò)PPT

1、第五章第五章 網(wǎng)絡(luò)層網(wǎng)絡(luò)層 5.1 5.1 網(wǎng)絡(luò)層功能和服務(wù)網(wǎng)絡(luò)層功能和服務(wù) 5.2 5.2 網(wǎng)絡(luò)層互連設(shè)備網(wǎng)絡(luò)層互連設(shè)備 5.3 5.3 路由選擇策略路由選擇策略 5.4 5.4 基本的路由算法基本的路由算法 5.5 5.5 基本的網(wǎng)關(guān)路由協(xié)議基本的網(wǎng)關(guān)路由協(xié)議 5.6 5.6 虛電路中數(shù)據(jù)包的傳輸虛電路中數(shù)據(jù)包的傳輸 5.7 5.7 擁塞控制和流量控制擁塞控制和流量控制 5.1 網(wǎng)絡(luò)層功能和服務(wù)網(wǎng)絡(luò)層功能和服務(wù) 為了實現(xiàn)端到端的傳遞，網(wǎng)絡(luò)層提供了為了實現(xiàn)端到端的傳遞，網(wǎng)絡(luò)層提供了兩種主要功能：交換和路由兩種主要功能：交換和路由 交換和路由需要在原始數(shù)據(jù)包上附加源交換和路由需要在原始數(shù)據(jù)包上

2、附加源和目的地址，這些地址和數(shù)據(jù)鏈路層的和目的地址，這些地址和數(shù)據(jù)鏈路層的上、下節(jié)點地址不同，網(wǎng)絡(luò)層地址是信上、下節(jié)點地址不同，網(wǎng)絡(luò)層地址是信源和信宿。源和信宿。 網(wǎng)絡(luò)層提供任意兩個網(wǎng)絡(luò)節(jié)點的可靠通網(wǎng)絡(luò)層提供任意兩個網(wǎng)絡(luò)節(jié)點的可靠通信。信。5.1.1 網(wǎng)絡(luò)層的功能網(wǎng)絡(luò)層的功能 信源到信宿的傳輸：將多條物理鏈路連信源到信宿的傳輸：將多條物理鏈路連接成一條傳輸路徑。接成一條傳輸路徑。 邏輯尋址：為了完成從信源到信宿的傳邏輯尋址：為了完成從信源到信宿的傳輸，在數(shù)據(jù)包的頭部加入源地址和目的輸，在數(shù)據(jù)包的頭部加入源地址和目的地址。地址。 路由：選擇從一點到另一點發(fā)送數(shù)據(jù)包路由：選擇從一點到另一點發(fā)送數(shù)據(jù)

3、包的最佳路經(jīng)。的最佳路經(jīng)。 地址轉(zhuǎn)換：將網(wǎng)絡(luò)層地址翻譯成對應(yīng)的地址轉(zhuǎn)換：將網(wǎng)絡(luò)層地址翻譯成對應(yīng)的物理地址。物理地址。 復(fù)用：同一條物理線路同時傳輸多個設(shè)復(fù)用：同一條物理線路同時傳輸多個設(shè)備間的數(shù)據(jù)備間的數(shù)據(jù) 流量和擁塞控制流量和擁塞控制 網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連: :解決網(wǎng)絡(luò)互連的有關(guān)問題解決網(wǎng)絡(luò)互連的有關(guān)問題5.1.2 面向連接的網(wǎng)絡(luò)服務(wù)面向連接的網(wǎng)絡(luò)服務(wù) 面向連接的網(wǎng)絡(luò)服務(wù)為數(shù)據(jù)傳輸建立一面向連接的網(wǎng)絡(luò)服務(wù)為數(shù)據(jù)傳輸建立一條虛電路，這條電路在整個數(shù)據(jù)傳輸過條虛電路，這條電路在整個數(shù)據(jù)傳輸過程中都是有效的。屬于這次數(shù)據(jù)傳輸過程中都是有效的。屬于這次數(shù)據(jù)傳輸過程的所有包都將按順序沿著這條電路傳程的所有

4、包都將按順序沿著這條電路傳輸。輸。 一個面向連接的網(wǎng)絡(luò)服務(wù)通過如下步驟一個面向連接的網(wǎng)絡(luò)服務(wù)通過如下步驟完成一次傳輸過程：完成一次傳輸過程： 發(fā)送者發(fā)送一個連接請求包發(fā)送者發(fā)送一個連接請求包 接收者使用一個連接確認包進行確認接收者使用一個連接確認包進行確認 發(fā)送者傳輸數(shù)據(jù)發(fā)送者傳輸數(shù)據(jù) 發(fā)送者發(fā)送一個連接終止請求包發(fā)送者發(fā)送一個連接終止請求包 接收者使用一個連接終止包進行確認接收者使用一個連接終止包進行確認 面向連接網(wǎng)絡(luò)服務(wù)的優(yōu)點：面向連接網(wǎng)絡(luò)服務(wù)的優(yōu)點： 允許一個協(xié)議包含全面的順序、差錯和允許一個協(xié)議包含全面的順序、差錯和流量控制。流量控制。 允許在流量控制上使用滑動窗口。允許在流量控制上使

5、用滑動窗口。 數(shù)據(jù)包中使用了較少的協(xié)議控制信息，數(shù)據(jù)包中使用了較少的協(xié)議控制信息，減少了額外開銷。減少了額外開銷。 面向連接網(wǎng)絡(luò)服務(wù)的缺點：面向連接網(wǎng)絡(luò)服務(wù)的缺點： 一旦連接建立以后，路由的靈活性就不一旦連接建立以后，路由的靈活性就不存在了。如果一條鏈路發(fā)生阻塞或出現(xiàn)存在了。如果一條鏈路發(fā)生阻塞或出現(xiàn)其他問題，后續(xù)的包不能使用其他的路其他問題，后續(xù)的包不能使用其他的路徑來替代。徑來替代。 它比面向非連接的網(wǎng)絡(luò)服務(wù)速度低。在它比面向非連接的網(wǎng)絡(luò)服務(wù)速度低。在面向連接的網(wǎng)絡(luò)服務(wù)中，包必須被檢查、面向連接的網(wǎng)絡(luò)服務(wù)中，包必須被檢查、或者被確認、或者被重傳或者被確認、或者被重傳。5.1.3 面向無連接

6、的網(wǎng)絡(luò)服務(wù)面向無連接的網(wǎng)絡(luò)服務(wù) 在面向非連接的網(wǎng)絡(luò)服務(wù)中，一次多包在面向非連接的網(wǎng)絡(luò)服務(wù)中，一次多包傳輸中，每個包被當(dāng)作一個獨立的單元。傳輸中，每個包被當(dāng)作一個獨立的單元。無連接協(xié)議不提供邏輯連接。發(fā)送者不無連接協(xié)議不提供邏輯連接。發(fā)送者不需要提醒接收者有通信即將到來，它僅需要提醒接收者有通信即將到來，它僅僅是發(fā)送數(shù)據(jù)。中間節(jié)點根據(jù)路由信息僅是發(fā)送數(shù)據(jù)。中間節(jié)點根據(jù)路由信息和報頭地址選擇路徑。和報頭地址選擇路徑。 面向非連接網(wǎng)絡(luò)服務(wù)的優(yōu)點：面向非連接網(wǎng)絡(luò)服務(wù)的優(yōu)點： 如果可靠性和排序可由上層協(xié)議來處理如果可靠性和排序可由上層協(xié)議來處理的話，的話，CLNSCLNS具有速度和開銷方面的優(yōu)勢。具有速

7、度和開銷方面的優(yōu)勢。如果某一條路經(jīng)發(fā)生阻塞或中斷，包可如果某一條路經(jīng)發(fā)生阻塞或中斷，包可以選擇另一條路經(jīng)。單個傳輸?shù)母鱾€片以選擇另一條路經(jīng)。單個傳輸?shù)母鱾€片斷可以通過不同的路徑傳輸，從而達到斷可以通過不同的路徑傳輸，從而達到最大的效率。最大的效率。 面向非連接網(wǎng)絡(luò)服務(wù)的缺點：面向非連接網(wǎng)絡(luò)服務(wù)的缺點： CLNSCLNS不可靠，無法保證數(shù)據(jù)包順序到達。不可靠，無法保證數(shù)據(jù)包順序到達。每個包所需的開銷較大，每個包必須攜每個包所需的開銷較大，每個包必須攜帶完整的地址信息。帶完整的地址信息。5.2 網(wǎng)絡(luò)層互連設(shè)備網(wǎng)絡(luò)層互連設(shè)備 網(wǎng)絡(luò)層互連設(shè)備主要是路由器。網(wǎng)絡(luò)層互連設(shè)備主要是路由器。5.2.1 路由器

8、路由器 路由器工作在網(wǎng)絡(luò)層。路由器在多個互路由器工作在網(wǎng)絡(luò)層。路由器在多個互連設(shè)備之間中繼包。路由器對來自某個連設(shè)備之間中繼包。路由器對來自某個網(wǎng)絡(luò)的包確定傳輸路徑，發(fā)送到互連網(wǎng)網(wǎng)絡(luò)的包確定傳輸路徑，發(fā)送到互連網(wǎng)絡(luò)中任何可能的目的網(wǎng)絡(luò)中。絡(luò)中任何可能的目的網(wǎng)絡(luò)中。路由器路由器路由器路由器總線令牌環(huán)令牌環(huán)令牌環(huán)路由器和交換機的區(qū)別路由器和交換機的區(qū)別5.2.2 第三層交換機第三層交換機 三層交換機的特征：三層交換機的特征： 轉(zhuǎn)發(fā)基于第三層地址的業(yè)務(wù)流轉(zhuǎn)發(fā)基于第三層地址的業(yè)務(wù)流 完全交換功能完全交換功能 完成特殊任務(wù)，如報文過濾完成特殊任務(wù)，如報文過濾 有路由功能有路由功能5.2.3 網(wǎng)關(guān)網(wǎng)關(guān) 網(wǎng)

9、關(guān)是一個協(xié)議轉(zhuǎn)換器。網(wǎng)關(guān)通常是安網(wǎng)關(guān)是一個協(xié)議轉(zhuǎn)換器。網(wǎng)關(guān)通常是安裝在路由器內(nèi)部的軟件?？梢怨ぷ髟谘b在路由器內(nèi)部的軟件?？梢怨ぷ髟贠SI的的7層。層。5.3 路由選擇策略路由選擇策略 路由選擇就是網(wǎng)絡(luò)中各個節(jié)點為到來的路由選擇就是網(wǎng)絡(luò)中各個節(jié)點為到來的數(shù)據(jù)包選擇一條輸出鏈路。數(shù)據(jù)包選擇一條輸出鏈路。 如果網(wǎng)絡(luò)內(nèi)部使用數(shù)據(jù)報，那么就必須如果網(wǎng)絡(luò)內(nèi)部使用數(shù)據(jù)報，那么就必須為每個到來的包作一次路由選擇。如果為每個到來的包作一次路由選擇。如果網(wǎng)絡(luò)內(nèi)部使用虛電路，則僅在建立一個網(wǎng)絡(luò)內(nèi)部使用虛電路，則僅在建立一個虛電路時作一次路由選擇，以后各數(shù)據(jù)虛電路時作一次路由選擇，以后各數(shù)據(jù)包都按建立的路由傳送。包都

10、按建立的路由傳送。5.3.1 路由選擇的基本要求路由選擇的基本要求 正確性：路由算法必須是正確的正確性：路由算法必須是正確的 簡單性：算法在計算上應(yīng)該簡單簡單性：算法在計算上應(yīng)該簡單 堅定性：長時間運行不會出現(xiàn)系統(tǒng)故障堅定性：長時間運行不會出現(xiàn)系統(tǒng)故障 穩(wěn)定性：算法是收斂的穩(wěn)定性：算法是收斂的 公平性：通信節(jié)點利用信道的機會均等公平性：通信節(jié)點利用信道的機會均等 最佳性：按一定的標準獲得最好的效果最佳性：按一定的標準獲得最好的效果5.3.2 路由選擇策略路由選擇策略 根據(jù)路由算法能否隨網(wǎng)絡(luò)的通信量或拓根據(jù)路由算法能否隨網(wǎng)絡(luò)的通信量或拓撲結(jié)構(gòu)變化而進行調(diào)整來劃分，路由選撲結(jié)構(gòu)變化而進行調(diào)整來劃分

11、，路由選擇算法可分為兩大類：擇算法可分為兩大類： 非適應(yīng)性路由選擇算法非適應(yīng)性路由選擇算法 適應(yīng)性路由選擇算法適應(yīng)性路由選擇算法 非適應(yīng)性路由選擇非適應(yīng)性路由選擇 非適應(yīng)性路由算法不能隨網(wǎng)絡(luò)的通信量非適應(yīng)性路由算法不能隨網(wǎng)絡(luò)的通信量變化而變化，但實現(xiàn)起來容易。有以下變化而變化，但實現(xiàn)起來容易。有以下幾種方法：幾種方法： 洪泛洪泛(flooding)法：某個節(jié)點收到一個法：某個節(jié)點收到一個包時，向所有與此節(jié)點相連的鏈路發(fā)送包時，向所有與此節(jié)點相連的鏈路發(fā)送這個包。這個包。 有選擇的洪泛法：滿足事先確定的條有選擇的洪泛法：滿足事先確定的條件的鏈路上轉(zhuǎn)發(fā)包。件的鏈路上轉(zhuǎn)發(fā)包。 固定路由法：按最短路徑

12、建立一個表，固定路由法：按最短路徑建立一個表，表上標明每個目的地址的包應(yīng)當(dāng)從哪條表上標明每個目的地址的包應(yīng)當(dāng)從哪條鏈路上轉(zhuǎn)發(fā)。鏈路上轉(zhuǎn)發(fā)。 隨機走動隨機走動(random walk)(random walk)法：隨機選法：隨機選擇一條鏈路進行轉(zhuǎn)發(fā)。擇一條鏈路進行轉(zhuǎn)發(fā)。 分散通信量法：每個節(jié)點上設(shè)置一個分散通信量法：每個節(jié)點上設(shè)置一個表，表中給出幾個可采用的輸出鏈路，表，表中給出幾個可采用的輸出鏈路，并且對每條鏈路賦予一定的概率，此概并且對每條鏈路賦予一定的概率，此概率就是利用此鏈路進行轉(zhuǎn)發(fā)的概率。率就是利用此鏈路進行轉(zhuǎn)發(fā)的概率。0.25M0.30N0.45PE0.15M0.30P0.55ND0

13、.10P0.25M0.65NC0.30L0.35N0.35MB0.10N0.40L0.50MA概率經(jīng)過概率經(jīng)過概率經(jīng)過目的站0.25M0.30N0.45PE0.15M0.30P0.55ND0.10P0.25M0.65NC0.30L0.35N0.35MB0.10N0.40L0.50MA概率經(jīng)過概率經(jīng)過概率經(jīng)過目的站APBCDEMNKL網(wǎng)絡(luò)拓撲節(jié)點K路由表 適應(yīng)性路由選擇適應(yīng)性路由選擇 非適應(yīng)性路由選擇算法不適合網(wǎng)絡(luò)中通非適應(yīng)性路由選擇算法不適合網(wǎng)絡(luò)中通信量變化很大的情況信量變化很大的情況,這時需要適應(yīng)性路這時需要適應(yīng)性路由選擇算法，適應(yīng)性路由選擇算法主要由選擇算法，適應(yīng)性路由選擇算法主要由以下由

14、以下3種：種： 孤立的路由選擇策略孤立的路由選擇策略 各節(jié)點只根據(jù)自己的狀態(tài)決定路由選擇，各節(jié)點只根據(jù)自己的狀態(tài)決定路由選擇，而不與其它節(jié)點交換信息。算法非常簡而不與其它節(jié)點交換信息。算法非常簡單，但并不準確，使用此方法有時效率單，但并不準確，使用此方法有時效率不高。不高。 分布式路由選擇策略分布式路由選擇策略 每個節(jié)點有一個路由表，并周期性地從每個節(jié)點有一個路由表，并周期性地從周圍相鄰的節(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息，同周圍相鄰的節(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息，同時，也將本節(jié)點做出的路由周期性地通時，也將本節(jié)點做出的路由周期性地通知相鄰的各節(jié)點。整個網(wǎng)絡(luò)的路由選擇知相鄰的各節(jié)點。整個網(wǎng)絡(luò)的路由選擇經(jīng)常處于動態(tài)變

15、化之中。經(jīng)常處于動態(tài)變化之中。 典型的算法有典型的算法有:RIP:RIP協(xié)議和協(xié)議和OSPFOSPF協(xié)議。協(xié)議。 集中式路由選擇策略集中式路由選擇策略 網(wǎng)絡(luò)控制中心網(wǎng)絡(luò)控制中心NCCNCC負責(zé)全網(wǎng)狀態(tài)信息的負責(zé)全網(wǎng)狀態(tài)信息的收集、路由計算、以及路由選擇的實現(xiàn)。收集、路由計算、以及路由選擇的實現(xiàn)。每個節(jié)點定期向網(wǎng)絡(luò)控制中心報告一些每個節(jié)點定期向網(wǎng)絡(luò)控制中心報告一些狀態(tài)信息。狀態(tài)信息。 優(yōu)點：各個節(jié)點不需要路由選擇計算優(yōu)點：各個節(jié)點不需要路由選擇計算 缺點：通信量大、可靠性差、網(wǎng)絡(luò)的規(guī)缺點：通信量大、可靠性差、網(wǎng)絡(luò)的規(guī)模受到限制模受到限制5.4 基本的基本的路由算法路由算法 距離最短的路徑是最佳路

16、徑，距離最短距離最短的路徑是最佳路徑，距離最短的標準可以是費用最小、傳輸延遲最小、的標準可以是費用最小、傳輸延遲最小、數(shù)據(jù)傳輸速率最大、以及這些因素的一數(shù)據(jù)傳輸速率最大、以及這些因素的一種組合。種組合。 有兩種最常用的計算最短路經(jīng)的方法：有兩種最常用的計算最短路經(jīng)的方法： 距離向量路由距離向量路由 鏈路狀態(tài)路由鏈路狀態(tài)路由5.4.1 距離向量路由算法距離向量路由算法 在距離向量路由中，每個路由器周期性在距離向量路由中，每個路由器周期性的將自己關(guān)于整個網(wǎng)絡(luò)的信息發(fā)送給它的將自己關(guān)于整個網(wǎng)絡(luò)的信息發(fā)送給它的鄰居。的鄰居。 每個路由器保存關(guān)于整個網(wǎng)絡(luò)的信息每個路由器保存關(guān)于整個網(wǎng)絡(luò)的信息 僅僅和鄰居

17、交換網(wǎng)絡(luò)信息僅僅和鄰居交換網(wǎng)絡(luò)信息 信息的交換是通過有規(guī)律的時間間隔來信息的交換是通過有規(guī)律的時間間隔來進行，一般每個進行，一般每個3030秒秒 每個路由器依據(jù)路由表來轉(zhuǎn)發(fā)數(shù)據(jù)包，每個路由器依據(jù)路由表來轉(zhuǎn)發(fā)數(shù)據(jù)包，距離向量路由算法的路由表中的每一項距離向量路由算法的路由表中的每一項一般具有如下的格式：一般具有如下的格式： NetID: Distance: NexthopNetID: Distance: Nexthop 例：例：FEDCBANet:7Net:6Net:5Net:4Net:3Net:2Net:1輪 路由器目的網(wǎng)絡(luò)12345670A1:1:-2:? 3:1:-4:?5:1:-6:?7

18、:?B1:1:-2:1:-3:?4:?5:?6:?7:?C1:?2:1:-3:?4:?5:?6:1:-7:?D1:?2:?3:?4:?5:?6:1:-7:1:-E1:?2:?3:?4:?5:1:-6:?7:1:-F1:?2:?3: 1:-4:1:-5:?6:?7:?1A1:1:-2:2:B3:1:-4:2:F5:1:-6:?7:2:EB1:1:-2:1:-3:2:A4:?5:2:A6:2:C7:?C1:2:B1:1:-3:?4:?5:?6:1:-7:2:DD1:?2:2:C3:?4:?5:2:E6:1:-7:1:-E1:2:A2:?3:2:A4:?5:1:-6:2:D7:1:-F1:2:A2:

19、?3:1:-4:1:-5:2:A6:?7:?2A1:1:-2:2:B3:1:-4:2:F5:1:-6:3:B7:2:EB1:1:-2:1:-3:2:A4:3:A5:2:A6:2:C7:3:AC1:2:B1:1:-3:3:B4:?5:3:A6:1:-7:2:DD1:3:C2:2:C3:3:E4:?5:2:E6:1:-7:1:-E1:2:A2:3:D3:2:A4:3:A5:1:-6:2:D7:1:-F1:2:A2:3:A3:1:-4:1:-5:2:A6:?7:3:A3A1:1:-2:2:B3:1:-4:2:F5:1:-6:3:B7:2:EB1:1:-2:1:-3:2:A4:3:A5:2:A6:2:

20、C7:3:AC1:2:B1:1:-3:3:B4:4:B5:3:A6:1:-7:2:DD1:3:C2:2:C3:3:E4:4:E5:2:E6:1:-7:1:-E1:2:A2:3:D3:2:A4:3:A5:1:-6:2:D7:1:-F1:2:A2:3:A3:1:-4:1:-5:2:A6:4:A7:3:A 算法的特點：算法的特點： 優(yōu)點：簡單、適用于小規(guī)模網(wǎng)絡(luò)優(yōu)點：簡單、適用于小規(guī)模網(wǎng)絡(luò) 缺點：網(wǎng)絡(luò)規(guī)模的伸展性差、對鏈路狀缺點：網(wǎng)絡(luò)規(guī)模的伸展性差、對鏈路狀態(tài)的變化響應(yīng)慢、路由包文尺寸大且包態(tài)的變化響應(yīng)慢、路由包文尺寸大且包文長與路由器的個數(shù)成正比文長與路由器的個數(shù)成正比 典型的協(xié)議是：典型的協(xié)議是：

21、 RIP(RoutingRIP(Routing Information Protocol) Information Protocol) 在路由器上鍵入命令在路由器上鍵入命令: : Router ripRouter rip Network 192.168.1.0Network 192.168.1.0 Network 192.168.2.0Network 192.168.2.05.4.2 鏈路狀態(tài)鏈路狀態(tài)路由算法路由算法 在鏈路狀態(tài)路由中，每個路由器和互連在鏈路狀態(tài)路由中，每個路由器和互連網(wǎng)絡(luò)中的所有其它路由器共享關(guān)于它鄰網(wǎng)絡(luò)中的所有其它路由器共享關(guān)于它鄰居的信息居的信息:共享關(guān)于鄰居的信息共享關(guān)

22、于鄰居的信息共享的信息發(fā)給所有的路由器共享的信息發(fā)給所有的路由器信息的共享在有規(guī)律的時間間隔內(nèi)進行信息的共享在有規(guī)律的時間間隔內(nèi)進行（一般（一般30分鐘）分鐘） 理解鏈路狀態(tài)路由的關(guān)鍵在于它和距離理解鏈路狀態(tài)路由的關(guān)鍵在于它和距離向量路由的不同之處。在鏈路狀態(tài)路由向量路由的不同之處。在鏈路狀態(tài)路由中，每個路由器和互連網(wǎng)絡(luò)中的所有其中，每個路由器和互連網(wǎng)絡(luò)中的所有其它路由器共享關(guān)于它鄰居的信息。它路由器共享關(guān)于它鄰居的信息。 鏈路狀態(tài)路由可分為兩步完成：第一步鏈路狀態(tài)路由可分為兩步完成：第一步是共享鏈路狀態(tài)信息，即每個路由器將是共享鏈路狀態(tài)信息，即每個路由器將它自己和它的所有鄰居之間的鏈路狀態(tài)它

23、自己和它的所有鄰居之間的鏈路狀態(tài)信息發(fā)送給互連網(wǎng)絡(luò)中的所有其它路由信息發(fā)送給互連網(wǎng)絡(luò)中的所有其它路由器。第二步是每個路由器根據(jù)自己所掌器。第二步是每個路由器根據(jù)自己所掌握的關(guān)于整個網(wǎng)絡(luò)的鏈路狀態(tài)信息計算握的關(guān)于整個網(wǎng)絡(luò)的鏈路狀態(tài)信息計算到每個網(wǎng)路的路由。到每個網(wǎng)路的路由。 鏈路狀態(tài)信息共享鏈路狀態(tài)信息共享FEDCBANet:7Net:6Net:5Net:4Net:3Net:2Net:11223425532323 (1)(1)路由器傳輸包的費用：在鏈路狀態(tài)路由器傳輸包的費用：在鏈路狀態(tài)路由中，費用是許多因素的加權(quán)值。這路由中，費用是許多因素的加權(quán)值。這些因素包括安全級別，流量和鏈路的傳些因素包括

24、安全級別，流量和鏈路的傳輸速率等。輸速率等。 (2)(2)鏈路狀態(tài)包：路由器通過向整個互鏈路狀態(tài)包：路由器通過向整個互連網(wǎng)絡(luò)中的所有路由器發(fā)送鏈路狀態(tài)包連網(wǎng)絡(luò)中的所有路由器發(fā)送鏈路狀態(tài)包(LSP)(LSP)，在網(wǎng)絡(luò)中擴散關(guān)于自己鄰居的，在網(wǎng)絡(luò)中擴散關(guān)于自己鄰居的信息。一個信息。一個LSPLSP通常包含四個信息域：通常包含四個信息域：廣告者的廣告者的IDID，所影響的目標網(wǎng)絡(luò)，所影響的目標網(wǎng)絡(luò)IDID，費，費用，鄰居路由器的用，鄰居路由器的IDID。 (3)(3)獲得關(guān)于鄰居路由器的信息：每個獲得關(guān)于鄰居路由器的信息：每個路由器都周期性地發(fā)送一個簡短的問候路由器都周期性地發(fā)送一個簡短的問候包來獲

25、取關(guān)于它們鄰居的信息。這些問包來獲取關(guān)于它們鄰居的信息。這些問候包很小，只占用很小的網(wǎng)絡(luò)資源。候包很小，只占用很小的網(wǎng)絡(luò)資源。 (4)(4)初始化：每個路由器在啟動時向它初始化：每個路由器在啟動時向它的所有鄰居發(fā)送一個問候包來獲取每條的所有鄰居發(fā)送一個問候包來獲取每條鏈路的狀態(tài)信息。然后它基于這些問候鏈路的狀態(tài)信息。然后它基于這些問候的結(jié)果準備一個的結(jié)果準備一個LSPLSP，并將它擴散到整，并將它擴散到整個網(wǎng)絡(luò)。像是說：大家好個網(wǎng)絡(luò)。像是說：大家好! !我是新路由我是新路由器，這里有人嗎器，這里有人嗎? ? (5)(5)鏈路狀態(tài)數(shù)據(jù)庫：每個路由器接收鏈路狀態(tài)數(shù)據(jù)庫：每個路由器接收每個其它路由器

26、發(fā)送來的每個其它路由器發(fā)送來的LSPLSP，并將它，并將它們的信息存放到一個鏈路狀態(tài)數(shù)據(jù)庫中。們的信息存放到一個鏈路狀態(tài)數(shù)據(jù)庫中。廣告者廣告者相關(guān)網(wǎng)絡(luò)相關(guān)網(wǎng)絡(luò)費用費用鄰居鄰居A11BA33FA52EB14AB22CC25BC62DD65CD73EE72DE53AF32AF43-FEDCBANet:7Net:6Net:5Net:4Net:3Net:2Net:11223425532323 典型的協(xié)議是典型的協(xié)議是OSPF(OpenOSPF(Open Short Path Short Path First)First) 路由器上啟動路由器上啟動OSPFOSPF協(xié)議協(xié)議: : router OSPF

27、99 Network 192.168.1.0 0.0.0.255 area 0 Network 192.168.2.0 0.0.0.255 area 0 DijkstraDijkstra算法計算路由表算法計算路由表 DijkstraDijkstra算法算法(1959)(1959)使用由節(jié)點和弧組使用由節(jié)點和弧組成的圖計算網(wǎng)絡(luò)中兩點之間的最短路徑。成的圖計算網(wǎng)絡(luò)中兩點之間的最短路徑。節(jié)點有兩種類型：網(wǎng)絡(luò)和路由器?；∫补?jié)點有兩種類型：網(wǎng)絡(luò)和路由器?；∫灿袃深悾郝酚善鞯骄W(wǎng)絡(luò)的鏈路和網(wǎng)絡(luò)到有兩類：路由器到網(wǎng)絡(luò)的鏈路和網(wǎng)絡(luò)到路由器的鏈路。在路由器的鏈路。在DijkstraDijkstra算法中，從算法中

28、，從路由器到網(wǎng)絡(luò)的鏈路的費用有效，而從路由器到網(wǎng)絡(luò)的鏈路的費用有效，而從網(wǎng)絡(luò)到路由器的鏈路的費用總是為網(wǎng)絡(luò)到路由器的鏈路的費用總是為0 0。 每個路由器在使用每個路由器在使用DijkstraDijkstra算法時，根算法時，根據(jù)下面四個步驟來形成自己的最短路經(jīng)據(jù)下面四個步驟來形成自己的最短路經(jīng)樹樹: :選擇自己作為樹的根選擇自己作為樹的根, ,并將根標記為永并將根標記為永久性節(jié)點久性節(jié)點, ,算法接著從根出發(fā)連接它的所算法接著從根出發(fā)連接它的所有鄰居節(jié)點有鄰居節(jié)點, ,這種連接是臨時性的。這種連接是臨時性的。算法比較所有的臨時連接算法比較所有的臨時連接, ,找出費用最找出費用最小的路徑小的路徑

29、, ,這個路經(jīng)上的所有弧和節(jié)點被這個路經(jīng)上的所有弧和節(jié)點被標記為最短路經(jīng)樹上的永久部分。標記為最短路經(jīng)樹上的永久部分。 算法考察鏈路狀態(tài)數(shù)據(jù)庫算法考察鏈路狀態(tài)數(shù)據(jù)庫, ,找出從這找出從這個選定的最短路經(jīng)向外延伸所能連接的個選定的最短路經(jīng)向外延伸所能連接的所有非永久性節(jié)點所有非永久性節(jié)點, ,將這些節(jié)點臨時性將這些節(jié)點臨時性的加到最短路經(jīng)樹上。的加到最短路經(jīng)樹上。 如果所有的節(jié)點已經(jīng)成為最短路經(jīng)樹如果所有的節(jié)點已經(jīng)成為最短路經(jīng)樹上的永久部分上的永久部分, ,則算法結(jié)束則算法結(jié)束, ,去掉非永久去掉非永久性的弧性的弧. .否則否則, ,轉(zhuǎn)步驟（轉(zhuǎn)步驟（2 2）繼續(xù)執(zhí)行。）繼續(xù)執(zhí)行。 FEDCBAN

30、et:7Net:6Net:5Net:4Net:3Net:2Net:11223425532323ANet:5Net:3Net:1123ANet:5Net:3Net:1123ANet:5Net:3Net:1123B1ANet:5Net:3Net:1123B1ANet:5Net:3Net:1123B1Net:23ANet:5Net:3Net:1123B1Net:23E2ANet:5Net:3Net:1123B1Net:23E2Net:74ANet:5Net:3Net:1123B1Net:23E2Net:74C3ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65AN

31、et:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3Net:46ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3Net:46D4ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3Net:46D49ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3Net:46D49ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3

32、Net:46D49最短樹的路由最短樹的路由(A(A路由器路由器) )ANet:5Net:3Net:1123B1Net:23E2Net:74C3Net:65F3Net:46D4E47B56-25F64-33B32-11下一個路由器費用目標網(wǎng)絡(luò)E47B56-25F64-33B32-11下一個路由器費用目標網(wǎng)絡(luò)Dijkstra算法總結(jié)算法總結(jié) 初始化初始化:設(shè)設(shè)N表示網(wǎng)絡(luò)節(jié)點集合表示網(wǎng)絡(luò)節(jié)點集合,先令先令N=1,對所有不在對所有不在N中的節(jié)點寫出中的節(jié)點寫出: S(V)= L(1,V) ;若節(jié)點若節(jié)點V與節(jié)點與節(jié)點1相鄰相鄰 ;若節(jié)點若節(jié)點V與節(jié)點與節(jié)點1不相鄰不相鄰 找出一個不在找出一個不在N中的

33、節(jié)點中的節(jié)點W,使使S(W)值值為最小為最小,把把W加入加入N中中,然后對所有不在然后對所有不在N中的節(jié)點按下式更新中的節(jié)點按下式更新: S(V)minS(V),S(W)+L(W,V) 重復(fù)步驟重復(fù)步驟(2),直到所有的網(wǎng)絡(luò)節(jié)點都直到所有的網(wǎng)絡(luò)節(jié)點都在在N中為止中為止.5.5 基本的網(wǎng)關(guān)路由協(xié)議基本的網(wǎng)關(guān)路由協(xié)議 互連網(wǎng)中提供兩級路由協(xié)議：互連網(wǎng)中提供兩級路由協(xié)議： 內(nèi)部網(wǎng)關(guān)協(xié)議內(nèi)部網(wǎng)關(guān)協(xié)議IGPIGP 外部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議EGPEGP5.5.1 互連網(wǎng)絡(luò)的路由問題互連網(wǎng)絡(luò)的路由問題 網(wǎng)絡(luò)互連可能需要多協(xié)議路由器，多協(xié)網(wǎng)絡(luò)互連可能需要多協(xié)議路由器，多協(xié)議路由器可以處理多種通信協(xié)議。議路由器

34、可以處理多種通信協(xié)議。 自治系統(tǒng)自治系統(tǒng)ASAS：一個自治系統(tǒng)就是處于一：一個自治系統(tǒng)就是處于一個管理機構(gòu)控制之下的路由器和網(wǎng)絡(luò)群個管理機構(gòu)控制之下的路由器和網(wǎng)絡(luò)群組。一個自治系統(tǒng)中的所有路由器必須組。一個自治系統(tǒng)中的所有路由器必須相互連接，運行相同的路由協(xié)議。它可相互連接，運行相同的路由協(xié)議。它可以連多個局域網(wǎng)上，同時也連到以連多個局域網(wǎng)上，同時也連到InternetInternet上上Net 1Net 2Net 3Net 4Net 5ABCDEFABCDEF(a) 一個互連網(wǎng)絡(luò))(b) 互連網(wǎng)絡(luò)的圖形圖9.17 互連網(wǎng)絡(luò)的例子5.5.2 內(nèi)部網(wǎng)關(guān)路由選擇協(xié)議內(nèi)部網(wǎng)關(guān)路由選擇協(xié)議 OSPF

35、(Open Shortest Path First)開放開放最短路徑優(yōu)先最短路徑優(yōu)先 OSPF路由協(xié)議是典型的鏈路狀態(tài)路由路由協(xié)議是典型的鏈路狀態(tài)路由協(xié)議，是互連網(wǎng)應(yīng)用最廣的路由協(xié)議。協(xié)議，是互連網(wǎng)應(yīng)用最廣的路由協(xié)議。5.5.3 外部網(wǎng)關(guān)路由選擇協(xié)議外部網(wǎng)關(guān)路由選擇協(xié)議 BGPv4是典型的外部網(wǎng)關(guān)協(xié)議，完成是典型的外部網(wǎng)關(guān)協(xié)議，完成自治系統(tǒng)間的路由選擇問題。自治系統(tǒng)間的路由選擇問題。 BGP協(xié)議是一種距離向量協(xié)議。協(xié)議是一種距離向量協(xié)議。5.6 虛電路中數(shù)據(jù)包的傳輸虛電路中數(shù)據(jù)包的傳輸 數(shù)據(jù)包在發(fā)送之前使用路由算法建立一數(shù)據(jù)包在發(fā)送之前使用路由算法建立一條虛電路，發(fā)送者沿著這條虛電路把數(shù)條虛電

36、路，發(fā)送者沿著這條虛電路把數(shù)據(jù)包傳遞給接收者。據(jù)包傳遞給接收者。ECBAH1H5H4H3H2D VCVC1 1:H:H1 1-A-B-E-H-A-B-E-H5 5 VCVC2 2:H:H1 1-A-B-D-H-A-B-D-H4 4 VCVC3 3:H:H2 2-B-D-E-H-B-D-E-H5 5 VCVC4 4:H:H3 3-C-B-E-H-C-B-E-H5 5 VC5:H1-A-B-C-E-H5 VC5:H1-A-B-C-E-H5 虛電路路由表：虛電路路由表： 包的傳送要依賴于路由表，每個交換節(jié)包的傳送要依賴于路由表，每個交換節(jié)點都有一個虛電路路由表。假如在這點都有一個虛電路路由表。假如在

37、這5 5個虛電路建立之前，網(wǎng)絡(luò)中沒有任何虛個虛電路建立之前，網(wǎng)絡(luò)中沒有任何虛電路存在，各個節(jié)點的路由表是空的。電路存在，各個節(jié)點的路由表是空的。當(dāng)這當(dāng)這5 5個虛擬電路建立完畢之后，網(wǎng)絡(luò)個虛擬電路建立完畢之后，網(wǎng)絡(luò)中的各個交換機的虛電路路由表也就形中的各個交換機的虛電路路由表也就形成了。表中的每一行記錄了一個虛電路成了。表中的每一行記錄了一個虛電路的信息。的信息。 路由表的建立：路由表的建立： H1H1發(fā)起建立發(fā)起建立3 3個虛電路，它們分別是個虛電路，它們分別是VC1VC1、VC2VC2和和VC5VC5，H1H1按順序分別給它們編號為按順序分別給它們編號為0 0、1 1和和2 2。H2H2發(fā)

38、起建立發(fā)起建立1 1個虛電路個虛電路, ,即即VC3VC3，H3H3給它編號為給它編號為0 0。H3H3發(fā)起建立發(fā)起建立1 1個虛電路，個虛電路，即即VC4VC4，H3H3給它編號為給它編號為0 0。 虛電路的編號：虛電路的編號： 每個節(jié)點對虛電路進行獨立編號。每個節(jié)點對虛電路進行獨立編號。 以虛電路以虛電路1為例，虛電路號碼的變換情為例，虛電路號碼的變換情況：況：H1H522003AECB例題例題 兩個用戶之間的傳輸線路由兩個用戶之間的傳輸線路由3段組成段組成,每每段的傳輸延遲為段的傳輸延遲為0.001s,呼叫建立時間為呼叫建立時間為0.2s,報文長報文長3200bit,分組大小為分組大小為

39、1024bit,報頭開銷為報頭開銷為16bit,線路數(shù)率線路數(shù)率9600bps。假。假設(shè)中間節(jié)點處理時間為零設(shè)中間節(jié)點處理時間為零,試問在下列交試問在下列交換下的端到端的延遲換下的端到端的延遲: (1)電路交換電路交換;(2)報文交換報文交換;(3)虛電路虛電路;(4)數(shù)據(jù)報數(shù)據(jù)報5.7 擁塞控制和流量控制擁塞控制和流量控制 擁塞控制的基本目的是防止整個網(wǎng)絡(luò)或擁塞控制的基本目的是防止整個網(wǎng)絡(luò)或網(wǎng)絡(luò)的一部分出現(xiàn)過多的數(shù)據(jù)包，而流網(wǎng)絡(luò)的一部分出現(xiàn)過多的數(shù)據(jù)包，而流量控制的目的是保證發(fā)送方發(fā)送的信息量控制的目的是保證發(fā)送方發(fā)送的信息量不會超過接收方的接收能力。量不會超過接收方的接收能力。5.7.1 擁塞控制擁塞控制 擁塞擁塞:網(wǎng)絡(luò)或其一部分出現(xiàn)過多的包網(wǎng)絡(luò)或其一部分出現(xiàn)過多的包,導(dǎo)導(dǎo)致網(wǎng)絡(luò)性能下降的現(xiàn)象。致網(wǎng)絡(luò)性能下降的現(xiàn)象。 包交換結(jié)點的模型包交換結(jié)點的模型節(jié)點4到主機到節(jié)點1到節(jié)點3到節(jié)點5輸入緩沖區(qū)輸出緩沖區(qū) 擁塞產(chǎn)生的原因擁塞產(chǎn)生的原因 節(jié)點的處理速度和鏈路的傳輸速度不夠節(jié)點的