一种跨层共享保护单播路由机制

张金宏 端木利亚 王兴伟 黄 敏

(东北大学信息科学与工程学院, 沈阳 110819)

一种跨层共享保护单播路由机制

张金宏 端木利亚 王兴伟 黄 敏

(东北大学信息科学与工程学院, 沈阳 110819)

为了减少IP over WDM光互联网中发生故障时受影响的业务数,提出了一种跨层共享保护单播路由机制．该路由机制可以在稀疏波长转换和光收发器数等多约束条件下,通过建立多层辅助图将多约束问题转换为图论问题,为业务在IP层提供保护,同时为重负载工作光路提供WDM层保护．此外,为了提高资源的利用率,提出了一种资源共享策略．根据共享资源的粒度,该资源共享策略可以分为逻辑链路保护资源共享策略和波长链路保护资源共享策略．基于欧洲教育科研网GEANT拓扑的仿真结果表明, 与专用保护单播路由机制相比,所提路由机制具有更低的阻塞率和更高的负载均衡度,能够有效解决光网络生存性问题．

光互联网;单播路由;共享保护;业务量疏导

市场的需求促使WDM技术快速发展．目前单光纤内能复用上千个波长,每个波长的容量也达到几百Gbit,一旦光网络发生故障,则会导致大量业务失效,造成严重影响．因此,WDM光互联网的生存性成为人们日益关注的重要问题,国内外学者已进行了大量的相关研究．文献[1-2] 通过考虑共享风险链路组约束,为工作路径提供保护;文献[3-4]采用区分可靠性保护的方法向不同用户提供不同的可靠性等级．根据业务是否预先给定,可将业务量疏导分为静态业务量疏导[5]和动态业务量疏导[6-7]两大类．文献[8]提出了一种新的多粒度疏导算法,通过改变模型中的不同因子,提高IP over WDM网络的业务疏导效率．然而,当前IP over WDM光互联网中的大多数动态生存性算法仅考虑了单约束情况,没有考虑光收发器数约束、稀疏波长转换约束等多约束情况．本文提出了一种多约束条件下的跨层共享保护单播路由机制(CSPURM)．基于波长分层图[9],设计了多层辅助图,将多约束问题转换为图论问题,采用物理链路上波长使用负载均衡和光路上带宽使用负载均衡的策略,以尽量减少发生物理链路故障时受影响业务数．同时,在跨层优化业务疏导算法[10]和跨层专用保护单播路由机制(CDPURM)[11]的基础上,提出了跨层共享保护单播路由算法，引入保护资源共享策略,对IP over WDM光互联网中的逻辑链路保护资源和波长链路保护资源进行分配,以提高网络对保护资源的利用率．跨层共享保护单播路由机制的核心思想是为业务在IP层提供保护,同时为重负载工作光路提供WDM层保护．

1 问题描述

1.1 多层辅助图

1.1.1 逻辑链路和接纳链路

1.1.2 波长转换链路

1.2 保护资源共享策略

保护资源共享是指如果2条工作路径不会同时发生故障,则其保护路径可以共享使用相同的保护资源．根据共享资源的粒度,保护资源共享策略可以分为逻辑链路保护资源共享策略和波长链路保护资源共享策略．

1.2.1 逻辑链路保护资源共享策略

1.2.2 波长链路保护资源共享策略

每条被用于共享保护的波长链路lw,都存在一个记录保护路径经过的物理链路的集合A3．为一条工作光路创建保护光路时,如果该工作光路经过的物理链路均不在该波长链路lw的A3中,那么其保护光路可以共享该波长链路．

2 跨层共享保护单播路由算法

2.1 链路代价

为了更好地实现负载均衡,本文为波长转换链路lc、逻辑链路ll、接纳链路la、波长链路lw分别设置了不同的等级αlc,αll,αla,αlw．设置波长转换链路优先级最高,然后依次是逻辑链路、接纳链路、波长链路;由此促使选路时优先选择波长转换链路最少的路径,其次选择逻辑链路数较少的路径,再次选择接纳链路数较少的路径,最后选择波长链路数较少的路径．

2.1.1 波长链路代价

波长链路代价反映了该波长链路所属的物理链路的负载情况,可以根据已用波长数占总波长数的比例来衡量．令no,np分别为该波长链路所属物理链路中的工作波长数和保护波长数．在计算WDM层保护时,波长链路代价Clw为

