全光网中定位故障链路的探测选择算法

齐小刚， 王晓琳， 刘立芳

(1. 西安电子科技大学 数学与统计学院，陕西 西安 710071;2. 西安电子科技大学 计算机学院，陕西 西安 710071)

在全光网中，故障管理是至关重要的功能块．当网络中的光纤遭到破坏时，链路上的所有业务都会中断．因此，一旦网络中发生故障，就需要进行故障诊断来定位故障发生的确切位置，从而进行进一步的故障分离和故障修复以恢复中断的业务．因为全光网络具有全光传输的特性，光路上的中间节点不进行光电转换，所以也就不能对信号采用传统的电子监测手段进行监测[1]．作为补救，文献[2]研究了基于链路的监测，这种监测方法对每条链路单独进行一次测试，即通过单跳监管光路发送光信号监测每条链路，这使得发送的探测数等于网络中的链路数．

为了减少发送的探测数，基于链路监测的进一步发展是使用一组多跳监管光路来发送光信号，每发送1次探测可以测试多条链路，相关的研究包括监测环[3]以及监测迹[4]，一条监管光路末端的监测站可以获得这条监管光路上探测信号所经过的一组链路的状态．通过适当地分配一组监管光路，远程网络控制中心依据监测站触发的告警就可以定位多条故障链路．

非适应性链路故障定位已经被广泛研究[4-7]，探测信号在多条监管光路上同时发送．文献[4]给出了关于定位大型稀疏网络中多条故障链路的随机游走算法．随机游走算法的目的是，使用两个监测站(发送方和接收方)通过多次随机游走来构造k分离路由矩阵去定位k条故障链路．为了使大型稀疏网络中的每条链路有惟一的二进制编码，探测信号必须从发送方到接收方随机地游走多次．因此，在随机游走算法中每条链路会被大量的探测经过，这将会增加发送的探测数以及每条链路上消耗的平均波长．

笔者提出启发式的探测选择方法，解决了随机游走算法中消耗大量的探测数以及波长问题．不同于随机游走算法中的非适应性方案，文中的思想是采用适应性的监测方案[3，8]．首先，需要找到用来故障检测的监测路径，接着在建立的所有监测路径上同时发送探测信号；然后，在有故障的路径上，按次序发送探测信号定位故障链路的确切位置，在定位过程中根据每次探测信号的返回结果，适应性地调整下一次的探测路径．

1　相关概念

图1　在监测路径上发送探测定位故障链路

监测路径是一条监管光路．在监测路径上发送探测可以进行故障检测与定位．如果监测路径上的一条链路出故障，那么在这条监测路径上的监测站会由于光信号的丢失而产生告警[9]．在监测路径上发送探测信号，如果探测信号返回到监测站，则表示在探测信号所经过的路径上没有故障链路，否则有故障链路．如在图1(a)中建立了一条监测路径，然后在图1(b)中给出了在监测路径上依次发送两个探测来定位故障链路(3，5)的过程，其中，节点1是监测站，探测p1所走的路径为1-5-3-5-1，探测p2所走的路径为1-5-1．

2　探测选择方法

在大型光网络中，由于光纤数据连接的透明性需求，监测站只能被放置在特殊的位置．因为使用的监测站越少，所需的管理花费就越少．和随机游走算法一致，在文中使用两个监测站进行故障检测．

2.1　故障检测

网络中出现故障链路时，首先需要建立监测路径，然后在建立好的监测路径上发送探测信号进行故障检测．一些监测路径返回故障信息后，网络管理中心就可以进行故障链路的定位．关于故障链路的检测，要求每条链路至少被1条监测路径经过，而面临的问题是如何找到可以检测到所有链路状态的最小监测路径集合，即就是优化关于故障检测所需的监测路径集合．如果存在故障链路，那么至少会有1条监测路径会报告故障．为了寻求能够覆盖所有链路E的最小监测路径集合，首先需要证明关于故障检测的最小监测路径集合问题是非确定多项式(Non-deterministic Polynomial，NP)完全问题，然后再给出找到最小监测路径集合的启发式算法．

2.1.1最小监测路径集合问题是NP完全问题

定理1最小监测路径集合等价于最小集合覆盖问题．

证明(最小集合覆盖问题⟹最小监测路径集合): 这部分要证的是最小集合覆盖问题的解是最小监测路径集合的解．最小集合覆盖问题的解是大小为k的集合C′，即C′覆盖N中的每个元素．如上述构造中提到的，如果集合Cj覆盖元素n，相当于与Cj对应的监测路径经过元素n对应的链路e．因此，大小为k的集合C′覆盖N中的每个元素，C′中表示的这k条监测路径将会经过E中的每条链路．因此，表示C′中的这些监测路径为大小是k的监测路径集合．

