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

李敏濤，陳荷荷，章曉春

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

引 言

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

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

1 突發包競爭解決機制研究

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

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

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

2 新算法

2.1 算法的提出

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

2.2 算法描述

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

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

(1)高優先級數據包CBDH和高優先級數據包OBDH1發生沖突。

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

(2)低優先級數據包CBDL和高優先級數據包OBDH發生沖突。

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

(3)兩個低優先級的突發數據包CBDL和OBDL發生沖突。

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

Fig.1 Two high priority when burst conflict

Fig.2 Low priority burst and high priority burst

3 仿真說明

3.1 仿真場景

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

概率密度為:

那么容易得出:

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

3.2 結果分析

仿真結果如圖3所示。

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

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

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

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 結論

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

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