擁塞控制算法第1頁，課件共40頁，創作于2023年2月一、擁塞控制

擁塞現象擁塞現象是指到達通信子網中某一部分的分組數量過多,使得該部分網絡來不及處理,以致引起這部分乃至整個網絡性能下降的現象,嚴重時甚至會導致網絡通信業務陷入停頓。

網絡吞吐量吞吐量是指在沒有幀丟失的情況下，設備能夠接受的最大速率。網絡的吞吐量與通信子網負荷(即通信子網中正在傳輸的分組數)有著密切的關系。第2頁，課件共40頁，創作于2023年2月擁塞現象的產生

當通信子網負荷比較小時,網絡的吞吐量隨網絡負荷的增加而線性增加。當網絡負荷增加到某一值后,若網絡吞吐量反而下降,則表征網絡中出現了擁塞現象。在一個出現擁塞現象的網絡中,到達某個節點的分組將會遇到無緩沖區可用的情況,從而使這些分組不得不由前一節點重傳,或者需要由源節點或源端系統重傳。當擁塞比較嚴重時,通信子網中相當多的傳輸能力和節點緩沖器都用于這種無謂的重傳,從而使通信子網的有效吞吐量下降。第3頁，課件共40頁，創作于2023年2月擁塞與死鎖提供的負載吞吐量理想的擁塞控制擁塞死鎖（吞吐量=0）無擁塞控制實際的擁塞控制輕度擁塞0(單位時間內輸入給網絡的分組數目)(單位時間內從網絡輸出的分組數目)第4頁，課件共40頁，創作于2023年2月區別流量控制只在一對給定的發送方和接收方之間，控制發送方不以超過接收方處理能力的速率發送數據。擁塞控制是一個全局性的過程，涉及到網絡中所有的主機、所有的路由器，以及與降低網絡傳輸性能有關的所有因素。聯系流量控制限制了進入網絡中的信息總量，可以在一定程度上減緩擁塞的作用。擁塞控制與流量控制區別聯系第5頁，課件共40頁，創作于2023年2月擁塞控制策略策略一：開環控制方法。重在預防，希望通過完美的設計來避免擁塞的發生需精心設計網絡的各個環節，盡可能減少不必要的數據重傳和避免數據過分集中在某個局部，同時還要嚴格控制進入子網的數據量以及數據流入的速度。策略二：閉環控制方法。重在解決，在擁塞發生后設法控制和緩解擁塞。需監視擁塞的發生，網絡中要定期收集一些性能參數，一旦參數值超過一定的門限，檢測到擁塞的結點立即通知有關結點，以便采取措施。第6頁，課件共40頁，創作于2023年2月通信量整形目標：迫使分組按照預定的速率進入網中漏桶算法基本思想：在主機和網絡之間接入一個“漏桶”。無論主機以多大的速率發送分組，“漏桶”中的分組總是以恒定的速率注入網中。如果主機發送過快，當“漏桶”滿了之后，多余的分組即被丟棄。優點：無論數據量有多大，數據總是以平均速率發送。缺點：漏桶滿后數據會丟失。第7頁，課件共40頁，創作于2023年2月漏桶模型說明綠色-未整形的流量紫色-整形后的流量紅色-丟失的分組第8頁，課件共40頁，創作于2023年2月漏桶的本質就是一個固定長度的分組隊列，主機發送的每一個分組都加入到隊列中排隊，如果隊列滿則分組被丟棄，同時隊列按照約定的速率向網絡發送分組。兩種情況：分組長度固定讓隊列每隔一個固定的時間發送一個分組。分組長度可變規定隊列每次可以發送的最大字節數。第9頁，課件共40頁，創作于2023年2月令牌桶算法漏桶算法的缺點：數據總以平均速率發送，突發數據到來時不能較快給予響應，有時還會丟失數據。希望能改進于是有令牌桶算法，特點：令牌桶中裝的不是分組而是令牌。桶中每隔Δt時間產生出一個令牌，當桶裝滿后，隨后產生的令牌就被丟棄。分組在桶外的緩沖區中等待發送，桶中有多少個令牌就允許發送多少個分組。(也可以規定：一個令牌表示允許發送k個字節)每個令牌用后即銷毀，當桶中沒有令牌時必須停止發送。第10頁，課件共40頁，創作于2023年2月令牌桶模型

說明