(最小监测路径集合⟹最小集合覆盖问题): 这部分要证的是最小监测路径集合的解是最小集合覆盖问题的解．最小监测路径集合的解是大小为k的一组监测路径，可以经过E中的每条链路．如上述构造中提到的，如果与监测路径m对应的集合Cj覆盖与链路e对应的元素n，则监测路径m经过链路e．因此，如果监测路径集合中的k条监测路径经过所有节点，则与k条监测路径对应的k个集合将覆盖链路所表示的所有元素．

2.1.2监测路径集合选择的启发式算法

关于故障检测的监测路径选择算法是基于启发式的算法来选择监测路径进行故障检测的．通过构造监测路径使得每条链路至少被1条监测路径经过．

算法1故障检测的监测路径选择．

输入: 网络拓扑G(V，E)，两个监测站(一个发送方s，一个接收方t)．

输出: 监测路径集合M．

初始化每条链路上的计数器ρ(ei)=0(i=1，2，…，|E|);

独立地构造M的每一行的过程如下:

while(∃ρ(ei)=0)

在G中找一条从s到t的随机游走mj(mj∉M);

把mj放入M中;

对mj经过的每条链路ei执行ρ(ei)++;

end while.

在算法1中使用了局部稀缺最优策略，其思想是在每条链路ei上安装一个计数器ρ(ei) (i=1，2，…，|E|)，ρ(ei)表示每条链路上经过的监测路径的数目．这样就可以控制从发送方s到接收方t的随机游走，即不是随机选择一个邻居节点进行随机游走，而是选择计数器上数值最小的链路进行游走．当在G上找到一条从s到t的随机游走mj，则在由mj经过的所有链路上的计数器加1．算法终止的条件是每条链路上的计数器ρ(ei)≠ 0，即就是每条链路至少被1条监测路径经过．因此，最小监测路径集合问题就被解决了．最后可以得到一组监测路径M，即就是最小监测路径集合．在M中的所有监测路径上同时发送探测来进行故障检测．

2.2　故障定位

当算法1生成监测路径集合后，如果存在故障链路，则开始进行故障链路定位．当网络中的故障链路被一条监测路径上的探测信号探测到时，将会在这条监测路径上发送更多的探测．这个故障表示在这条故障的监测路径上存在1个或多个故障链路．但是，这些探测可能不会精确地定位故障链路的具体位置．因此，在这些有故障的监测路径上将会发送更多的探测来定位故障链路．故障定位需要发送的探测数要使得有故障的监测路径上的所有链路的状态可以被判断出来．

在故障定位过程中使用一个监测站，从监测站发出的探测信号最终会返回到这个监测站．因此探测所走的路径相当于是一条环路，即每条链路上有互反方向的两个波长．如图1(b)探测p1所走的路径是1-5-3-5-1，实际探测所监测的范围是1-5-3，这样可以引入折半查找的思想来进行快速的故障定位．算法2是基于折半查找方法[3]来明确地定位所有故障链路．在折半查找的方法中，对每条有故障的监测路径进行独立的查找．在每条故障的监测路径上，第1次探测是从监测站发送到监测路径的中间点．如果探测失败，则接着对第1次探测所经过的路径的前半部分发送探测；否则，以相同的方式对监测路径的后半部分进行探测．

算法2故障定位的探测选择．

输入: 监测路径集合M，1个监测站．

输出: 故障链路集合F．

由算法1得到监测路径集合M;

for(M中的每条监测路径)

在所有的监测路径上同时发送探测信号;

//faultylink(a，b)表示节点a和节点b之间的链路是故障的

flag←Binarysearch(p，low，high，faultylink(a，b))

while(flag为false)//如果链路是故障的，则找到替换路径

把faultylink(a，b)放入F中;

在节点a和节点b之间找到的最短路径替换faultylink(a，b);

flag←Binarysearch(p，low，high，faultylink(a，b));

end while.

end for.

折半查找在每条监测路径上只能识别出1条故障链路．在每条监测路径上，由于探测信号不能在故障链路上进行传送，所以故障链路后面的链路状态无法判断出来．因此，当在1条监测路径上定位出1条故障链路后，找一条最短路径替换这条故障链路，也就是在与故障链路相邻的两个节点间找到这条最短路径．这个过程一直持续到这条监测路径上的所有故障链路都被识别出来．图2给出示例，节点4的度为3，网络中有3条故障链路，一条探测所走的路径是1-4-3-4-1，实际的探测信号监测范围是1-4-3．图2在路径1-4-3-4-1上使用折半查找方法可以定位出故障链路(1，4)，但是不能定位出故障链路(3，4)．由于在节点1和节点4之间不能找到无故障的替换路径，所以在监测路径1-4-3上故障链路(1，4)后面的故障链路(3，4)不能被定位到．

