一种基于网络风险的路由波长分配算法

d o i :10.13756/j .g t x y j

.2015.05.004光通信系统与网络技术

一种基于网络风险的路由波长分配算法

高会生,王法宁

(华北电力大学电子与通信工程系,河北保定 071003

)摘要:大多数RWA (路由波长分配)问题研究都是基于阻塞率二负载均衡二信号损伤和物理攻击的,很少涉及到业务与链路工

作状态的依赖关系,然而链路的失效必然造成全网业务安全性能的下降三文章从业务风险的角度描述链路失效对全网业务

的影响,提出了一种基于网络风险的RWA 算法 R -RWA 三在路由分配阶段,

该算法把具有较小网络风险的路由方案分配给光路请求,以降低链路失效对全网业务的影响三仿真结果表明,与经典S P (最短路径)算法相比,该算法可以有效地降低网络的安全风险,提高网络的抗风险能力三关键词:光网络;路由波长分配;链路失效;风险

中图分类号:T N 915 文献标志码:A 文章编号:1005-8788(2015)05-0012-03

C o n s i d e r a t i o n s o f an e t w o r k r i s k -b a s e dRW Aa l g

o r i t h m G a oH u i s h e n g ,W a n g F a n i n g

(D e p a r t m e n t o fE l e c t r o n i c a n dC o mm u n i c a t i o nE n g i n e e r i n g ,N o r t hC h i n aE l e c t r i cP o w e rU n i v e r s i t y ,B a o d i n g 0

71003,C h i n a )A b s t r a c t :M o s t o f t h eR o u t i n g a n dW a v e l e n g t hA s s i g n m e n t (RWA )p r o b l e m s a r e r e l a t e d t ob l o c k i n g r a t e ,l o a db a l a n c i n g ,s i g -n a l d a m a g e a n d p h y s i c a l a t t a c k s ,a n d r a r e l y i n v o l v e dw i t h t h e d e p e n d e n c y o f s e r v i c e s o n t h e l i n kw o r k i n g s

t a t e .H o w e v e r ,l i n k f a i l u r e sw i l l s u r e l y c a u s e t h e d e t e r i o r a t i o no f t h e t r a f f i c s e c u r i t yp e r f o r m a n c e so f t h ee n t i r en e t w o r k .F r o mt h e p e r s p

e c t i v eo

f t r a f f i c r i s k s ,t h i s a r t i c l e d e s c r i b e s t h e i m p a c t s o f l i n k f a i l u r e s o n t h e e n t i r e n e t w o r k s e r v i c e s a n d p r o p o s e s a n e t w o r k r i s k -b a s e d RWAa l

g o r i t

h m ,

i .e .R -RWA.I nt h e p h a s eo f r o u t i n g a s s i g n m e n t ,t h i sa l g o r i t h ma l l o c a t e s t h er o u t i n g s

c h e m ew i t h m i n o r n e t w o r k r i s k s t o l i g h t p a t h r e q u e s t s s o a s t o r e

d u c

e t h e i m p a c t s o

f t h e l i n k f a i l u r e s o n t h e e n t i r e n e t w o r k s e r v i c e s .T h e s i m u l a -t i o n r e s u l t s s h o wt h a t c o m p a r e dw i t ht h ec l a s s i c a lD i j k s t r a +F F ,t h i sa l

g o r i t

h mc a ne f f e c t

i v e l y r e d u c e t h en e t w o r ks e c u r i t y r i s k s a n d i m p r o v e t h en e t w o r ka n t i -r i s ka b i l i t y .K e y w

o r d s :o p t i c a l n e t w o r k ;RWA ;l i n k f a i l u r e ;r i s k 0 引 言

光通信的最大优势在于其潜在的巨大带宽,而

光纤的传输容量与多波长的复用密切相关,但单根光纤可复用的波长数是有限的,因此RWA (路由波

长分配)问题引起了人们的高度关注三RWA 问题属于N P -C 问题,在解决大规模网络的RWA 问题时通常采用启发式算法三现有的启发式方案大多从

