TCP網絡擁塞控制算法比較研究

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

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

1 算法簡介

1.1 TCP Newreno

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

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

1.2 TCP Vegas

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

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內擁塞窗口不會變化,這樣A和E的比較就較為準確。比較值同另一個門限值λ[7]作比較,當比較值達到門限值λ,Vegas就進入擁塞避免階段。

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

1.3 TCP Sack1

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

1.4 TCP Fack

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

2 仿真比較與分析

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

圖1 網絡拓撲結構

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

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

圖2 擁塞窗口對比

圖3 吞吐量對比

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

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

圖4 丟失率對比

圖5 平均隊列長度對比

3 結 語

仿真結果表明,Vegas算法采用時間延遲作為擁塞度量,使用RT T的變化來判斷網絡可用帶寬,能較好地預測網絡帶寬使用情況,其吞吐量、鏈路利用率都較好,數據包丟失率小、緩存隊列長度較小,具有良好的應用前景。由于Fack算法數據包丟失率最大,將來可以改進其擁塞超時策略以提高算法性能。Vegas算法在各方面都優于其他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.