OBS考慮優(yōu)先級的突發(fā)包碎片可控合并重傳算法

陳荷荷

(溫州職業(yè)技術(shù)學院電子電氣工程系，溫州325000)

引 言

伴隨著密集波分復用(dense wavelength division multiplexing，DWDM)技術(shù)的發(fā)展［1-2］，單根光纖的傳播速度已經(jīng)達到了Tbit/s級，光纖通信已然成為未來全光網(wǎng)絡(luò)通信技術(shù)的主要載體。而光交換技術(shù)作為全光網(wǎng)絡(luò)通信技術(shù)的一個關(guān)鍵技術(shù)，越來越受到國內(nèi)外很多研究機構(gòu)和學者的高度重視，已經(jīng)成為現(xiàn)代光網(wǎng)絡(luò)研究的一個重要領(lǐng)域［3］。目前較主流的光交換技術(shù)主要有以下3種方案:光電路交換(optical circuit switching，OCS)、光分組交換(optical packet switching，OPS)和光突發(fā)交換(optical burst switching，OBS)［4］。OCS 技術(shù)是一種面向連接的交換方式，其交換粒度大，帶寬利用率不高，并不是現(xiàn)在主流的光交換技術(shù)。OPS技術(shù)實一種不面向連接的交換方式，在進行數(shù)據(jù)傳輸前不需要建立路由、分配資源，相比OCS，OPS技術(shù)具有很高的資源利用率和較強的適應突發(fā)數(shù)據(jù)的能力，但是它對光器件的要求非常高，多個分組的精確同步的技術(shù)難點實現(xiàn)比較困難。

QIAO等人提出了一種全新的光交換技術(shù)OBS，作為OCS到OPS的過渡技術(shù)，OBS技術(shù)結(jié)合了兩者的優(yōu)點，交換粒度適中、難度適中、靈活性強、網(wǎng)絡(luò)帶寬資源利用率高，被譽為是未來光網(wǎng)絡(luò)中最有前途的光交換技術(shù)［4］。當網(wǎng)絡(luò)中的數(shù)據(jù)到達邊緣節(jié)點時，節(jié)點將數(shù)據(jù)按照一定的匯聚算法組裝成一個突發(fā)數(shù)據(jù)包(burst data packet，BDP)，并為此數(shù)據(jù)包產(chǎn)生一個突發(fā)控制分組(burst control packet，BCP)，OBS通過預先發(fā)送BCP，來為數(shù)據(jù)包單向預留資源，從而使突發(fā)數(shù)據(jù)包能夠透明地通過各個核心節(jié)點，提高了網(wǎng)絡(luò)傳送的效率［5］。從OBS的傳輸原理可見，這種資源預留機制是單向的，當網(wǎng)絡(luò)有多個邊緣節(jié)點同時向某核心節(jié)點的同一端口、同一波長發(fā)送數(shù)據(jù)時，就有可能造成多個資源競爭同一條鏈路資源，從而造成了數(shù)據(jù)的沖突［6］。如何降低丟包率、提高網(wǎng)絡(luò)的性能，成為了目前光交換網(wǎng)絡(luò)的研究熱點。

作者在第一部分將詳細介紹目前國內(nèi)外對于如何降低突發(fā)包的丟包率問題的研究現(xiàn)狀和存在的不足，進而提出新算法;在第二部分將對新算法模型進行詳細的敘述并分析;在第三部分對新算法進行仿真驗證，進而提出新算法在改善網(wǎng)絡(luò)性能方面優(yōu)于其它算法的證據(jù);在第四部分對新算法進行總結(jié)。

1 算法背景

