ＴＣＰ擁塞控制與算法概述

[摘要]隨著Internet廣泛應用,擁塞控制技術已成為網絡研究熱點之一,描述Internt端到端產生擁塞的基本原因,重點闡述TCP擁塞控制策略和擁塞控制四種算法的性能及應用,進一步分析TCP擁塞控制技術最新研究成果及方向。

[關鍵詞]Internet TCP協議 擁塞控制 算法

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0810062-02

隨著Internet廣泛應用,用戶對網絡服務質量要求更高,同時越來越嚴重的網絡擁塞問題引起廣泛關注。當前人們對Internet擁塞控制理論研究主要集中在2個方面:首先是在Internet的端系統(或源系統),本質上是一種基于信源的擁塞控制策略;其次是在Internet的中間鏈路節點系統,本質上是一種基于路由器等網絡中間鏈路節點的擁塞控制策略。Internet系統的可靠性、魯捧性越來越依賴于擁塞控制機制,由于當前網絡擁塞控制的大部分工作是由TCP協議完成的。因此,分析和研究更有效的TCP擁塞控制策略及算法具有重要的意義。

一、擁塞控制基本概念

許多學者和網絡專家認為網絡擁塞現象產生的根本原因或判斷標準是用戶(或叫源系統)提供給網絡的負載(Load)超過網絡系統資源容量和處理能力(Overload)[1][17],直接表現為數據包延時增加、丟棄概率增大、吞吐量(goodput)急劇下降、上層應用系統性能下降,甚至導致網絡崩潰(congestioncollapse)的發生。目前公認比較權威的“擁塞”解析是由Jacobson(1988)[2]提出:當一個子網或者子網的一部分出現太多分組的時候,網絡性能開始下降,這種情況稱為擁塞(congestion)。文獻[3][4][5]比較一致形象描述了網絡擁塞情況,如圖(1):當源系統(用戶)發送的數據分組總量小于系統容量范圍的時候,所有分組可以被遞交,也就是理想的范圍。當源系統(用戶)發送的數據分組總量超過系統容量范圍的時候,擁塞就開始出現,分組開始丟失率增大、延時加大、網絡性能隨分組數量增大急速下降,甚至整個系統發生崩潰。[6]

Meom C(2000)提出網絡負載情況分析:圖(2)、(3)描述了當網絡發生擁塞崩潰時,微小的負載增量都將使網絡的有效吞吐量(goodput)急劇下降。網絡負載較小時,吞吐量與網絡負載之間呈線性關系,網絡延遲緩慢增加;網絡負載超過(Knee)后,網絡吞吐量增長緩慢,網絡延遲增長變快;網絡負載到達(Cliff)后,網絡吞吐量急劇下降,網絡延遲急劇上升。原先有學者提出擁塞產生最基本的原因是由存儲空間不夠、帶寬容量不夠、處理器處理能力低引起的,但實踐表明:即使提供足夠的空間、帶寬、無限提高處理器能力也無法避免網絡擁塞發生。研究表明:擁塞控制涉及到Internet、通信、物理、非線性規劃、系統控制、優化等理論系統,是個復雜的系統工程。[7]

二、TCP擁塞控制策略

Internet擁塞控制策略實施一般在傳輸層進行,因為TCP協議一直是主要的端到端(end-to-end)的資源分配方案。TCP擁塞控制策略一般實現擁塞避免(congestion avoidance)和擁塞控制(congestion control)2種相輔相成的功能。擁塞避免是“預防”機制,它的目標是避免網絡進入擁塞狀態,使網絡運行在高吞吐量、低延遲的狀態下;擁塞控制是“恢復”機制,它用于把網絡從擁塞狀態中恢復出來。TCP擁塞控制目標保證網絡運行在輕微擁塞的最佳狀態,即使發生擁塞也保證網絡系統不會崩潰。[8]

三、TCP擁塞控制算法分析

目前的TCP擁塞控制算法是基于Jacobson于1988年提出的,TCP協議采用的擁塞控制算法已經成為保證Internet穩定性的重要因素,大大提高了網絡傳輸的性能。其實要真正解決擁塞的方案是減慢數據率,理論上采用分組守恒的原則。TCP通過動態管理維護擁塞窗口(congestion window就是傳送端可以連續傳送封包的大小,簡稱cwnd)來實現擁塞檢測、擁塞避免功能。TCP擁塞控制算法一般采用如下策略:慢啟動(Slow Start),擁塞避免(Congestion Avoidance)、快速重傳(Fast Retransmit)和快速恢復(Fast Recovery)。與此對應的TCP擁塞控制算法主要有:TCP Tahoe、TCP Reno、New-Reno TCP、TCPSACK、TCP Vegas。

(一)TCP Tahoe

TCP Tahoe算法是擁塞控制早期版本,它實現三個最基本的功能:即Tahoe=Slow Start+Congestion Avoidance+Fast Retransmit。它檢測網絡擁塞的基本思路是:每當送出一個封包,會啟動一個計時器,如果計時器在約定時間內沒有收到該封包的ACK,就表示網絡出現擁塞。當收到重復的ACK封包時,表示接收端一直沒有收到某一個封包,也代表網絡出現擁塞。TCP Tahoe的工作機制是:當網絡連接啟動時,cwnd=1 segment,ssthresh

=65535 bytes。每收到一個ACK,cwnd就會增加,而增加的方式有2種方法:Slow Start及Congestion Avoidance。進入Slow Start或Congestion Avoidance是由cwnd是否超過ssthresh來判斷,若cwnd

(二)TCP Reno and New-Reno TCP

