一種跨層共享保護單播路由機制

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

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

一種跨層共享保護單播路由機制

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

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

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

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

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

1 問題描述

1.1 多層輔助圖

1.1.1 邏輯鏈路和接納鏈路

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

1.2 保護資源共享策略

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

1.2.1 邏輯鏈路保護資源共享策略

1.2.2 波長鏈路保護資源共享策略

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

2 跨層共享保護單播路由算法

2.1 鏈路代價

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

2.1.1 波長鏈路代價

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

(1)

2.1.2 接納鏈路代價

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

(2)

(3)

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

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

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

Clc=αlc

(4)

2.1.4 邏輯鏈路代價

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

(5)

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

(6)

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

2.2 算法描述

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

2.2.1 工作LSP的建立

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

算法1 工作LSP建立算法

輸出:工作LSP．

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

then算法結(jié)束

else

if路徑中有接納鏈路

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

end if

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

end if

2.2.2 保護LSP的建立

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

算法2 保護LSP建立算法

輸出:保護LSP．

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

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

else

if路徑中有接納鏈路

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

end if

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

end if

2.2.3WDM層保護

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

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

輸入:工作LSP．

輸出:已標記的保護光路．

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

將所有邏輯鏈路的鏈路代價設置為∞;

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

then算法結(jié)束

else

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

then

else

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

end if

end if

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

then

else

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

end if

end if

將重負載工作光路標記為“已保護”;

分配資源;

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

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

end if

2.2.4 業(yè)務離去

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

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

算法4 資源釋放算法

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

輸出:業(yè)務離去后更新的網(wǎng)絡拓撲．

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

while邏輯鏈路屬于保護LSP

do

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

do

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

if物理鏈路帶寬為0

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

end if

end while

end while

if光路的工作負載小于QL

then

while波長鏈路屬于保護LSP

do

if物理鏈路屬于工作LSP

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

end if

if波長鏈路中A3=?

then設置波長鏈路狀態(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é)果及分析

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

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

圖1 阻塞率隨業(yè)務強度變化

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

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

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

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

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

圖4 負載均衡度隨業(yè)務強度變化

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

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

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

4 結(jié)語

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

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)系人), 男, 博士, 教授, 博士生導師, wangxw@mail.neu.edu.cn.

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

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

10.3969/j.issn.1001-0505.2015.02.006

TP393

A

1001-0505(2015)02-0231-05