2013-11-071路由選擇與網絡擁塞控制本章掌握重點：

網絡層的主要功能和提供的服務；

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

概述ISO

定義網絡層為一個網絡連接的兩個傳輸層實體間交換網絡服務數據單元提供功能和規程的方法，它使傳輸層實體看不到下面資源的使用情況。網絡層是處理端到端傳輸的最低層。網絡層要解決的關鍵問題:了解通信子網的拓撲結構，選擇路由;另一個需要解決的問題是網絡的擁塞控制.2013-11-073概述1.1

網絡層的任務(1)通信子網的拓撲結構(2)路由選擇方法(3)流量和擁塞控制(4)網絡互連OSI標準集中于網絡層提供給傳輸層的功能和服務，以及網絡層與傳輸層及數據鏈路層的接口。2013-11-074網絡層概述1.2

向傳輸層提供的服務面向連接的服務:將復雜的功能放在網絡層(通信子網)

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

N_Response時間

2013-11-07N_Confirm

OSI網絡層服務原語的使用示例2013-11-078

階段連接建立數據傳輸連接拆除

服務連接建立

原語N_Connect.RequestN_Connect.IndicationN_Connect.ResponseN_Connect.Confirm可選服務接收確認

加速數據

傳輸

原語N_DataAcknowledge.RequestN_DataAcknowledge.IndicationN_ExpeditedData.RequestN_ExpeditedData.Indication數據傳輸重

建連接釋放

N_Data.Request

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

表6-1

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

網絡層的內部結構2013-11-0713網絡層概述虛電路（virtual

circuit）在發送第一個數據包之前要進行連接的建立,一般等待時間為RTT.

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

很小的VC標識,因此每個包的開銷很小.

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

立一個新的連接.

連接建立為預留資源提供了支持.數據報（datagram）沒有連接建立階段每個包包含完整的目的地址每個包獨立地被轉發轉發表由路由協議動態生成2013-11-0714服務與子網類型不同組合2013-11-0715小結網絡層的地位位于數據鏈路層和傳輸層之間，使用數據鏈路層提供的服務，為傳輸層提供服務；通信子網的最高層；處理端到端傳輸的最低層。網絡層的作用屏蔽各種不同類型網絡之間的差異，實現互連了解通信子網的拓撲結構，選擇路由，實現報文的網絡傳輸網絡層的兩種實現方式

——

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

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

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

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

路由選擇與流量控制的關系

時延

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

路由選擇算法的分類

分類決策地點決策時間性能準則網絡信息源（與路由選擇有關的信息）路選策略

2013-11-07

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

對路由選擇算法的要求

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

簡單性:實現方便，軟硬件開銷小；

自適應性,也稱健壯性:算法能夠適應業務量和網

絡拓撲的變化

穩定性:能長時間無故障運行;

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

最優性:盡量選取"好的"路由4.

路由選擇的實現——路由表節點1上的路由表節點4上的路由表目的節點23456目的節點356下一個節點22442下一個節點355路由算法路由選擇的實現-路由表

2

3

1

6

4

5

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

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

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

tree）

從所有的源節點到一個給定的目的節點的最優路由的集

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

簡單路由選擇算法1.

隨機路由選擇2.

洪泛式路由選擇3.

固定式路由選擇絕對固定式路由選擇迂回式路由選擇2013-11-0724靜態路由算法

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

個出口轉發出去。缺點也是十分明顯的，可能造

成某些分組長期在通信子網中轉，到達不了目的

節點。

洪泛算法（Flooding）:

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

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

外的所有輸出線路發送。

主要問題:洪泛要產生大量重復包。

解決措施:每個包頭包含站點計數器，每經過一站計數

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

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

73

532863

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

擴散法（續）解決方法

在數據包頭設一計數器初值，每經過一個節

點自動減1，計數值為0

時，丟棄該數據包

在每個節點上建立登記表，則數據包再次經

過時丟棄

缺點：重復數據包多，浪費帶寬

優點：可靠性高，路徑最短，常用于軍事2013-11-0727靜態路由算法

固定式路由選擇

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

計算得到的固定路由表，它給出了子網中每個節點作為目的節點

時，分組對應的轉發出口的對應關系。每收到一個分組，去查表

中目的節點，找出相應的轉發出口。優點是簡單、實現方便，可

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

適應網絡的業務量及拓撲變化。

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

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

