一种基于最短长度m2圈算法的故障监测方案

陈第全，王贤亮，靳　敏，姜元帅，王　楠,张　炎

(1.重庆市电力公司, 重庆 400015；2.重庆邮电大学 光纤通信技术重点实验室,重庆 400065;3.重庆电信研究院， 重庆 401336)



一种基于最短长度m2圈算法的故障监测方案

陈第全1，王贤亮1，靳敏1，姜元帅1，王楠2,张炎3

(1.重庆市电力公司, 重庆 400015；2.重庆邮电大学 光纤通信技术重点实验室,重庆 400065;3.重庆电信研究院， 重庆 401336)

摘要：针对光突发交换网络中“逐跳检验”监测模式成本较高等问题，提出了一种新的基于最短长度m2圈算法的光突发交换网络故障监测机制。该机制根据最短长度m2圈算法寻找光突发交换网络中的圈覆盖放置故障探测模块，从而形成基于圈覆盖的光突发交换网络故障监测模式。同时，在最短长度m2圈算法的基础上提出一种相应的故障定位算法，利用异或关系衡量告警编码与链路相关编码是否吻合，从而进行快速故障定位。计算结果表明，基于最短长度m2圈算法的故障监测机制具备网络开销小、故障定位率高和故障定位快速等特点。

关键词：光突发交换；最短长度m2圈算法；故障监测；故障定位

0引言

光突发交换(optical burst switching ，OBS)技术由于结合了光电路交换和光分组交换二者的优点，成为波分复用光网络面向高突发、高速率IP业务的主要实现方案[1-4]。在OBS网络中，如果出现短暂的服务中断，将可能导致大量的数据流失，所以其快速的故障检测和定位就显得极其重要[5-8]。

在OBS网络中，故障的检测可以通过一些网络性能监视器来完成。在文献[9-11]中提出的圈覆盖理论能有效地降低检测成本和监视器的数目，并利用3种启发式圈覆盖算法来发现网络的圈覆盖，即深度优先搜索(heuristic depth first searchin，HDFS)、最短路径欧拉匹配(shortest path eulerian matching，SPEM)和生成树圈覆盖算法(heuristic spanning-tree，HST)。三者之中，HST算法相对于其他算法能够比较好地完成定位故障和减少网络的资源开销[9]，但是在故障定位率、圈长度以及监视器开销等方面都需要进一步改进，基于以上思想本文提出了基于最短长度m2圈算法(minimum-length monitoring cycles，m2cycles)的故障监测方法。

1故障监测方案的描述

1.1m2圈算法

m2圈算法的基本思想是：在一个给定的网络拓扑中，首先基于一条给定的链路，临时移除这条链路，然后找到这条移除链路所对应的2个端节点，并连接这2个节点之间的所有最短路径。集合这些基于一条给定的链路找到的最短路径，从而构建成一个最短长度的圈集合。m2圈构建可以分为2个主要步骤：扩展和优化。扩展过程就是构造出一系列的m2圈的集合，优化过程就是从以上集合中移除(添加)所有多余(遗失)的m2圈。具体过程如下所述。

1)初始化。

首先把图G(V,E)中所有的链路标为未覆盖。初始化集合B为空集∅。对在图G(V,E)中的每一条链路构建m2圈。然后把这些找到的圈按长度升序排列，并且添加到列表θ。

2)对集合B进行扩展。

步骤①搜索列表θ，从中找到第一个的m2圈，此圈含有一些未覆盖的链路，把这些没有覆盖的链路加入到集合F。

步骤②从F中选一条链路，然后找到所有覆盖它的m2圈。若m2圈覆盖至少一条标注为未覆盖的链路，那么就把这个m2圈添加到集合B中。把这些新的m2圈所覆盖的链路标记为已覆盖，然后把他们添加到T中。

步骤③把F中的剩余链路重复步骤②，直到没有新的m2圈可以添加到集合B中。

步骤④查找图G(V,E)所有链路还有没有未被覆盖到的，如果有的话，再转入步骤①。否则转入优化阶段。

3)针对告警信息的m2圈算法优化。

