擁塞控制

出自 MBA智库百科(https://wiki.mbalib.com/)

　　擁塞控制是一種用來調整傳輸控制協議（TCP）連接單次發送的分組數量（單次發送量，在英文文獻和程式代碼中常叫做cwnd）的演算法。它通過增減單次發送量逐步調整，使之逼近當前網路的承載量。如果單次發送量為1，此協議就退化為停等協議。單次發送量是以位元組來做單位的；但是如果假設TCP每次傳輸都是按照最大報文段來發送數據的，那麼也可以把數據包個數當作單次發送量的單位，所以有時我們說單次發送量增加1也就是增加相當於1個最大報文段的位元組數。

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

　　擁塞控制假設分組的丟失都是由網路繁忙造成的。擁塞控制有三種動作，分別對應主機感受到的情況：

　　1.收到一條新確認。這很好，表明當前的單次發送量小於網路的承載量。

　　2.收到三條對同一分組的確認，即三條重覆的確認。單次發送量往往大於3，例如發送序號為0、10、20、30、40的5條長度為10位元組的分組，其中序號20的丟了，則返回的確認是10、20、20、20。3個20就是重覆的確認。

　　3.對某一條分組的確認遲遲未到，即超時。例如發送序號為0、10、20、30、40的5條長度為10位元組的分組，其中序號30的丟了，則返回的確認是10、20、30、30。這才只有兩條重覆確認。然而剛剛說過，單次發送量往往大於3，所以超時更可能是因為不止一條分組或確認丟失而引起的，這說明網路比上一情況中的更加繁忙。

　　當主機收到一條新確認，此時可以增加單次發送量。若當前單次發送量小於倍增閥限（在英文文獻和程式代碼中常叫做ssthresh），則單次發送量加倍（乘以2），即指數增長；否則單次發送量加1，即線性增長。

　　當主機收到三條重覆的確認——單次發送量減半，倍增閥限等於單次發送量。（進入線性增長期）

　　當主機探測到超時——倍增閥限=單次發送量÷2，單次發送量=1。

　　1.TCP的擁塞控制

　　TCP是Internet上通用的傳輸層協議之一，是目前應用最廣泛的傳輸控制協議，其核心是擁塞控制機制。基於Internet的交換機的通信通道、處理速度及緩衝存儲空間通常是網上所有主機共用的資源，也是網路系統潛在的瓶頸。隨著信源主機數以及信源業務端業務量的不斷增多，瓶頸處就有可能發生資源競爭，從而導致網路擁塞。TCP的一個重要組成部分是執行擁塞控制和擁塞恢復的演算法集合。TCP擁塞控制演算法的目標是最大限度利用網路帶寬，同時不產生數據流傳輸中的擁塞現象。因此，自從上個世紀80年代出現第一次擁塞崩潰以來，TCP擁塞控制策略就在不斷地進行完善和改進。

　　2.傳統的TCP擁塞控制機制

　　傳統的TCP中的擁塞控制機制主要是基於VanJacobson提出的"慢啟動"演算法、"擁塞避免"演算法和一個用於估計周轉RTT(roundtriptime)的演算法。

　　慢啟動演算法通過觀察到新分組進入網路的速率應該與另一端返回確認的速率相同而進行工作。慢啟動為發送方的TCP增加了另一個視窗：擁塞視窗(congestionwindow)，記為cwnd。當與另一個網路的主機建立TCP連接時，擁塞視窗被初始化為1個報文段（即另一端通告的報文段大小）。每收到一個ACK，擁塞視窗就增加一個報文段（cwnd以位元組為單位，但是慢啟動以報文段大小為單位進行增加）。發送方取擁塞視窗與通告視窗中的最小值作為發送上限。擁塞視窗是發送方使用的流量控制，而通告視窗則是接收方使用的流量控制。發送方開始時發送一個報文段，然後等待ACK。當收到該ACK時，擁塞視窗從1增加為2，即可以發送兩個報文段。當收到這兩個報文段的ACK時，擁塞視窗就增加為4，這是一種指數增加的關係。在某些點上可能達到了互聯網的容量，於是中間路由器開始丟棄分組。擁塞避免演算法是一種處理丟失分組的方法。該演算法假定由於分組受到損壞引起的丟失是非常少的（遠小於1%），因此分組丟失就意味著在源主機和目的主機之間的某處網路上發生了擁塞。有兩種分組丟失的指示：發生超時和接收到重覆的確認。擁塞避免演算法和慢啟動演算法是兩個目的不同、獨立的演算法。但是當擁塞發生時，我們希望降低分組進入網路的傳輸速率，於是可以調用慢啟動來作到這一點。在實際中這兩個演算法通常在一起實現。1990年出現的TCPReno版本增加了"快速重傳"演算法、"快速恢復"演算法，避免了當網路擁塞不夠嚴重時採用"慢啟動"演算法而造成過大地減小發送視窗尺寸的現象。

　　3.擁塞控制的四個階段

　　a．慢啟動階段(slowstart)：發送方一開始便向網路發送多個報文段，直至達到接收方通告的視窗大小為止。當發送方和接收方處於同一個區域網時，這種方式是可以的。但是如果在發送方和接收方之間存在多個路由器和速率較慢的鏈路時，就有可能出現一些問題。一些中間路由器必須緩存分組，並有可能耗盡存儲器的空間。

　　b．擁塞避免階段（congestionavoidance）：當發現超時或收到3個相同ACK確認幀時，則表示有丟包事件，此時網路已發生擁塞現象，此時要進行相應的擁塞控制。將慢啟動閾值設置為當前擁塞視窗的一半；如檢測到超時，擁塞視窗就被置為l。如果擁塞視窗小於或等於慢啟動閾值，TCP重新進人慢啟動階段；如果擁塞視窗大於慢啟動閾值，TCP執行擁塞避免演算法。

　　c．快速重傳階段(fastretransmit)：當TCP源端收到到三個相同的ACK副本時，即認為有數據包丟失，則源端重傳丟失的數據包，而不必等待RTO超時。同時將ssthresh設置為當前cwnd值的一半，並且將cwnd減為原先的一半。

　　d．快速恢復階段(fastrecovery)：當"舊"數據包離開網路後，才能發送"新"數據包進入網路，即同一時刻在網路中傳輸的數據包數量是恆定的。如果發送方收到一個重覆的ACK，則認為已經有一個數據包離開了網路，於是將擁塞視窗加1。

　　4.對傳統TCP擁塞控制機制的發展及改進

　　(1)對慢啟動的改進　　

　　慢啟動(slowstart)演算法通過逐漸增加cwnd的大小來探測可用的網路容量，防止連接開始時採用不合適的發送量導致網路擁塞。然而有時該演算法也會浪費可用的網路容量，因為慢啟動演算法總是從cwnd＝l開始，每收到一個ACK，cwnd增加l，對RTT時間長的網路，為使cwnd達到一個合適的值，需要花很長的時間，特別是網路實際容量很大時，會造成浪費。為此可採用大的初始視窗，大的初始視窗避免了延遲ACK機制下單個報文段初始視窗的等待超時問題，縮短了小TCP流的傳輸時間和大延遲鏈路上的慢啟動時間。

　　在慢啟動階段，在每個RTT時間內，cwnd增加一倍，這樣當cwnd增加到一定的值時，就可能導致以網路能夠處理的最大容量的2倍來發送數據，從而淹沒網路。Hoe建議使用packet-pair演算法和測量RTT來為ssthresh估計合適值，以此來適時地結束慢啟動階段。但是由於受各方面干擾，估算合理的ssthresh值並不容易，因此這個方法的效果是有限的。而Smooth-start較為平滑地從慢啟動過渡到擁塞避免階段，減少了報文段丟失和突發通訊量，提高了TCP擁塞控制的性能。

　　(2)對重傳與恢復的改進

　　為了避免不必要的重傳超時，有人提出了一種受限傳輸機制：如果接收方的廣播視窗允許的話，發送方接收到一個或者兩個重覆的ACK(acknowledgment)後，繼續傳輸新的數據報文段。受限的傳輸機制允許具有較小視窗的TCP連接進行錯誤恢復，而且避免了不必要的重傳。

　　有很多情況下，數據報文段並沒有丟失，但TCP發送方可能會誤判數據報文段丟失，然後調用擁塞控制規程減少擁塞視窗的大小。比如當重傳定時器過早溢出時，發送方在重傳數據報文段時不必要地減少了擁塞視窗，而這時並沒有數據報文段丟失。如果是由於數據報文段的重新組織而不是數據報文段丟失，而導致3個重覆的確認，同樣會導致發送方不必要地在快速重傳數據報文段後減少擁塞視窗。

　　如果TCP的發送方在重傳數據報文段一個RTT後發現接收方接收到了重傳數據報文段的兩個拷貝，則可以推斷重傳是不必要的。這時，TCP的發送方可以撤銷對擁塞視窗的減少。發送方可以通過將慢啟動門限增加到原始值，調用慢啟動規程使擁塞視窗恢複原先值。除了恢復擁塞視窗，TCP發送方還可以調整重覆確認門限或者重傳超時參數來避免由於多次不必要的重傳而浪費帶寬。

　　(3)對公平性的改進

　　在擁塞避免階段，如果沒有發生丟包事件，則TCP發送方的cwnd在每個RTT時間內大約可以增加一個報文段大小，但這樣會造成具有不同RTT時間或視窗尺寸的多個連接在瓶頸處對帶寬競爭的不公平性，RTT時間或視窗小的連接，相應的cwnd增長速度也相對緩慢，所以只能得到很小一部分帶寬。

　　要解決上述問題，可以通過在路由器處使用公平隊列和TCP友好緩存管理來進行控制以增加公平性。然而如沒有路由器的參與，要增加公平性，就要求TCP發送端的擁塞控制進行相應的改變，在擁塞避免階段使共用同一資源的各個TCP連接以相同速度發送數據，從而確保了各個連接間的公平性。