阻塞率[1]二负载均衡[2]二信号损伤[3]和物理攻击[4]

等

方面考虑RWA 问题,很少涉及网络业务与光纤链路工作状态的依赖关系的研究三链路失效是指数据无法在链路上正常传输,包括由于串扰二色散二传输损耗及非线性损伤等各种损伤造成链路质量下降导致的链路失效,也包括由于雷击二覆冰和台风等自然灾害造成的链路失效三本文着重考虑由于自然灾害所造成的链路失效对网络业务的影响,并以网络的最大风险R m 来定义这种影响,提出了一种基于网络风险的RWA 算法 R -RWA 三在解决RWA

问题时,以最大风险R m 为优化目标,目的在于在不

增加任何管理设备成本的前提下,通过恰当的路由波长设计,使得网络发生单链路失效时,全网的安全性能下降最小,以提高网络的抗风险能力三

1 R -RW A 算法的基本原理

1.1 业务可靠性

在光通信网络中,一根光纤往往承载着巨大的数据量三发生单链路失效时,若两节点之间只存在一条业务路由,则会直接造成业务的中断三因此,重要业务一般都会采用1+1保护方式对数据业务进行保护,提高其传输可靠性三单路径无保护业务和双路径1+1保护业务是两种比较常见的业务,其路由配置情况如图1所示三单链路失效是链路失效中发生率最高的一种三下面分析单链路失效对单路径

无保护业务和双路径1+1保护业务传输可靠性的影响三

设业务a 为单路径无保护业务,其源节点为s ,汇节点为t ,业务路由为{e 1二e 2二 二e i 二 二e n }

,1?i ?n ,如图1(a )所示三设链路e i 的可靠性为r i ,

则收稿日期:2015-04-15

作者简介:高会生(1963-)

,男,河北保定人三教授,博士,主要研究方向为通信网的管理和风险评估二电力系统通信三通信作者:王法宁,硕士研究生三E -m a i l :w f n _n c e p

u @163.c o m 2

12015年 第5期总第191期

光通信研究

S T U D Y O N O P T I C A LC OMMU N I C A T I O N S

2015.10

(S u m.N o .191

)

s

e 1

t

…e 2e n

e 1p e 2q

…

s

t

…e 11

e 12

e 22

e 21

