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

李敏濤，陳荷荷，章曉春

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

引 言

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

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

1 突發(fā)包競(jìng)爭(zhēng)解決機(jī)制研究

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

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

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

2 新算法

2.1 算法的提出

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

2.2 算法描述

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

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

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

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

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

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

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

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

Fig.1 Two high priority when burst conflict

Fig.2 Low priority burst and high priority burst

3 仿真說明

3.1 仿真場(chǎng)景

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

概率密度為:

那么容易得出:

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

3.2 結(jié)果分析

仿真結(jié)果如圖3所示。

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

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

圖3c反映了仿真到達(dá)2s時(shí)，不同網(wǎng)絡(luò)負(fù)載的各業(yè)務(wù)延時(shí)比較，從圖中可以看出，不管是高優(yōu)先級(jí)業(yè)務(wù)還是低優(yōu)先級(jí)業(yè)務(wù)，隨著相應(yīng)網(wǎng)絡(luò)比重的增加，延時(shí)都會(huì)增加，綜合考慮到網(wǎng)絡(luò)的丟包率，認(rèn)為為此犧牲的延時(shí)是有價(jià)值的。

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 結(jié)論

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

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