面向共享风险链路组故障恢复的多路径路由生成算法*
2016-08-22赵甜甜孟相如赵志远张亚坤
赵甜甜， 孟相如， 赵志远， 张亚坤
(空军工程大学 信息与导航学院，陕西 西安 710077)
面向共享风险链路组故障恢复的多路径路由生成算法*
赵甜甜， 孟相如， 赵志远， 张亚坤
(空军工程大学 信息与导航学院，陕西 西安 710077)
为了在IP层恢复网络共享风险链路组(SRLG)故障，提出一种基于改进人工蜂群算法的网络多路径路由生成算法。针对SRLG故障特点建立多路径路由生成模型，最后通过改进人工蜂群算法求解。仿真验证该方法不仅可以生成满足SRLG约束的备用路径，还可以增强故障恢复能力、降低算法复杂度、缩短重路由的平均路径长度。
共享风险链路组； 多路径路由； 生成算法； 人工蜂群算法
0 引 言
在基于WDM的光传输网络中，光纤为网络高速、大量传输数据业务提供了便利，但是因为光纤故障可能引发IP层多条相关联的链路同时故障[1]。此外，自然灾害和人为攻击等原因也会引发一片区域内关联的多条链路同时失效的情况。IETF工作组定义这些故障为共享风险链路组(shared risk link group,SRLG)故障[2]。
文献[3～6]提出的网络可生存性方法大多以解决单、双链路故障或单节点故障为主，且假设链路故障是独立发生的。现实情况却是基于SRLG的故障频繁发生，而大多数先应式故障恢复方法在处理此类故障时无能为力。
利用多路径路由技术解决SRLG故障问题的研究已经起步[7]，文献[8]基于故障概率和风险将SRLG故障划分等级提出两种部分不相交的多路径路由模型，利用“地震图”仿真验证；文献[9]以多路径中联合故障概率最小为目标建模并求解最佳路径。
本文提出一种面向SRLG故障恢复的多路径路由生成算法,并通过仿真验证了本文方法在实际网络中的性能。
1 相关理论
多路径路由技术解决网络故障的基本思路是：在网络层预先计算工作和备用两条不同的路径，当网络链路或节点发生故障时，可以无中断地切换工作路径至备用路径，达到故障快速恢复的目的。
由于共享底层一条物理网络链路断路而引发上层IP层多条链路同时断路的故障类型称之为SRLG故障，称这些同时受到影响的相关联的IP层链路为SRLG。
多路径路由依据保护元素不同，可分为链路不相交多路径(link disjoint multi path,LD—MP)、节点不相交多路径(node disjoint multi path,ND—MP)和SRLG不相交多路径(SRLG disjoint multi path,SD—MP)。图1(a)～(d)分别为从
节点B到节点K的原始拓扑路径,LD—MP,ND—MP和SD—MP示意图。假设图中存在一个SRLG包括三条链路：C→D,D→H,G→H，从节点B到节点K的原始路径为B→C→D→E→K，与之链路不相交路径为图(a)中B→A→D→H→K，与之节点不相交路径为图(b)中B→F→G→H→K，与之SRLG不相交路径为图(c)中B→A→K。
图1 不相交多路径示意图Fig 1 Disjoint multi path schematic diagram
LD—MP条件：若路径s→d的工作路径包含链路i→j，则s→d的备用路径不包含i→j，也不包含j→i。对∀s∈N/{d}，∀i,j∈N，表达式为
(1)
ND—MP条件：若路径s→d的工作路径包含节点i，则s→d的备用路径不包含节点i。对于∀s∈N
(2)
SD—MP条件：若路径s→d的工作路径包含r中任何一条链路，则s→d的备用路径不包含r中所有链路。对于∀s∈N
(3)
2 面向SRLG故障恢复的多路径路由生成算法
传统多路径生成算法一般基于工作路径优先考虑，在原始拓扑中找到最优路径作为工作路径，然后将工作路径经过的所有链路和这些链路所在SRLG包含的所有链路删除，在余下的路径中找到次优的路径作为备用路径。这种生成算法操作简单，但是易造成“陷阱”，即由于过度删除使得本身存在的符合条件的路径未在运行该算法时找到。文献[10]提出可变链路权值SRLG分离的双路由选择策略具有一定的实用价值。
本文面向SRLG故障恢复，综合多路径建模时路径不相交、节点不相交、SRLG不相交的约束条件建立多路径生成模型，并利用改进的人工蜂群算法求解。
2.1 生成模型建立
面向SRLG故障恢复的多路径路由生成模型
(4)
s.t.
∀s∈N{d}and∀i∈N
(5)
∀s∈N/{d}and ∀i∈N
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
算法变量定义如表1。
表1 算法变量定义 Tab 1 Algorithm variables defined
其中，式(4)为目标函数，通过三个可变参数λ1,λ2,λ3调节链路、节点以及SRLG对工作路径和备用路径权重的影响；式(5)、式(6)分别限定工作路径和备用路径在初始节点、中间节点和目的节点的网络流量的大小；式(7)、式(8)分别表示工作路径和备用路径的链路不存在环路；式(9)～式(12)为约定工作路径和备用路径链路、节点、SRLG不相交条件。
2.2 改进蜂群算法求解
人工蜂群(artificial bee colony,ABC)算法是一种启发式群智能全局寻优算法，该算法通过模拟蜜蜂觅食等行为求解数值优化问题，具有参数调节少、操作简单、易于实现、鲁棒性强、收敛速度快等特点[11]。
利用人工蜂群算法求解面向SRLG故障恢复的多路径路由生成问题时，结合可变参数调节并设立公告板公式SRLG信息，提出基于改进的人工蜂群(modified ABC,MABC)算法。
1)二进制编码:为了降低算法搜索的时间复杂度，采用二进制顺序字符串网络编码方式，即网络G(N,L,R)共N个节点、L条链路，编码形成2Lbit二进制字符串，分别对应网络链路的正方向和反方向。若某路径经过某链路正方向则前Lbit该位置为1，若经过某链路反方向,则后Lbit该位置为1，不经过的位置为0。
2)可变参数调节:当网络中链路与节点比高时，表示网络中可选路径数量丰富，可以加大λ1和λ2所占比重；当网络中SRLG数量较少时，表示SRLG对网络的影响是很大的，可以加大λ3所占比重。
3)增加公告板:公示每个SRLG包含的链路信息，跟随蜂获得引领蜂分享的蜜源信息后和进行邻域搜索后都会对比查找公告板SRLG信息以便剔除有共同信息的蜜源，保持不跟随状态。
改进人工蜂群算法流程如图2所示。
图2 MABC算法流程图Fig 2 Flow chart of MABC algorithm
3 仿真与性能分析
3.1 仿真环境与参数
1)网络生成：利用网络生成器BRITE随机生成包含11个节点，21条链路的随机网络拓扑。
图3 随机网络拓扑示意图Fig 3 Diagram of random network topology
2)故障设置：设置两个SRLG，r1={1-7.4-11,6-8}，r2={1-4,3-5,7-8}。
3.2 仿真结果分析
将本文改进算法、人工蜂群算法、文献[10]路径分离方法、工作路径优先算法四种不同方法作为对比组，从故障恢复能力和平均路径长度两方面对比分析。
图4 故障恢复能力对比图Fig 4 Contrast figure of failure recovery ability
由图4可知:本文所提方法故障恢复能力与文献[10]所提方法均很大，在SRLG数量较少时，可以达到100 %生成，在SRLG数量增多时，恢复能力略有下降，但是较工作路径优先算法恢复能力强。
图5 平均路径长度对比图Fig 5 Contrast figure of average path length
由图5可知:相比较文献[10]和工作路径优先算法，人工蜂群算法可以缩短恢复路径长度，原因在群智能生成算法以路径经过的链路长短为适应值函数筛选蜜源位置。与传统人工蜂群算法相比，本文算法引入可变参数调节使得生成的备用路径是较优的恢复路径。
4 结束语
本文提出面向SRLG故障恢复的多路径路由生成算法，通过分析SRLG故障特点引入可变参数调节多路径路由生成模型，并利用二进制编码、设立公告板公示SRLG信息等改进人工蜂群算法对模型求解。通过与其他恢复方
法对比可知本文方法可以提高多路径路由的恢复效果，有一定的理论意义。
[1] Chen Zhen,Han Fuye,Cao Junwei,et al.Cloud computing-based forensic analysis for collaborative network security management system[J].Tsinghua Science and Technology,2013,18(1):40-50.
[2] Papadimitriou D,Poppe F,Jones J.Inference of shared risk link groups[EB/OL].2001—11—14.http:∥www.watersprings.org/pub/id/draft-many-inference-srlg-02.txt.
[3] Jayavelu G,Ramasubramanian S,Younis O.Maintaining colored trees for disjoint multipath routing under node failures[J].IEEE/ACM Transactions on Networking,2009,17(1):346-359.
[4] Zhang Mingui,Liu Bin.Traffic engineering for proactive failure recovery of IP networks[J].Tsinghua Science and Technology,2011,16(1):55-61.
[5] 伍 文，孟相如，刘芸江，等.IP网络弹性路由层拓扑生成优化算法[J].电子科技大学学报，2014，43(5)：769-774.
[6] 王明鸣，孟相如，李纪真，等.基于着色树优化的网络并发双链路故障恢复方法[J].计算机应用研究,2015,32(6):1822-1825.
[7] 王 滨，杨 强，吴春明.IP网络可生存性技术[M].北京：人民邮电出版社，2013.
[8] Moritz Kiese,Velislava Marcheva,Jorg Eberspacher,et al.Diverse routing based on shared risk link group[C]∥7th International Workshop on the Design of Reliable Communication Networks,IEEE,2009:153-159.
[9] Lee Hyang-Won,Modiano Eytan,Lee Kayi.Diverse routing in networks with probabilistic failures[J].IEEE/ACM Transactions on Networking,2010,18(6):1895-1907.
[10] 孙 晨，白显毅.一种基于SRLG分离的双路由选择策略[J].计算机技术与发展,2009,19(12):131-134.
[11] 暴 励.一种思维进化蜂群算法[J].电子学报,2015,43(5):948-954.
Generation algorithm of multi-path routing for recovery from shared risk link group failures*
ZHAO Tian-tian， MENG Xiang-ru， ZHAO Zhi-yuan， ZHANG Ya-kun
(School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China)
Aiming at recovering from network shared risk link group(SRLG)failures in IP layer,a generation algorithm of network multi-path routing is proposed based on modified artificial bee colony algorithm.A multi-path routing generation model focusing on SRLG failure characteristic is created and modified artificial bee colony algorithm is used to solve it.Simulation results show that this method can not only generate backup path satisfied to SRLG constraints, but also can strengthen failure recovery ability,reduce algorithm complexity and shorten average length of rerouting path.
shared risk link group(SRLG); multi-path routing; generation algorithm; artificial bee colony algorithm
10.13873/J.1000—9787(2016)07—0129—03
2015—10—09
国家自然科学基金资助项目(61201209)
TP 393
A
1000—9787(2016)07—0129—03
赵甜甜(1990-)，女，山西临汾人，硕士研究生，主要研究方向为网络抗毁性。
