計(jì)算機(jī)通信網(wǎng)絡(luò)之路由選擇與網(wǎng)絡(luò)擁塞控制

2013-11-071路由選擇與網(wǎng)絡(luò)擁塞控制本章掌握重點(diǎn)：

網(wǎng)絡(luò)層的主要功能和提供的服務(wù)；

路由選擇和流量控制思想；2013-11-0721

概述ISO

定義網(wǎng)絡(luò)層為一個(gè)網(wǎng)絡(luò)連接的兩個(gè)傳輸層實(shí)體間交換網(wǎng)絡(luò)服務(wù)數(shù)據(jù)單元提供功能和規(guī)程的方法，它使傳輸層實(shí)體看不到下面資源的使用情況。網(wǎng)絡(luò)層是處理端到端傳輸?shù)淖畹蛯?。網(wǎng)絡(luò)層要解決的關(guān)鍵問題:了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，選擇路由;另一個(gè)需要解決的問題是網(wǎng)絡(luò)的擁塞控制.2013-11-073概述1.1

網(wǎng)絡(luò)層的任務(wù)(1)通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)(2)路由選擇方法(3)流量和擁塞控制(4)網(wǎng)絡(luò)互連OSI標(biāo)準(zhǔn)集中于網(wǎng)絡(luò)層提供給傳輸層的功能和服務(wù)，以及網(wǎng)絡(luò)層與傳輸層及數(shù)據(jù)鏈路層的接口。2013-11-074網(wǎng)絡(luò)層概述1.2

向傳輸層提供的服務(wù)面向連接的服務(wù):將復(fù)雜的功能放在網(wǎng)絡(luò)層(通信子網(wǎng))

無連接服務(wù):將復(fù)雜的功能放在傳輸層通信子網(wǎng)提供的服務(wù)（面向連接或無連接）與通信子網(wǎng)結(jié)構(gòu)（虛電路或數(shù)據(jù)報(bào)）沒有必然聯(lián)系。2013-11-075網(wǎng)絡(luò)服務(wù)面向連接方式包括連接建立、數(shù)據(jù)傳送及連接釋放三個(gè)階段。一條連接由下列方面規(guī)定：(1)由端系統(tǒng)與一個(gè)網(wǎng)絡(luò)或幾個(gè)網(wǎng)絡(luò)之間三方或多方一致同意而建立的一條路徑。(2)協(xié)商確定的參數(shù)值和任選項(xiàng)(Options)；(3)連接標(biāo)識(shí)（例如虛電路號(hào)）；(4)指定連續(xù)的數(shù)據(jù)單元之間邏輯關(guān)系、排序和控制的有關(guān)上下文內(nèi)容。無連接方式不在端系統(tǒng)之間建立這類關(guān)系，所需要的僅是通信實(shí)體之間的關(guān)聯(lián)。2013-11-076服務(wù)原語服務(wù)原語是層服務(wù)用戶和服務(wù)提供者之間的一種抽象且與實(shí)現(xiàn)無關(guān)的交互，服務(wù)原語不必直接與協(xié)議要素相關(guān)。服務(wù)原語可分為請(qǐng)求、指示、響應(yīng)和證實(shí)四種類型。7面向連接服務(wù)原語端系統(tǒng)A傳輸層網(wǎng)絡(luò)層通信媒介（數(shù)據(jù)鏈路層）端系統(tǒng)B網(wǎng)絡(luò)層傳輸層N_RequestN_Indication

N_Response時(shí)間

2013-11-07N_Confirm

OSI網(wǎng)絡(luò)層服務(wù)原語的使用示例2013-11-078

階段連接建立數(shù)據(jù)傳輸連接拆除

服務(wù)連接建立

原語N_Connect.RequestN_Connect.IndicationN_Connect.ResponseN_Connect.Confirm可選服務(wù)接收確認(rèn)

加速數(shù)據(jù)

傳輸

原語N_DataAcknowledge.RequestN_DataAcknowledge.IndicationN_ExpeditedData.RequestN_ExpeditedData.Indication數(shù)據(jù)傳輸重

建連接釋放

N_Data.Request

N_Data.IndicationN_Reset.RequestN_Reset.IndicationN_Reset.ResponseN_Reset.ConfirmN_Disconnect.RequestN_Disconnect.Indication

表6-1

