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

20世紀80年代中期,計算機網(wǎng)絡經(jīng)歷了第1次由于網(wǎng)絡擁塞引起的網(wǎng)絡崩潰,在2個相距500m的網(wǎng)絡之間,數(shù)據(jù)吞吐量從32kbps降到了40bps[1],網(wǎ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ā)送窗口內(nèi)多個報文丟失的情況。在Reno快速恢復算法中,當發(fā)送方收到一個不重復的應答后就退出快速恢復狀態(tài),而在Newreno算法中,只有當所有報文都被應答后才退出快速恢復狀態(tài)。

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

1.2 TCP Vegas

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

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

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

實際傳輸速率A定義為:

其中,RT T為當前觀察到的值。

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

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

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

1.3 TCP Sack1

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

1.4 TCP Fack

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

2 仿真比較與分析

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

圖1 網(wǎng)絡拓撲結構

從圖2可以看出,在相同的環(huán)境下,Newreno、Sack1和Fack的3種算法的擁塞窗口曲線在平衡狀態(tài)后均呈鋸齒狀,所不同的是,Fack在超時后把擁塞窗口置1,經(jīng)歷慢啟動后達到一個平衡狀態(tài)。3種算法的共同點是都必須周期性地丟失報文段以維持這種平衡。實驗表明在低帶寬的環(huán)境下,這對傳輸速率還不會造成很大影響,傳輸速率在達到平衡狀態(tài)后周期性變化。Vegas在20s以后擁塞窗口變成直線,說明窗口維持在一個定值。這是因為用α和β兩個常數(shù)來控制擁塞窗口的變化,當發(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采用延遲作為擁塞度量,并且通過比較實際傳輸速率和期望傳輸速率之間的差值來預知擁塞的發(fā)生,而Sack1、Newreno、Fack的3種算法采用了報文段丟失作為擁塞度量。在網(wǎng)絡環(huán)境比較平穩(wěn)的條件下,Vegas算法就體現(xiàn)了其優(yōu)越性,能更準確地預知網(wǎng)絡擁塞的情況,從而及時采取擁塞控制措施。當網(wǎng)絡發(fā)生擁塞時Fack把窗口置1,窗口突然減少到1,產(chǎn)生報文發(fā)送振蕩使得網(wǎng)絡擁塞無法及時緩解,造成丟失報文增加。

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

圖4 丟失率對比

圖5 平均隊列長度對比

3 結 語

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

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

[2]羅萬明,林闖,閻保平.TCP/IP擁塞控制研究 [J].計算機學報,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].信息技術,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.