張金宏 端木利亞 王興偉 黃 敏

(東北大學(xué)信息科學(xué)與工程學(xué)院, 沈陽 110819)

一種跨層共享保護(hù)單播路由機(jī)制

張金宏 端木利亞 王興偉 黃 敏

(東北大學(xué)信息科學(xué)與工程學(xué)院, 沈陽 110819)

為了減少IP over WDM光互聯(lián)網(wǎng)中發(fā)生故障時受影響的業(yè)務(wù)數(shù),提出了一種跨層共享保護(hù)單播路由機(jī)制．該路由機(jī)制可以在稀疏波長轉(zhuǎn)換和光收發(fā)器數(shù)等多約束條件下,通過建立多層輔助圖將多約束問題轉(zhuǎn)換為圖論問題,為業(yè)務(wù)在IP層提供保護(hù),同時為重負(fù)載工作光路提供WDM層保護(hù)．此外,為了提高資源的利用率,提出了一種資源共享策略．根據(jù)共享資源的粒度,該資源共享策略可以分為邏輯鏈路保護(hù)資源共享策略和波長鏈路保護(hù)資源共享策略．基于歐洲教育科研網(wǎng)GEANT拓?fù)涞姆抡娼Y(jié)果表明, 與專用保護(hù)單播路由機(jī)制相比,所提路由機(jī)制具有更低的阻塞率和更高的負(fù)載均衡度,能夠有效解決光網(wǎng)絡(luò)生存性問題．

光互聯(lián)網(wǎng);單播路由;共享保護(hù);業(yè)務(wù)量疏導(dǎo)

市場的需求促使WDM技術(shù)快速發(fā)展．目前單光纖內(nèi)能復(fù)用上千個波長,每個波長的容量也達(dá)到幾百Gbit,一旦光網(wǎng)絡(luò)發(fā)生故障,則會導(dǎo)致大量業(yè)務(wù)失效,造成嚴(yán)重影響．因此,WDM光互聯(lián)網(wǎng)的生存性成為人們?nèi)找骊P(guān)注的重要問題,國內(nèi)外學(xué)者已進(jìn)行了大量的相關(guān)研究．文獻(xiàn)[1-2] 通過考慮共享風(fēng)險鏈路組約束,為工作路徑提供保護(hù);文獻(xiàn)[3-4]采用區(qū)分可靠性保護(hù)的方法向不同用戶提供不同的可靠性等級．根據(jù)業(yè)務(wù)是否預(yù)先給定,可將業(yè)務(wù)量疏導(dǎo)分為靜態(tài)業(yè)務(wù)量疏導(dǎo)[5]和動態(tài)業(yè)務(wù)量疏導(dǎo)[6-7]兩大類．文獻(xiàn)[8]提出了一種新的多粒度疏導(dǎo)算法,通過改變模型中的不同因子,提高IP over WDM網(wǎng)絡(luò)的業(yè)務(wù)疏導(dǎo)效率．然而,當(dāng)前IP over WDM光互聯(lián)網(wǎng)中的大多數(shù)動態(tài)生存性算法僅考慮了單約束情況,沒有考慮光收發(fā)器數(shù)約束、稀疏波長轉(zhuǎn)換約束等多約束情況．本文提出了一種多約束條件下的跨層共享保護(hù)單播路由機(jī)制(CSPURM)．基于波長分層圖[9],設(shè)計了多層輔助圖,將多約束問題轉(zhuǎn)換為圖論問題,采用物理鏈路上波長使用負(fù)載均衡和光路上帶寬使用負(fù)載均衡的策略,以盡量減少發(fā)生物理鏈路故障時受影響業(yè)務(wù)數(shù)．同時,在跨層優(yōu)化業(yè)務(wù)疏導(dǎo)算法[10]和跨層專用保護(hù)單播路由機(jī)制(CDPURM)[11]的基礎(chǔ)上,提出了跨層共享保護(hù)單播路由算法，引入保護(hù)資源共享策略,對IP over WDM光互聯(lián)網(wǎng)中的邏輯鏈路保護(hù)資源和波長鏈路保護(hù)資源進(jìn)行分配,以提高網(wǎng)絡(luò)對保護(hù)資源的利用率．跨層共享保護(hù)單播路由機(jī)制的核心思想是為業(yè)務(wù)在IP層提供保護(hù),同時為重負(fù)載工作光路提供WDM層保護(hù)．