面向連接的服務(wù)及原語與面向連接的服務(wù)有關(guān)的原語有六種2013-11-079無連接服務(wù)原語N_Unitdata服務(wù)不提供差錯(cuò)控制，也不提供流量控制、分組重新排序及其它的控制N_Unitdata.request(源地址，目的地址，QoS，用戶數(shù)據(jù))N_Unitdata.indication(源地址，目的地址，QoS，用戶數(shù)據(jù))還有3條屬于正式標(biāo)準(zhǔn)的附件中的服務(wù)原語：N_Facility.request(QoS)N_Facility.indication(目的地址，QoS，原因)N_Report.indication(目的地址，QoS，原因)建連時(shí)延建立網(wǎng)絡(luò)連接所需要的時(shí)間建連失敗概率建立網(wǎng)絡(luò)連接失敗次數(shù)與嘗試次數(shù)之比吞吐量單位時(shí)間內(nèi)傳送的數(shù)據(jù)量轉(zhuǎn)換時(shí)延從發(fā)送請(qǐng)求原語至目的端，到接收指示原語所需要的時(shí)間殘留誤差率通過網(wǎng)絡(luò)服務(wù)邊界仍有出錯(cuò)、丟失、重復(fù)數(shù)據(jù)占傳送數(shù)據(jù)總數(shù)的比例傳送失敗概率傳送失敗數(shù)占傳送嘗試總數(shù)的比例連接恢復(fù)力在網(wǎng)絡(luò)連接過程中，服務(wù)提供者激活釋放和復(fù)位的概率拆連時(shí)延從發(fā)起連接拆除請(qǐng)求至成功釋放所需要的時(shí)間拆連失敗概率未成功拆除連接次數(shù)與嘗試次數(shù)之比連接保護(hù)能力網(wǎng)絡(luò)服務(wù)提供者試圖防止對(duì)用戶數(shù)據(jù)的未授權(quán)操作的程度連接優(yōu)先權(quán)考慮網(wǎng)絡(luò)連接及其數(shù)據(jù)的相對(duì)重要性最大開銷網(wǎng)絡(luò)服務(wù)的開銷范圍2013-11-0710面向連接的服務(wù)質(zhì)量轉(zhuǎn)換時(shí)延從發(fā)出N_Unitdata請(qǐng)求至響應(yīng)所需要的時(shí)間接入保護(hù)防止對(duì)網(wǎng)絡(luò)服務(wù)用戶信息的非法監(jiān)測(cè)和操縱開銷決定性因素確定對(duì)數(shù)據(jù)選擇路由所需要的開銷殘留誤差率某數(shù)據(jù)單元發(fā)生丟失、重復(fù)或誤傳的可能性優(yōu)先權(quán)數(shù)據(jù)單元之間的相對(duì)重要性源路由指定數(shù)據(jù)傳向目的地的路徑2013-11-0711無連接的服務(wù)質(zhì)量比較項(xiàng)目數(shù)據(jù)報(bào)子網(wǎng)虛電路子網(wǎng)初始建立連接不需要需要地址每個(gè)分組都含有完整的源地址和目的地址每個(gè)分組含有一個(gè)短的虛電路號(hào)，目的站地址僅在連接建立階段使用狀態(tài)信息子網(wǎng)不存儲(chǔ)狀態(tài)信息已建立的虛電路占用子網(wǎng)路由表空間路由選擇每個(gè)分組獨(dú)立選擇虛電路一建立，路由就已確定，所有分組都經(jīng)過此路徑分組的順序到達(dá)目的站時(shí)可能不按發(fā)送順序總是按發(fā)送順序到達(dá)目的站節(jié)點(diǎn)故障影響除節(jié)點(diǎn)崩潰時(shí)會(huì)丟失分組外，無其他影響所有經(jīng)過失效設(shè)備的虛電路都會(huì)被終止差錯(cuò)處理由主機(jī)承擔(dān)對(duì)主機(jī)透明（由通信子網(wǎng)承擔(dān)）擁塞控制由主機(jī)負(fù)責(zé)，較難實(shí)現(xiàn)由通信子網(wǎng)負(fù)責(zé)，若每條虛電路分配有足夠的緩沖區(qū)，則容易控制功能復(fù)雜性部分在傳輸層在網(wǎng)絡(luò)層適用方式面向連接和無連接服務(wù)面向連接服務(wù)2013-11-07121.3

網(wǎng)絡(luò)層的內(nèi)部結(jié)構(gòu)2013-11-0713網(wǎng)絡(luò)層概述虛電路（virtual

circuit）在發(fā)送第一個(gè)數(shù)據(jù)包之前要進(jìn)行連接的建立,一般等待時(shí)間為RTT.

連接請(qǐng)求包含完整的目的地地址,但每個(gè)數(shù)據(jù)包只攜帶

很小的VC標(biāo)識(shí),因此每個(gè)包的開銷很小.

如果連接的鏈路或交換機(jī)故障,連接將被中斷,必須建

立一個(gè)新的連接.

連接建立為預(yù)留資源提供了支持.數(shù)據(jù)報(bào)（datagram）沒有連接建立階段每個(gè)包包含完整的目的地址每個(gè)包獨(dú)立地被轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)表由路由協(xié)議動(dòng)態(tài)生成2013-11-0714服務(wù)與子網(wǎng)類型不同組合2013-11-0715小結(jié)網(wǎng)絡(luò)層的地位位于數(shù)據(jù)鏈路層和傳輸層之間，使用數(shù)據(jù)鏈路層提供的服務(wù)，為傳輸層提供服務(wù)；通信子網(wǎng)的最高層；處理端到端傳輸?shù)淖畹蛯印＞W(wǎng)絡(luò)層的作用屏蔽各種不同類型網(wǎng)絡(luò)之間的差異，實(shí)現(xiàn)互連了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，選擇路由，實(shí)現(xiàn)報(bào)文的網(wǎng)絡(luò)傳輸網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式

——

數(shù)據(jù)報(bào)和虛電路都屬于分組交換，采用存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制。數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)路由，分組帶有全網(wǎng)唯一的地址虛電路(virtual

circuit)：先在源端和目的端之間建立一條虛電路，所有分組沿虛電路按次序存儲(chǔ)轉(zhuǎn)發(fā)，最后拆除虛電路。在虛電路中，每個(gè)分組無須進(jìn)行路徑選擇。網(wǎng)絡(luò)層提供的服務(wù)面向連接的服務(wù)和無連接的服務(wù)。2013-11-07162

路由選擇算法路由選擇的定義指的是在分布式分組交換網(wǎng)中每個(gè)節(jié)點(diǎn)具有自動(dòng)選擇傳送分組到達(dá)目的地的最佳路徑的能力,就是說節(jié)點(diǎn)設(shè)備要根據(jù)一定的原則通過計(jì)算來確定每一分組發(fā)往宿端的最佳輸出路徑.2.1

關(guān)于路由選擇(1)能正確、迅速、合理地傳送報(bào)文信息；(2)能適應(yīng)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)或鏈路故障而引起的拓?fù)渥兓?，使?bào)文在故障條件下一般仍能到達(dá)終點(diǎn)。(3)能適應(yīng)網(wǎng)絡(luò)流量的變化，使各通路的流量均勻，整個(gè)網(wǎng)絡(luò)的通信設(shè)備負(fù)荷平衡，充分發(fā)揮效率；(4)算法盡量簡(jiǎn)單，以減少網(wǎng)絡(luò)開銷。2013-11-0717提交的負(fù)荷吞吐量流量控制路由選擇時(shí)延1.

