OBS基于回退和信道分級的沖突解決算法

李敏濤，陳荷荷，章曉春

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

引 言

隨著波分復用技術的發(fā)展，光網絡傳輸能力也大幅度地得到了提升，但是光網絡中節(jié)點的路由交換能力卻沒有得到同步提高，這已成為當前光網絡傳輸?shù)钠款i。目前比較主流的光交換技術主要有光電路交換(optical circuit switching，OCS)、光分組交換(optical package switching，OPS)和光突發(fā)交換(optical burst switching，OBS)。OCS技術比較成熟，但是交換的粒度比較大，帶寬利用率不高，而OPS對于光器件的要求又非常高，實現(xiàn)的成本和技術難點比較大。

OBS技術結合了OCS和OPS的優(yōu)點，規(guī)避了其技術難點，是近年來光交換技術研究的熱點［1］，有望成為下一代光網絡的核心交換技術。當網絡數(shù)據(jù)到達邊緣節(jié)點時，會根據(jù)一定的突發(fā)包匯聚算法使網絡數(shù)據(jù)組成突發(fā)數(shù)據(jù)包(burst data packet，BDP)，每一個BDP都會產生一個相應的突發(fā)控制分組(burst control packet，BCP)，BCP包含 BDP傳輸交換所必須的控制信息。網絡節(jié)點預先發(fā)送BCP，為BDP進行單向資源預留，使得BDP能夠按照預留的資源路徑進行數(shù)據(jù)的發(fā)送。有了這種資源預留機制，BDP在數(shù)據(jù)通道中傳輸時，就可以采用全光交換和傳輸，從而省略了光/電/光轉換，達到了一個較好的傳輸效果。但是這種資源預留機制是單向的，很容易造成多個突發(fā)包競爭同一條鏈路資源的情況，沖突的產生必然會導致網絡丟包率的上升，從而使得網絡的性能下降。如何降低因突發(fā)包競爭資源而造成的網絡性能的降低成為目前光突發(fā)交換研究的熱點。

1 突發(fā)包競爭解決機制研究

目前解決突發(fā)包沖突問題，無外乎有降低突發(fā)沖突的概率和降低丟包率兩種方法［2］。主流的方法主要有:光緩存、波長轉換、偏射路由和突發(fā)包分段丟棄技術等［3-4］。這些方法都能從給一定角度上緩和網絡的丟包率，但是各自仍有缺點，在網絡負擔比較重的情況下，甚至可能會帶來更多的沖突問題，從而增加了丟包率并且?guī)砹吮容^嚴重的延時［5］。

利用信道分級來解決突發(fā)包競爭問題［6］，此方法人為地將信道分為Ⅰ級信道和Ⅱ級信道，當突發(fā)包到達核心節(jié)點時，優(yōu)先選擇用Ⅰ級信道來傳輸，若Ⅰ級信道忙碌，再選擇Ⅱ級信道傳輸，如果Ⅱ級信道忙碌，則延時做轉發(fā)，如果有空余的Ⅱ級信道，則發(fā)送，否則丟棄，此方法能夠較好地進行業(yè)務優(yōu)先級的區(qū)分，Ⅰ級信道保證系統(tǒng)較低的延時性，Ⅱ級信道保證較低的丟包率［7］。

回退信道競爭解決機制(back-off channel contention resolution，BCCR)，主要思想是將鏈路中波分復用(wavelength division multiplexing，WDM)的多條信道中抽取少量作為回退信道，當發(fā)生競爭時，將突發(fā)包通過回退信道發(fā)送到上游節(jié)點，根據(jù)網絡負擔情況，重新進行路由轉發(fā)［8］。這種方法能夠有效地降低丟包率，但是其固定地占用了一部分網絡的信道作為回退資源，沒有考慮當回退信道發(fā)生競爭業(yè)務發(fā)生競爭時的處理方法，在網絡業(yè)務繁重時，反而會帶來更多的丟包率，并且這種方法并沒有很好地考慮到數(shù)據(jù)包的優(yōu)先級問題，不能很好地保證網絡的服務質量(quality of service，QoS)［9］。

2 新算法

2.1 算法的提出