1 問題描述

1.1 多層輔助圖

1.1.1 邏輯鏈路和接納鏈路

1.1.2 波長轉(zhuǎn)換鏈路

1.2 保護(hù)資源共享策略

保護(hù)資源共享是指如果2條工作路徑不會同時發(fā)生故障,則其保護(hù)路徑可以共享使用相同的保護(hù)資源．根據(jù)共享資源的粒度,保護(hù)資源共享策略可以分為邏輯鏈路保護(hù)資源共享策略和波長鏈路保護(hù)資源共享策略．

1.2.1 邏輯鏈路保護(hù)資源共享策略

1.2.2 波長鏈路保護(hù)資源共享策略

每條被用于共享保護(hù)的波長鏈路lw,都存在一個記錄保護(hù)路徑經(jīng)過的物理鏈路的集合A3．為一條工作光路創(chuàng)建保護(hù)光路時,如果該工作光路經(jīng)過的物理鏈路均不在該波長鏈路lw的A3中,那么其保護(hù)光路可以共享該波長鏈路．

2 跨層共享保護(hù)單播路由算法

2.1 鏈路代價

為了更好地實現(xiàn)負(fù)載均衡,本文為波長轉(zhuǎn)換鏈路lc、邏輯鏈路ll、接納鏈路la、波長鏈路lw分別設(shè)置了不同的等級αlc,αll,αla,αlw．設(shè)置波長轉(zhuǎn)換鏈路優(yōu)先級最高,然后依次是邏輯鏈路、接納鏈路、波長鏈路;由此促使選路時優(yōu)先選擇波長轉(zhuǎn)換鏈路最少的路徑,其次選擇邏輯鏈路數(shù)較少的路徑,再次選擇接納鏈路數(shù)較少的路徑,最后選擇波長鏈路數(shù)較少的路徑．

2.1.1 波長鏈路代價

波長鏈路代價反映了該波長鏈路所屬的物理鏈路的負(fù)載情況,可以根據(jù)已用波長數(shù)占總波長數(shù)的比例來衡量．令no,np分別為該波長鏈路所屬物理鏈路中的工作波長數(shù)和保護(hù)波長數(shù)．在計算WDM層保護(hù)時,波長鏈路代價Clw為

(1)

2.1.2 接納鏈路代價

接納鏈路代價表示節(jié)點處光發(fā)送器和光接收器的使用情況．令ntr,nre,natr,nare分別表示該節(jié)點處的光發(fā)送器總數(shù)、光接收器總數(shù)、可用光發(fā)送器數(shù)以及可用光接收器數(shù),則該節(jié)點相應(yīng)的邏輯節(jié)點到所有波長節(jié)點的接納鏈路代價Cla為

(2)

(3)

為重負(fù)載工作光路提供WDM層保護(hù)時,如果保護(hù)路徑的第一跳波長鏈路或最后一跳波長鏈路是共享的,那么保護(hù)路徑源節(jié)點或目的節(jié)點不需要再次分配光發(fā)送器或光接收器．將保護(hù)路徑源節(jié)點處的出邊接納鏈路和目的節(jié)點處的入邊接納鏈路設(shè)置為αla,其他接納鏈路設(shè)置為∞．

2.1.3 波長轉(zhuǎn)換鏈路代價

波長轉(zhuǎn)換鏈路除了引入波長轉(zhuǎn)換帶來的延時外,并不對網(wǎng)絡(luò)的負(fù)載產(chǎn)生影響．因此,波長轉(zhuǎn)換鏈路代價Clc為

Clc=αlc

(4)

2.1.4 邏輯鏈路代價