步骤⑤首先构造一个告警编码列表TA，这个列表中的行向量代表图G(V,E)中链路的告警编码，列向量代表集合B中的m2圈。初始化时TA的输入为0，对于每一个m2圈，它所覆盖到的链路标为1，否则标为0。

步骤⑥把TA中的每个列向量依次与其他列向量进行比较，首先列向量被依次标记出来，然后检查没有被标记的其他列向量是否出现全零行或者再出现相同告警编码。如果在移除这个被标记起来的列向量以后，出现一些全零行或者出现个别相同的告警编码变为不同的情况，说明这个m2圈不是多余的，然后对下一个列向量进行检查。否则，把这个列向量从TA中删除，相应的m2圈也从集合B中删除。重复步骤⑥直到所有的列向量都被检查过。

步骤⑦如果TA中出现两个或者多个相同告警编码时，算法随机选取具有相同告警编码链路中的一条，同时从图G(V,E)中移除具有相同告警编码的链路集合中剩下的链路，然后用选取的这条链路和其他具有相同告警编码链路的节点一起建立新的m2圈，这些新的m2圈只覆盖所选取的那条链路，而不覆盖那些具有相同告警编码的其他链路，反之亦然。如果找到多个这样的m2圈，只把最短长度的m2圈添加到B中，并且把它变成一个新的列向量添加到TA中。

步骤⑧将集合B初始化为C,C就是我们要找的最后m2圈集合，对应的告警编码为TA。

1.2基于m2圈的故障定位算法

在图G(V,E)中，链路ei∈E(i=1,2,…,L)和m2圈cj二者的关系可以定义为一个二进制编码aij来表示

(1)

进而可以通过相关联的编码ai=(ai1,ai2,…,aiM)表示链路ei与所有m2圈的关系，此外对于故障时所触发的告警mj与m2圈cj也可以得到以下关系

(2)

这样，所有m2圈的告警编码就可以表示为m=(m1m2…mM)。

倘若m2圈发出告警，并产生了告警编码。为判定链路ei是否属于故障候选链路，需要利用异或关系衡量告警编码与链路相关编码是否吻合，表示为

(3)

(3)式中，i=1,2,…,L，若Fi为0，则表明二者是吻合的，链路ei就是告警编码m=(m1m2…mM)相关的故障候选链路。

上述方法对所有的链路相关编码aij进行了逐个检查，提前判断出可能的告警编码mj，进而得到故障告警集合。故障时直接对比定位，有效地减少故障定位的时间。

1.3复杂度分析

本文m2圈算法由圈构造、增加丢失的圈和移除多余的圈3部分组成，分析发现算法的复杂度是由圈构造这部分决定。N个节点的网络拓扑至多有N2条链路，对每条未覆盖的链路需要利用最短路径算法寻找一个圈进行覆盖，而最短路径算法的复杂度为O(N2)，因此，圈构造的复杂度不会超过O(N4)。所以，整个m2算法的复杂度至多为O(N4)。

2性能比较

2.1探测圈的评价标准

为评价不同圈发现算法的性能，直观有效地发现合适的圈，在OBS网络环境中定义以下变量和参数来衡量圈覆盖发现算法。

给定网络的物理拓扑为有限无向连通图G(V,E)，V(G)是网络中节点的总数，E(G)是网络中链路的总数。

定义L(ci)为圈ci的边数，等于通过跳数计算出的探测突发(probeburst,PB)的生命周期。同时，应尽量减小圈长度，以此保证PB与数据突发(databurst,DB)使用通道时不发生冲突。|L(ci)|为圈长L(ci)的数量，圈覆盖C的总长度可以表示为

(4)

(4)式中，M为C中元素的个数。当发现一个圈覆盖C时，C中圈的平均长度为

avrg_length(C)=L(C)/M

(5)

当发现一个圈覆盖时，C中所有圈的最大长度为

max_length(C)=max{l(ci)|i=1,2,…,M}

(6)

当发现一个圈覆盖时，图G(V,E)中平均每个节点需要配置的监测设备的个数表示为

(7)

因此，基于m2圈的监测算法主要目的就是尽可能减少cost(p)。

文献[12]中提到对于给定的一个拓扑，其在度数为2的路径上的链路(一条路径上除了这条路径的端点的度数以外，其所有内部节点的度数都为2)需要额外增加监视器才能进行完全定位。同时，为了客观地反映增加的监视器带来的损耗，定义了损耗减少率为

