基于穩(wěn)定路徑的可靠數(shù)據(jù)傳輸協(xié)議建模研究

摘要:分析了基于穩(wěn)定路徑的數(shù)據(jù)傳輸方式，發(fā)現(xiàn)如果采用傳統(tǒng)的可靠數(shù)據(jù)傳輸協(xié)議存在效率低下的問(wèn)題，提出了一種基于穩(wěn)定路徑的可靠數(shù)據(jù)傳輸協(xié)議(RDTSP)#65377;采用CPN(coloured Petri net) tools對(duì)協(xié)議進(jìn)行了建模分析#65377;狀態(tài)空間結(jié)果表明，該協(xié)議是可靠#65380;可行和完備的#65377;

關(guān)鍵詞:穩(wěn)定路徑; 可靠數(shù)據(jù)傳輸; 滑動(dòng)窗口; 著色Petri網(wǎng)

中圖分類號(hào):TP393.02文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2007)10-0289-03

底層計(jì)算機(jī)通信網(wǎng)絡(luò)提供的服務(wù)是不可靠的分組交付#65377;當(dāng)數(shù)據(jù)傳輸過(guò)程中出現(xiàn)網(wǎng)絡(luò)硬件失效或網(wǎng)絡(luò)負(fù)載太重時(shí)，分組可能丟失，數(shù)據(jù)可能被破壞#65377;此外，底層網(wǎng)絡(luò)技術(shù)會(huì)規(guī)定一個(gè)最佳分組長(zhǎng)度或采取其他提高傳輸效率的手段，這些均會(huì)影響可靠性#65377;滑動(dòng)窗口協(xié)議是計(jì)算機(jī)網(wǎng)絡(luò)實(shí)現(xiàn)可靠數(shù)據(jù)傳輸?shù)幕緳C(jī)制，可以有效保證端到端之間傳輸?shù)姆纸M不亂序#65380;不重復(fù)#65380;不丟失#65377;滑動(dòng)窗口協(xié)議經(jīng)過(guò)不斷改進(jìn)和完善，形成了TCP Tahoe[1] #65380;TCP Reno[2]#65380;TCP SACK[3]和TCP Vegas[4]等多種版本#65377;目前較成熟的版本是TCP Vegas#65377;

傳統(tǒng)的IP數(shù)據(jù)轉(zhuǎn)發(fā)是基于逐跳式的，每個(gè)轉(zhuǎn)發(fā)數(shù)據(jù)的路由器都要根據(jù)IP包頭的目的地址查找路由表來(lái)獲得下一跳的出口，這是個(gè)繁瑣且效率低下的工作#65377;當(dāng)今的互聯(lián)網(wǎng)應(yīng)用需求日益增多，對(duì)帶寬#65380;時(shí)延的要求也越來(lái)越高#65377;為了提高轉(zhuǎn)發(fā)效率，出現(xiàn)了ATM[5]#65380;MPLS[6]等網(wǎng)絡(luò)技術(shù)#65377;這些技術(shù)采用穩(wěn)定的傳輸路徑，將尋路與轉(zhuǎn)發(fā)功能分離，簡(jiǎn)化傳輸?shù)囊幌盗羞^(guò)程，從而大大提高了網(wǎng)絡(luò)的傳輸效率#65377;目前的計(jì)算機(jī)網(wǎng)絡(luò)在網(wǎng)絡(luò)的核心部分基本上采用基于虛電路的ATM，或具有穩(wěn)定路徑的MPLS，或電信專線#65377;根據(jù)研究，網(wǎng)絡(luò)在一段時(shí)間內(nèi)的狀態(tài)是相對(duì)穩(wěn)定的[7]#65377;一個(gè)從源端到目的端的數(shù)據(jù)流分組基本上穿過(guò)一系列比較固定的鏈路和網(wǎng)絡(luò)設(shè)備#65377;通過(guò)深入研究穩(wěn)定路徑的特點(diǎn)發(fā)現(xiàn)，使用原始的滑動(dòng)窗口協(xié)議存在著不必要的丟包以及分組延時(shí)過(guò)長(zhǎng)等問(wèn)題，因此本文對(duì)滑動(dòng)窗口協(xié)議進(jìn)行了有效的改進(jìn)#65377;CPN[8]是從Petri網(wǎng)演化而來(lái)的，在系統(tǒng)建模#65380;計(jì)算機(jī)軟件技術(shù)#65380;自動(dòng)控制系統(tǒng)#65380;網(wǎng)絡(luò)通信協(xié)議工程等得到了廣泛的應(yīng)用#65377;