每一條邏輯鏈路都對應(yīng)著WDM層的一條光路,邏輯鏈路帶寬的容量就是光路的帶寬容量．本文將已用帶寬占總帶寬的比例作為衡量一條邏輯鏈路負(fù)載情況的標(biāo)準(zhǔn)．已用帶寬占總帶寬的比例越大,說明該邏輯鏈路的負(fù)載越重,在選路時應(yīng)盡可能避開該鏈路,必須為該鏈路設(shè)置較大的鏈路代價．令bt,bo,bp,bs分別表示該邏輯鏈路的總帶寬、工作帶寬、保護(hù)帶寬和用戶請求帶寬,則邏輯鏈路Cll的鏈路代價為

(5)

在保護(hù)資源共享情況下,為業(yè)務(wù)請求建立保護(hù)LSP時,影響邏輯鏈路的鏈路代價的因素除了該邏輯鏈路負(fù)載外,還有保護(hù)LSP經(jīng)過該邏輯鏈路需要新分配的帶寬數(shù)bnew．邏輯鏈路Cll的鏈路代價為

(6)

由式(6)可知,若沒有足夠的空閑帶寬,該邏輯鏈路不可用．請求的保護(hù)帶寬越少,鏈路代價越小,當(dāng)沒有請求保護(hù)帶寬時,鏈路代價為0．

2.2 算法描述

跨層共享保護(hù)單播路由算法的核心包括以下4個部分:① 為業(yè)務(wù)請求建立工作LSP;② 為業(yè)務(wù)請求建立保護(hù)LSP;③ 為重負(fù)載工作光路提供WDM層保護(hù);④ 業(yè)務(wù)離去時釋放資源．

2.2.1 工作LSP的建立

首先，將約束條件和網(wǎng)絡(luò)拓?fù)滢D(zhuǎn)換成對應(yīng)的多層輔助圖;然后,將該圖作為輸入,通過運(yùn)行工作LSP建立算法,計算出工作LSP．

算法1 工作LSP建立算法

輸出:工作LSP．

根據(jù)式(1)～(5)設(shè)置各種鏈路代價;

then算法結(jié)束

else

if路徑中有接納鏈路

then為業(yè)務(wù)建立一條新的光路

end if

分配資源,依次更新邏輯鏈路的帶寬情況;

end if

2.2.2 保護(hù)LSP的建立

為了使保護(hù)LSP和工作LSP不會同時發(fā)生故障,將保護(hù)LSP與工作LSP的物理鏈路分離開．

算法2 保護(hù)LSP建立算法

輸出:保護(hù)LSP．

將工作LSP經(jīng)過的物理鏈路所對應(yīng)的波長鏈路和邏輯鏈路的鏈路代價設(shè)為∞;

then釋放所占用的資源,算法結(jié)束

else

if路徑中有接納鏈路

then需要為保護(hù)請求建立一條新的光路

end if

分配資源,依次更新邏輯鏈路的帶寬情況;

end if

2.2.3WDM層保護(hù)

當(dāng)光路的工作負(fù)載超過指定閾值QH時,稱其為重負(fù)載工作光路．為一條重負(fù)載工作光路提供保護(hù)時,并不實際創(chuàng)建光路,而是在保護(hù)光路經(jīng)過的波長鏈路上進(jìn)行記錄,當(dāng)故障發(fā)生時才動態(tài)地創(chuàng)建保護(hù)光路．

算法3 WDM層保護(hù)光路創(chuàng)建算法

輸入:工作LSP．

輸出:已標(biāo)記的保護(hù)光路．

將重負(fù)載工作光路經(jīng)過的物理鏈路所對應(yīng)的所有波長鏈路的鏈路代價設(shè)置為∞;

將所有邏輯鏈路的鏈路代價設(shè)置為∞;

根據(jù)2.1.2節(jié)設(shè)置所有接納鏈路的鏈路代價;

then算法結(jié)束

else

if路徑第一跳波長鏈路使用狀態(tài)不是“被用于保護(hù)”