(8)

(8)式中：M为监视器增加之前的个数；M′表示完全定位需要增加的监视器个数。

T(ei)表示当发现一个圈覆盖时，链路ei被覆盖的次数，这里ei∈E。T(ei)越大，表明监视器耗用链路ei的带宽越多，又设图G(V,E)的圈覆盖C中被覆盖T(ei)次的链路有|T(ei)|条。当发现一个圈覆盖时，平均每条链路被覆盖的次数表示为

(9)

在真实通信网络中，大多数链路都是可以完全定位的，但它并不能保证始终达到这一目的，因为一些告警编码对于特殊链路是不能精确定位的(例如：在度数为2的路径上的链路，其告警编码是一样的)。因此，需要一个最低定位门限来衡量，定义为故障定位率，用DL来表示

(10)

(10)式中：E(G)表示所有被监视链路的总和，即为图G(V,E)中链路的总数；A为所有告警编码的集合总和。因为可能出现很多被覆盖到的链路其告警编码是一样的，所以，E(G)要大于A，为了达到较准确的定位，我们要尽可能找到一种圈发现算法，其定位率尽可能趋近于1，最理想的情况是达到完全精确定位，即DL=1。

2.2m2圈覆盖算法与其他算法的统计比较

图1为4种典型的MESH网络拓扑。采用图1中国教育和科研计算机网(chinaeducationandresearchnetwork,CERNET)、国家科学基金网(nationalsciencefoundationnetwork,NSFNET)、贝尔通信研究中心(Bellcommunicationsresearchcenter,BELLCORE)，小型网络(smallnetwork,SMALLNET)的拓扑来仿真，并对几种圈覆盖算法的监测成本用以上几个标准进行比较分析，仿真结果如图2—图7所示。

图2为4种圈覆盖发现算法在不同拓扑中的cost(p)，从图2中可以看出，m2圈算法和HST算法使用的探测突发监测设备数目最多，而SPEM算法使用的数目最少，大约少使用了接近一半的探测突发监测设备。图2为4种不同网络拓扑中所需监测器的个数情况，而监测器个数就是圈覆盖中圈的个数。由于HST所需要的监测器的个数是多于HDFS和SPEM的[9]，因此，这里只对HST和m2圈算法的监测器个数进行分析。由于HST的圈覆盖是基于生成树机制进行构造的，所有构造的圈没有多余。相反，m2圈覆盖算法构造的圈是有多余的，不过m2圈可以针对告警信息对圈覆盖进行优化，去除多余的圈，这就保证了m2圈覆盖算法的圈个数不会多于HST算法，因此，其监测器个数也不会多于HST算法。

图1　4种典型的MESH网络拓扑Fig.1　Topologies of four typical network

图2　4种圈覆盖发现算法在不同拓扑中的cost(p)Fig.2　cos t(p)computed by four cycle finding algorithms

图3和图4主要对4种算法寻找到的圈覆盖的平均圈长度和最大长度分别进行了对比分析。无论对于平均圈长度还是最大长度，m2圈算法寻找到的圈覆盖都优于其他算法，因而m2算法可以极大地缓解PB与DB对数据通道的竞争。

图3　4种圈覆盖发现算法在不同拓扑中的avrg_length(C)Fig.3　avrg_length(C) computed by four cycle finding algorithms

图5为4种算法寻找到的圈覆盖对链路的平均覆盖次数。虽然m2圈算法中链路平均覆盖次数不是最少的，一定程度上增加了PB消耗掉的链路带宽。不过，由于PB消耗的带宽数量级远低于波长信道，因此PB额外消耗的链路带宽对算法性能的影响很小。

图4　4种圈覆盖发现算法在不同拓扑中的max_length(C)Fig.4　max_length(C) computed by four cycle finding algorithms

图5　4种圈覆盖发现算法在不同拓扑中的avrg_T(E)Fig.5　avrg_T(E) computed by four cycle finding algorithms

