TCP擁塞控制建模分析方法

夏愛民,劉 棟,張 帆

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

0 引言

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

1 建模仿真

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

1.1 協(xié)議建模

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

圖1 利用CPN對TCP建模結(jié)果

1.2 仿真過程

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

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

2 性能分析

如圖1所示的CPN模型經(jīng)過等價變換,可以得到圖2所示的網(wǎng)絡(luò)模型?？紤]一條單瓶頸鏈路,鏈路中只有一個路由器會發(fā)生擁塞,其出口速率為C,緩存大小為B。源端到路由器的延時為Tfw,路由器到收端再由收端返回發(fā)端的延時為Tfb。數(shù)據(jù)包的長度為定值L。

圖2 網(wǎng)絡(luò)模型

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

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

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

3 性能測試結(jié)果

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

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

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

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

因此,在設(shè)計擁塞避免機(jī)制的過程中,應(yīng)綜合考慮擁塞窗口大小和緩存隊列長度。在擁塞比較小的情況下,應(yīng)該增大擁塞窗口,提高發(fā)送速率,同時減小緩存隊列,減少排隊延遲,從而增大帶寬利用率。而在擁塞嚴(yán)重的情況下,應(yīng)該減小擁塞窗口以減輕對網(wǎng)絡(luò)的負(fù)擔(dān),同時增大緩存隊列長度,減少擁塞的發(fā)生。

4 結(jié)束語

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

[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].計算機(jī)學(xué)報,2001,24(1):1-18.

[4]林 闖.計算機(jī)網(wǎng)絡(luò)和計算機(jī)系統(tǒng)的性能評價[M]:北京:清華大學(xué)出版社,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.