1穩(wěn)定路徑的數(shù)據(jù)傳輸方式

穩(wěn)定路徑數(shù)據(jù)傳輸方式與傳統(tǒng)的IP數(shù)據(jù)報(bào)傳輸方式不同#65377;傳統(tǒng)數(shù)據(jù)報(bào)方式在發(fā)送數(shù)據(jù)之前，不預(yù)先確定轉(zhuǎn)發(fā)路徑，而是在轉(zhuǎn)發(fā)的每一跳各個(gè)數(shù)據(jù)報(bào)獨(dú)立尋找路徑#65377;這種方式使得同一通信流的數(shù)據(jù)報(bào)在轉(zhuǎn)發(fā)過(guò)程中可能經(jīng)過(guò)不同的轉(zhuǎn)發(fā)路徑#65377;因此，數(shù)據(jù)報(bào)到達(dá)目的地的順序與發(fā)送順序可能不一致#65377;數(shù)據(jù)報(bào)方式的數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程如圖1所示#65377;P1和P2是同一通信流先后發(fā)送的兩個(gè)數(shù)據(jù)報(bào)，它們的傳輸路徑不同，因此到達(dá)Hb時(shí)可能失序#65377;

與數(shù)據(jù)報(bào)方式不同，穩(wěn)定路徑方式在發(fā)送數(shù)據(jù)之前，需要建立穩(wěn)定的數(shù)據(jù)傳輸路徑，如ATM的虛電路和MPLS的LSP等#65377;同一數(shù)據(jù)流的分組在轉(zhuǎn)發(fā)過(guò)程中不再逐跳尋找，而是根據(jù)包頭的路徑信息沿著預(yù)先建立好的穩(wěn)定路徑傳送到目的地#65377;分組到達(dá)目的地的順序與發(fā)送順序是一致的，不會(huì)發(fā)生失序分組#65377;穩(wěn)定路徑方式的數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程如圖2所示#65377;Ha到Hb之間預(yù)先建立起了一條固定路徑，分組P1和P2均沿著這條路徑發(fā)送到Hb，因此到達(dá)Hb時(shí)P1與P2的順序保持不變#65377;

2RDTSP協(xié)議描述

2.1RDTSP協(xié)議的基本思想

基于穩(wěn)定路徑的數(shù)據(jù)傳輸如果直接使用傳統(tǒng)的滑動(dòng)窗口機(jī)制，則存在著網(wǎng)絡(luò)利用率低下的問(wèn)題#65377;這是因?yàn)樵诜€(wěn)定路徑的數(shù)據(jù)傳輸過(guò)程中，只要分組不丟失，就不會(huì)出現(xiàn)失序分組;接收方只要收到失序的分組，就可以判斷出有分組丟失了#65377;若直接使用傳統(tǒng)的滑動(dòng)窗口機(jī)制，那么接收方即使知道分組丟失了，也不能通知發(fā)送方重傳，而必須等到發(fā)送方的重傳定時(shí)器溢出后才重傳丟失的分組#65377;以一個(gè)三位滑動(dòng)窗口的接收窗口(圖3)為例分析存在的問(wèn)題#65377;

該接收窗口下界為3，上界為6#65377;此時(shí)接收方希望收到3#分組，卻收到了4#分組，接著又收到了5##65380;6#分組#65377;因?yàn)槭盏降倪@三個(gè)分組均在接收窗口內(nèi)，所以被接收方接收了#65377;接收方又陸續(xù)收到了7##65380;0#分組#65377;由于3#分組一直沒(méi)有收到，接收窗口不能向前滑動(dòng)，而剛收到的7#和0#分組不在接收窗口內(nèi)，將它們丟棄#65377;當(dāng)發(fā)送方超時(shí)定時(shí)器溢出后，發(fā)送方才重傳3#分組;收到3#分組后，接收窗口向前滾動(dòng)，可以繼續(xù)接收7##65380;0#分組#65380;……#65377;