Jacobson(1990)等人在Tahoe TCP的基礎上加入了快速恢復形成了RenoTCP算法Reno=Slow Start+Congestion Avoidance+Fast Retransmit+Fast Recovery。快速恢復算法的目的是在快速重傳之后提高TCP算法的吞量。NewReno TCP(1996年,Fall和Floy在Reno的基礎上提出了New Reno)算法是Reno TCP算法的基礎上對快速恢復算法進行修改,添加了恢復應答判斷功能,以增強TCP終端通過ACK報文信息分析報文傳輸狀況的能力。NewReno TCP算法使TCP終端可以把一次擁塞丟失多個報文的情形與多次擁塞的情形區分開來,進而在每一次擁塞發生后擁塞窗口只減半一次,從而提高了TCP的頑健性和吞吐量。[12]

(三)TCP-SACK

SACK TCP(1996年,Mathis、Mahdavi、Floy和Romanow提出了Reno的另一變形:SACK)算法也是在Reno TCP算法的基礎上增加了選擇確認SACK和選擇重傳功能。SACK的基本思想是接受方TCP發送SACK分組來通知發送方接受數據的情況,這樣發送方只重傳丟失的分組。SACK在進入快速重傳狀態時,如果網絡中的所有分組已經得到確認,那就會退出快速重傳狀態。

(四)TCP Vegas

L S Brakmo(1996)等提出了一種新的擁塞控制算法TCP Vegas。即“選擇性重復”(selective repeat)策略。Vegas對Reno進行了三項重要的技術改進:(1)采用了新的重傳觸發機制,即用一個重復ACK(而非Reno中的3個)來啟動超時判定規程,這樣可以更及時地檢測到擁塞的發生;(2)在慢啟動階段采用了更加謹慎的方式來增加窗口大小,減少了不必要的分組丟失;(3)改進“擁塞避免”階段的窗口調整法。[6]

四、結束語

隨著TCP擁塞控制研究的深入,已經有相當完善的擁塞控制算法理論,許多學者在文獻[2][3][4]基礎上對TCP擁塞控制進行深入研究,提出把系統控制理論引進擁塞控制,對TCP連接的公平性、建模等方面對TCP進行了擴展和改良。文獻[13][14]等提出改進“慢啟動”算法、用數學建模方式、優化理論來解決網絡擁塞和算法組合策略;文獻[15][16]等對最新TCP擁塞控制算法最新研究動態作了較好的分析總結,把線性規劃、資源分配、競爭機制理論引入算法思想;文獻[10]等對TCP擁塞控制在特殊網絡中(高速網絡、無線網絡)進行深入的研究,并對TCP擁塞法進一步改良和組合、完善利用NS2仿真模型做了一些有意義數據和案例,為研究擁塞控制算法作了重要工作。總之,TCP擁塞控制算法還在不斷發展中,將來會有更加完善的算法運用到實踐中,由于作者水平有限,文中不足之處,懇請批評指正!

參考文獻:

[1]Tanenbaum A S.Co mputer letworks.The third edition.B Pret.ice HalI.1996,374-378.

[2]Jacobson Congestion avoidance and contro1.ACM Co mputer Co mmunication Review,1988,18(4):314-329.

[3]Jacobson v.Co ngestion Avoidance and Co ntro1.IEEE/ACM Transaction Networking,1998,6(3):314-329.

[4]Gevros P,Crowcroft J,Kirstein P,et a1.Co ngestion contromechanisms and the best effort service mode1.IEEE Network,2001,15(3):16-26.

[5]Steves W.TCP S1ows Start,Co ngestion Avoidance,Fast Retransmit,and Fast Recovery Algorithms.RFC2001,1997.

[6]劉擁民、蔣新華、年曉紅等,Internet端到端擁塞控制研究綜[J].計算機科學,2008,Vo1.35№.2:6-12.

[7]Meom C.A new approach to model the stationary behavior ofTCP Co nnections.IEEE Co mputer Society,2000.

[8]Jain,R.Ramakrishnan,K.K.Chiu,Dah-Ming.Congestion avoidance in computer networks with a connectionless network layer.Technical Report,DEC-TR-506,Digital Equipment Corporation,1988.

[9]Floyd,S.Fall,K.Promoting the use of end-to-end congestion controlin theInternet.IEEE/ACMTransactionsonNetworking,1999,7(4):458-472.

[10]http://www.cs.nctu.edu.tw/-cmtsai/cgi-bin/wiki.pl?action=bro

wse;diff=2;id=TCP_Tahoe.Comments on TCP_Tahoe.

[11]章淼、吳建平、林闖,互聯網端到端擁塞控制研究綜述[J].軟件學報,2002,Vol.13,No.3:354-363.

[12]封寧、白光偉,TCP擁塞控制算法的組合策略研究[J].微計算機信息(管控一體化),2009,第25卷,第4-3期:159-161.

[13]曹雪峰,TCP擁塞控制算法建模分析[J].現代計算機(總第二九九期)2009.1:120-122.

[14]馬義忠、司穎、竇戰偉,基于接收驅動的擁塞控制算法分析[J].計算機工程,2009.02,第35卷,第4期:119-124.

[15]何炎祥、熊乃學、楊燕,一種改進的TCP擁塞控制算法[J].計算機研究與發展,2005,42(12):2070-2076.

[16]賀婷婷、謝高崗、張廣興等,802.11無線接入TCP連接本地延遲抖動的理論模型[J].計算機應用研究,2009.01,第26卷,第1期:272-279.

[17]Audrew S.Tanenbaum著,潘愛民譯,計算機網絡(第四版)[M].北京:清華大學出版社,2004:256-271.

作者簡介:

劉國棟(1980-),廣東河源人,中山大學信息科學與技術學院計算機科學系2008級計算機軟件與理論碩士研究生,任職于廣州南洋理工職業學院,主要從事計算機教學工作。