綠色-未整形的流量紫色-整形后的流量紅色-桶內令牌黃色-丟失的令牌特點允許主機在空閑時積累令牌，空閑時間越長令牌積累就越多，當有突發數據到來時，一次允許發送的數據量就大，可以較快地響應突發輸入。另外，當令牌桶裝滿時，丟棄令牌而不丟棄分組，因而不會造成數據丟失第11頁，課件共40頁，創作于2023年2月令牌桶算法

算法實現如一個令牌表示允許發送一個分組，令牌桶實際上就是一個令牌計數器。如一個令牌表示允許發送k

個字節，令牌桶實際上就是一個字節計數器。優點：丟棄令牌，但不會造成數據的丟失缺點：有時突發數據量仍較大改進措施：在令牌桶之后再加一個漏桶，并令漏桶的輸出速率大于令牌桶的ρ值但小于網絡的峰值速率。第12頁，課件共40頁，創作于2023年2月常見擁塞控制方法緩沖區預分配法

該法用于虛電路分組交換網中。在建立虛電路時,讓呼叫請求分組途經的節點為虛電路預先分配一個或多個數據緩沖區若某個節點緩沖器已被占滿,則呼叫請求分組另擇路由,或者返回一個"忙"信號給呼叫者。這樣,通過途經的各節點為每條虛電路開設的永久性緩沖區(直到虛電路拆除),就總能有空間來接納并轉送經過的分組分組丟棄法

該法不必預先保留緩沖區,當緩沖區占滿時,將到來的分組丟棄定額控制法

這種方法在通信子網中設置適當數量的稱做"許可證"的特殊信息,一部分許可證在通信子網開始工作前預先以某種策略分配給各個源節點,另一部分則在子網開始工作后在網中四處環游。當源節點要發送來自源端系統的分組時,它必須首先擁有許可證,并且每發送一個分組注銷一張許可證。目的節點方則每收到一個分組并將其遞交給目的端系統后,便生成一張許可證。這樣便可確保子網中分組數不會超過許可證的數量,從而防止了擁塞的發生第13頁，課件共40頁，創作于2023年2月二、基于的TCP擁塞控制算法由于TCP是目前Internet上應用廣泛的傳輸層協議因此下面介紹TCP基于窗口的端到端的擁塞控制機制

實施擁塞控制是TCP的兩個主要任務之一，由于IP層在發生擁塞時不向端系統提供任何顯式的反饋信息，因而TCP擁塞控制采用的是基于窗口的端到端的閉環控制方式。第14頁，課件共40頁，創作于2023年2月基本概念擁塞窗口(cwnd):擁塞控制的關鍵參數，控制源端在擁塞情況下一次最多能發送多少數據包。

通告窗口(awnd):接收端對源端發送窗口大小所做的限制，在建立連接時山接收方通過ACK確認帶給源端

慢啟動閥值(ssthresh):擁塞控制中用來限制發送窗口大小的門限值，它是慢啟動階段與擁塞避免階段的分界點，初始值設為65535bytes或awnd的大小。

回路響應時間(RTT):一個數據包從源端發送到接收端直至源端收到接收端R寸該數據包確認信息所經歷的時間間隔。

超時重傳計數器(RTO):描述數據包從發送到失效的時間間隔，是源端用來判斷數據報是否丟失和網絡擁塞的重要參數，通常設為2RTT或SRTT第15頁，課件共40頁，創作于2023年2月加法增加乘法減少(AIMD)窗口算法在現有的TCP/IP協議體系下，TCP擁塞控制機制主要基于加法增加乘法減少(AIMD)算法。由于計算機計算能力和存儲能力的提高，通告窗口一般都比較大，因此當前發送窗口的大小大多數情況下等于擁塞窗口的大小。第16頁，課件共40頁，創作于2023年2月AIMD的具體工作過程為：

(1)源端每收到一個ACK，擁塞窗口按下式增加：Incr＝MSS×(MSS/cwnd)(MSS為分組大小)cwnd＝cwnd＋Incr也就是如果每個發出的分組都在最近的RTT(往返時延)時間內獲得確認，源端就將cwnd增加1，即加法增加。(2)當發生超時，TCP將超時看作擁塞的標志，并減小發送速率。每發生一次超時，源端重新計算擁塞窗口值：cwnd＝cwnd/2也就是，一次超時，擁塞窗口值減為當前值的一半，即乘法減少。第17頁，課件共40頁，創作于2023年2月TCP擁塞控制的四個階段啟動階段擁塞避免階段快速重傳階段快速恢復階段第18頁，課件共40頁，創作于2023年2月1啟動階段