從上面的例子可以看到，如果直接采用傳統(tǒng)的滑動(dòng)窗口機(jī)制，即使接收方知道3#分組丟失，也不能通知發(fā)送方重傳，而必須等到發(fā)送方的重傳定時(shí)器溢出，導(dǎo)致接收窗口遲遲不能向前滾動(dòng)，只好丟棄窗口外的7#和0#分組#65377;這樣不但降低了網(wǎng)絡(luò)吞吐量，而且增加了數(shù)據(jù)報(bào)的傳輸時(shí)延#65377;

基于穩(wěn)定路徑的改進(jìn)滑動(dòng)窗口協(xié)議與傳統(tǒng)的滑動(dòng)窗口協(xié)議的主要不同在于:接收方可以根據(jù)分組序號(hào)判斷出是否有分組丟失，一旦有分組丟失，則立即通知發(fā)送方重傳，而不需要等到發(fā)送方重傳定時(shí)器溢出才重傳#65377;這樣，在圖3中就可以快速重傳3#分組，滑動(dòng)窗口可以快速向前移動(dòng)，因而不必丟棄7#和0#分組，避免了7#和0#分組的重傳#65377;這樣避免了網(wǎng)絡(luò)資源的浪費(fèi)，同時(shí)減少了數(shù)據(jù)報(bào)傳輸時(shí)延#65377;

2.2改進(jìn)的滑動(dòng)窗口協(xié)議描述

1)發(fā)送窗口算法用Low表示發(fā)送窗口當(dāng)前的下界值;High表示發(fā)送窗口當(dāng)前的上界值;N表示發(fā)送窗口的容量，如三位滑動(dòng)窗口N=23即N=8#65377;發(fā)送窗口與接收窗口容量相同，均為N#65377;

Num=High-Low;

發(fā)送Num個(gè)PACKET;

啟動(dòng)定時(shí)器;

When接收到ACK DO

{ j=ACK序列號(hào);

if j在發(fā)送窗口中

{ if j<>i

i=(j+1) mod N;

發(fā)送PACKETi;

else 

i=(i+1) mod N;

發(fā)送 PACKETi

}

}

When定時(shí)器超時(shí)

{ 重傳 PACKETi;

重新啟動(dòng)定時(shí)器;

}

2)接收窗口算法用Low表示接收窗口當(dāng)前的下界值;High表示接收窗口當(dāng)前的上界值;N表示接收窗口的容量#65377;

If有PACKET準(zhǔn)備發(fā)送

捎帶ACK;

When接收到 PACKET

{ j=PACKET的序號(hào);

If j不在接收窗口中 

{ m=(i-1)mod N;

發(fā)送 ACKm;

}

Else if j<>i

{ 接收 PACKETj;

m=(i-1) mod N;

發(fā)送 ACKm;

}

Else 

{ 接收PACKETj;

m=接收窗口中與I相鄰的區(qū)域最大序號(hào)值;

發(fā)送ACKm;

}

i=(m+1)mod N;

}

3RDTSP協(xié)議的CPN模型

RDTSP協(xié)議CPN模型如圖4所示#65377;模型包括三個(gè)部分，即發(fā)送方#65380;接收方和傳輸數(shù)據(jù)的信道#65377;發(fā)送方包括兩個(gè)位置，即S_win和NextSend以及兩個(gè)變遷SendData和ReceiveAck#65377;接收方包括一個(gè)位置R_win和一個(gè)變遷ReceiveData#65377;信道包括兩個(gè)位置DataChannel和AckChannel#65377;

模型的左邊描述發(fā)送方行為#65377;位置S_win表示發(fā)送窗口的狀態(tài)，它的初始標(biāo)志是1′(0，1)，表示會(huì)話開(kāi)始時(shí)發(fā)送窗口的下界是0，上界是1#65377;位置NextSend表示發(fā)送方發(fā)送的下一個(gè)分組序號(hào)，由ACK的值和當(dāng)前發(fā)送窗口共同決定#65377;位置NextSend的初始標(biāo)志是1′0，表示發(fā)送方發(fā)送的第一個(gè)分組是0#分組#65377;變遷SendData將分組發(fā)送到信道上，并且返回下一個(gè)發(fā)送分組的序號(hào)#65377;變遷ReceiveAck從信道接收ACK，接著改變滑動(dòng)窗口上#65380;下界，并且返回即將發(fā)送的下一個(gè)分組的序號(hào)#65377;