图2 在3边连通的网络中的3条故障链路图3 k条链路组成图中的割

定理2用1个监测站来定位所有可能的k条故障链路的充分必要条件是网络为k+1 边连通的．

证明通过反证法来证明充分性．假设网络是k边连通的而不是k+1边连通的．因为网络不是k+1 边连通的，所以如图3存在一组k条链路，删掉它们后网络变得不连通，标记这些链路为l1，l2，…，lk．现在假设这k条链路都是故障的，当通过折半查找方法定位到故障链路l1后，不能找到健康的替换路径来替换掉l1，因为网络是k边连通的，而且这k条链路都是故障的．因此，当l1和li(li∈ (l2，…，lk))在同一监测路径上时，l1后面的故障(li)不能被监测站定位到，引出矛盾．因此，在k边连通的网络中不能定位出k条故障链路，即就是k+1 边连通是构造探测集合的充分条件．

通过构造法来证明必要性．因为网络是k+1边连通的，网络中的任意k条故障链路故障使得网络至少是1边连通的．对于任意一个故障链路，总能找到健康的替换路径并使用折半查找方法来定位同一监测路径上的其他故障链路．因此，总能找到这样的探测来定位k条故障链路．

在折半查找过程中，low表示探测的起始点，high表示探测的终止点．探测所走的路径是low-high-low，实际探测所监测的范围R是low-high．在监测站发送每次探测的开始，low是0，high是 |m|-1，|m|表示监测路径的长度．因此，初始的mid是 (|m|- 1)/2>．监测站将在监测路径上发送初始的探测，其探测的终点为high节点．p表示发送的探测，flag为折半查找的返回值．当flag为真时，探测路径上不存在故障链路；否则，返回一条故障链路．

为了减少计算时间，一条从发送方s开始到接收方t的随机游走所经过的节点被存放在vector容器中．由算法2得到的故障链路集合F被存放在内部数据结构中(C++中的std::set)，使得找到的F中不存在重复的故障链路．每条链路上的计数器ρ(ei)存放在平衡二叉查找树上(C++中的std::map)，这提供了快速查找和修改功能．当执行一条随机游走mj时，则需要更新被这条随机游走经过的所有链路上的计数器．

3　仿真结果

在Visual studio 2010上模拟全光网故障定位仿真系统，依据BA模型[10]生成平均节点度为2和3，节点范围为50～500，链路数从100到500的大型无标度网络，在生成的大型无标度网络上测试随机游走[4]算法和探测选择算法的性能．对于生成的每一个无标度网络，在故障检测过程中，固定两个最大度节点，分别为发送方和接收方(两个监测站)，以及任意选择一个最大度节点作为故障定位过程中的监测站．文中给出发送的探测数和每条链路上探测相关的平均波长数的仿真结果．由于在故障检测过程中所有的探测信号在监测路径上同时发送，则会造成每条链路上消耗过多的监测资源[11-12]．而在故障定位过程中每条探测在监测路径上按次序发送，探测经过的每条链路上消耗单个波长[13]，因此，文中只考虑故障检测过程中平均每条链路上消耗的监测波长．通过统计定位故障所发送的探测和每个探测的路径长度，来得出仿真结果要呈现的探测数和平均每条链路上消耗的监测波长．探测选择算法运行结果的仿真图描绘的每一点为在不同网络拓扑上100次实验的平均值，而随机游走算法的结果是通过不断地增加监测迹的数量来找到能够惟一定位故障链路所需的监测迹的数量，即就是发送的探测的数量．

3.1　在平均节点度为2的网络中定位所有的单链路故障

由BA模型生成无标度网络的过程可以知道平均节点度为2的网络的边连通度为2．依据定理2，在边连通度为2的网络中所有的单链路故障可以被定位出来．图4(a)给出了在平均节点度为2的网络中定位所有单链路故障时，随机游走算法和探测选择算法需要发送的探测数．从图4(a)可以看出，随机游走算法比探测选择算法需要发送更多的探测．图4(b)给出了在定位所有单链路故障时两种算法消耗的平均波长数的对比．为了在平均节点度为2的网络中定位所有的单链路故障，探测选择算法在每条链路上大约需要的平均波长数为6，而随机游走算法在每条链路上大约消耗的波长是22．

图4　平均节点度为2的网络中随机游走算法和探测选择算法的性能