路由選擇與流量控制的關(guān)系

時(shí)延

被拒絕的負(fù)荷路由選擇和流量控制之間的交互作用182.

路由選擇算法的分類

分類決策地點(diǎn)決策時(shí)間性能準(zhǔn)則網(wǎng)絡(luò)信息源（與路由選擇有關(guān)的信息）路選策略

2013-11-07

要素每一節(jié)點(diǎn)（分布式）中央節(jié)點(diǎn)（集中式）源節(jié)點(diǎn)節(jié)點(diǎn)子集分組（數(shù)據(jù)報(bào)）會(huì)話（虛電路）鏈路數(shù)設(shè)施代價(jià)時(shí)延吞吐量無本地相鄰節(jié)點(diǎn)路徑上的節(jié)點(diǎn)所有節(jié)點(diǎn)靜態(tài)——簡(jiǎn)單類算法自適應(yīng)2013-11-07193.

對(duì)路由選擇算法的要求

正確性:確保分組從源節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)；

簡(jiǎn)單性:實(shí)現(xiàn)方便，軟硬件開銷?。?/p>

自適應(yīng)性,也稱健壯性:算法能夠適應(yīng)業(yè)務(wù)量和網(wǎng)

絡(luò)拓?fù)涞淖兓?/p>

穩(wěn)定性:能長(zhǎng)時(shí)間無故障運(yùn)行;

公平性:每個(gè)節(jié)點(diǎn)都有機(jī)會(huì)傳送信息;

最優(yōu)性:盡量選取"好的"路由4.

路由選擇的實(shí)現(xiàn)——路由表節(jié)點(diǎn)1上的路由表節(jié)點(diǎn)4上的路由表目的節(jié)點(diǎn)23456目的節(jié)點(diǎn)356下一個(gè)節(jié)點(diǎn)22442下一個(gè)節(jié)點(diǎn)355路由算法路由選擇的實(shí)現(xiàn)-路由表

2

3

1

6

4

5

2013-11-07如：路徑選擇的原則是使到達(dá)目的節(jié)點(diǎn)的鏈路(hops)數(shù)最少,當(dāng)存在2條以上的最少鏈路的路徑時(shí),則可以選擇其中一條.路由表對(duì)每個(gè)目的節(jié)點(diǎn)指出分組應(yīng)該發(fā)向的下一個(gè)節(jié)點(diǎn).

20節(jié)點(diǎn)1上的路由表入虛電路(-,-)(-,-)(-,-)(2,1)(4,2)(4,4)出虛電路(2,1)(4,2)(4,4)(-,-)(-,-)(-,-)節(jié)點(diǎn)4上的路由表入虛電路(1,2)(1,4)(3,5)(5,4)出虛電路(5,4)(3,5)(1,4)(1,2)2013-11-0721路由算法虛電路使用的路由表

路由表中使用的是虛電路號(hào)而不是目的節(jié)點(diǎn)輸入虛電路,(X,n)表示前一個(gè)節(jié)點(diǎn)X和虛電路號(hào);輸出虛電路,(X,n)表示后一個(gè)節(jié)點(diǎn)X和虛電路號(hào);(-,-)表示虛電路在這個(gè)節(jié)點(diǎn)上起始和或終止.2013-11-0722匯集樹（sink

tree）

從所有的源節(jié)點(diǎn)到一個(gè)給定的目的節(jié)點(diǎn)的最優(yōu)路由的集

合形成了一個(gè)以目的節(jié)點(diǎn)為根的樹，稱為匯集樹；2013-11-07232.2

簡(jiǎn)單路由選擇算法1.

隨機(jī)路由選擇2.

洪泛式路由選擇3.

固定式路由選擇絕對(duì)固定式路由選擇迂回式路由選擇2013-11-0724靜態(tài)路由算法

隨機(jī)路由選擇:是由收到分組的節(jié)點(diǎn)隨機(jī)地選擇一

個(gè)出口轉(zhuǎn)發(fā)出去。缺點(diǎn)也是十分明顯的，可能造

成某些分組長(zhǎng)期在通信子網(wǎng)中轉(zhuǎn)，到達(dá)不了目的

節(jié)點(diǎn)。

洪泛算法（Flooding）:

又分為完全擴(kuò)散和選擇擴(kuò)散兩種

基本思想:把收到的每一個(gè)包，向除了該包到來的線路

外的所有輸出線路發(fā)送。

主要問題:洪泛要產(chǎn)生大量重復(fù)包。

解決措施:每個(gè)包頭包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過一站計(jì)數(shù)

器減1，為0時(shí)則丟棄該包；2013-11-0725

擴(kuò)散法（flooding）不計(jì)算路徑，有路就走1542911

73

532863

6如從5出發(fā)到4：數(shù)據(jù)包從51,2；23,6；36,4；63,7；74要解決的問題：數(shù)據(jù)包重復(fù)到達(dá)某一節(jié)點(diǎn)，如3，62013-11-0726

擴(kuò)散法（續(xù)）解決方法

在數(shù)據(jù)包頭設(shè)一計(jì)數(shù)器初值，每經(jīng)過一個(gè)節(jié)

點(diǎn)自動(dòng)減1，計(jì)數(shù)值為0

時(shí)，丟棄該數(shù)據(jù)包

在每個(gè)節(jié)點(diǎn)上建立登記表，則數(shù)據(jù)包再次經(jīng)

過時(shí)丟棄

缺點(diǎn)：重復(fù)數(shù)據(jù)包多，浪費(fèi)帶寬