當連接剛建立或超時時，進入慢啟動階段。當新建TCP連接時，擁塞窗口(cwnd)被初始化為一個數據包大小(缺省為512或536bytes)。實際發送窗口win取擁塞窗口與接收方提供的通告窗口的較小值，即win=min(cwnd,awnd)，每收到一個ACK確認，就增加一個數據包發送量，這樣慢啟動階段cwnd隨RTT呈指數級增長(1個、2個、4個、8個…)第19頁，課件共40頁，創作于2023年2月優點：

慢啟動采用逐漸增大cwnd的方法，可以防止TCP在啟動一個連接時向網絡發送過多的數據包而造成不必要的數據丟失和網絡擁塞，并且它還能夠避免采用單純的AIMD算法造成的吞吐量增加過慢的問題為了防止cwnd的無限制增長引起網絡擁塞，引入一個狀態變量：慢啟動閾值ssthresh當cwnd<ssthresh時，使用上述的慢啟動算法，cwnd隨RTT呈指數增長。當cwnd>ssthresh時，使用下面的擁塞避免算法，減緩cwnd的增長速度。第20頁，課件共40頁，創作于2023年2月2擁塞避免階段當TCP源端發現超時或收到3個相同的ACK確認幀時，即認為網絡將發生擁塞，此時進入擁塞避免階段。在擁塞避免階段，慢啟動域值ssthresh將被設置為當前cwnd的一半，當發生超時時，cwnd被置為初始值1。此時，如果cwnd<ssthresh，TCP重新進入慢啟動過程；如果cwnd>=ssthresh，則執行擁塞避免算法，即cwnd在每次收到一個ACK確認時只增加1/cwnd個數據包。擁塞避免階段cwnd隨RTT呈線性增長。第21頁，課件共40頁，創作于2023年2月算法描述如下：初始化:cwnd=1ssthresh=65535byteswin=min(cwnd,awnd)

當新的ACK確認到達時，執行以下算法:foreveryarrivedpacketsifcwnd<ssthreshcwnd+=1；慢啟動elsecwnd+=SMSS*SMSS/cwnd;擁塞避免階段

當檢測到丟包時，發送方執行以下操作:ssthresh=max[min(cwnd/2,awin),2];

如果檢測到定時器超時，cwnd=1;其中SMSS是發送方的最大報文段長度.第22頁，課件共40頁，創作于2023年2月從以上算法看出：在擁塞避免階段，當數據包超時時，cwnd被置為1，重新進入慢啟動階段，這會導致過大地減小發送窗口尺寸，降低TCP連接的吞吐量。因此，引入了快速重傳和快速恢復機制。第23頁，課件共40頁，創作于2023年2月3快速重傳階段當網絡發生擁塞時，如果源端等待超時之后再進行擁塞控制，那么從出現擁塞到實施控制有一定的時延。除了超時之外，源端還可以使用重復ACK作為擁塞信號。源端在接收到重復ACK時并不能確定是由于分組丟失還是分組亂序產生的，通常假定如果是分組亂序，在目的端處理之前源端只可能收到一個或兩個重復的ACK;如果源端連續接收到三個或更多的重復ACK，表明網絡中某處已經發生了擁塞，這時，源端不等到重傳定時器超時就重發這個可能丟失的分組，這就是快速重傳算法。第24頁，課件共40頁，創作于2023年2月在快速重傳階段，當源端收到3個或3個以上重復的ACK時，就判定數據包丟失，同時ssthresh設置為當前cwnd的一半，并重傳丟失的包，進入快速恢復階段。第25頁，課件共40頁，創作于2023年2月4快速恢復階段當快速重傳算法重傳了可能丟失的分組之后，如果TCP重新進入慢啟動階段，將會使擁塞窗口減為1，重新開始探測網絡帶寬，從而嚴重影響網絡吞吐量，因此快速恢復算法在快速重傳之后轉去執行擁塞避免算法，避免了過大地減小發送窗口而導致的網絡性能下降。第26頁，課件共40頁，創作于2023年2月在快速恢復階段，每收到重復的ACK，則cwnd加1；收到非重復ACK時，置cwnd＝ssthresh，轉入擁塞避免階段；如果發生超時重傳，則置ssthresh為當前cwnd的一半，cwnd＝1，重新進入慢啟動階段。第27頁，課件共40頁，創作于2023年2月算法描述如下：step1:if(dupacks=3){ssthresh=max(2,cwnd/2);cwnd=ssthresh+3*segsize;}step2:重傳丟失的分組step3:此后每收到一個重復的ACK確認時cwnd=cwnd+1step4:當收到對新發送數據的ACK確認時，cwnd=ssthresh，這個ACK能夠對那些在丟失的分組之后，第一個重復ACK之前發送的所有包進行確認第28頁，課件共40頁，創作于2023年2月三、典型TCP擁塞控制算法

