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ù) 為了實(shí)現(xiàn)端到端的傳遞，網(wǎng)絡(luò)層提供了為了實(shí)現(xiàn)端到端的傳遞，網(wǎng)絡(luò)層提供了兩種主要功能：交換和路由兩種主要功能：交換和路由 交換和路由需要在原始數(shù)據(jù)包上附加源交換和路由需要在原始數(shù)據(jù)包上

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

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

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

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

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

7、度和開銷方面的優(yōu)勢(shì)。如果某一條路經(jīng)發(fā)生阻塞或中斷，包可如果某一條路經(jīng)發(fā)生阻塞或中斷，包可以選擇另一條路經(jīng)。單個(gè)傳輸?shù)母鱾€(gè)片以選擇另一條路經(jīng)。單個(gè)傳輸?shù)母鱾€(gè)片斷可以通過(guò)不同的路徑傳輸，從而達(dá)到斷可以通過(guò)不同的路徑傳輸，從而達(dá)到最大的效率。最大的效率。 面向非連接網(wǎng)絡(luò)服務(wù)的缺點(diǎn)：面向非連接網(wǎng)絡(luò)服務(wù)的缺點(diǎn)： CLNSCLNS不可靠，無(wú)法保證數(shù)據(jù)包順序到達(dá)。不可靠，無(wú)法保證數(shù)據(jù)包順序到達(dá)。每個(gè)包所需的開銷較大，每個(gè)包必須攜每個(gè)包所需的開銷較大，每個(gè)包必須攜帶完整的地址信息。帶完整的地址信息。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ò)層。路由器在多個(gè)互路由器工作在網(wǎng)絡(luò)層。路由器在多個(gè)互連設(shè)備之間中繼包。路由器對(duì)來(lái)自某個(gè)連設(shè)備之間中繼包。路由器對(duì)來(lái)自某個(gè)網(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)路由器和交換機(jī)的區(qū)別路由器和交換機(jī)的區(qū)別5.2.2 第三層交換機(jī)第三層交換機(jī) 三層交換機(jī)的特征：三層交換機(jī)的特征： 轉(zhuǎn)發(fā)基于第三層地址的業(yè)務(wù)流轉(zhuǎn)發(fā)基于第三層地址的業(yè)務(wù)流 完全交換功能完全交換功能 完成特殊任務(wù)，如報(bào)文過(guò)濾完成特殊任務(wù)，如報(bào)文過(guò)濾 有路由功能有路由功能5.2.3 網(wǎng)關(guān)網(wǎng)關(guān) 網(wǎng)

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

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

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

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

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

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

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

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

17、交換網(wǎng)絡(luò)信息僅僅和鄰居交換網(wǎng)絡(luò)信息 信息的交換是通過(guò)有規(guī)律的時(shí)間間隔來(lái)信息的交換是通過(guò)有規(guī)律的時(shí)間間隔來(lái)進(jìn)行，一般每個(gè)進(jìn)行，一般每個(gè)3030秒秒 每個(gè)路由器依據(jù)路由表來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包，每個(gè)路由器依據(jù)路由表來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包，距離向量路由算法的路由表中的每一項(xiàng)距離向量路由算法的路由表中的每一項(xiàng)一般具有如下的格式：一般具有如下的格式： 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 算法的特點(diǎn)：算法的特點(diǎn)： 優(yōu)點(diǎn)：簡(jiǎn)單、適用于小規(guī)模網(wǎng)絡(luò)優(yōu)點(diǎn)：簡(jiǎn)單、適用于小規(guī)模網(wǎng)絡(luò) 缺點(diǎn)：網(wǎng)絡(luò)規(guī)模的伸展性差、對(duì)鏈路狀缺點(diǎn)：網(wǎng)絡(luò)規(guī)模的伸展性差、對(duì)鏈路狀態(tài)的變化響應(yīng)慢、路由包文尺寸大且包態(tài)的變化響應(yīng)慢、路由包文尺寸大且包文長(zhǎng)與路由器的個(gè)數(shù)成正比文長(zhǎng)與路由器的個(gè)數(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)路由中，每個(gè)路由器和互連在鏈路狀態(tài)路由中，每個(gè)路由器和互連網(wǎng)絡(luò)中的所有其它路由器共享關(guān)于它鄰網(wǎng)絡(luò)中的所有其它路由器共享關(guān)于它鄰居的信息居的信息:共享關(guān)于鄰居的信息共享關(guān)

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

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

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

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