優(yōu)點(diǎn)：可靠性高，路徑最短，常用于軍事2013-11-0727靜態(tài)路由算法

固定式路由選擇

固定式單路由算法(絕對(duì)固定式路由選擇):每個(gè)節(jié)點(diǎn)都有一張人工

計(jì)算得到的固定路由表，它給出了子網(wǎng)中每個(gè)節(jié)點(diǎn)作為目的節(jié)點(diǎn)

時(shí)，分組對(duì)應(yīng)的轉(zhuǎn)發(fā)出口的對(duì)應(yīng)關(guān)系。每收到一個(gè)分組，去查表

中目的節(jié)點(diǎn)，找出相應(yīng)的轉(zhuǎn)發(fā)出口。優(yōu)點(diǎn)是簡(jiǎn)單、實(shí)現(xiàn)方便，可

選擇正常情況下的最佳路由。缺點(diǎn)是路由表不能聯(lián)機(jī)修改，不能

適應(yīng)網(wǎng)絡(luò)的業(yè)務(wù)量及拓?fù)渥兓?/p>

固定式多路由算法（迂回式路由選擇）:固定式多路由算法是任何

一對(duì)節(jié)點(diǎn)之間有多條可選路由。一旦最佳的路由不通，或負(fù)荷過

大，就可以選擇第二、第三條路由。實(shí)現(xiàn)方法是每個(gè)節(jié)點(diǎn)裝有一

張路由表，對(duì)應(yīng)每個(gè)目的節(jié)點(diǎn)，給出最佳、次佳、再次佳……的

后繼節(jié)點(diǎn)和權(quán)數(shù)。缺點(diǎn)是路由表不能聯(lián)機(jī)修改。2013-11-07282.3

動(dòng)態(tài)路由選擇自適應(yīng)路由選擇方法是從路徑和時(shí)延兩方面考慮的1.

孤立的自適應(yīng)路由算法2.

分布式自適應(yīng)路由選擇2013-11-0729(1)孤立的自適應(yīng)路由算法選擇路由時(shí)，僅僅孤立地依據(jù)本節(jié)點(diǎn)自身的當(dāng)前運(yùn)行狀態(tài)（流量和排隊(duì)）信息來決定路由，而與網(wǎng)絡(luò)其他各節(jié)點(diǎn)的狀態(tài)無關(guān)。這種算法比較簡(jiǎn)單，但是它的適應(yīng)能力也有限。因?yàn)樗荒苓m應(yīng)網(wǎng)絡(luò)各節(jié)點(diǎn)或鏈路狀態(tài)的變化。最短排隊(duì)等待法

（“熱土豆”法）最短排隊(duì)加偏法考慮了本節(jié)點(diǎn)排隊(duì)狀態(tài)和網(wǎng)絡(luò)拓?fù)鋬煞N因素2013-11-0730一般，孤立法路由選擇要求節(jié)點(diǎn)必須具備：1.2.3.4.一張預(yù)置于本節(jié)點(diǎn)的固定式路由表；本節(jié)點(diǎn)各輸出鏈路的目前狀態(tài)（通或斷）；本節(jié)點(diǎn)等待發(fā)送的各鏈路排隊(duì)長(zhǎng)度；進(jìn)行路由運(yùn)算的選路程序。2013-11-0731······輸出隊(duì)列節(jié)點(diǎn)

N

·輸入緩沖器·輸出緩沖器

·NPL網(wǎng)采用的分叉路由選擇法

第一路徑（權(quán)3）B類第二路徑（權(quán)1）圖6-12

NPL網(wǎng)依據(jù)權(quán)重值的路由選擇2013-11-0732(2)分布式自適應(yīng)路由選擇分布式路由選擇法在現(xiàn)行網(wǎng)絡(luò)中用的最多。距離矢量路由算法狀態(tài)鏈路路由算法特點(diǎn)是：在網(wǎng)絡(luò)相鄰節(jié)點(diǎn)之間，每經(jīng)過一定時(shí)間相互交換一次狀態(tài)信息，各節(jié)點(diǎn)根據(jù)相鄰節(jié)點(diǎn)送來的狀態(tài)信息來修改自己的路由表。雖然每次修改只能反映相鄰節(jié)點(diǎn)的狀態(tài)變化，但是經(jīng)過n次修改即可反映出第n級(jí)相鄰節(jié)點(diǎn)的狀態(tài)改變。所以分布式路由選擇可以適應(yīng)整個(gè)網(wǎng)絡(luò)的狀態(tài)變化，只是附近節(jié)點(diǎn)處的狀態(tài)較快得到反映，遠(yuǎn)處節(jié)點(diǎn)的狀態(tài)較慢得到反映。you

are

here

Highway

B33Which

is

the

best

way

toLittleton?

Littleton180

miles

Littleton206

milesLittleton

74

miles

2013-11-07Highway

E81

miles

Littleton159

miles

Highway

A

31

milesHighway

D112

miles

22

miles

Highway

C,

4

miles

Littleton319

miles最短路徑的含義最短路徑問題是圖論中的一個(gè)經(jīng)典問題，是指在一個(gè)帶權(quán)圖的兩個(gè)頂點(diǎn)之間找出一條具有最小權(quán)的路徑。路徑度量的一種方法是計(jì)算站點(diǎn)數(shù)量或經(jīng)過的鏈路條數(shù)。另一種度量是以公里為單位的地理距離，路徑的權(quán)重是長(zhǎng)度。在大多數(shù)情況下，鏈路的度量可以是距離、信道帶寬、平均業(yè)務(wù)量、通信費(fèi)用、隊(duì)列平均長(zhǎng)度、測(cè)量的時(shí)延和其它一些因素的函數(shù)而計(jì)算出來。2013-11-0734最短路徑的一般性質(zhì)a.

