TCP擁塞控制建模分析方法

夏愛民,劉 棟,張 帆

(1.南開大學信息技術科學學院,天津300071;2.中國電子設備系統工程公司研究所,北京100141;3.北京航天指揮控制中心,北京100094)

0 引言

近年來,互聯網應用呈爆炸式發展,極大地改變了人們的生活方式。不過海量的網絡應用帶來了非常嚴重的網絡擁塞問題[1-3]。現有的TCP擁塞控制思路、方法和技術在多目標的不同環境中更是面臨著挑戰。在TCP行為研究及協議設計中,如何得到較好的仿真結果是一個非常迫切的問題。不過現有的建模方法大多是在協議層面的研究,而不是對實際傳輸的網絡情況進行研究。利用著色Petri網(Colored Petri Net,CPN)[4-6]建立TCP傳輸協議的擁塞控制模型是有效的解決途徑之一。通過對模擬結果的分析,說明了該模型能夠有效地刻畫TCP的擁塞控制特性,從而指導擁塞避免算法的設計。

1 建模仿真

選擇時間著色Petri網(Timed CPN,TCPN)來對TCP系統擁塞控制相關行為,包括窗口、延時和緩存等進行描述,擁塞窗口嚴格按照AIMD變化。此外,為簡化分析,假設在發生擁塞時源端始終采用慢啟動而不會采用避免階段算法。

1.1 協議建模

變量的定義參考文獻[4]。位置名的含義如下:S表示數據發送源端;Span表示數據發送端的發送間隔;I表示到達瓶頸路由器;B表示瓶頸路由器緩存;W表示等待隊列;Wait表示位于等待隊列中的數據包的發送間隔;M和R分別表示正在服務的數據包和接收端。另外,變遷名T1T6分別代表數據從源端發送為M發出的數據包貼上不同的時間標簽、數據從路由器發送為W等待隊列的數據包打上時間標簽、數據包丟失、回復Ack、進入路由器以及離開路由器。用CPN對TCP傳輸控制協議進行建模的結果如圖1所示。

圖1 利用CPN對TCP建模結果

1.2 仿真過程

圖1中數據包從S發出經過T2(該變遷只允許發送擁塞窗口大小的數據包)到達I。如果此時B中有空閑緩存,則實施變遷T4,進入等待隊列W,否則實施T1通告丟包,窗口減半。位于等待隊列W中的數據包經過T6后被依次標記上固定的間隔時間進入M,該間隔代表路由器對每個數據包的發送延時。變遷T5為每個包加上傳輸時延后進入R,隨后經過T3,數據返回源端,擁塞窗口和確認窗口均增加1。

B、T4和T5以及之間的相互變遷,其作用相當于B到T1存在的一條抑止弧。位置Span的作用在于讓每個經過T2變遷發送出去的數據包具有一個不同的時間戳(由于源端實際發送的發送延時)。同理,位置Wait的作用是為了把在等待隊列中的數據包在離開時擁有不同時間戳(由于路由器的發送延時)。注意到T2、T1和T3在變遷實施時對擁塞窗口、當前窗口和已確認的最大窗口進行了調整,這是進行擁塞控制的關鍵。

2 性能分析

如圖1所示的CPN模型經過等價變換,可以得到圖2所示的網絡模型。考慮一條單瓶頸鏈路,鏈路中只有一個路由器會發生擁塞,其出口速率為C,緩存大小為B。源端到路由器的延時為Tfw,路由器到收端再由收端返回發端的延時為Tfb。數據包的長度為定值L。

圖2 網絡模型

類似于經典的拇指規則(Rule of Thumbs)分析,可以獲得:

給出了保持鏈路利用率100%的條件為B≥RTT×C/3,其中RTT=Tfw+Tfb表示往返時延。

式(1)表示源端在t時刻收到阻塞信息,此時的窗口大小等于已發報文的數量,包括路由器緩存中的,鏈路上傳輸的以及丟失的ε三部分。式(2)表示源端在窗口減半后停止發送,且須等待W(t)/2的報文被確認,擁塞窗口恢復到原來的位置時才能繼續發送,在這一段時間內,路由器以速率C向外發送緩存數據。為保持鏈路利用率為100%,沒有空閑,路由器向外發送的這一段時間應大于源端等待W(t)/2個報文確認的時間。由于采用慢啟動算法,每一次確認導致發送端的擁塞窗口值和已被確認序號均增加1,所以要確認減半的W(t)/2個報文,實際只需要W(t)/4個Ack即可。

