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

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

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

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

概述ISO

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

N_Response時間

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ù)不提供差錯控制，也不提供流量控制、分組重新排序及其它的控制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，原因)建連時延建立網(wǎng)絡(luò)連接所需要的時間建連失敗概率建立網(wǎng)絡(luò)連接失敗次數(shù)與嘗試次數(shù)之比吞吐量單位時間內(nèi)傳送的數(shù)據(jù)量轉(zhuǎn)換時延從發(fā)送請求原語至目的端，到接收指示原語所需要的時間殘留誤差率通過網(wǎng)絡(luò)服務(wù)邊界仍有出錯、丟失、重復(fù)數(shù)據(jù)占傳送數(shù)據(jù)總數(shù)的比例傳送失敗概率傳送失敗數(shù)占傳送嘗試總數(shù)的比例連接恢復(fù)力在網(wǎng)絡(luò)連接過程中，服務(wù)提供者激活釋放和復(fù)位的概率拆連時延從發(fā)起連接拆除請求至成功釋放所需要的時間拆連失敗概率未成功拆除連接次數(shù)與嘗試次數(shù)之比連接保護能力網(wǎng)絡(luò)服務(wù)提供者試圖防止對用戶數(shù)據(jù)的未授權(quán)操作的程度連接優(yōu)先權(quán)考慮網(wǎng)絡(luò)連接及其數(shù)據(jù)的相對重要性最大開銷網(wǎng)絡(luò)服務(wù)的開銷范圍2013-11-0710面向連接的服務(wù)質(zhì)量轉(zhuǎn)換時延從發(fā)出N_Unitdata請求至響應(yīng)所需要的時間接入保護防止對網(wǎng)絡(luò)服務(wù)用戶信息的非法監(jiān)測和操縱開銷決定性因素確定對數(shù)據(jù)選擇路由所需要的開銷殘留誤差率某數(shù)據(jù)單元發(fā)生丟失、重復(fù)或誤傳的可能性優(yōu)先權(quán)數(shù)據(jù)單元之間的相對重要性源路由指定數(shù)據(jù)傳向目的地的路徑2013-11-0711無連接的服務(wù)質(zhì)量比較項目數(shù)據(jù)報子網(wǎng)虛電路子網(wǎng)初始建立連接不需要需要地址每個分組都含有完整的源地址和目的地址每個分組含有一個短的虛電路號，目的站地址僅在連接建立階段使用狀態(tài)信息子網(wǎng)不存儲狀態(tài)信息已建立的虛電路占用子網(wǎng)路由表空間路由選擇每個分組獨立選擇虛電路一建立，路由就已確定，所有分組都經(jīng)過此路徑分組的順序到達目的站時可能不按發(fā)送順序總是按發(fā)送順序到達目的站節(jié)點故障影響除節(jié)點崩潰時會丟失分組外，無其他影響所有經(jīng)過失效設(shè)備的虛電路都會被終止差錯處理由主機承擔(dān)對主機透明（由通信子網(wǎng)承擔(dān)）擁塞控制由主機負(fù)責(zé)，較難實現(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ā)送第一個數(shù)據(jù)包之前要進行連接的建立,一般等待時間為RTT.

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

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

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

立一個新的連接.

連接建立為預(yù)留資源提供了支持.數(shù)據(jù)報（datagram）沒有連接建立階段每個包包含完整的目的地址每個包獨立地被轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)表由路由協(xié)議動態(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ǎng)絡(luò)層的作用屏蔽各種不同類型網(wǎng)絡(luò)之間的差異，實現(xiàn)互連了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，選擇路由，實現(xiàn)報文的網(wǎng)絡(luò)傳輸網(wǎng)絡(luò)層的兩種實現(xiàn)方式

——

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

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

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

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

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

時延

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

路由選擇算法的分類

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

2013-11-07

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

對路由選擇算法的要求

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

簡單性:實現(xiàn)方便，軟硬件開銷??；

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

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

穩(wěn)定性:能長時間無故障運行;

公平性:每個節(jié)點都有機會傳送信息;

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

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

2

3

1

6

4

5

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

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

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

tree）

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

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

簡單路由選擇算法1.

隨機路由選擇2.

洪泛式路由選擇3.

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

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

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

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

節(jié)點。

洪泛算法（Flooding）:

又分為完全擴散和選擇擴散兩種

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

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

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

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

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

擴散法（flooding）不計算路徑，有路就走1542911

73

532863

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

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

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

點自動減1，計數(shù)值為0

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

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

過時丟棄

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

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

固定式路由選擇