最短路徑(A,B)上的某一段(Na,Nb)亦為最短路徑。b.

最短路徑(A,B)被中間節(jié)點(diǎn)X分割成兩段，則兩段路徑(A,X)和(X,B)分別都是最短路徑計(jì)算最短路徑的經(jīng)典算法-Dijkstra算法（圖：p227）2013-11-0735距離矢量路由算法距離矢量（Distance

Vector）算法的基本工作原理是每個(gè)路由器維護(hù)一張矢量表，表中列出了到每個(gè)目的地已知的最佳距離和路徑。通過在相鄰路由器之間交換信息來更新表的信息。2013-11-0736To通過A通過I通過H通過KA0242021B12363128C25181936D4027824E1473022F23201940G1831631H1720019I2101422J911710K2422220L293399J到A延時(shí)為8J到I延時(shí)為10J到H延時(shí)為12J到K延時(shí)為6線路8A20A28I20H17I30I18H12H10I0-6K15K節(jié)點(diǎn)J的新路由表2013-11-0737J重新估計(jì)的延時(shí)注意：AI為21；IA為24因?yàn)椋和头档男诺懒髁坎灰欢ㄏ嗤?，?jié)點(diǎn)A和I也并非在同一時(shí)刻測(cè)得，且線路狀態(tài)是動(dòng)態(tài)變化的

所謂節(jié)點(diǎn)即路由器

當(dāng)前節(jié)點(diǎn)為JEAIHDLC

GKBFJD-V算法的路由表更新狀態(tài)鏈路路由算法鏈路狀態(tài)（link

state）算法，與距離矢量算法不同，它是一種全局的路由選擇算法，算法的輸入是網(wǎng)絡(luò)拓?fù)鋱D。每個(gè)節(jié)點(diǎn)將鏈路狀態(tài)包向網(wǎng)絡(luò)中所有其他的節(jié)點(diǎn)廣播。鏈路狀態(tài)包包括節(jié)點(diǎn)的身份和它到相鄰節(jié)點(diǎn)的代價(jià)信息。最后的結(jié)果是所有的節(jié)點(diǎn)都具有同樣的網(wǎng)絡(luò)拓?fù)鋱D。獲得了網(wǎng)絡(luò)拓?fù)鋱D之后，每個(gè)節(jié)點(diǎn)就可以計(jì)算路由路徑了2013-11-0738ACBDCCDDE-FFA-BBCCDBECFCA-BBCCDBEBFBAABAC-DDEEFE39面向無連接服務(wù)的實(shí)現(xiàn)（數(shù)據(jù)報(bào)子網(wǎng)）路由器A按左邊的路由表運(yùn)行，后來發(fā)現(xiàn)如到E和F應(yīng)該走B才更好，于是更新路

由表2013-11-07ABCDERouterCarrier’s

equipmentLANH1Process

P1

PacketProcess

P1

H2

F1A的路由表E的路由表C的路由表數(shù)據(jù)報(bào)子網(wǎng)中分組的尋徑C1C3出口A1A3入口C1C2入口H11H32入口E1E2出口F1F2出口40H1和H2已建立了1#連接H3要和H2建立連接只能是2#

2013-11-07A的路由表虛電路子網(wǎng)中分組的尋徑ABCDERouterCarrier’s

equipmentLANH1Process

P1

PacketProcess

P1

H2

F1H3

面向連接服務(wù)的實(shí)現(xiàn)（虛電路子網(wǎng)）Process

P3C的路由表E的路由表2013-11-073

網(wǎng)絡(luò)流量控制3.1

流量控制的作用吞吐量

理想情況

有流控

無流控

死鎖

擁塞區(qū)吞吐量增大將發(fā)生擁塞?網(wǎng)絡(luò)資源包括網(wǎng)絡(luò)節(jié)點(diǎn)內(nèi)的信息緩沖

器、節(jié)點(diǎn)處理器、

輸入/輸出鏈路等。

?無限制的信息流進(jìn)

入網(wǎng)絡(luò)會(huì)導(dǎo)致?lián)砣?/p>

?當(dāng)報(bào)文在網(wǎng)絡(luò)中經(jīng)負(fù)載

歷了比所期望的時(shí)

延更長(zhǎng)的時(shí)間時(shí)，

就認(rèn)為網(wǎng)絡(luò)產(chǎn)生了

擁塞。

412013-11-0742造成網(wǎng)絡(luò)擁塞的因素緩沖器容量不夠從多個(gè)輸入端到達(dá)同一節(jié)點(diǎn)的分組要求同一條輸出鏈路時(shí)，就形成分組排隊(duì)。若緩沖器容量不夠，則造成分組丟失。在某種程度上增加緩沖器容量會(huì)有所幫助但有人研究發(fā)現(xiàn)，如果路由器增加為無限大的緩沖，擁塞會(huì)更嚴(yán)重，而不是緩解。因?yàn)楫?dāng)分組到達(dá)隊(duì)列的前面時(shí)，它已經(jīng)超時(shí)，一個(gè)重復(fù)的分組又重新進(jìn)入隊(duì)列，因而增加了到目的地所有線路的負(fù)載。處理器速度太低，或者鏈路帶寬不夠升級(jí)其中之一而非全部稍有好處，但往往只是把瓶頸轉(zhuǎn)移到系統(tǒng)中別的地方。事實(shí)上，問題往往是由于系統(tǒng)各部分之間的不平衡而造成的。2013-11-07432013-11-0744擁塞控制和流量控制的關(guān)系擁塞控制必須使得通信子網(wǎng)能夠傳送所有待傳送的數(shù)據(jù)，它是一個(gè)全局性的問題，涉及到所有主機(jī)、路由器、路由器中的存儲(chǔ)轉(zhuǎn)發(fā)處理的行為。流量控制是與某發(fā)送者和某接收者之間的點(diǎn)到點(diǎn)的業(yè)務(wù)量有關(guān)。它的任務(wù)是確保一個(gè)快速的發(fā)送者不能以比接收者能承受的速率更高的速度傳輸數(shù)據(jù)。簡(jiǎn)單的說，流量控制是防止網(wǎng)絡(luò)擁塞的一種機(jī)制。2013-11-07452013-11-0746流量控制的主要功能防止由于網(wǎng)絡(luò)和用戶過載而產(chǎn)生的吞吐量降低及響應(yīng)時(shí)間增長(zhǎng)避免死鎖在用戶之間合理分配資源網(wǎng)絡(luò)及其用戶之間的速率匹配要求n條鏈路的用戶：1單元/秒