3 性能測試結果

令C=1Mb/s,B=8 pkt,Tfw=0,Tfb=200 ms,L=1 500 byte。忽略超時重傳,并且在路由器使用ECN,即一旦丟包立刻通知源端。對應于CPN模型,位置B的初始標志為8,T3為路由器的服務時間間隔1/μ=12 pkt/ms,在T8到R的弧上要消耗200 ms之后確認信息發回至源端。計算得到B≥5.6≈6 pkts,CPN/Tools模擬結果如圖3所示。

圖3(a)表示擁塞窗口變化過程,圖3(b)表示緩存隊列長度變化過程。圖中路由器緩存B為3個包大小。可以看到傳輸的開始階段因為慢啟動,擁塞窗口呈現指數形式的增長,相應的緩存隊列長度也有一個逐漸振蕩增長的過程。經過一段時間后發生擁塞,可以看到:當緩存小于臨界值6時,窗口的變化不規律,穩定性較差,緩存隊列在空和滿之間劇烈振蕩;當緩存為臨界值時窗口變化趨于規律的鋸齒形,緩存隊列也趨向規律振蕩,在最小值處恰為0;而當緩存大于臨界值時,窗口變化呈現出規律的鋸齒形,緩存隊列也按規律的V字鋸齒形變化,隊長始終大于0,即隊列不為空,鏈路利用率為100%。

另外,注意到曲線中有的變化發生于同一時刻,這種現象有2個方面的原因:①因為Petri網能夠描述并發,因此同一時刻發生的多次變化能夠被記錄下來;②當路由器的緩存十分小時,振蕩更為劇烈,丟包也更為頻繁,因此發送端擁塞窗口值也保持在較低值變化,而由于刻度的關系所以顯得更為明顯。

圖3 擁塞窗口和緩存隊列長度變化示意圖

因此,在設計擁塞避免機制的過程中,應綜合考慮擁塞窗口大小和緩存隊列長度。在擁塞比較小的情況下,應該增大擁塞窗口,提高發送速率,同時減小緩存隊列,減少排隊延遲,從而增大帶寬利用率。而在擁塞嚴重的情況下,應該減小擁塞窗口以減輕對網絡的負擔,同時增大緩存隊列長度,減少擁塞的發生。

4 結束語

在計算機網絡傳輸協議的應用中,CPN具備的模型能力與有效性為計算機網絡的Petri網模型方法提供了有益的啟示。利用著色Petri網對TCP協議的傳輸控制進行模擬,形象刻畫了協議運行過程中傳輸控制的各種動作以及協議與網絡相互影響的過程。通過模擬發現該模型能夠比較準確地體現TCP協議擁塞控制的基本特性,而且由于Petri網對并發過程具備自然的描述能力,網絡的并發特性能夠得到體現。作為一個TCP擁塞控制的基本模型,由于沒有引入額外細節,從而避免了多余的復雜性。該模型可用來模擬和分析各種網絡參數,能為協議或者算法設計提供有效的參考。

[1]JACOBSON V.Congestion Avoidance and Control[J].IEEE/ACM Transaction Networking,1998,6(3):314-329.

[2]Caserri C,Meo M.A New Approach to Model the Stationary Behavior of TCP Connections[C].In:Proc IEEE IN FOCOM 2000,Tel Aviv,Israel,2000:367-375.

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

[4]林 闖.計算機網絡和計算機系統的性能評價[M]:北京:清華大學出版社,2001.

[5]JENSEN K,COLORED P N.CONCEPTS B.Analysis Methods and Practical Use,Basic Concepts[M].NewYork:Springer-Verlag,1997:25-30.

[6]SUN Xin,FEI Mei-ri,SUN You-xian.The Application of Colored Petri Nets in Systems Analysis[C].Shanghai:Proceedings of The 4th World Congress on Intelligent Control and Automation,2002:582-586.