图6为4种圈覆盖发现算法在不同拓扑中的DL。从图6中可以看出,在故障定位率方面m2圈算法和HST算法的定位率较高，相比其他2种算法在定位方面要精确很多。图6中的仿真参数定位率为链路总数与不重复告警编码集合的比值，可见定位率由不重复的告警编码集合决定。由于HST算法的定位率是优于HDFS和SPEM的，因此，这里只对HST和m2圈算法的定位率进行分析。如果两条故障链路的告警编码一样，m2圈算法需要移除两条故障链路中的一条并重新为另外一条链路寻找一个圈。倘若m2圈算法找不到这样一个圈，就无法区分这两个故障，并表明这两条故障链路在一个圈上，那么这个圈必为HST构造的圈覆盖中仅有的一个圈，因此，HST同样无法区分这2个故障。同理，如果m2圈覆盖算法可以区分这2个故障，那么HST算法也可以区分这2个故障。所以HST和本文m2圈覆盖算法的故障定位率是相同的。

图6　4种圈覆盖发现算法在不同拓扑中的DLFig.6　DL computed by four cycle finding algorithms

图7为4种圈覆盖发现算法在不同拓扑中的G。在4种拓扑都达到完全定位时，m2圈相比其他3种圈发现算法，其监视器的损耗减少率是最多的。图7中的仿真参数损耗减少率经过分析可以看出是由监视器增加之前的个数和完全定位需要增加的监视器个数决定的。由于HST和本文m2圈算法的故障定位率相同，因此，达到完全定位m2圈算法需要增加的监测器个数不会多于HST算法。而经过图2对监测器个数的分析，可知m2圈算法监测器增加之前的个数不会多于HST算法。从而m2圈算法监视器增加之前的个数与完全定位需要增加的监视器个数之和也不会多于HST算法，即m2圈覆盖算法的损耗减少率是不少于HST算法的。然而由于不同网络拓扑的平均连通度不同，所以，在有些网络拓扑上2种算法的损耗减少率是相同的。

图7　4种圈覆盖发现算法在不同拓扑中的GFig.7　G computed by four cycle finding algorithms

图2—图7表明：圈覆盖算法可有效地减少探测模块的数量。但是4种算法要针对不同网络拓扑进行有效地选择,m2圈算法不仅有较高的故障定位率，并且相对于其他3种算法所需要的平均圈长度和最长圈长度最小。

3结论

本文提出了一种新的基于m2圈覆盖的故障监测方法,运用圈覆盖理论减少OBS网络中需要的故障监视器的数量，并在4个典型网络拓扑中对4种不同圈覆盖算法的故障定位率、监视器的损耗概率、对于链路的负荷方面进行了性能比较。仿真表明，基于m2圈覆盖的OBS网络故障监测机制可以对监视器成本和链路带宽开销进行很好的折中，相对于逐跳校验模型，该监测机制在探测模块昂贵时可以有效地降低网络监测成本。

参考文献：

[1]WU G, ZHANG T, CHEN J, et al. An index-based parallel scheduler for optical burst switching networks[J]. Lightwave Technology, 2011, 29(18): 2766-2773.

[2]BELBEKKOUCHE A, HAFID A, GENDREAU M, et al. Path-based QoS provisioning for optical burst switching networks[J]. Journal of Lightwave Technology, 2011, 29(13): 2048-2063.

[3]AKAR N, KARASAN E, VLACHOS K G, et al. A survey of quality of service differentiation mechanisms for optical burst switching networks[J]. Optical Switching and Networking, 2010, 7(1): 1-11.

[4]KLINKOWSKO M,PEDRO J,CAREGLIO D,et al.An overview of routing methods in optical burst switching networks[J].Optical Switching and Networking,2010,7(2):41-53.

[5]OGINO N, NAKAMURA H. All-optical monitoring path computation based on lower bounds of required number of paths[C]//Communications (ICC), 2011 IEEE International Conference on.Kyoto,Japan: IEEE Press,2011:1-6.

[6]GARG A K. An efficient fault localization or detection mechanism for high speed optical networks[J]. Optik-International Journal for Light and Electron Optics, 2013, 124(21): 5127-5130.

[7]HE W, WU B, HO P H, et al. Monitoring trail allocation for SRLG failure localization[C]//Global Telecommunications Conference (GLOBECOM 2011). Houston ,USA:IEEE Press, 2011: 1-5.