n條鏈路，每條容量1單元/秒n個(gè)要求一條鏈路的用戶：1單元/秒鏈路資源的分配舉例47DTEDTEDCEDCE節(jié)點(diǎn)節(jié)點(diǎn)鏈路級(jí)入網(wǎng)級(jí)入網(wǎng)級(jí)3.2

流量控制所經(jīng)歷的層次

傳輸級(jí)

入口到出口級(jí)

虛電路級(jí)2013-11-07虛電路級(jí)

虛電路級(jí)五種不同級(jí)別的流量控制2013-11-0748流量控制和緩沖策略流量控制是發(fā)送方和接收方之間的傳輸速率上的匹配，為使沒有得到確認(rèn)的PDU在超時(shí)后的重發(fā)，通常必須在緩沖區(qū)中暫存在數(shù)據(jù)鏈路層，實(shí)現(xiàn)的是點(diǎn)對(duì)點(diǎn)的通信，雙方緩沖區(qū)的大小根據(jù)滑動(dòng)窗口協(xié)議而定而傳輸層實(shí)現(xiàn)的是端到端的通信，某一時(shí)刻，一臺(tái)主機(jī)可能同時(shí)與多臺(tái)主機(jī)建立了連接，多個(gè)連接必須有多組緩沖區(qū)，所以緩沖區(qū)的動(dòng)態(tài)分配和管理策略與數(shù)據(jù)鏈路層相比較要復(fù)雜得多49流量控制和緩沖策略舉例TPDU序號(hào)主機(jī)A消息主機(jī)B注釋123<請(qǐng)求8個(gè)緩沖區(qū)><ack=15,buf=4

><seq=0,data=m0>A想要8個(gè)緩沖區(qū)B只有4個(gè)緩沖區(qū)A發(fā)送了m0，A剩下3個(gè)緩沖區(qū)

4

5

6

7

8

9101112131415<seq=1,data=m1><seq=2,data=m2><ack=1,buf=3><seq=3,data=m3><seq=4,data=m4><seq=2,data=m2><ack=4,buf=0><ack=4,buf=1><ack=4,buf=2><seq=5,data=m5><seq=6,data=m6><ack=6,buf=0>A發(fā)送了m1，A剩下2個(gè)緩沖區(qū)A發(fā)送了m2，A剩下1個(gè)緩沖區(qū)B確認(rèn)了m0,m1，并剩下3個(gè)緩沖區(qū)A發(fā)送了m3，A剩下1個(gè)緩沖區(qū)A發(fā)送了m4后剩下0個(gè)緩沖區(qū)，暫停m2超時(shí)A重發(fā)m2，A剩下0個(gè)緩沖區(qū)B確認(rèn)了m4，并剩下0個(gè)緩沖區(qū)B確認(rèn)了m4，并剩下1個(gè)緩沖區(qū)B確認(rèn)了m4，B有了2個(gè)緩沖區(qū)A發(fā)送了m5，A剩下1個(gè)緩沖區(qū)A發(fā)送了m6后剩下0個(gè)緩沖區(qū)，暫停B確認(rèn)了m6，并剩下0個(gè)緩沖區(qū)

162013-11-07B確認(rèn)了m6，并剩下4個(gè)緩沖區(qū)B沒有收

到m2A沒有收

到ACK

可能導(dǎo)

致死鎖

表示上交了1個(gè)<ack=6,buf=4>

動(dòng)態(tài)緩沖區(qū)分配2013-11-07503.4

流量整形技術(shù)流量整形提供了一種機(jī)制來控制發(fā)送到網(wǎng)絡(luò)上的通信量的大小以及流量的發(fā)送速率?；谶@種理由，流量整形需要在網(wǎng)絡(luò)的邊沿實(shí)現(xiàn)以便控制進(jìn)入網(wǎng)絡(luò)的流量。流量整形存在兩種主要的算法：漏桶算法（leaky

bucket

algorithm）和令牌漏桶算法（token

bucket

algorithm）。與之相比，TCP滑動(dòng)窗口協(xié)議只是限制一次傳送數(shù)據(jù)的數(shù)量，而不是傳送的速率。2013-11-0751主機(jī)網(wǎng)未整形的流量漏桶算法的工作示意圖

包含漏桶的接口整形后的流量

絡(luò)

圖

6-22