(a ）

单路径无保护业务

（b ）

双路径1+1保护业务

图1 业务路由配置方式

链路正常状态下,业务a 的可靠性为r a =?n

i =1

r i 三假

设失效链路为e k (1?k ?n )三链路e k 由正常状态

转入失效状态后,业务完全中断,业务a 的可靠性变为r ?a =0三因此链路失效前后业务a 的可靠性变化为Δr a =r a -r ?a =?n

i =1r i 三

设业务b 采用1+1保护方式,其源节点为s ,汇

节点为t 三传输业务时,发端同时在两条路由中传输相同的数据三正常情况下,收端选收主路由的数据,只有主路由发生链路失效时,收端才会通过切换选

收保护路由的数据三设路由{e 11二e 12二 二e 1i 二

二e 1p },1?i ?p ,为业务主路由,路由{e 21二e 22二 二e 2j 二

二e 2q },1?j ?q ,为业务保护路由,如图1(b )所示三设业务主路由上链路e 1i 的可靠性为r 1i ,保护路由上链路e 2j 的可靠性为r 2j ,则链路正常工作时,业务b 的可靠性为

r b =?p i =1

r 1i +?q j =1

r 2j -?p i =1

r 1i 四?q

j =1

r 2j 三

假设失效链路e 1k (1?k ?p )在主路由上,链路e 1k 由正常状态转入失效状态后,

业务b 的数据只能经由保护路由传输,其可靠性变为r ?b =?q

j =1r 2j ,因此链路失效前后业务b 的可靠性变化为

Δr b =r b -r ?b =?p

i =1

r 1i -?p

i =1

r 1i 四?q

j =1

r 2j 三

1.2 网络风险R

网络的运行风险取决于风险事件发生的概率和事件发生后对业务的影响程度三网络的运行风险主要来自于光缆二通信设备等三通信设备的可靠性较高,而且在重要位置还有备用,所以本文只考虑光缆链路对网络运行质量的影响三分析光缆链路的可靠性时需要同时考虑光缆和光放大器的影响三设光缆单位长度的可靠性为r L ,光放大器的可靠性为r A 三链路e j 长度为l ,其上有m A 个光放大器,则链路e j

的可靠性可表示为r j =

r l L 四r m A A 三单链路失效对全网业务的影响由业务的可靠性

变化和业务的权重决定三设失效的链路为e j ,

业务b i 的权重为ωi ,则链路e j 失效前后全网业务的可靠

性扰动为ΔE j =ep

i =1

(ωi 四ΔB i j ),式中,ΔB i j 为链路e j

失效前后业务b i 的可靠性扰动,即ΔB i j =B i j -B ?i j ,

B i j 二B ?i j 分别为链路e j 失效前二

后业务b i 的可靠性三那么网络的最大风险R m =m a x {(1-r j )四ΔE j }

三1.3 R -R W A 算法

R -RWA 算法考虑到业务与链路失效的依赖关

系,确立风险值指标,在搜索最优路由解时以降低网络的最大风险R m 为目标三R m 越小,当网络发生单链路失效时,全网业务的可靠性扰动就越小,数据的传输也就越可靠三下面对算法进行详细描述三

设图G (V ,E )为网络的实际拓扑结构,其中,V

为节点集合,且V ={ν1,ν2, ,νm }

,E 为链路集合,且E ={e 1,e 2, ,e n }三光路请求集合为S L P ={S L P 1,S L P 2, ,S L P p },S L P i ={s i ,t i ,d i }

(i =1,2, ,p )

,s i 和t i 分别为光路请求的源节点和汇节点,d i 为业务类型三d i =1表示是单路径无保护业务;d i =

2表示是双路径1+1保护业务三假定网络中的节点都具有全波长转换能力,则负载最大的链路所承载的光路数即为网络所需波长数三同时,为

了保证能够得到一对路径完全分离的工作路由和保护路由,网络中每个节点的度应大于1三根据光路请求矩阵求出各个光路请求的k 最短路由三网络的路由方案表示为X ={x 1,x 2, ,x p }

,式中,x i =1,2, ,k ,x i 表示第

i 个光路请求采取的是k 最短路由中的第x i 条路由三算法的执行过程如下:

步骤1:初始化三设置k 最短路径的k 值,求解

各个光路请求的k 最短路由三初始路由解设为光路请求的最短路径路由,即X n o w ={1,1, ,1

},路由方案最优解X b e s t =X n o w ;

计算当前路由方案的R m =m a x R (X n o w ),并置R m 的最优解为B e s t R =

m a x R (X n o w );置禁忌表t a b u l i s t 为空,

禁忌长度为t l ,最大迭代次数为S t o p L ,循环变量i =1三步骤2:判断是否满足算法结束条件,若i ?S t o p

L ,则由当前解X n o w 从某一光路请求的k 最短路由中随机选取一条新的路由,得到一个新的邻域解,由此产生邻域解集合三计算所有邻域解的R m ,

并按从小到大的顺序排序,转入步骤3三若i >S t o p

L ,则转入步骤4三步骤3:若邻域解的B e s t R 优于当前最优解

B e s t R ,则用此邻域最优解X n e i _b e s t 替换当前解X n o w

和最优解X b e s t ,

并将其放入禁忌表中,更新禁忌表3

1高会生等: 一种基于网络风险的路由波长分配算法