[8]ALI M L, HO P H, TAPOLCAI J. Fault localization in all-optical linear networks[C]//Knowledge and Smart Technology (KST), 2014 6th International Conference on. Chon buri, Thailand: IEEE Press, 2014: 93-98.

[9]ZENG H, HUANG C, VUKOVIC A. Spanning-tree based monitoring-cycle construction for fault detection and localization in mesh AONs[C]//Communications(ICC), 2005 IEEE International Conference on. Seoul, Korea: IEEE Press, 2005: 1726-1730.

[10] ZENG H, HUANG C. Fault detection and path performance monitoring in meshed all-optical networks[C]//Global Telecommunications Conference, 2004. Texas, USA: IEEE Press, 2004: 2014-2018.

[11] 王汝言, 常交法, 隆克平, 等. 基于圈覆盖的光突发交换网状网故障监测方案[J]. 北京邮电大学学报, 2007, 30(4): 111-115.

WANG R,CHANG J,LONG Keping, et al. Fault Detection Mechanism Based on Probe Cycle Cover in Meshed Optical Burst Switching Networks[J]. Journal of Beijing University of Posts and Telecommunications, 2007，30 (4):111-115.

[12] WANG R Y, LONG K P, WU W, et al. A Limited Deflection Routing Algorithm Based on Burst Loss Threshold in OBS Networks[J]. The Journal of China Universities of Posts and Telecommunications, 2005, 12(3): 44-48.

DOI：10.3979/j.issn.1673-825X.2016.03.016

收稿日期：2014-09-21

修订日期：2015-07-18通讯作者：陈第全chendiquancq@163.com

基金项目：国家电网公司科技项目(SGTYHT/13-JS-175)；重庆市电子信息产品测试工程技术研究中心，重庆市工程技术中心(渝科委发[2014]1号)；重庆市科技平台与基地建设计划项目(工程技术研究中心)(cstc2014pt-gc40002)

Foundation Items：The science and technology projects of State Grid(SGTYHT/13-JS-175)；The Chongqing Engineering Research center of Electronic Information Products Testing[2014]1); The R & D Base Capacity Improvement Project of Chongqing Science & Technology commission(cstc2014pt-gc40002)

中图分类号：TN929

文献标志码：A

文章编号：1673-825X(2016)03-0377-06

作者简介：

陈弟全(1969-)，男，重庆人，工程师，主要研究方向为电力通信。E-mail: chendiquancq@163.com。

王贤亮(1975-)，男，重庆人，硕士研究生，副高级工程师，主要研究方向为信息通信技术研究。E-mail: wangxliang163@163.com。

靳敏(1989-)，女，重庆人，本科。主要研究方向为信息通信运维工作，参与信息通信相关项目实施，开展信息通信技术研究。E-mail: jinminm163@163.com。

姜元帅(1983-)，男，重庆人，专科，主要研究方向为变电运行维护、信息运行维护、电力营销等工作。E-mail: jiangys163@163.com。

(编辑：田海江)

A fault detection mechanism based on minimum-length probe cycle cover algorithm

CHEN Diquan1，WANG Xianliang1，JIN Min1，JIANG Yuanshuai1，WANG Nan2，ZHANG Yan3

(1. Chongqing Electric Power Company, Chongqing 400015, P.R. China；2. Key Laboratory of Optical Fiber Communication, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China；3. Chongqing Institude of Telecommunications, Chongqing 401336, P.R. China)

Abstract:A new fault detection mechanism based on minimum-length probe cycle cover algorithm is proposed in terms of costly sing-hop test module in optical burst switching networks. The minimum-length cycle finding algorithm is used to find cycle cover for optical burst switching networks. After that, a probe module is assigned for each cycle and a fault detection mechanism based on probe cycle cover is formed in optical burst switching networks. Meanwhile a corresponding fault localization method based on minimum-length probe cycle cover is developped. The mechanism compares the alarm code with the associative code to achieve fast link localization. The computation and statistic results show that this fault detection mechanism has the features of the least amount of network resources, higher fault localization degree and fast fault localization, etc.

Keywords：optical burst switching; minimum-length probe cycle cover algorithm; fault detection; fault localization