漏桶算法這種策略相當(dāng)于將非平穩(wěn)的分組流變成了一個(gè)平穩(wěn)的分組流，從而平滑了數(shù)據(jù)分組的突發(fā)性。漏桶算法是網(wǎng)絡(luò)世界中流量整形或速率限制時(shí)經(jīng)常使用的一種算法，該算法首先由Turner(1986)提出來。令牌漏桶算法漏桶算法總是使輸出模式保持一個(gè)固定的平均速率，而不管突發(fā)業(yè)務(wù)流的大小。通常在應(yīng)用環(huán)境中，希望當(dāng)突發(fā)業(yè)務(wù)到來時(shí)，輸出可以相應(yīng)的加快一些，使得輸出業(yè)務(wù)流具有一定的突發(fā)性。因此對(duì)漏桶算法進(jìn)行改進(jìn)，提出了令牌漏桶算法。在令牌漏桶算法中，漏桶中保留的不是數(shù)據(jù)分組，而是令牌。系統(tǒng)每隔?T個(gè)時(shí)間單位產(chǎn)生一個(gè)令牌，送入漏桶中。當(dāng)漏桶滿時(shí)，產(chǎn)生的新令牌將被丟棄。對(duì)于數(shù)據(jù)分組來說，只有獲得了令牌才可以發(fā)送。當(dāng)有多個(gè)分組要發(fā)送，可以根據(jù)獲取的令牌數(shù)決定一次可發(fā)送的分組數(shù)，從而使漏桶的輸出具有一定的突發(fā)性。2013-11-0752b2013-11-0753輸入包輸出包令牌漏桶算法的概念模型

r

令牌數(shù)/秒

刪除令牌

圖

6-23

令牌漏桶算法的概念模型漏桶算法能夠強(qiáng)行限制數(shù)據(jù)的傳輸速率，而令牌漏桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時(shí)還允許某種程度的突發(fā)傳輸。4

網(wǎng)絡(luò)擁塞控制總的來說，網(wǎng)絡(luò)產(chǎn)生擁塞的原因是需求大于供給，也就是端系統(tǒng)提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源容量和處理能力，表現(xiàn)為數(shù)據(jù)報(bào)延時(shí)、丟棄概率增加、上層應(yīng)用性能下降等。通常產(chǎn)生擁塞的直接原因有以下三點(diǎn)：(1)存儲(chǔ)空間不足(2)帶寬容量不足(3)處理器處理速度慢2013-11-0754量絡(luò)網(wǎng)絡(luò)性能和網(wǎng)絡(luò)負(fù)載的關(guān)系當(dāng)網(wǎng)絡(luò)的負(fù)載較小時(shí)，吞吐量和負(fù)載呈線性關(guān)系；當(dāng)負(fù)載達(dá)到膝點(diǎn)（knee

point)之后，隨著負(fù)載的繼續(xù)增加，吞吐量的增量變化很小；當(dāng)負(fù)載超過了崖點(diǎn)（cliff

point)之后，吞吐量卻急劇下降。2013-11-0755網(wǎng)吞吐膝點(diǎn)

數(shù)據(jù)業(yè)務(wù)

分組丟失崖點(diǎn)語音、視頻業(yè)務(wù)分組丟

失

負(fù)載

圖6-28

網(wǎng)絡(luò)負(fù)載與吞吐量的關(guān)系曲線通常將膝點(diǎn)附近稱為擁塞避免區(qū)，膝點(diǎn)和崖點(diǎn)間的區(qū)域成為擁塞恢復(fù)區(qū)，而崖點(diǎn)之后的區(qū)域稱為擁塞崩潰區(qū)。輕度擁塞重度擁塞無擁塞2013-11-0756擁塞對(duì)延遲的影響無擁塞輕度擁塞嚴(yán)重?fù)砣麜r(shí)延

發(fā)送的分組儲(chǔ)存-轉(zhuǎn)發(fā)死鎖（Store-and-Forward

Deadlock）在最壞情況下，擁塞變得十分嚴(yán)重以致線路上沒有了通信。圖7

-

1

6說明了這個(gè)問題。A、B和C三個(gè)節(jié)點(diǎn)的緩沖區(qū)都滿了，不能再接受更多的分組。。換句話說，A等待B清空緩沖區(qū)，B等待C清空緩沖區(qū)，而C則等待A清空緩沖區(qū)。這種所有節(jié)點(diǎn)都等待一件不會(huì)發(fā)生的事件的情形，稱為死鎖（D

e

a

dl

o

c

k，也稱為死結(jié)或閉鎖）。

2013-11-07A的分組都是發(fā)往B的，而B由于緩沖區(qū)滿了而不能接收任何分組。這樣，

A要等到B發(fā)送掉一些分組，釋放出緩沖空間后，才能發(fā)送。B的分組是送往C的，而C的緩沖區(qū)也滿了。C的分組是送往A的，而A的緩沖區(qū)同樣客滿

57重裝死鎖（Reassembly

Deadlock）節(jié)點(diǎn)讓來自于不同源節(jié)點(diǎn)（

A和B）的輸入分組使用公共緩沖區(qū)。它還對(duì)從A和B來的輸入分組使用選擇性重傳的滑動(dòng)窗口協(xié)議進(jìn)行控制。然后，接收器在將它們發(fā)往主機(jī)前將它們重新裝配。

2013-11-07A和B都發(fā)送了它們的分組0，而且都還未到達(dá)。然而，A和B后續(xù)發(fā)送的分組1～3都到達(dá)了。假設(shè)，如果緩沖區(qū)已滿，節(jié)點(diǎn)無法接收更多的分組。由于兩邊都缺分組0，節(jié)點(diǎn)無法將它們重裝，從而無法將它們投送給主機(jī)。此外，即使分組0到達(dá)了，節(jié)點(diǎn)也不會(huì)接收它們。