then

else

WDM層保護(hù)失敗,算法結(jié)束

end if

end if

if路徑最后一跳波長鏈路使用狀態(tài)不是“被用于保護(hù)”

then

else

WDM層保護(hù)失敗,算法結(jié)束

end if

end if

將重負(fù)載工作光路標(biāo)記為“已保護(hù)”;

分配資源;

保護(hù)路徑經(jīng)過的各波長鏈路使用狀態(tài)設(shè)置為“被用于保護(hù)”;

將工作路徑經(jīng)過的物理鏈路集合添加到保護(hù)路徑經(jīng)過的各波長鏈路的A3中;

end if

2.2.4 業(yè)務(wù)離去

業(yè)務(wù)離去時,原來擁有WDM層保護(hù)的工作光路的負(fù)載可能小于閾值QH,如果此時刪除其保護(hù)路徑,則可能馬上又出現(xiàn)一個使用該光路的新業(yè)務(wù),導(dǎo)致負(fù)載超過QH,產(chǎn)生抖動．因此,需要設(shè)置另一個閾值QL(QL

業(yè)務(wù)離去時,需要釋放其工作LSP和保護(hù)LSP上占用的資源,具體算法偽代碼如下．

算法4 資源釋放算法

輸入:申請離去業(yè)務(wù)的工作LSP和保護(hù)LSP．

輸出:業(yè)務(wù)離去后更新的網(wǎng)絡(luò)拓?fù)洌?/p>

依次釋放工作LSP邏輯鏈路上占用的帶寬;

while邏輯鏈路屬于保護(hù)LSP

do

while物理鏈路屬于邏輯鏈路集合A1

do

物理鏈路帶寬減去該業(yè)務(wù)請求帶寬;

if物理鏈路帶寬為0

then 物理鏈路從A1中刪除,將保護(hù)帶寬的值重新設(shè)置為A1中各物理鏈路帶寬的最大值

end if

end while

end while

if光路的工作負(fù)載小于QL

then

while波長鏈路屬于保護(hù)LSP

do

if物理鏈路屬于工作LSP

then從波長鏈路集合A3中刪除

end if

if波長鏈路中A3=?

then設(shè)置波長鏈路狀態(tài)為“未使用”

end if

if波長鏈路為路徑最后一跳

then目的節(jié)點光接收器數(shù)加1

end if

if波長鏈路為路徑第一跳

then源節(jié)點光發(fā)送器數(shù)加1

end if

end while

end if

3 仿真結(jié)果及分析

將所提的跨層共享保護(hù)單播路由機(jī)制在基于歐洲教育科研網(wǎng)GEANT拓?fù)渖戏抡鎸崿F(xiàn)．仿真模型中,業(yè)務(wù)到達(dá)率服從泊松分布,業(yè)務(wù)持續(xù)時間服從負(fù)指數(shù)分布,參照文獻(xiàn)[3,11]設(shè)置系統(tǒng)仿真參數(shù)．在此基礎(chǔ)上,與文獻(xiàn)[11]中的跨層專用保護(hù)單播路由機(jī)制進(jìn)行對比．

圖1為阻塞率隨業(yè)務(wù)強(qiáng)度的變化情況．隨著業(yè)務(wù)強(qiáng)度的增加,阻塞率逐漸增大,且跨層專用保護(hù)路由算法的阻塞率比跨層共享保護(hù)路由算法高．跨層共享保護(hù)單播路由算法中業(yè)務(wù)的保護(hù)路徑可以共享保護(hù)資源,網(wǎng)絡(luò)為業(yè)務(wù)保護(hù)分配的資源少,可供后續(xù)業(yè)務(wù)使用的資源多,因此,在開始階段,隨著業(yè)務(wù)強(qiáng)度的增加,阻塞率并無太大變化．

圖1 阻塞率隨業(yè)務(wù)強(qiáng)度變化

