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

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

1 算法簡(jiǎn)介

1.1 TCP Newreno

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

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

1.2 TCP Vegas

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

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

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

實(shí)際傳輸速率A定義為:

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

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

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

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

1.3 TCP Sack1

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

1.4 TCP Fack

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

2 仿真比較與分析

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

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

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

圖2 擁塞窗口對(duì)比

圖3 吞吐量對(duì)比

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

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

圖4 丟失率對(duì)比

圖5 平均隊(duì)列長(zhǎng)度對(duì)比

3 結(jié) 語(yǔ)

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

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

[2]羅萬(wàn)明,林闖,閻保平.TCP/IP擁塞控制研究 [J].計(jì)算機(jī)學(xué)報(bào),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]劉擁民,年曉紅.對(duì)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.