582013-11-0759處理擁塞的控制方法（1）分組刪除(Packet

Elimination)如果一個(gè)節(jié)點(diǎn)上出現(xiàn)分組的過度聚集就丟棄其中一部分。這減少了等待傳輸?shù)姆纸M數(shù)量，降低了網(wǎng)絡(luò)的負(fù)荷。當(dāng)然，缺點(diǎn)是被丟棄的分組無法到達(dá)目的地。發(fā)送節(jié)點(diǎn)的協(xié)議最終會(huì)得知哪幾個(gè)分組沒有到達(dá)目的地并將它們重發(fā)。刪除分組的行為聽起來很激進(jìn)，但是如果擁塞只是零星的，網(wǎng)絡(luò)協(xié)議會(huì)妥善處理，只有一些運(yùn)氣不好的用戶的分組會(huì)受到最小限度的毀壞。2013-11-0760處理擁塞的控制方法（2）流量控制(Flow

Control)流量控制協(xié)議用來控制要發(fā)送的分組的數(shù)量。然而，這并不是一種真正的擁塞控制方法。問題在于，流量控制只限制了兩點(diǎn)間的分組數(shù)量，然而擁塞通常是由于來自多個(gè)源的分組涌入一個(gè)節(jié)點(diǎn)所造成。因此，即使節(jié)點(diǎn)控制了它們發(fā)送的分組數(shù)量，如果有太多節(jié)點(diǎn)發(fā)送分組，擁塞仍會(huì)出現(xiàn)。2013-11-0761處理擁塞的控制方法（3）緩沖分配(

Buffer

Allocation)

這種方法能用于虛電路技術(shù)中。虛電路是網(wǎng)絡(luò)節(jié)點(diǎn)間建立起的路徑，它在任何數(shù)據(jù)分組真正發(fā)送前被確定。一旦建立了路徑，那條路徑上的節(jié)點(diǎn)的協(xié)議會(huì)為此虛電路特別預(yù)留緩沖區(qū)。當(dāng)其他要建立虛電路的請(qǐng)求到達(dá)此節(jié)點(diǎn)，它在沒有緩沖區(qū)的情況下會(huì)拒絕申請(qǐng)。然后，網(wǎng)絡(luò)協(xié)議會(huì)為電路另辟蹊徑，或通知源節(jié)點(diǎn)虛電路申請(qǐng)被拒絕。2013-11-0762處理擁塞的控制方法（4）抑制分組(Choke

Packet)這種方法提供了一種更動(dòng)態(tài)的方式來處理擁塞。每個(gè)節(jié)點(diǎn)監(jiān)控它的輸出鏈路中的活動(dòng)，記錄每條鏈路的使用情況。如果線路的使用率低，則擁塞的危險(xiǎn)小。線路的使用率不斷增長(zhǎng)，則表示大量的分組正在被發(fā)送。如果任何一條鏈路的使用率超過某個(gè)特定的標(biāo)準(zhǔn)，節(jié)點(diǎn)協(xié)議就會(huì)使它自己進(jìn)入一種特殊的警告狀態(tài)。在警告狀態(tài)期間，節(jié)點(diǎn)會(huì)發(fā)送特殊的抑制分組來響應(yīng)任何要求以此超標(biāo)鏈路作為輸出的進(jìn)入分組。抑制分組會(huì)到達(dá)進(jìn)入分組的源節(jié)點(diǎn)。當(dāng)源節(jié)點(diǎn)收到抑制分組時(shí)，它就在一段時(shí)間內(nèi)減少它發(fā)送的分組的數(shù)量。2013-11-07632013-11-07642013-11-07652013-11-0766寬帶網(wǎng)絡(luò)中的擁塞控制機(jī)制開環(huán)擁塞控制閉環(huán)擁塞控制2013-11-0767

開環(huán)擁塞控制又稱預(yù)防式擁塞控制每個(gè)終端系統(tǒng)在申請(qǐng)帶寬時(shí)要提供相關(guān)的業(yè)務(wù)參數(shù)，如峰值速率(PCR)、信元時(shí)延的變化(CDV)、信元的維持速率(SCR)、突發(fā)容限(BT)等，網(wǎng)絡(luò)通過連接接納控制（CAC）算法及用法參數(shù)控制（UPC）來限制用戶的接納及保證用戶接納后的服務(wù)質(zhì)量（QoS）。一旦連接請(qǐng)求得到確認(rèn)，則在整個(gè)傳輸過程中其QoS得到保證，如缺少用戶要求的網(wǎng)絡(luò)資源，則連接請(qǐng)求遭到拒絕。主要優(yōu)點(diǎn)是控制算法性能的本身不受傳輸時(shí)延的影響，只要用戶對(duì)QoS提出明確的要求，通過CAC和UPC兩個(gè)階段就能有效地控制網(wǎng)絡(luò)的擁塞。缺陷是不能充分利用網(wǎng)絡(luò)的空閑帶寬，因而資源的利用率較低。2013-11-0768閉環(huán)擁塞控制閉環(huán)擁塞控制(反應(yīng)式(Reactive)或反饋式(Feedback)擁塞控制)工作原理是根據(jù)網(wǎng)絡(luò)中的反饋信息動(dòng)態(tài)地調(diào)整每個(gè)連接的信元發(fā)送速率，以提高帶寬的利用率并及時(shí)消除網(wǎng)絡(luò)擁塞。源算法和鏈路算法依據(jù)擁塞控制算法實(shí)現(xiàn)的位置不同，可以將擁塞控制算法分為源算法(Source

Algorithm)和鏈路算法(LinkAlgorithm)。源算法在主機(jī)和網(wǎng)絡(luò)邊緣設(shè)備中執(zhí)行，它的主要作用是根據(jù)反饋信息調(diào)整發(fā)送速率；鏈路算法在網(wǎng)絡(luò)內(nèi)部（如路由器和交換機(jī)）中執(zhí)行，它的主要作用是檢測(cè)網(wǎng)絡(luò)擁塞的發(fā)生，生成擁塞反饋信息。兩種類型的控制算法實(shí)際上互相補(bǔ)充，形成一個(gè)完整的擁塞控制系統(tǒng)。擁塞控制算法設(shè)計(jì)的關(guān)鍵問題是如何給出反饋信息和如何對(duì)反饋信息進(jìn)行響應(yīng)。2013-11-0769擁塞控制窗口2013-11-0770TCP/IP的擁塞控制機(jī)制TCP擁塞控制算法的例子0481216202440322416

8

0門限