大，就可以選擇第二、第三條路由。實現方法是每個節點裝有一

張路由表，對應每個目的節點，給出最佳、次佳、再次佳……的

后繼節點和權數。缺點是路由表不能聯機修改。2013-11-07282.3

動態路由選擇自適應路由選擇方法是從路徑和時延兩方面考慮的1.

孤立的自適應路由算法2.

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

（“熱土豆”法）最短排隊加偏法考慮了本節點排隊狀態和網絡拓撲兩種因素2013-11-0730一般，孤立法路由選擇要求節點必須具備：1.2.3.4.一張預置于本節點的固定式路由表；本節點各輸出鏈路的目前狀態（通或斷）；本節點等待發送的各鏈路排隊長度；進行路由運算的選路程序。2013-11-0731······輸出隊列節點

N

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

·NPL網采用的分叉路由選擇法

第一路徑（權3）B類第二路徑（權1）圖6-12

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

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

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

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

所謂節點即路由器

當前節點為JEAIHDLC

GKBFJD-V算法的路由表更新狀態鏈路路由算法鏈路狀態（link

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

由表2013-11-07ABCDERouterCarrier’s

equipmentLANH1Process

P1

PacketProcess

P1

H2

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

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

equipmentLANH1Process

P1

PacketProcess

P1

H2

F1H3

面向連接服務的實現（虛電路子網）Process

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

網絡流量控制3.1

流量控制的作用吞吐量

理想情況

有流控

無流控

死鎖

擁塞區吞吐量增大將發生擁塞?網絡資源包括網絡節點內的信息緩沖

器、節點處理器、

輸入/輸出鏈路等。

?無限制的信息流進

入網絡會導致擁塞。

?當報文在網絡中經負載

歷了比所期望的時

延更長的時間時，

就認為網絡產生了

擁塞。

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

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

流量控制所經歷的層次

傳輸級

入口到出口級

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

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

><seq=0,data=m0>A想要8個緩沖區B只有4個緩沖區A發送了m0，A剩下3個緩沖區

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發送了m1，A剩下2個緩沖區A發送了m2，A剩下1個緩沖區B確認了m0,m1，并剩下3個緩沖區A發送了m3，A剩下1個緩沖區A發送了m4后剩下0個緩沖區，暫停m2超時A重發m2，A剩下0個緩沖區B確認了m4，并剩下0個緩沖區B確認了m4，并剩下1個緩沖區B確認了m4，B有了2個緩沖區A發送了m5，A剩下1個緩沖區A發送了m6后剩下0個緩沖區，暫停B確認了m6，并剩下0個緩沖區

162013-11-07B確認了m6，并剩下4個緩沖區B沒有收

到m2A沒有收

到ACK

可能導

致死鎖

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

動態緩沖區分配2013-11-07503.4

流量整形技術流量整形提供了一種機制來控制發送到網絡上的通信量的大小以及流量的發送速率。基于這種理由，流量整形需要在網絡的邊沿實現以便控制進入網絡的流量。流量整形存在兩種主要的算法：漏桶算法（leaky

bucket

algorithm）和令牌漏桶算法（token

bucket

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

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

絡

圖

6-22

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

r

令牌數/秒

刪除令牌

圖

6-23

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

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

point)之后，隨著負載的繼續增加，吞吐量的增量變化很小；當負載超過了崖點（cliff

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

數據業務

分組丟失崖點語音、視頻業務分組丟

失

負載

圖6-28

網絡負載與吞吐量的關系曲線通常將膝點附近稱為擁塞避免區，膝點和崖點間的區域成為擁塞恢復區，而崖點之后的區域稱為擁塞崩潰區。輕度擁塞重度擁塞無擁塞2013-11-0756擁塞對延遲的影響無擁塞輕度擁塞嚴重擁塞時延

發送的分組儲存-轉發死鎖（Store-and-Forward

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

-

1

6說明了這個問題。A、B和C三個節點的緩沖區都滿了，不能再接受更多的分組。。換句話說，A等待B清空緩沖區，B等待C清空緩沖區，而C則等待A清空緩沖區。這種所有節點都等待一件不會發生的事件的情形，稱為死鎖（D

e

a

dl

o

c

k，也稱為死結或閉鎖）。

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

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

57重裝死鎖（Reassembly

Deadlock）節點讓來自于不同源節點（

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

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

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

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

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

Buffer

Allocation)

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

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

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

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

8

0門限