在OBS網(wǎng)絡(luò)中，當網(wǎng)絡(luò)資源發(fā)生競爭時，傳統(tǒng)解決沖突的方法主要有光緩存法［7］、波長轉(zhuǎn)換法［8］和偏射路由法［9］，這些方法在一定程度上能改善網(wǎng)絡(luò)丟包率，但是各自仍有著無法彌補的缺點。另有學者提出，可將沖突的突發(fā)包丟棄，這種方法實現(xiàn)比較簡單，但是它比較容易帶來較大的丟包率?；谝陨峡紤]，有研究者提出光組合突發(fā)交換技術(shù)(optical composite burst switching，OCBS)［10］，此算法考慮將突發(fā)包分段丟棄的策略，將沖突的數(shù)據(jù)包進行頭尾分割，丟棄部分，這種方法能夠降低網(wǎng)絡(luò)的丟包率。但是研究發(fā)現(xiàn)，網(wǎng)絡(luò)的負載有時候并不是平穩(wěn)的，在某一時刻它負載非常重，這個時候采用突發(fā)包的分段丟棄策略，丟棄了大量的競爭包，但是在下一時刻，網(wǎng)絡(luò)負載可能就比較輕，這樣就浪費了網(wǎng)絡(luò)資源，并且分段丟棄策略通常沒有考慮到突發(fā)包的優(yōu)先級，這樣對于很多實際的基于服務質(zhì)量(quality of service，QoS)的業(yè)務來講是不利的［11］。又有學者在此基礎(chǔ)上提出了一種基于優(yōu)先級的先分割后緩存沖突解決算法(priority-based burst segmentation-optical buffer contention resolution，PBSCR)［12］，此算法考慮了突發(fā)包的優(yōu)先級，將分割突發(fā)包進行光緩存處理，從而保證了高優(yōu)先級突發(fā)包的低丟包率。但是這種算法引入了光緩存處理，使突發(fā)包碎片一直游離在網(wǎng)絡(luò)路徑中，極容易造成網(wǎng)絡(luò)路徑的阻塞，使信道的利用率下降。還有學者提出了突發(fā)包丟棄并重傳策略(burst abandon and retransmission，BAR)，對于產(chǎn)生競爭的突發(fā)包采用丟棄之后，在中心節(jié)點會往突發(fā)包匯聚的邊緣節(jié)點處發(fā)送一個確認字符信號，告知邊緣節(jié)點該突發(fā)包已經(jīng)被丟棄，與此同時邊緣節(jié)點重新發(fā)送一個該突發(fā)包的副本，這種策略在一定程度上可以降低丟包率，但是此算法沒有考慮業(yè)務的優(yōu)先級等級，并且每次都采用重傳整個突發(fā)包的方案，當網(wǎng)絡(luò)負載比較大時，這種重傳方案反而會增大沖突產(chǎn)生的概率，從而增大數(shù)據(jù)在核心節(jié)點的阻塞率，并且在一個支持QoS的OBS網(wǎng)絡(luò)，并不需要重傳所有的被丟棄的突發(fā)包［13］，這種算法使得網(wǎng)絡(luò)傳送數(shù)據(jù)的效率低下。在此基礎(chǔ)上，作者提出了一種新型的考慮優(yōu)先級的突發(fā)包碎片可控合并重調(diào)度算法(burst-segment recombination and controllable retransmission algorithm based on priority，BSRCR)。

2BSRCR算法介紹

2．1 BSRCR算法模型

BSRCR算法的模型如圖1所示，當突發(fā)包在核心節(jié)點發(fā)生沖突時，根據(jù)突發(fā)包的優(yōu)先級采用分段丟棄的策略，當分片結(jié)束后，目的核心節(jié)點會發(fā)送一個反饋信息給邊緣匯聚節(jié)點。假設(shè)在某一時刻Ti，鏈路中有散落的n個突發(fā)包碎片，這些突發(fā)包碎片有自己的重傳概率，分別為 αi1，αi2，…，αin。規(guī)定優(yōu)先級較高的碎片的重傳概率較高，這里假設(shè)αi1＞αi2＞…＞αin，即1號碎片的優(yōu)先級最高，2號碎片次之，n號碎片優(yōu)先級最低。當網(wǎng)絡(luò)業(yè)務較為繁忙時，由于重傳的碎片數(shù)目繁多，就有可能會造成網(wǎng)絡(luò)通信的阻塞，所以在邊緣節(jié)點處，設(shè)計一個突發(fā)包碎片重組裝機制，此機制采用混合優(yōu)先級的方式，在組裝時，將優(yōu)先級高的碎片盡量往中間靠，優(yōu)先級低的碎片依次往兩邊放，這樣能很好地保證高優(yōu)先級業(yè)務的順利通過，并且也盡可能地保證低優(yōu)先級的通過。