模型的右邊描述接收方行為#65377;位置R_win表示接收窗口的狀態(tài)，它的初始標(biāo)志是1′(0，1)，表示會(huì)話開(kāi)始時(shí)接收窗口可以接收0#和1#分組#65377;變遷ReceiveData從信道接收分組，接著改變接收窗口，并且向信道發(fā)送ACK#65377;

模型信道部分包括兩個(gè)位置#65377;位置DataChannel的token值表示正在從發(fā)送方向接收方傳輸?shù)姆纸M序列號(hào);位置AckChannel的token值表示正在從接收方向發(fā)送方傳輸?shù)腁CK包序列號(hào)#65377;

4狀態(tài)空間分析

CPN tools提供的一個(gè)重要工具就是狀態(tài)空間分析工具#65377;通過(guò)狀態(tài)空間報(bào)告可以對(duì)系統(tǒng)的有界性(boundedness)#65380;回歸性(home)#65380;活性(liveness)以及公平性(fairness)進(jìn)行分析#65377;表1列出了基于穩(wěn)定路徑的可靠數(shù)據(jù)傳輸協(xié)議CPN模型狀態(tài)空間分析的部分報(bào)告#65377;

表1中第一列描述了狀態(tài)空間的統(tǒng)計(jì)信息#65377;數(shù)據(jù)顯示，本模型的狀態(tài)空間包括562個(gè)節(jié)點(diǎn)和1 538條弧;生成狀態(tài)空間所用的時(shí)間不到1 s，狀態(tài)空間是完整的#65377;第二列描述了狀態(tài)空間的活性#65377;本模型沒(méi)有死標(biāo)志和死變遷，所有變遷均是活的#65377;當(dāng)發(fā)送數(shù)據(jù)序列號(hào)為滑動(dòng)窗口上界時(shí)，發(fā)送方繼續(xù)發(fā)送序

列號(hào)為滑動(dòng)窗口下界的數(shù)據(jù)，這是一個(gè)不中斷的循環(huán)發(fā)送過(guò)

程#65377;第三列表明所有標(biāo)志均是回歸標(biāo)志#65377;整個(gè)傳輸過(guò)程是一個(gè)循環(huán)過(guò)程，經(jīng)過(guò)若干步后總會(huì)回到當(dāng)前標(biāo)志#65377;以上報(bào)告顯示，基于穩(wěn)定路徑的可靠數(shù)據(jù)傳輸協(xié)議是完全正確#65380;可靠的，滿足系統(tǒng)的有界性#65380;回歸性以及活性等方面的要求#65377;

5結(jié)束語(yǔ)

本文在研究了穩(wěn)定路徑的數(shù)據(jù)傳輸方式的特點(diǎn)后，提出了一種基于穩(wěn)定路徑的可靠數(shù)據(jù)傳輸協(xié)議，通過(guò)快速重傳丟失報(bào)文，避免了大量冗余的數(shù)據(jù)重傳，提高了網(wǎng)絡(luò)傳輸效率#65377;通過(guò)對(duì)本模型的建模仿真，驗(yàn)證了使用改進(jìn)的滑動(dòng)窗口協(xié)議確實(shí)能夠?qū)崿F(xiàn)穩(wěn)定路徑的可靠數(shù)據(jù)傳輸，驗(yàn)證了該協(xié)議的正確性#65380;可行性和完備性#65377;

參考文獻(xiàn):

[1]JACOBSON V. Congestion avoidance and control[J]. ACM Computer Communication Review， 1988，18(4):314-329.

[2]RFC 2001， TCP slow start， congestion avoidance， fast retransmit， and fast recovery algorithms[S]. 

[3]RFC 2018， TCP selective acknowledgement options[S].

[4]BRAKMO L S， PETERSON L L. TCP Vegas: endtoend congestion avoidance on a global Internet[J]. IEEE Journal on Selected Areas in Communications， 1995，13(8):14651480.

[5]TOBAGI F A. Fast packet switch architectures for broadband integrated services digital network[C]//Proc of the IEEE. 1990:133167.

[6]RFC 3031， Multiprotocol label switching architecture[S].

[7]PAXSON V. Measurements and analysis of endtoend Internet dynamics[D]. Berkeley: UC Berkeley， 1996:25-58.

[8]JENSEN K. Coloured Petri nets: basic concepts， analysis methods and practical use volume 1: basic concepts[M]. Germany:SpringerVerlag， 1992:29-51.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”