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

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

[關鍵詞]Internet TCP協(xié)議 擁塞控制 算法

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

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

一、擁塞控制基本概念

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

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

二、TCP擁塞控制策略

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

三、TCP擁塞控制算法分析

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

(一)TCP Tahoe

TCP Tahoe算法是擁塞控制早期版本,它實現(xiàn)三個最基本的功能:即Tahoe=Slow Start+Congestion Avoidance+Fast Retransmit。它檢測網絡擁塞的基本思路是:每當送出一個封包,會啟動一個計時器,如果計時器在約定時間內沒有收到該封包的ACK,就表示網絡出現(xiàn)擁塞。當收到重復的ACK封包時,表示接收端一直沒有收到某一個封包,也代表網絡出現(xiàn)擁塞。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?？焖倩謴退惴ǖ哪康氖窃诳焖僦貍髦筇岣逿CP算法的吞量。NewReno TCP(1996年,Fall和Floy在Reno的基礎上提出了New Reno)算法是Reno TCP算法的基礎上對快速恢復算法進行修改,添加了恢復應答判斷功能,以增強TCP終端通過ACK報文信息分析報文傳輸狀況的能力。NewReno TCP算法使TCP終端可以把一次擁塞丟失多個報文的情形與多次擁塞的情形區(qū)分開來,進而在每一次擁塞發(fā)生后擁塞窗口只減半一次,從而提高了TCP的頑健性和吞吐量。[12]

(三)TCP-SACK

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

(四)TCP Vegas

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

四、結束語

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

參考文獻:

[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]章淼、吳建平、林闖,互聯(lián)網端到端擁塞控制研究綜述[J].軟件學報,2002,Vol.13,No.3:354-363.

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

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

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

[15]何炎祥、熊乃學、楊燕,一種改進的TCP擁塞控制算法[J].計算機研究與發(fā)展,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級計算機軟件與理論碩士研究生,任職于廣州南洋理工職業(yè)學院,主要從事計算機教學工作。