26、發(fā)送來(lái)的每個(gè)其它路由器發(fā)送來(lái)的LSPLSP，并將它，并將它們的信息存放到一個(gè)鏈路狀態(tài)數(shù)據(jù)庫(kù)中。們的信息存放到一個(gè)鏈路狀態(tài)數(shù)據(jù)庫(kù)中。廣告者廣告者相關(guān)網(wǎng)絡(luò)相關(guān)網(wǎng)絡(luò)費(fèi)用費(fèi)用鄰居鄰居A11BA33FA52EB14AB22CC25BC62DD65CD73EE72DE53AF32AF43-FEDCBANet:7Net:6Net:5Net:4Net:3Net:2Net:11223425532323 典型的協(xié)議是典型的協(xié)議是OSPF(OpenOSPF(Open Short Path Short Path First)First) 路由器上啟動(dòng)路由器上啟動(dòng)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算法計(jì)算路由表算法計(jì)算路由表 DijkstraDijkstra算法算法(1959)(1959)使用由節(jié)點(diǎn)和弧組使用由節(jié)點(diǎn)和弧組成的圖計(jì)算網(wǎng)絡(luò)中兩點(diǎn)之間的最短路徑。成的圖計(jì)算網(wǎng)絡(luò)中兩點(diǎn)之間的最短路徑。節(jié)點(diǎn)有兩種類型：網(wǎng)絡(luò)和路由器?；∫补?jié)點(diǎn)有兩種類型：網(wǎng)絡(luò)和路由器?；∫灿袃深悾郝酚善鞯骄W(wǎng)絡(luò)的鏈路和網(wǎng)絡(luò)到有兩類：路由器到網(wǎng)絡(luò)的鏈路和網(wǎng)絡(luò)到路由器的鏈路。在路由器的鏈路。在DijkstraDijkstra算法中，從算法中

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

29、, ,這個(gè)路經(jīng)上的所有弧和節(jié)點(diǎn)被這個(gè)路經(jīng)上的所有弧和節(jié)點(diǎn)被標(biāo)記為最短路經(jīng)樹上的永久部分。標(biāo)記為最短路經(jīng)樹上的永久部分。 算法考察鏈路狀態(tài)數(shù)據(jù)庫(kù)算法考察鏈路狀態(tài)數(shù)據(jù)庫(kù), ,找出從這找出從這個(gè)選定的最短路經(jīng)向外延伸所能連接的個(gè)選定的最短路經(jīng)向外延伸所能連接的所有非永久性節(jié)點(diǎn)所有非永久性節(jié)點(diǎn), ,將這些節(jié)點(diǎn)臨時(shí)性將這些節(jié)點(diǎn)臨時(shí)性的加到最短路經(jīng)樹上。的加到最短路經(jīng)樹上。 如果所有的節(jié)點(diǎn)已經(jīng)成為最短路經(jīng)樹如果所有的節(jié)點(diǎn)已經(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下一個(gè)路由器費(fèi)用目標(biāo)網(wǎng)絡(luò)E47B56-25F64-33B32-11下一個(gè)路由器費(fèi)用目標(biāo)網(wǎng)絡(luò)Dijkstra算法總結(jié)算法總結(jié) 初始化初始化:設(shè)設(shè)N表示網(wǎng)絡(luò)節(jié)點(diǎn)集合表示網(wǎng)絡(luò)節(jié)點(diǎn)集合,先令先令N=1,對(duì)所有不在對(duì)所有不在N中的節(jié)點(diǎn)寫出中的節(jié)點(diǎn)寫出: S(V)= L(1,V) ;若節(jié)點(diǎn)若節(jié)點(diǎn)V與節(jié)點(diǎn)與節(jié)點(diǎn)1相鄰相鄰 ;若節(jié)點(diǎn)若節(jié)點(diǎn)V與節(jié)點(diǎn)與節(jié)點(diǎn)1不相鄰不相鄰 找出一個(gè)不在找出一個(gè)不在N中的

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

34、可以處理多種通信協(xié)議。 自治系統(tǒng)自治系統(tǒng)ASAS：一個(gè)自治系統(tǒng)就是處于一：一個(gè)自治系統(tǒng)就是處于一個(gè)管理機(jī)構(gòu)控制之下的路由器和網(wǎng)絡(luò)群個(gè)管理機(jī)構(gòu)控制之下的路由器和網(wǎng)絡(luò)群組。一個(gè)自治系統(tǒng)中的所有路由器必須組。一個(gè)自治系統(tǒng)中的所有路由器必須相互連接，運(yùn)行相同的路由協(xié)議。它可相互連接，運(yùn)行相同的路由協(xié)議。它可以連多個(gè)局域網(wǎng)上，同時(shí)也連到以連多個(gè)局域網(wǎng)上，同時(shí)也連到InternetInternet上上Net 1Net 2Net 3Net 4Net 5ABCDEFABCDEF(a) 一個(gè)互連網(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)間的路由選擇問(wèn)題。自治系統(tǒng)間的路由選擇問(wèn)題。 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 虛電路路由表：虛電路路由表： 包的傳送要依賴于路由表，每個(gè)交換節(jié)包的傳送要依賴于路由表，每個(gè)交換節(jié)點(diǎn)都有一個(gè)虛電路路由表。假如在這點(diǎn)都有一個(gè)虛電路路由表。假如在

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

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

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