圖2為阻塞率隨波長數(shù)的變化情況．隨著波長數(shù)的增加,跨層專用保護(hù)路由算法阻塞率持續(xù)下降．對于跨層共享保護(hù)路由算法,當(dāng)波長數(shù)大于12時,隨著波長數(shù)的增加,阻塞率幾乎不變．這是因為跨層共享保護(hù)路由算法可以共享使用保護(hù)資源,在相同業(yè)務(wù)強(qiáng)度下較跨層專用保護(hù)路由算法所需的波長數(shù)少．

圖2 阻塞率隨波長數(shù)變化

圖3為阻塞率隨光收發(fā)器數(shù)的變化情況．隨著光收發(fā)器數(shù)的增加,阻塞率逐漸減?。?dāng)光收發(fā)器數(shù)大于12后,阻塞率變化不大,這是因為此時波長數(shù)成為主要制約因素．同時,因在跨層共享保護(hù)路由算法中保護(hù)路徑可以共享資源,故其阻塞率比跨層專用保護(hù)路由算法低．由此可知,跨層共享保護(hù)路由機(jī)制的阻塞率較低,能夠快速完成業(yè)務(wù)疏導(dǎo)目標(biāo)．

圖3 阻塞率隨光收發(fā)器數(shù)變化

負(fù)載均衡度用于描述網(wǎng)絡(luò)中各物理鏈路的負(fù)載分布情況．圖4為負(fù)載均衡度隨業(yè)務(wù)強(qiáng)度的變化情況．隨著業(yè)務(wù)強(qiáng)度的增加,負(fù)載均衡度逐漸減?。@是因為業(yè)務(wù)強(qiáng)度越大,網(wǎng)絡(luò)中每條鏈路的負(fù)載越重,各鏈路負(fù)載差別越小,負(fù)載均衡度越小,最后趨近于1．跨層共享保護(hù)路由算法的負(fù)載均衡度與跨層專用保護(hù)路由算法有略微差別．這是因為跨層共享保護(hù)路由算法中保護(hù)資源是共享的,在計算保護(hù)路徑時應(yīng)優(yōu)先考慮盡可能少的占用資源,然后才是負(fù)載均衡,故其負(fù)載均衡度下降較為緩慢．

圖4 負(fù)載均衡度隨業(yè)務(wù)強(qiáng)度變化

圖5為負(fù)載均衡度隨波長數(shù)的變化情況．當(dāng)波長數(shù)小于20時,跨層共享保護(hù)路由算法采用資源共享,優(yōu)先選擇占用資源較少的鏈路,其次再考慮負(fù)載均衡,因此其負(fù)載均衡度較跨層專用保護(hù)路由算法高．

圖5 負(fù)載均衡度隨波長數(shù)變化

綜上所述,與跨層專用保護(hù)單播路由機(jī)制相比,所提的跨層共享保護(hù)單播路由算法具有更低的阻塞率和更高的負(fù)載均衡度,能夠有效地將業(yè)務(wù)進(jìn)行疏導(dǎo),減少業(yè)務(wù)阻塞率．

4 結(jié)語

在光收發(fā)器數(shù)約束、稀疏波長轉(zhuǎn)換約束等多約束情況下,設(shè)計了多層輔助圖,將多約束問題轉(zhuǎn)化為圖論問題,同時引入資源共享策略以提高網(wǎng)絡(luò)的資源利用率,從而提出了一種跨層共享保護(hù)單播路由機(jī)制．該路由機(jī)制不僅能為業(yè)務(wù)在IP層提供保護(hù),同時為重負(fù)載工作光路提供WDM層保護(hù),有效解決了IP over WDM光互聯(lián)網(wǎng)中的生存性問題．IP over WDM中的多播路由保護(hù)機(jī)制是今后研究的重點．

References)

[1]Shao X, Yeo Y K, Bai Y, et al. Backup reprovisioning after shared risk link group (SRLG) failures in WDM mesh networks [J].JournalofOpticalCommunicationsandNetworking, 2010, 2(8): 587-599.

