TCP網(wǎng)絡(luò)擁塞控制算法比較研究

陳 琳,雙雪芹 (長江大學(xué)計算機科學(xué)學(xué)院,湖北荊州434023)

20世紀80年代中期,計算機網(wǎng)絡(luò)經(jīng)歷了第1次由于網(wǎng)絡(luò)擁塞引起的網(wǎng)絡(luò)崩潰,在2個相距500m的網(wǎng)絡(luò)之間,數(shù)據(jù)吞吐量從32kbps降到了40bps[1],網(wǎng)絡(luò)擁塞控制問題便引起了研究者們的廣泛關(guān)注,并在擁塞控制領(lǐng)域開展了大量的研究工作[2]。在眾多研究文獻中,采用的擁塞控制機制集中在2個方面:TCP擁塞控制和IP擁塞控制。筆者對TCP擁塞控制機制中的4種典型算法TCP Newreno、TCP Vegas、TCP Sack1、TCP Fack進行了研究,在NS仿真環(huán)境下進行了比較分析,得出了不同算法的優(yōu)缺點,并指明了擁塞控制機制研究的下一步方向。

1 算法簡介

1.1 TCP Newreno

TCP Newreno[3～5]是基于窗口反饋機制的端到端擁塞控制算法,即發(fā)送方根據(jù)接收到的反饋包(ACK包)所攜帶的信息,決定如何調(diào)整擁塞窗口的大小。該算法是對文獻 [6]中快速恢復(fù)算法的改進,考慮了一個發(fā)送窗口內(nèi)多個報文丟失的情況。在Reno快速恢復(fù)算法中,當(dāng)發(fā)送方收到一個不重復(fù)的應(yīng)答后就退出快速恢復(fù)狀態(tài),而在Newreno算法中,只有當(dāng)所有報文都被應(yīng)答后才退出快速恢復(fù)狀態(tài)。

TCP Newreno利用一種Partial ACK包[3]在快速恢復(fù)階段觸發(fā)數(shù)據(jù)包的重傳。Partial ACK包是指當(dāng)一個窗口出現(xiàn)多個分組丟失時,確認了部分發(fā)送分組的重傳分組的ACK包。數(shù)據(jù)傳輸過程中有多個分組丟失后,Newreno在快速恢復(fù)階段每隔1個往返延遲 (RT T)重傳1個丟失的分組,直到擁塞窗口的所有丟失分組都被重傳。當(dāng)在快速恢復(fù)階段接收到第1個Partial ACK時,將重傳定時器復(fù)位。

1.2 TCP Vegas

TCP Vegas[7]也是對Reno算法的改進,和Reno采用報文段丟失作為擁塞度量所不同的是,Vegas采用延遲作為擁塞度量,并且通過比較實際傳輸速率和期望傳輸速率之間的差值來預(yù)知擁塞的發(fā)生,并在重傳機制和慢啟動機制方面做了一定修改。其主要機制如下:

1)擁塞避免 期望傳輸速率E定義為:

其中,cwnd為擁塞窗口大小;BaseRT T為所觀察到的最小的RT T。

實際傳輸速率A定義為:

其中,RT T為當(dāng)前觀察到的值。

Vegas將E與A的差值與門限值α和β比較(α＜β)[7],當(dāng)差值小于α?xí)r,Vegas在下1個RTT中將擁塞窗口加1;當(dāng)差值大于β時,Vegas則在下1個RT T中將擁塞窗口減1;否則擁塞窗口保持不變。

2)慢啟動 在改進的慢啟動算法中,每2個RT T時間間隔就將cwnd增加一倍。因此在2個RT T期間,在一個R TT內(nèi)擁塞窗口不會變化,這樣A和E的比較就較為準確。比較值同另一個門限值λ[7]作比較,當(dāng)比較值達到門限值λ,Vegas就進入擁塞避免階段。

3)快速重傳/快速恢復(fù) 在發(fā)送數(shù)據(jù)段時,Vegas讀取并記錄下系統(tǒng)時間。當(dāng)一個ACK包到達時,Vegas再次讀取系統(tǒng)時鐘并以該時間和先前記錄下的時間來計算RTT。當(dāng)接收到重復(fù)ACK時,Vegas檢查當(dāng)前RT T是否比超時值大,如果是,Vegas就立即重發(fā)相應(yīng)的數(shù)據(jù)段,而不必等到第3個重復(fù)ACK包到來。當(dāng)接收到非重復(fù)ACK時,如果它是重發(fā)之后的第1或第2個確認,Vegas將再次檢測第1個未被確認的數(shù)據(jù)包發(fā)送的時間和此時的時間間隔是否大于超時值,如果是,Vegas將重發(fā)該數(shù)據(jù)段。