針對以上的情況，作者提出了一種考慮業(yè)務優(yōu)先級的基于信道分級的帶回退業(yè)務的沖突解決算法。該算法主要包括:(1)人為地將信道分為3類信道，Ⅰ級信道主要用來傳輸優(yōu)先級較高的業(yè)務，而Ⅱ級優(yōu)先級信道用來傳輸?shù)蛢?yōu)先級業(yè)務和部分高優(yōu)先級競爭突發(fā)包轉發(fā)，回退信道(back-off channel，BC)主要用來進行競爭突發(fā)包的回退轉發(fā)，在不同的網絡負載情況下，此3類信道能進行自適應的比例配比變化;(2)對于發(fā)生競爭的突發(fā)包，作者采用分段切割，盡量轉發(fā)的思想，根據(jù)優(yōu)先級的比較來進行綜合考慮。這種算法的核心思想是最大限度地保障高優(yōu)先級的業(yè)務的傳輸特性，此外，盡量保證低優(yōu)先級業(yè)務的丟包率。

2.2 算法描述

作者定義信道類型有3類:Ⅰ級信道、Ⅱ級信道和回退信道，信道總數(shù)不變。為了方便描述，將業(yè)務類型簡單得分為高優(yōu)先級業(yè)務和低優(yōu)先級業(yè)務兩類［10］。t時刻開始標志信道分級，從該時刻開始，Ⅰ級信道只能傳送高優(yōu)先級業(yè)務，Ⅱ級信道可以傳送高優(yōu)先級和低優(yōu)先級業(yè)務。

IDC(input data channel)為輸入數(shù)據(jù)信道，ODC(output data channel)為輸出數(shù)據(jù)信道，CBDH(content burst data with high priority)為高優(yōu)先級競爭數(shù)據(jù)包，OBDH(original burst data with high priority)為高優(yōu)先級原數(shù)據(jù)包，CBDL(content burst data with low priority)為低優(yōu)先級競爭數(shù)據(jù)包，OBDL(original burst data with low priority)為低優(yōu)先級競爭數(shù)據(jù)包，BC為回退信道，Mh表示高優(yōu)先級業(yè)務的最大回退次數(shù)，用i來表示高優(yōu)先級業(yè)務回退次數(shù)的統(tǒng)計，Ml表示低優(yōu)先級業(yè)務的最大回退次數(shù)，用j來表示低優(yōu)先級回退次數(shù)的統(tǒng)計。NⅠ為Ⅰ級信道的數(shù)目，NⅡ為Ⅱ級信道的條數(shù)，NBC為回退信道的條數(shù)，N為總的信道鏈路條數(shù)。

(1)高優(yōu)先級數(shù)據(jù)包CBDH和高優(yōu)先級數(shù)據(jù)包OBDH1發(fā)生沖突。

CBDH被分段，CBDH'沿著原先預設的路線(即ODC1)繼續(xù)發(fā)送，CBDL″進行路由偏射到附近空閑的Ⅰ級信道ODC2上進行發(fā)送，如圖1a所示。若偏射路由找不到空閑的Ⅰ級信道，則偏射到回退信道，經過一個回退機制，回退到前段節(jié)點，接著再轉發(fā)到下一個節(jié)點的IDC，此時相當于延時了兩倍的傳輸節(jié)點之間的傳輸時延，這時重新進行選擇Ⅰ級信道進行數(shù)據(jù)的轉發(fā)，如圖1b所示。如果依然和各ODC上的數(shù)據(jù)發(fā)生沖突，則進入回退模式，同時計數(shù)器i++，當回退次數(shù)超過了極限，即i≥Mh時此時說明高優(yōu)先業(yè)務過于繁忙，則在第Mh+1次將CBDH″偏射到臨近的Ⅱ級信道，并將此信道標為Ⅰ級信道，NⅠ++，NⅡ--(注意:NⅡ≥1)，如圖1c所示，如果找不到，則丟棄此突發(fā)包。

(2)低優(yōu)先級數(shù)據(jù)包CBDL和高優(yōu)先級數(shù)據(jù)包OBDH發(fā)生沖突。