[2]Tapolcai J, Ho P H, Rónyai L, et al. Failure localization for shared risk link groups in all-optical mesh networks using monitoring trails [J].JournalofLightwaveTechnology, 2011, 29(10): 1597-1606.

[3]Diego L, Massimo T, Achille P. Algorithms and models for backup reprovisioning in WDM networks [J].IEEE/ACMTransactionsonNetworking, 2010, 18(6):1883-1894.

[4]Zhao J H, Qu H, Li Z Z. Protection mechanism with differentiated service reliability in multi-domain optical networks based on conditional risk disjunction degree [C]//2009IEEEInternationalConferenceonBroadbandNetwork&MultimediaTechnology. Beijing, China, 2009: 388-392.

[5]Zhu K, Mukherjee B. Traffic grooming in an optical WDM mesh network [J].IEEEJournalonSelectedAreasinCommunications, 2002, 20(1): 122-133.

[6]Farahmand F, Zhang Q, Jue J P. Dynamic traffic grooming in optical burst-switched networks [J].JournalofLightwaveTechnology, 2005, 23(10): 3167.

[7]Thiagarajan S, Somani A K. Traffic Grooming for Survivable WDM mesh networks [J].OpticalNetworksMagazine, 2002, 3(3):88-98.

[8]Wang X W, Hou W G, Guo L, et al. A new multi-granularity grooming algorithm based on traffic partition in IP over WDM networks [J].ComputerNetworks, 2011, 55(3):807-821.

[9]Chen C, Banerjee S. A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks [C]//ProceedingsIEEEINFOCOM. Los Alamitos, CA, USA, 1996:164-171.

[10]Wang X W, Cheng H, Li K Q, et al. A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks [J].JournalofParallelandDistributedComputing, 2013, 73(6): 807-822.

[11]Duanmu L Y, Wang X W, Huang M. A cross-layer dedicated protection unicast routing scheme in IP over WDM optical internet [C]//IEEEInternationalConferenceonSoftwareEngineeringandServiceScience. Beijing, China, 2014:1032-1035.

Cross-layer shared protection unicast routing mechanism

Zhang Jinhong Duanmu Liya Wang Xingwei Huang Min

(College of Information Science and Engineering, Northeastern University, Shenyang 110819, China)

In order to reduce the amount of the impacted traffic due to failures in the IP (internet protocol) over WDM (wavelength division multiplex) optical Internet, a cross-layer shared protection unicast routing mechanism is proposed. Under the multiple constraints, such as sparse wavelength conversion and the number of optical transceivers, the proposed mechanism can provide protection for the traffic in the IP layer and the heavy-loaded working lightpath in the WDM layer by transforming the multi-constraints problem into the graph theory problem through building the multi-layer auxiliary graph. In addition, a resource sharing strategy is introduced to improve the resource utilization. According to the granularity of the shared resources, this strategy can be divided into the resource sharing strategy for logic link protection and that for wavelength link protection. Simulation is implemented on the topology of the European research and academic network GEANT. The results show that compared with the dedicated protection unicast routing mechanism, the proposed routing mechanism can effectively solve the survivability problem in the optical network with lower blocking rate and higher load balancing degree.

optical Internet; unicast routing; shared protection; traffic grooming

10.3969/j.issn.1001-0505.2015.02.006

2014-10-30. 作者簡介: 張金宏(1982—), 男, 博士生; 王興偉(聯(lián)系人), 男, 博士, 教授, 博士生導(dǎo)師, wangxw@mail.neu.edu.cn.

國家杰出青年科學(xué)基金資助項目(61225012, 71325002)、高等學(xué)校博士學(xué)科點專項科研基金資助項目(20120042130003)、遼寧省“百千萬人才工程”資助項目(2013921068) .

張金宏,端木利亞,王興偉，等.一種跨層共享保護(hù)單播路由機(jī)制[J].東南大學(xué)學(xué)報:自然科學(xué)版,2015,45(2):231-235.

10.3969/j.issn.1001-0505.2015.02.006

TP393

A

1001-0505(2015)02-0231-05