--Vegas算法分析Vegas算法以RTT的變化作為擁塞信號，調節源端的發送速率。如果發現RTT變大，Vegas就認為網絡發生擁塞，開始減小cwnd；如果RTT變小，Vegas則解除擁塞，再次增加cwnd。這樣，在理想情況下，cwnd值會穩定在一個合適的范圍內。Vegas的重傳策略與上述算法也不同，它是在收到一個重復ACK后，比較數據包發出的時間和當前時間，然后決定是否重發。這樣能更及時地重傳丟失的數據包，提高響應速度。該算法采用RTT的改變來判斷網絡的可用帶寬，能較好的預測網絡帶寬的使用情況，其公平性、效率都較好。第29頁，課件共40頁，創作于2023年2月TCPVegas中最重要的就是擁塞避免階段，擁塞避免階段主要是通過計算期望的吞吐量和實際的吞吐量之間的差值來決定如何改變發送窗口的大小，而期望的吞吐量與實際吞吐量之間的差值為:其中代表傳輸延時，也是當緩存中數據包為空時的RTT值(BaseRTT),cwnd代表源端在每個往返時間(RTT)中允許發送窗口的大小，期望的吞吐量為cwnd/T，設r代表實際網絡中的RTT，實際的吞吐量為cwnd/r第30頁，課件共40頁，創作于2023年2月由((3.1)式得到路由器緩存中的數據包個數為

…（1）

TCPVegas通過計算d值和兩個參數,之間的關系來改變窗口,,是兩個常數，一般取1和3。表明如果緩存中數據包數目保持在和之間，所以TCPVegas擁塞避免的目標就是要控制在路由器中的隊列長度第31頁，課件共40頁，創作于2023年2月使用圖的網絡拓撲模型，即是由n個源端和n個目的端通過一段由兩個路由器之間的鏈路而組成，由于源端的發送窗口在每個 RRT只會變化一次，所以網絡模型可以看成是離散的，采樣時間是RRT，需要說明的是，RTT是隨著網絡情況的變化而變化的，不是一個固定的值第32頁，課件共40頁，創作于2023年2月假定各個連接的RTT都是相同的。用cwnd.(k)(1<_m<_n)代表第m個源端在第k個RTTT時間段時窗口的大小，意味著在第k個KIT時間段中，源端能發送cwnd}}(k)大小的數據，r(k)代表第k個時間段的RTT，用q(k)代表在第k個時間段時路由器緩存中數據包的數量，用B表示路由器緩存的大小。所有的路由器都使用FIFO先進先出的隊列管理算法，用L表示瓶頸鏈路處理數據的速度第33頁，課件共40頁，創作于2023年2月這樣在k+l個RTT時間段時的隊列長度q(k+I)可表示為由（1）式變換為表示的是在第k個RTT時間段時路由器緩存中數據包的數量。第34頁，課件共40頁，創作于2023年2月TCPVegas線性增大或減小窗口是基于d(k)的大小，d(k)代表數據包在路由器中的數量，當d(k)小于時，說明網絡資源還沒有充分利用，需要進一步的增大發送窗口，當d(k)大于時，則減小發送窗口，防止發生擁塞。如果在,之間，則窗口不變。可用下面的公式來說明:第35頁，課件共40頁，創作于2023年2月TCPTahoe算法Tahoe算法是TCP的早期版本。它的核心思想是：讓cwnd以指數增長方式迅速逼進可用信道容量，然后慢慢接近均衡。Tahoe包括3個基本的擁塞控制算法：“慢啟動”、“擁塞避免”和“快速重傳”。(1)慢啟動：避免了連接建立時突發數據流對網絡的沖擊。初始設置cwnd為1，并按指數型方式增長，直至cwnd超過