(1)

2.1.2 接纳链路代价

接纳链路代价表示节点处光发送器和光接收器的使用情况．令ntr,nre,natr,nare分别表示该节点处的光发送器总数、光接收器总数、可用光发送器数以及可用光接收器数,则该节点相应的逻辑节点到所有波长节点的接纳链路代价Cla为

(2)

(3)

为重负载工作光路提供WDM层保护时,如果保护路径的第一跳波长链路或最后一跳波长链路是共享的,那么保护路径源节点或目的节点不需要再次分配光发送器或光接收器．将保护路径源节点处的出边接纳链路和目的节点处的入边接纳链路设置为αla,其他接纳链路设置为∞．

2.1.3 波长转换链路代价

波长转换链路除了引入波长转换带来的延时外,并不对网络的负载产生影响．因此,波长转换链路代价Clc为

Clc=αlc

(4)

2.1.4 逻辑链路代价

每一条逻辑链路都对应着WDM层的一条光路,逻辑链路带宽的容量就是光路的带宽容量．本文将已用带宽占总带宽的比例作为衡量一条逻辑链路负载情况的标准．已用带宽占总带宽的比例越大,说明该逻辑链路的负载越重,在选路时应尽可能避开该链路,必须为该链路设置较大的链路代价．令bt,bo,bp,bs分别表示该逻辑链路的总带宽、工作带宽、保护带宽和用户请求带宽,则逻辑链路Cll的链路代价为

(5)

在保护资源共享情况下,为业务请求建立保护LSP时,影响逻辑链路的链路代价的因素除了该逻辑链路负载外,还有保护LSP经过该逻辑链路需要新分配的带宽数bnew．逻辑链路Cll的链路代价为

(6)

由式(6)可知,若没有足够的空闲带宽,该逻辑链路不可用．请求的保护带宽越少,链路代价越小,当没有请求保护带宽时,链路代价为0．

2.2 算法描述

跨层共享保护单播路由算法的核心包括以下4个部分:① 为业务请求建立工作LSP;② 为业务请求建立保护LSP;③ 为重负载工作光路提供WDM层保护;④ 业务离去时释放资源．

2.2.1 工作LSP的建立

首先，将约束条件和网络拓扑转换成对应的多层辅助图;然后,将该图作为输入,通过运行工作LSP建立算法,计算出工作LSP．

算法1 工作LSP建立算法

输出:工作LSP．

根据式(1)～(5)设置各种链路代价;

then算法结束

else

if路径中有接纳链路

then为业务建立一条新的光路

end if

分配资源,依次更新逻辑链路的带宽情况;

end if

2.2.2 保护LSP的建立

为了使保护LSP和工作LSP不会同时发生故障,将保护LSP与工作LSP的物理链路分离开．

算法2 保护LSP建立算法

输出:保护LSP．

将工作LSP经过的物理链路所对应的波长链路和逻辑链路的链路代价设为∞;

then释放所占用的资源,算法结束

else

if路径中有接纳链路

then需要为保护请求建立一条新的光路

end if

分配资源,依次更新逻辑链路的带宽情况;

end if

2.2.3WDM层保护

当光路的工作负载超过指定阈值QH时,称其为重负载工作光路．为一条重负载工作光路提供保护时,并不实际创建光路,而是在保护光路经过的波长链路上进行记录,当故障发生时才动态地创建保护光路．

算法3 WDM层保护光路创建算法

输入:工作LSP．

输出:已标记的保护光路．

将重负载工作光路经过的物理链路所对应的所有波长链路的链路代价设置为∞;

将所有逻辑链路的链路代价设置为∞;

根据2.1.2节设置所有接纳链路的链路代价;

then算法结束

else

if路径第一跳波长链路使用状态不是“被用于保护”

then

else

WDM层保护失败,算法结束

end if

end if

if路径最后一跳波长链路使用状态不是“被用于保护”

then

else

WDM层保护失败,算法结束

end if

end if

将重负载工作光路标记为“已保护”;

分配资源;

保护路径经过的各波长链路使用状态设置为“被用于保护”;

将工作路径经过的物理链路集合添加到保护路径经过的各波长链路的A3中;