Fig.1 Principle diagram of BSRCR

2．2 BSRCR算法模型分析

由于基于突發(fā)包粒度的整包重傳方案已經(jīng)不適用于分段重傳的描述方法，在描述突發(fā)數(shù)據(jù)丟失率時，采用字節(jié)丟失率(byte-loss probability，BLP)代替包丟失率作為衡量網(wǎng)絡(luò)的性能指標。算法的流程圖按照圖2所示。

Fig.2 Flow diagram of BSRCR

算法詳細描述如下。

(1)信息反饋階段:在時刻Ti，邊緣節(jié)點向核心節(jié)點發(fā)送數(shù)據(jù)包時，因為發(fā)生資源競爭，采用突發(fā)包分片的策略，優(yōu)先級較高的突發(fā)包順利傳送到核心節(jié)點處，優(yōu)先級較低或者競爭無法處理的突發(fā)包碎片因此被丟棄，這些突發(fā)包的碎片為1號，2號，…，n號突發(fā)包，優(yōu)先級按照數(shù)字的變大而降低。同時，核心節(jié)點向邊緣節(jié)點發(fā)送一個反饋信息，要求邊緣節(jié)點以一定的重傳概率重傳這些被丟棄的突發(fā)包碎片，重傳概率分別為 αi1，αi2，…，αin，重傳概率的設(shè)定根據(jù)網(wǎng)絡(luò)的業(yè)務擁擠程度和突發(fā)包的優(yōu)先級綜合決定，通常優(yōu)先級較高的，重傳概率較大。

(2)突發(fā)包碎片重組階段:當邊緣節(jié)點收到反饋信息，得到的需要重傳的突發(fā)包碎片過多時，邊緣節(jié)點就開始進行突發(fā)包碎片的重組。為了方便描述，假設(shè)每次突發(fā)包碎片重組的個數(shù)最多3個，優(yōu)先級編號為1，2，3，其中，1號為最高優(yōu)先級，2號為次高優(yōu)先級，3號為最低優(yōu)先級，重傳概率滿足αi0＞αi1＞αi2。為了保證高優(yōu)先級業(yè)務的順利重傳，在混合重組時，將優(yōu)先級高的突發(fā)包碎片放在中間，優(yōu)先級低得碎片放在兩邊，即如圖3所示的組包方式，那么在時刻Ti+1重組包成功的概率為:

Fig.3 Contention occurred when the recombinant burst retransmit

(3)可控重傳階段:假設(shè)重組包成功的突發(fā)包以概率1進行發(fā)送，那么重組包在時刻Ti+1由邊緣節(jié)點以概率重新發(fā)送，重發(fā)的情況如圖3所示分情況討論。當出現(xiàn)圖3a所示時，兩個重組突發(fā)數(shù)據(jù)包(data burst，DB)DB1和DB2發(fā)生沖突，那么將DB1的尾部發(fā)生分片，并根據(jù)它的重傳概率進行重傳。當發(fā)生如圖3b中的情況，DB2的尾部發(fā)生分片，并重傳。

用r來表示網(wǎng)絡(luò)中源節(jié)點和目的節(jié)點之間的一條最優(yōu)路徑，用ηr，i表示路徑r上Ti時刻較高優(yōu)先級的突發(fā)包碎片的離開率，θr，i表示路徑 r上 i時刻的突發(fā)包阻塞率。那么根據(jù)流量守恒定律，時刻i上，源節(jié)點中需要重新組包重傳的突發(fā)包碎片增長率等于目的節(jié)點突發(fā)包的成功離開率，則有:

