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

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

中圖分類號(hào):TP3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0810062-02

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

一、擁塞控制基本概念

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

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

二、TCP擁塞控制策略

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

三、TCP擁塞控制算法分析

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

(一)TCP Tahoe

TCP Tahoe算法是擁塞控制早期版本,它實(shí)現(xiàn)三個(gè)最基本的功能:即Tahoe=Slow Start+Congestion Avoidance+Fast Retransmit。它檢測網(wǎng)絡(luò)擁塞的基本思路是:每當(dāng)送出一個(gè)封包,會(huì)啟動(dòng)一個(gè)計(jì)時(shí)器,如果計(jì)時(shí)器在約定時(shí)間內(nèi)沒有收到該封包的ACK,就表示網(wǎng)絡(luò)出現(xiàn)擁塞。當(dāng)收到重復(fù)的ACK封包時(shí),表示接收端一直沒有收到某一個(gè)封包,也代表網(wǎng)絡(luò)出現(xiàn)擁塞。TCP Tahoe的工作機(jī)制是:當(dāng)網(wǎng)絡(luò)連接啟動(dòng)時(shí),cwnd=1 segment,ssthresh

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

(二)TCP Reno and New-Reno TCP

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

(三)TCP-SACK

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

(四)TCP Vegas

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

四、結(jié)束語

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

參考文獻(xiàn):

[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].計(jì)算機(jī)科學(xué),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)網(wǎng)端到端擁塞控制研究綜述[J].軟件學(xué)報(bào),2002,Vol.13,No.3:354-363.

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

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

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

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

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

[17]Audrew S.Tanenbaum著,潘愛民譯,計(jì)算機(jī)網(wǎng)絡(luò)(第四版)[M].北京:清華大學(xué)出版社,2004:256-271.

作者簡介:

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