說明此時競爭發(fā)生在Ⅱ級信道，此時將CBDL進行分段，CBDL'沿著原先預設的信道(即ODC1)發(fā)送，被分段的CBDL″被偏射到附件空閑的ODC2上進行發(fā)送，見圖2a，若沒有合適的Ⅱ級信道轉發(fā)，則發(fā)射到回退信道，若回退信道忙碌，則直接丟棄此包，若回退信道空閑，則進入回退機制，經過突發(fā)包兩倍的傳輸時延，重新回到IDC進行下一次的轉發(fā)，見圖2b;如果回退的次數(shù)j超過了Ml，說明網絡低優(yōu)先級業(yè)務的負擔很繁重，則在第Ml+1此進行Ⅰ級信道尋找，如果找到一條合適的信道，則將此信道標為Ⅱ級信道，NⅡ++，NⅠ--，見圖2c，如果找不到，則丟棄此突發(fā)包。

(3)兩個低優(yōu)先級的突發(fā)數(shù)據(jù)包CBDL和OBDL發(fā)生沖突。

說明此時競爭發(fā)生在Ⅱ級信道，將CBDL分段成CBDL'和CBDL″，CBDL'隨著原先預設的信道資源和OBDL發(fā)送，而CBDL″則偏射路由，去尋找空閑的Ⅱ級信道，轉發(fā)此數(shù)據(jù)，如果沒有空閑的Ⅱ級信道，為了不讓低優(yōu)先級的業(yè)務過多的占用網絡資源，選擇直接丟棄。

Fig.1 Two high priority when burst conflict

Fig.2 Low priority burst and high priority burst

3 仿真說明

3.1 仿真場景

為了分析高低優(yōu)先級兩類突發(fā)包的丟包率情況，假定兩類數(shù)據(jù)以泊松分布到達核心節(jié)點［9］，高優(yōu)先級業(yè)務的到達率為λh，低優(yōu)先級的到達率為λl，總的到達率為λ。高低優(yōu)先級業(yè)務的到達時間設為τh和τl，服從指數(shù)分布。系統(tǒng)中鏈路總的條數(shù)為N，Ⅰ級信道條數(shù)為NⅠ，Ⅱ級信道條數(shù)為NⅡ，備用信道的數(shù)目用NBC來表示，那么，Ⅰ級信道可以用排隊模型M/D/NⅠ/NⅠ表示，Ⅱ級信道用M/D/NⅡ/NⅡ表示(其中，M和D表示常數(shù)，排隊模型M/D/NⅡ/NⅡ表示突發(fā)數(shù)據(jù)以泊松分布到達，系統(tǒng)服務時間為常數(shù) D，有 NⅡ個服務對象，容量為 NⅡ的模型)，則有:

概率密度為:

那么容易得出:

系統(tǒng)的仿真環(huán)境OBS-NS搭建在開源的NS-2平臺上，NS版本為2.28，采用的操作系統(tǒng)是開源UNIX操作系統(tǒng)。為了簡化仿真過程，作者在系統(tǒng)中做如下約定:每條光鏈路包含65個波長信道，其中56個為數(shù)據(jù)信道，分為Ⅰ級信道和Ⅱ級信道，初始設置Ⅱ級信道個數(shù)為28條，Ⅱ級信號個數(shù)為28條，8個作為回退信道，1個為控制信道，波長信道傳輸速率為10Gbit/s，邊緣節(jié)點數(shù)據(jù)流按照Poisson過程隨機到達，兩種優(yōu)先級的網絡負載采用歸一化處理，設高優(yōu)先的業(yè)務負載和低優(yōu)先級的業(yè)務負載為L(0≤L≤1)，匯聚算法采用固定長度匯聚算法，IP包得平均長度為1250byte，突發(fā)數(shù)據(jù)包到達平均間隔是0.0001s，假設信道之間轉發(fā)延時是0.0001s，仿真開始時間是0s，結束時間是2s。

3.2 結果分析

仿真結果如圖3所示。

圖3a表示的是在網絡負載優(yōu)先級不同的配比L下，高優(yōu)先級業(yè)務和低優(yōu)先級業(yè)務的丟包率情況，從圖中可以看出來，當網絡里高優(yōu)先級業(yè)務占主要部分時，隨著仿真時間的推移，高優(yōu)先級業(yè)務的丟包率呈現(xiàn)快速下降的趨勢;而低優(yōu)先級業(yè)務的丟包率則一直保持較低的水平。這是由于新算法采用了動態(tài)調配不同等級信道的數(shù)目，當高優(yōu)先級業(yè)務沖突較為嚴重時，表明網絡中高優(yōu)先級業(yè)務的負擔比較重，隨著時間的推移，新算法自適應得增加Ⅰ級信道的數(shù)目，并且由于回退機制的引入，大大降低了丟包率。