即:

則突發(fā)包在路徑r上i時刻的離開率為:

λr，0表示路徑r上突發(fā)包在源節(jié)點的到達率，那么，路徑r上，從0時刻到i時刻這一段時間的突發(fā)包總到達率 λr，i可以表示為:

用Lr，ij(t)表示在i時刻、路徑r上的第j個突發(fā)包碎片的分布長度，那么:

同時，i時刻、路徑r上的組合突發(fā)包總碎片長度為:

用Gr，i(t)表示在 i時刻、路徑r上的組合突發(fā)包的總分布長度，那么:

即:

3 仿真說明

系統(tǒng)的仿真環(huán)境OBS-NS搭建在開源的NS-2平臺上，NS版本為2.28，采用的操作系統(tǒng)是開源的linux操作系統(tǒng)。仿真的網(wǎng)絡(luò)拓撲采用美國國家科學基金會網(wǎng)絡(luò)，它包含14個節(jié)點，21條雙向傳輸鏈路。選用的路徑r包含1個入口邊緣節(jié)點、1個出口邊緣節(jié)點、3個核心節(jié)點。為了簡化仿真過程，作者在系統(tǒng)中做如下約定:每條光鏈路包含16個數(shù)據(jù)信道和1條控制信道，每個數(shù)據(jù)信道的傳輸速率為10Gbit/s，邊緣節(jié)點數(shù)據(jù)流按照Poisson過程隨機到達，網(wǎng)絡(luò)負載采用歸一化處理，匯聚算法采用固定長度匯聚算法，網(wǎng)絡(luò)互聯(lián)協(xié)議(internet protocol，IP)包的平均長度為1250byte，突發(fā)數(shù)據(jù)包到達平均間隔是0.0001s，假設(shè)信道之間轉(zhuǎn)發(fā)延時是0.0001s，仿真開始時間是0s，結(jié)束時間是2s，假設(shè)突發(fā)包碎片重傳的次數(shù)為3，即i≤3，每次重組合的最大包數(shù)為3，即j≤3。對于重傳概率，假設(shè)一個突發(fā)包的重傳概率是隨著重傳次數(shù)的增加而減少，令 αij=0．8α(i-1)j(其中i=2，3;j=1，2，3)。

圖4～圖7中給出了算法的仿真結(jié)果，圖中對橫坐標的業(yè)務負載量和縱坐標的比特丟失率、網(wǎng)絡(luò)阻塞率均做歸一化處理。

Fig.4 Byte loss probability of BSRCR with different retransmit probability when traffic load changes

Fig.5 Byte loss probability of BSRCR，OCBS and BAR when traffic load changes

Fig.6 Path blocking probability of BSRCR with different retransmit probability when traffic load changes

Fig.7 Path blocking probability of BSRCR，OCBS and BAR when traffic load changes

圖4 中給出了BSRCR算法在路徑r上，針對不同的重傳概率，突發(fā)數(shù)據(jù)業(yè)務的字節(jié)丟失率情況。仿真了4 組數(shù)據(jù)，分別是當 α1j=0．3，α1j=0．5，α1j=0．7和 α1j=0．9時的數(shù)據(jù)情況，同時滿足 αij=0．8α(i-1)j(其中，i=2，3;j=1，2，3)?？梢杂^察到，這4組數(shù)據(jù)都反映了隨著網(wǎng)絡(luò)中業(yè)務量的增大，突發(fā)包的字節(jié)丟失率也在增大。同時，在相同的數(shù)據(jù)業(yè)務量情況下，當業(yè)務的重傳概率越大，那么該突發(fā)數(shù)據(jù)包的比特丟失率也較低。從中可以得出結(jié)論，對于網(wǎng)絡(luò)中優(yōu)先級比較高地業(yè)務，當發(fā)生不可避免的沖突時，若適當?shù)卦黾铀闹貍鞲怕?，可以大大降低其丟字節(jié)率，這樣可以保證高優(yōu)先級業(yè)務的順利通過。