end if

2.2.4 业务离去

业务离去时,原来拥有WDM层保护的工作光路的负载可能小于阈值QH,如果此时删除其保护路径,则可能马上又出现一个使用该光路的新业务,导致负载超过QH,产生抖动．因此,需要设置另一个阈值QL(QL

业务离去时,需要释放其工作LSP和保护LSP上占用的资源,具体算法伪代码如下．

算法4 资源释放算法

输入:申请离去业务的工作LSP和保护LSP．

输出:业务离去后更新的网络拓扑．

依次释放工作LSP逻辑链路上占用的带宽;

while逻辑链路属于保护LSP

do

while物理链路属于逻辑链路集合A1

do

物理链路带宽减去该业务请求带宽;

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设置波长链路状态为“未使用”

end if

if波长链路为路径最后一跳

then目的节点光接收器数加1

end if

if波长链路为路径第一跳

then源节点光发送器数加1

end if

end while

end if

3 仿真结果及分析

将所提的跨层共享保护单播路由机制在基于欧洲教育科研网GEANT拓扑上仿真实现．仿真模型中,业务到达率服从泊松分布,业务持续时间服从负指数分布,参照文献[3,11]设置系统仿真参数．在此基础上,与文献[11]中的跨层专用保护单播路由机制进行对比．

图1为阻塞率随业务强度的变化情况．随着业务强度的增加,阻塞率逐渐增大,且跨层专用保护路由算法的阻塞率比跨层共享保护路由算法高．跨层共享保护单播路由算法中业务的保护路径可以共享保护资源,网络为业务保护分配的资源少,可供后续业务使用的资源多,因此,在开始阶段,随着业务强度的增加,阻塞率并无太大变化．

图1 阻塞率随业务强度变化

图2为阻塞率随波长数的变化情况．随着波长数的增加,跨层专用保护路由算法阻塞率持续下降．对于跨层共享保护路由算法,当波长数大于12时,随着波长数的增加,阻塞率几乎不变．这是因为跨层共享保护路由算法可以共享使用保护资源,在相同业务强度下较跨层专用保护路由算法所需的波长数少．

图2 阻塞率随波长数变化

图3为阻塞率随光收发器数的变化情况．随着光收发器数的增加,阻塞率逐渐减小．但当光收发器数大于12后,阻塞率变化不大,这是因为此时波长数成为主要制约因素．同时,因在跨层共享保护路由算法中保护路径可以共享资源,故其阻塞率比跨层专用保护路由算法低．由此可知,跨层共享保护路由机制的阻塞率较低,能够快速完成业务疏导目标．

图3 阻塞率随光收发器数变化

负载均衡度用于描述网络中各物理链路的负载分布情况．图4为负载均衡度随业务强度的变化情况．随着业务强度的增加,负载均衡度逐渐减小．这是因为业务强度越大,网络中每条链路的负载越重,各链路负载差别越小,负载均衡度越小,最后趋近于1．跨层共享保护路由算法的负载均衡度与跨层专用保护路由算法有略微差别．这是因为跨层共享保护路由算法中保护资源是共享的,在计算保护路径时应优先考虑尽可能少的占用资源,然后才是负载均衡,故其负载均衡度下降较为缓慢．

图4 负载均衡度随业务强度变化

图5为负载均衡度随波长数的变化情况．当波长数小于20时,跨层共享保护路由算法采用资源共享,优先选择占用资源较少的链路,其次再考虑负载均衡,因此其负载均衡度较跨层专用保护路由算法高．

图5 负载均衡度随波长数变化

综上所述,与跨层专用保护单播路由机制相比,所提的跨层共享保护单播路由算法具有更低的阻塞率和更高的负载均衡度,能够有效地将业务进行疏导,减少业务阻塞率．

4 结语

在光收发器数约束、稀疏波长转换约束等多约束情况下,设计了多层辅助图,将多约束问题转化为图论问题,同时引入资源共享策略以提高网络的资源利用率,从而提出了一种跨层共享保护单播路由机制．该路由机制不仅能为业务在IP层提供保护,同时为重负载工作光路提供WDM层保护,有效解决了IP over WDM光互联网中的生存性问题．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—), 男, 博士生; 王兴伟(联系人), 男, 博士, 教授, 博士生导师, 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