圖3b表示的是當仿真結束時，不同網絡負載的各業(yè)務丟包率比較，比較的是新算法的高優(yōu)先業(yè)務丟包率、低優(yōu)先級業(yè)務丟包率和回退信道競爭解決機制(back-off channel contention resolution，BCCR)算法。從圖中可以看到，新算法在保證高優(yōu)先級業(yè)務的低丟包率的情況下，對低優(yōu)先級業(yè)務也有非常大的改善，盡管在某些時候可能會不如傳統(tǒng)的BCCR算法，但是符合優(yōu)先保證高優(yōu)先級業(yè)務的原則。

圖3c反映了仿真到達2s時，不同網絡負載的各業(yè)務延時比較，從圖中可以看出，不管是高優(yōu)先級業(yè)務還是低優(yōu)先級業(yè)務，隨著相應網絡比重的增加，延時都會增加，綜合考慮到網絡的丟包率，認為為此犧牲的延時是有價值的。

Fig.3 a—packet loss probability of high priority and low priority serviceswith different load b—packet loss probability of high priority，low priority and BCCR services c—time delay of high priority and low priority services

4 結論

提出了一種新型的考慮業(yè)務優(yōu)先級的基于信道分級的帶回退業(yè)務的沖突解決算法，該算法采用信道分級，將信道分為Ⅰ和Ⅱ兩個級別，用來區(qū)別對待高低優(yōu)先級兩類業(yè)務，并且能根據(jù)實時網絡業(yè)務的動態(tài)配比自適應地調整兩類信道的數(shù)目;算法還劃分出一部分的回退信道作為保護機制，當突發(fā)包發(fā)生競爭時，根據(jù)競爭業(yè)務的優(yōu)先級進行突發(fā)包分段處理，被分段的突發(fā)包可以經過優(yōu)先級比較，進入回退信道，在保護高優(yōu)先級業(yè)務的穩(wěn)定地低丟包率的同時，也能大幅度降低低優(yōu)先級的丟包率和網絡業(yè)務的延時。仿真結果證實，相比較BCCR算法，這種新型的沖突解決算法確實能夠良好地保證高優(yōu)先級的低丟包率，并且對低優(yōu)先級的業(yè)務的丟包率也能大幅度降低。這些結果對于OBS網絡的優(yōu)化和設計都是有一定的參考作用的。

［1］CHEN Y，QIAO C，YU Y.Optical burst switching:a new area in optical networking research［J］.IEEE Network，2004，18(3):16-23.

［2］JIY F，WANG H X.Optical burst switching networks［M］.Beijing:Beijing University of Posts and Telecommunications Press，2005:38-45(in Chinese).

［3］VU H L，ZUKERMAN M.Blocking probability for priority classes in optical burst switching networks［J］.IEEE Communications Letters，2002，6(5):214-216.

［4］HOU R，SUN JQ，DING PF.Study of fair burst segmentation or droppingmethod in optical burst switched multi-hop network［J］.Journal of Electronics＆ Information Technology，2006，28(11):2144-2147(in Chinese).

［5］BIF J，ZHANGM，YE PD.A novel prioritized scheme for contention resolution in optical burst switched networks［J］.Acta Photonica Siniea，2005，34(6):900-904(in Chinese).

［6］XIANG B B，ZHU J，ZHANG J.Research on channel grading contention in OBS networks［J］.Optical Communication Technique，2011，15(4):20-22(in Chinese).

［7］BARAKAT N，DARCM TE，GANTIS.Back-off channel contention resolution in optical networks［C］//Optical Fiber Communication/National Fiber Optic Engineers Conference.New York，USA:IEEE，2008:759-762.

［8］LEE SK，SRIRAM K，KIM H K，etal.Contention-based limited deflection routing protocol in optical burst-switched networks［J］.IEEE Journal of Selected Areas in Communication，2005，23(8):1596-1611.

［9］HOU R，SUN JQ，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).

［10］WANG B Y，GUAN A H，ZHANG Y.A preemption window mechanism based on priority in E-OBSnetworks［J］.Laser Technology，2011，35(4):531-538(in Chinese).