圖5中給出了隨著網(wǎng)絡(luò)中業(yè)務量的增加，BSRCR算法、OCBS算法、BAR算法的比特丟失率比較，這里BSRCR的業(yè)務重傳概率選取α1j=0．5，從圖5中可以觀察到，在開始網(wǎng)絡(luò)業(yè)務量較小時，BRCR算法的突發(fā)包比特丟失率最小，而BSRCR和OCBS的丟比特率比較接近，但是隨著網(wǎng)絡(luò)業(yè)務的逐漸增大，BRCR算法的比特丟失率呈現(xiàn)比較大的上升率，而OCBS算法次之，BSRCR的丟比特率對于業(yè)務的增加呈現(xiàn)了較好的適應性，增加的趨勢較為緩慢。這是因為BSRCR采用了新型的可控合并重調(diào)度算法，當網(wǎng)絡(luò)業(yè)務較為繁忙時，它會綜合考慮此時網(wǎng)絡(luò)業(yè)務的負載情況和突發(fā)包的優(yōu)先程度，需要選擇合適的重傳概率，并將網(wǎng)絡(luò)中過多的突發(fā)包碎片進行合適的重組包算法，這樣也減少了重發(fā)時的路徑阻塞情況，提高了重發(fā)的成功概率。

圖6反映的是BSRCR針對不同的重傳概率，突發(fā)數(shù)據(jù)業(yè)務在路徑r上的阻塞率。從圖6中可知，在相同的業(yè)務量情況下，越高的重傳概率帶來了相對較大的網(wǎng)絡(luò)阻塞率，并且，隨著網(wǎng)絡(luò)中業(yè)務量的增加，路徑的阻塞率會逐漸增加，但是當業(yè)務量增加到一定程度，由于BSRCR采用了突發(fā)碎片重組裝辦法，網(wǎng)絡(luò)路徑的阻塞率反而會呈現(xiàn)一定的下降趨勢，這對于高重傳概率帶來的高阻塞率有非常好的調(diào)節(jié)作用。

圖7中給出了不同業(yè)務量情況下，BSRCR算法、OCBS算法、BAR算法的網(wǎng)絡(luò)阻塞率比較，這里BSRCR的業(yè)務重傳概率選取α1j=0．5，從圖7中可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)負載的增加，BAR由于采取了突發(fā)包重傳策略，會更加加重網(wǎng)絡(luò)的阻塞率，而OCBS算法對于發(fā)生競爭的突發(fā)包采取直接丟棄的措施，故對于網(wǎng)絡(luò)的阻塞率的影響較為平緩，而采用的BSRCR算法對于業(yè)務的阻塞率介于BRCR算法和OCBS算法中間。

4 結(jié)論