3.2　在平均节点度为3的网络中定位任意两条链路故障

基于BA模型，平均节点度为3的网络的边连通度为3．图5(a)给出了定位平均节点度为3的网络中的任意两条故障链路时，随机游走算法和探测选择算法所需发送的探测数．对比探测选择算法，图5(a)表明随机游走算法需要更多的探测，图5(b)比较了定位任意两条链路故障时，两种算法在每条链路上需要的平均波长数．在每条链路上，探测选择算法大约需要的波长数为5，而随机游走算法需要的波长数大约为20．

图5　平均节点度为3的网络中随机游走算法和探测选择算法的性能

文中也研究了算法的稳健性，可通过增加链路数来增加网络规模．如图4(a)和5(a)所示，随着网络规模的增加，定位链路故障所需的探测数也在增加．因为链路数越多，定位越困难．

4　结 束 语

文中研究了全光网中使用适应性探测方案定位故障链路的探测选择算法，证明了最小监测路径集合问题是NP完全问题，接着通过启发式的监测路径选择算法来找到最小监测路径集合．进一步提出了在网络连通度方面用一个监测站来定位故障链路的充分必要条件．探测选择算法首先获得关于故障检测的一组监测路径，接着在有故障的监测路径上按次序发送探测信号来进行故障定位，避免了随机游走算法中消耗的大量探测和波长问题．仿真结果表明，探测选择算法有更优越的性能，具有很强的实际意义．

参考文献：

[1] 熊余, 董先存, 李圆圆, 等. 软件定义光网络中基于最小点覆盖的控制平面跨层生存性设计[J]. 电子与信息学报, 2016, 38(5): 1211-1218.

XIONG Yu, DONG Xiancun, LI Yuanyuan, et al. The Cross-layer Survivable Design of Control Plane Based on Minimum Point Covering in Software Defined Optical Network[J]. Journal of Electronics & Information Technology, 2016, 38(5): 1211-1218.

[2]HARVEY N J A, PATRASCU M, WEN Y G, et al. Non-adaptive Fault Diagnosis for All-optical Networks via Combinatorial Group Testing on Graphs[C]//Proceedings of the 2007 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 697-705.

[3]ALI M L, HO P H, TAPOLCAI J. SRLG Failure Localization Using Nested M-trails and Their Application to Adaptive Probing[J]. Networks, 2015, 66(4): 347-363.

[4]XUAN Y, SHEN Y, NGUYEN N P, et al. Efficient Multi-link Failure Localization Schemes in All-optical Networks[J]. IEEE Transactions on Communications, 2013, 61(3): 1144-1151.

[5]ALI M L, HO P H, TAPOLCAI J. A Novel M-trail Allocation Method for SRLG Fault Localization in All-optical Networks[J]. Optical Switching and Networking, 2017, 23(2): 179-188.

[6]TAPOLCAI J, RONYAI L, HOSSZU E, et al. Signaling Free Localization of Node Failures in All-optical Networks[C]//Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway: IEEE, 2014: 1860-1868.

[7] 刘英挺, 朱睿杰, 杜晓明, 等. 全光网中采用可信度模型的故障定位技术[J]. 西安电子科技大学学报, 2016, 43(6): 152-157.

LIU Yingting, ZHU Ruijie, DU Xiaoming, et al. Mechanism for Fault Location Based on the Credibility Model of All Optical Networks[J]. Journal of Xidian University, 2016, 43(6): 152-157.

[8]NATU M, SETHI A S, LLOYD E L. Efficient Probe Selection Algorithms for Fault Diagnosis[J]. Telecommunication Systems, 2008, 37(1/3): 109-125.

[9]张新, 常义林, 孙方涛, 等. 一种改进的网络故障监测算法[J]. 西安电子科技大学学报, 2006, 33(3): 416-421.

ZHANG Xin, CHANG Yilin, SUN Fangtao, et al. An Improved Algorithm for Monitoring the Network Fault[J]. Journal of Xidian University, 2006, 33(3): 416-421.

[10]ALBERT R, BARABASI A L. Statistical Mechanics of Complex Networks[J]. Quantitative Biology, 2001, 74(1): 47-97.

[11]THAI M T. Group Testing Theory in Network Security: Advanced Solution[M]. New York: Springer, 2012: 3-4.

[12]ALI M L, HO P H, TAPOLCAI J. SRLG Fault Localization Using Nested M-trails[J]. Computer Networks, 2015, 85: 63-79.

[13]WANG B, HO P H. Energy-efficient Routing and Bandwidth Allocation in OFDM-based Optical Networks[J]. Journal of Optical Communications and Networking, 2016, 8(2): 71-84.