固定式單路由算法(絕對固定式路由選擇):每個節(jié)點都有一張人工

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)鏈路路由算法特點是：在網(wǎng)絡(luò)相鄰節(jié)點之間，每經(jīng)過一定時間相互交換一次狀態(tài)信息，各節(jié)點根據(jù)相鄰節(jié)點送來的狀態(tài)信息來修改自己的路由表。雖然每次修改只能反映相鄰節(jié)點的狀態(tài)變化，但是經(jīng)過n次修改即可反映出第n級相鄰節(jié)點的狀態(tài)改變。所以分布式路由選擇可以適應(yīng)整個網(wǎng)絡(luò)的狀態(tài)變化，只是附近節(jié)點處的狀態(tài)較快得到反映，遠(yuǎn)處節(jié)點的狀態(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最短路徑的含義最短路徑問題是圖論中的一個經(jīng)典問題，是指在一個帶權(quán)圖的兩個頂點之間找出一條具有最小權(quán)的路徑。路徑度量的一種方法是計算站點數(shù)量或經(jīng)過的鏈路條數(shù)。另一種度量是以公里為單位的地理距離，路徑的權(quán)重是長度。在大多數(shù)情況下，鏈路的度量可以是距離、信道帶寬、平均業(yè)務(wù)量、通信費用、隊列平均長度、測量的時延和其它一些因素的函數(shù)而計算出來。2013-11-0734最短路徑的一般性質(zhì)a.

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

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

Vector）算法的基本工作原理是每個路由器維護一張矢量表，表中列出了到每個目的地已知的最佳距離和路徑。通過在相鄰路由器之間交換信息來更新表的信息。2013-11-0736To通過A通過I通過H通過KA0242021B12363128C25181936D4027824E1473022F23201940G1831631H1720019I2101422J911710K2422220L293399J到A延時為8J到I延時為10J到H延時為12J到K延時為6線路8A20A28I20H17I30I18H12H10I0-6K15K節(jié)點J的新路由表2013-11-0737J重新估計的延時注意：AI為21；IA為24因為：往和返的信道流量不一定相同，節(jié)點A和I也并非在同一時刻測得，且線路狀態(tài)是動態(tài)變化的

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

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

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

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

由表2013-11-07ABCDERouterCarrier’s

equipmentLANH1Process

P1

PacketProcess

P1

H2

F1A的路由表E的路由表C的路由表數(shù)據(jù)報子網(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ù)的實現(xiàn)（虛電路子網(wǎng)）Process

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

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

流量控制的作用吞吐量

理想情況

有流控

無流控

死鎖

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

器、節(jié)點處理器、

輸入/輸出鏈路等。

?無限制的信息流進

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

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

歷了比所期望的時

延更長的時間時，

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

擁塞。

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

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

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

傳輸級

入口到出口級

虛電路級2013-11-07虛電路級

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

><seq=0,data=m0>A想要8個緩沖區(qū)B只有4個緩沖區(qū)A發(fā)送了m0，A剩下3個緩沖區(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個緩沖區(qū)A發(fā)送了m2，A剩下1個緩沖區(qū)B確認(rèn)了m0,m1，并剩下3個緩沖區(qū)A發(fā)送了m3，A剩下1個緩沖區(qū)A發(fā)送了m4后剩下0個緩沖區(qū)，暫停m2超時A重發(fā)m2，A剩下0個緩沖區(qū)B確認(rèn)了m4，并剩下0個緩沖區(qū)B確認(rèn)了m4，并剩下1個緩沖區(qū)B確認(rèn)了m4，B有了2個緩沖區(qū)A發(fā)送了m5，A剩下1個緩沖區(qū)A發(fā)送了m6后剩下0個緩沖區(qū)，暫停B確認(rèn)了m6，并剩下0個緩沖區(qū)

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

到m2A沒有收

到ACK

可能導(dǎo)

致死鎖

表示上交了1個<ack=6,buf=4>

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

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

bucket

algorithm）和令牌漏桶算法（token

bucket

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

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

絡(luò)

圖

6-22

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

r

令牌數(shù)/秒

刪除令牌

圖

6-23

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

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

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

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

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

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

失

負(fù)載

圖6-28

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

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

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

-

1

6說明了這個問題。A、B和C三個節(jié)點的緩沖區(qū)都滿了，不能再接受更多的分組。。換句話說，A等待B清空緩沖區(qū)，B等待C清空緩沖區(qū)，而C則等待A清空緩沖區(qū)。這種所有節(jié)點都等待一件不會發(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é)點讓來自于不同源節(jié)點（

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

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

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

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

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

Buffer

Allocation)

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

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

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

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

8

0門限