夏愛民,劉 棟,張 帆

(1.南開大學(xué)信息技術(shù)科學(xué)學(xué)院,天津300071;2.中國(guó)電子設(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è)計(jì)中,如何得到較好的仿真結(jié)果是一個(gè)非常迫切的問題。不過現(xiàn)有的建模方法大多是在協(xié)議層面的研究,而不是對(duì)實(shí)際傳輸?shù)木W(wǎng)絡(luò)情況進(jìn)行研究。利用著色Petri網(wǎng)(Colored Petri Net,CPN)[4-6]建立TCP傳輸協(xié)議的擁塞控制模型是有效的解決途徑之一。通過對(duì)模擬結(jié)果的分析,說明了該模型能夠有效地刻畫TCP的擁塞控制特性,從而指導(dǎo)擁塞避免算法的設(shè)計(jì)。

1 建模仿真

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

1.1 協(xié)議建模

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

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

1.2 仿真過程

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

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

2 性能分析

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

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

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

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

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

3 性能測(cè)試結(jié)果

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

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

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

圖3 擁塞窗口和緩存隊(duì)列長(zhǎng)度變化示意圖

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

4 結(jié)束語

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

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

[4]林 闖.計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)的性能評(píng)價(jià)[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.