OBS考慮優先級的突發包碎片可控合并重傳算法

陳荷荷

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

引 言

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

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

作者在第一部分將詳細介紹目前國內外對于如何降低突發包的丟包率問題的研究現狀和存在的不足，進而提出新算法;在第二部分將對新算法模型進行詳細的敘述并分析;在第三部分對新算法進行仿真驗證，進而提出新算法在改善網絡性能方面優于其它算法的證據;在第四部分對新算法進行總結。

1 算法背景

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

2BSRCR算法介紹

2．1 BSRCR算法模型

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

Fig.1 Principle diagram of BSRCR

2．2 BSRCR算法模型分析

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

Fig.2 Flow diagram of BSRCR

算法詳細描述如下。

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

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

Fig.3 Contention occurred when the recombinant burst retransmit

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

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

即:

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

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

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

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

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

即:

3 仿真說明

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

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

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上，針對不同的重傳概率，突發數據業務的字節丟失率情況。仿真了4 組數據，分別是當 α1j=0．3，α1j=0．5，α1j=0．7和 α1j=0．9時的數據情況，同時滿足 αij=0．8α(i-1)j(其中，i=2，3;j=1，2，3)。可以觀察到，這4組數據都反映了隨著網絡中業務量的增大，突發包的字節丟失率也在增大。同時，在相同的數據業務量情況下，當業務的重傳概率越大，那么該突發數據包的比特丟失率也較低。從中可以得出結論，對于網絡中優先級比較高地業務，當發生不可避免的沖突時，若適當地增加它的重傳概率，可以大大降低其丟字節率，這樣可以保證高優先級業務的順利通過。

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

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

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

4 結論

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

［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，FU 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).