提出了一種考慮優(yōu)先級的可控合并重調(diào)度算法BSRCR。當OBS網(wǎng)絡(luò)中突發(fā)包因為競爭網(wǎng)絡(luò)資源而發(fā)生沖突時，該算法采用基于優(yōu)先級的突發(fā)包分片辦法，同時，目的節(jié)點向邊緣節(jié)點發(fā)送一個反饋信息，使得邊緣節(jié)點以一定的概率重傳該突發(fā)包分片。該重傳概率根據(jù)網(wǎng)絡(luò)的復雜情況和突發(fā)包分片的優(yōu)先級動態(tài)決定，并針對由于重發(fā)的突發(fā)包碎片過多、而使得網(wǎng)絡(luò)路徑阻塞率過大的問題，采用突發(fā)包碎片進行一定優(yōu)先等級排列的碎片重組，這樣減少了網(wǎng)絡(luò)中突發(fā)包碎片的數(shù)量，大大降低了網(wǎng)絡(luò)的路徑堵塞率，并保證了高優(yōu)先級業(yè)務的順利傳送。在仿真部分中，給出了BSRCR算法在路徑r上，針對不同的重傳概率，突發(fā)數(shù)據(jù)業(yè)務的字節(jié)丟失率情況和業(yè)務阻塞情況，仿真結(jié)果對設(shè)定重傳概率、突發(fā)碎片重組包方案、及業(yè)務優(yōu)先級等方面提供了一定的參考意義。同時，還給出了不同業(yè)務量情況下，BSRCR算法、OCBS算法、BAR算法的比特丟失情況和網(wǎng)絡(luò)業(yè)務阻塞情況比較，仿真結(jié)果證實，對于業(yè)務負載比較大的情況，BSRCR算法在比特丟失率方面較之OCBS算法和BAR算法，有很好的表現(xiàn)。在不同業(yè)務情況下，在網(wǎng)絡(luò)阻塞率的改善方面，BSRCR算法介于BRCR算法和OCBS算法之間，但是其對業(yè)務比特丟失率方面的改善，這點阻塞率方面的犧牲是值得的。

［1］ BERGMAN L A，YEH C，MOROOKIAN J.Advances in multichannel multi Gbytes/s bit-parallel WDM single fiber link［J］.IEEE Transactions on Advanced Packaging，2001，24(4):456-462.

［2］ ZHAO T F，WANG W K，LIU L.A preferential shared path protection algorithm for WDM optical network［J］.Laser Technology，2012，36(3):408-412(in Chinese).

［3］ WANG B Y，GUAN A H，ZHANG Y，et al.A preemption window mechanism based on priority in E-OBS networks［J］.Laser Technology，2011，35(4):531-534(in Chinese).

［4］ QIAO Ch M，YOO M.Optical burst switching-a new paradigm for an optical internet［J］.Journal of High Speed Networks，Special Issue on Optical Networks，1999，8(1):69-84.

［5］ WANG B Y，GUAN A Y，ZHANG Y，et al.A deflection routing algorithm based on priority and load-balancing in optical burst switching networks［J］.Laser Technology，2011，35(3):343-347(in Chinese).

［6］ QIAO C.Labeled optical burst switching for IP-over-WDM integra-tion［J］.IEEE Communication Magazine，2000，38(9):104-114.

［7］ HOU R.Performance analysis of an improved burst outputted scheme in a limited buffer equipped OBS core node［J］.Optik-International Jouranl for Light and Electron Optics，2012，123(5):400-403.

［8］ YAO M，WEN A，LIU Z.Blocking probability of asynchronous optical burst/packet switches with limited range wavelength conversion［J］.IEEE Photonics Technology Letters，2006，18(12):1302-1304.

［9］ BALIGA J，WONG E W M，ZUKERMAN M.Analysis of bufferless OBS/OPS networks with multiple deflections［J］.IEEE Communication Letters，2009，13(12):974-976.

［10］ DETTI A，ERAMO V，LISTANTI M.Performance evaluation of a new technique for IP support in a WDM optical network:optical composite burst switching(OCBS)［J］.IEEE Journal of Lightwave Technology，2002，20(2):154-165.

［11］ HOU R，SUN J Q，DING P F.Study on a priority based contention resolution for optical burst switching networks［J］.Journal of Electronics＆ Information Technology，2006，28(4):747-752(in Chinese).

［12］ GUAN A H，WANG B Y，F(xiàn)U H L.A burst segmentation-optical buffer contention resolution mechanism based on priority in OBS networks［J］.Journal of Optoelectronics·Laser，2012，23(2):273-279(in Chinese).

［13］ LOU X，NING F，GAO Z H.ACK retransmission scheme on TCP over OBS networks［J］.Optical Communication Technique，2008，10(4):21-24(in Chinese).