1.3 TCP Sack1

Sack1[8,9]也是基于算法Reno的改進。當(dāng)檢測到擁塞后,不用重傳從數(shù)據(jù)包丟失到檢測到丟失時發(fā)送的全部數(shù)據(jù)包,而是對這些數(shù)據(jù)包進行有選擇的確認和重傳,從而避免不必要的重傳,減少時延,提高網(wǎng)絡(luò)吞吐量。與Reno所不同的是,接收端的ACK包中包含了一些SACK塊,每個SACK塊表示了接收端收到的分組序列中缺少的分組段范圍,這使得發(fā)送端可以明確地知道哪些分組應(yīng)該進行重傳。SACK算法的發(fā)送端在收到第2個重復(fù)的ACK包后,進入到快速恢復(fù)階段,它設(shè)置了1個變量估計網(wǎng)絡(luò)中正在傳輸?shù)姆纸M數(shù)量,只有該變量的值小于擁塞窗口時,發(fā)送端才被允許發(fā)送分組數(shù)據(jù)。發(fā)送端每收到1個重復(fù)的帶有SACK信息的ACK包 (表明新的分組被接到),就將該變量減1;每次有新的或者重發(fā)的分組被發(fā)送,變量的值就被加1個分組的大小。同時,發(fā)送端維持1個稱為計分板的數(shù)據(jù)結(jié)構(gòu),記錄從SACK中得知的未被確認的分組,發(fā)送端如果被允許發(fā)送,就重傳計分板中指示的最后的分組,如果計分板為空,就發(fā)送新的分組。當(dāng)收到確認了所有的進入快速恢復(fù)之前未確認的分組的ACK后,便退出快速恢復(fù)階段?？梢钥吹?計分板指出了哪些分組需要重傳,而上述所設(shè)置的變量決定了什么時候重傳哪些分組。

1.4 TCP Fack

TCP Fack[10]是基于對TCP Sack1的修改。Fack引入3個TCP發(fā)送端狀態(tài)參數(shù):未確認分組中的第1個序號、待發(fā)送的第1個分組的序號、接收端收到的最新的分組序號,在恢復(fù)階段發(fā)送端估計網(wǎng)絡(luò)中的分組數(shù) (待發(fā)送的第1個分組的序號減去接收端收到的最新的分組序號,并加上正在網(wǎng)絡(luò)中重傳的分組數(shù)),當(dāng)發(fā)送端估計的分組數(shù)小于擁塞窗口時,發(fā)送端被允許發(fā)送或者重發(fā)分組。

2 仿真比較與分析

筆者在NS[11]仿真環(huán)境下進行仿真,仿真采用基于圖1的啞鈴?fù)負浣Y(jié)構(gòu),對Newreno、Vegas、Sack1、Fack 4種算法進行了仿真,得到每個算法在圖1場景下的擁塞窗口、吞吐量、丟失率和平均隊列變化曲線圖。圖1中si為源端,di為接收端,R1、R2為路由器,采用RED隊列策略,由n個連接共享一段由R1、R2構(gòu)成的瓶頸鏈路。瓶頸鏈路的帶寬為1.5Mbps,傳播延遲為20ms。分組的大小設(shè)為552Bytes,端點帶寬分別是10Mbps,延遲為5ms。網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)流類型為FTP。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

從圖2可以看出,在相同的環(huán)境下,Newreno、Sack1和Fack的3種算法的擁塞窗口曲線在平衡狀態(tài)后均呈鋸齒狀,所不同的是,Fack在超時后把擁塞窗口置1,經(jīng)歷慢啟動后達到一個平衡狀態(tài)。3種算法的共同點是都必須周期性地丟失報文段以維持這種平衡。實驗表明在低帶寬的環(huán)境下,這對傳輸速率還不會造成很大影響,傳輸速率在達到平衡狀態(tài)后周期性變化。Vegas在20s以后擁塞窗口變成直線,說明窗口維持在一個定值。這是因為用α和β兩個常數(shù)來控制擁塞窗口的變化,當(dāng)發(fā)送傳輸速率和期望傳輸速率之差介于α和β之間,窗口不變化了,使鏈接達到穩(wěn)定點后傳輸速率維持在較高的水平。

圖3是4種算法的吞吐量曲線。由圖3可以看出,Vegas在后期擁塞窗口維持在一個較高的平衡狀態(tài),吞吐量也保持在一個高的水平;Newreno和Sack1兩種算法在平衡狀態(tài)的吞吐量也是非常接近的,波動比較小。Fack在超時后是把窗口置為1,經(jīng)歷慢啟動后才達到一個平衡狀態(tài),使得其吞吐量曲線波動較大,但總體還是處于一個平穩(wěn)狀態(tài)。

圖2 擁塞窗口對比

圖3 吞吐量對比

從圖4顯示的丟失率對比可以看出,在開始的4s內(nèi),Vegas、Sack1、New reno和Fack的4個算法的丟失率從小到大排列。Vegas算法的丟失率最少,而Fack算法的丟失率最大。這是因為Vegas采用延遲作為擁塞度量,并且通過比較實際傳輸速率和期望傳輸速率之間的差值來預(yù)知擁塞的發(fā)生,而Sack1、Newreno、Fack的3種算法采用了報文段丟失作為擁塞度量。在網(wǎng)絡(luò)環(huán)境比較平穩(wěn)的條件下,Vegas算法就體現(xiàn)了其優(yōu)越性,能更準確地預(yù)知網(wǎng)絡(luò)擁塞的情況,從而及時采取擁塞控制措施。當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時Fack把窗口置1,窗口突然減少到1,產(chǎn)生報文發(fā)送振蕩使得網(wǎng)絡(luò)擁塞無法及時緩解,造成丟失報文增加。

圖5為平均隊列長度對比變化曲線圖。由圖5可見,Vegas算法的平均隊列長度較小,對鏈路的利用率最高,Fack算法次之。

圖4 丟失率對比

圖5 平均隊列長度對比

3 結(jié) 語

仿真結(jié)果表明,Vegas算法采用時間延遲作為擁塞度量,使用RT T的變化來判斷網(wǎng)絡(luò)可用帶寬,能較好地預(yù)測網(wǎng)絡(luò)帶寬使用情況,其吞吐量、鏈路利用率都較好,數(shù)據(jù)包丟失率小、緩存隊列長度較小,具有良好的應(yīng)用前景。由于Fack算法數(shù)據(jù)包丟失率最大,將來可以改進其擁塞超時策略以提高算法性能。Vegas算法在各方面都優(yōu)于其他3種算法,但由于判斷條件依賴于RT T的估算,因此設(shè)計一個性能良好的RT T估算算法變得尤為重要,這也是筆者下一步研究的方向。

[1]Jacobson V.Congestion avoidance and control[J].Proceeding of SIGCOMM'88,1988.314～329.

[2]羅萬明,林闖,閻保平.TCP/IP擁塞控制研究 [J].計算機學(xué)報,2001,24(1):1～18.

[3]Floyd S,Henderson T.The New reno modification to T CP's fast recovery algorithm[J].RFC 2582,1999.

[4]Clark D,Hoe J.Start-up dy namics of TCP's congestion control and avoidance schemes[J].Presentation to Internet End-to-End research Group,1995.

[5]Grieco L A,Mascolo S.Performance evaluation and comparison of Westwood+,New Reno,and Vegas TCP congestion control[J].Computer Communication Review,2004,34(2):25～38.

[6]Jacobson V.M odified T CP congestion avoidance Algorithm.http://ftp.ee.lbl.gov/

[7]Brakino L S.TCP vegas.New techniques for congestion detection&avoidance[C].Proc SIGGCOM M,1999.

[8]M atthew W,Jamshid W,Sally F,et al.TCP selective acknowledgement options[J].RFC 2081,1996.

[9]劉擁民,年曉紅.對SACK擁塞控制算法的研究 [J].信息技術(shù),2003,(9):55～58.

[10]Matllls M,Mahdavi J.Forward acknowledgement(FACK):refiningTCP congestion control[J].Proc SIGCOMM,1996.281～291.

[11]The Network Simulator-ns-2.http://www.isi.edu/nsnam/ns/2004.