基于探测圈覆盖的光突发交换网络故障定位

包宋建

（重庆文理学院 电子电气工程学院，重庆 402160）

0 引言

光网络故障的识别和定位是极其重要的，现有的一些故障定位算法主要有Rete算法、数据挖掘算法、图论里的相关算法等，但是这些算法对于OBS网络而言，缺乏适用性。本文提出了基于探测圈覆盖的光突发交换网络故障定位方案。该方案分为2个阶段：1）收集由故障触发的告警信息，组成相应的二进制告警相关矩阵；2）采用预计算的方式，利用告警矩阵进行定位，能在兼顾漏告警和误告警的情况下解决多故障定位问题，找到可能的故障设备集合，进行有效定位。

1 OBS网络设备告警能力分析

对OBS网络硬件设备告警能力分析主要根据故障发生时网络硬件设备的反应状况定义。在对硬件设备的告警能力分析时，主要考虑以下3个特性[1]：

1）自身告警。拥有此特性的设备可以发出关于自身硬故障的告警。

2）外部告警。拥有此特性的设备可以与管理器进行通信，发出关于外部其他设备的故障告警。

3）硬故障屏蔽。拥有此特性的设备可以屏蔽后面的硬件设备硬故障。

对光网络中硬件设备具体分类如表1所示。从上面的分析可以看出，在OBS网络中，当某些网络器件发生故障的时候就有可能产生漏告警以及误告警的情况，所以在下面的故障定位算法中，考虑了漏告警和误告警的情况，这样能够使网络管理者快速有效地定位OBS网络故障，并执行OBS网络故障管理措施，使得整个OBS网络有效有序传输。

表1 OBS网络硬件设备告警能力

2 OBS网络中故障探测和定位算法

在OBS网络中，无论是单一故障还是多故障都能被告警器探测到并发出警报，为了降低故障管理的复杂度和成本，尽量用最少的监视设备来监视整个OBS网络元素。干扰告警（误告警和漏告警）的出现会使得故障定位的难度加大，对此，故障定位方案主要分为2个步骤：1）探测和收集OBS网络元素的各种告警信息；2）应用提到的故障定位算法，最后得到可能发生故障的OBS网络故障设备集合。具体流程如图1所示。

在收到来自监视设备的告警后，无论告警的类型如何，故障定位算法都将运行，把刚收到的告警信息与预先计算出来的告警矩阵进行比较，在这个比较过程中将产生可能发生故障的OBS网络故障设备集合，然后对发出和接收的信号进行处理和分析，从此集合中确定准确的故障设备。

2.1 基于m2圈的OBS网络链路故障定位算法

在监测范围内的OBS网络元素无论何时发生故障，监视设备都将产生告警。但是OBS网络中也经常受到错误告警和漏告警的干扰，原因在其监视设备中的门限值较低或其在监视设备中的门限值较高[2]。在图G(V,E)中，链路ei∈E(i=1,2,…,L)和m2圈cj两者的关系可以定义为一个二进制编码aij表示

每一条链路ei对应的所有m2圈就可以得到相关联的编码ai=(ai1,ai2,…,aiM)，此外对于发生故障时所触发的告警mj与m2圈cj也可以得到以下关系

这样，所有m2圈的告警编码就可以表示为m=(m1,m2,…,mM)。一旦接受到m2圈中的告警，那么告警编码随即产生。比较告警编码mj与每条链路所相关的编码aij，如果链路相关编码和告警编码吻合，那么这条链路就是故障候选链路之一，两者的比较关系用异或关系来衡量，表示为

式中：i=1,2,…,L，如果Fi为0，那么链路ei就是告警编码m=(m1,m2,…,mM)的一个候选故障点。按照以上方法检查完所有的链路相关编码aij后，就获得所有的告警候选集合。可以预先列举出所有可能的告警编码mj，建立相应的故障告警集合，当故障发生时可以直接进行对比定位，所以这种算法可以节省大量的故障定位时间。

2.2 OBS网络节点故障定位算法

生存性实施的故障定位只需将故障定位到资源即可[3]。资源是相对于业务而言的。下面介绍一种故障定位机制，在这个机制之中C代表所有OBS网络器件的集合，M代表所有监视器集合，OBS光网络器件v的一个告警域（当v发生故障时，引起告警的所有监视设备集合）用Domain(v)表示。定义响铃的监视设备集合用MR表示（MR⊆M）。同理，定义MS为没有响铃的监视设备集合（MS=M/MR）。设定C ′是C的一个子集，MA(C ′)为在没有误告警和漏告警的情况下，C′中的所有设备发生故障时监视器都会正常发出告警。那么当告警产生干扰的情况下，MA(C ′)≠MR。误告警可表示为MF(C ′)=MR/MA(C ′)。同理可得，漏告警可表示为MM(C ′)=MS⋂MA(C ′)。多故障定位的目标就是在覆盖告警矩阵中所有响铃的告警（即在告警矩阵中为1的告警）而不是未响铃告警（即在告警矩阵中为0的告警），尽量使得最终的故障设备集合最小，达到精确定位的目的。所以本文想找到C的一个子集C′，其中故障设备集| |C′的数量尽量最小，并且没有误告警时，上述情况满足MF(C′)=φ；没有漏告警的情况满足MM(C′)=φ。在定位算法中，需要考虑以下4种情况：

1）没有误告警和漏告警的故障定位问题

其实在理想情况下的多故障定位问题等同于一个集覆盖问题（set cover问题），而集覆盖问题又是一个完全NP问题[4]。为了解决这个问题，本文借鉴集覆盖中的自适应贪婪优化算法来对多故障进行定位，此算法在告警矩阵中反复逐一选取告警域中包括最多响铃告警的故障设备。

对任意一个OBS网络拓扑，首先通过探测圈发现算法得到一个告警矩阵，然后对其运行故障定位算法，并满足条件Domain(c)⊆MR。对于多故障的情况，把收到的告警编码求并，在定位算法运行期间告警矩阵中的各个网络设备（网络节点）根据条件逐一进行定位比较，即满足

2）有一个误告警，没有漏告警的情况

OBS网络是通过时域共享、统计复用光波长信道来有效支持上层协议或高层用户产生的突发业务，所以信道中光信号的有无是随机的，无光（Loss-of-light）并不意味着一定有故障事件发生。这使得通过监测光信号的有无来确定是否产生告警的故障监测点会产生过多的误告警，以至于故障定位算法无法定位故障，或者由于监视设备中的告警门限值设置较低时，也可能产生此情况[5]。所以当收到响铃的告警集MR时，其中可能存在一些误告警，需要确定一个网络设备集FD⊆C，它有最少的误告警数目（即| MF(FD)|最小）并且满足MM(C′)=φ。具体算法为：

3）有一个漏告警，没有误告警的情况

这是在监视设备中的告警门限值设置较高时可能产生的情况。需要确定一个网络设备集FD⊆C，它有最少的漏告警数目（即| MM(FD)|最小）并且满足MF(C ′)=φ。由于漏告警的问题是一个完全NP问题，所以其相对于误告警的纠正要困难得多[6]，所以应该设置监视器的告警门限，使得漏告警的数目达到最少，以减少故障定位过程中带来的干扰。具体算法为：

4）有一个误告警和一个漏告警的情况

在真实OBS网络中，网络的运行状况是很复杂的，很难确定只有一个漏告警或者只有一个误告警的发生，因此本文提出这样一个算法尽量对两者同时发生时共同进行考虑。具体算法为：

基于探测圈的故障定位算法考虑了4种情况：1）没有误告警和漏告警；2）一个误告警，没有漏告警；3）一个漏告警，没有误告警；4）一个误告警和一个漏告警。本算法举例见表2。

表2 告警相关矩阵

对于任意一个OBS网络拓扑，先确定找到所有的最短长度m圈，然后产生如表2所示的告警矩阵，假如接收到一个告警集合为{1，1，1，0，0}，那么说明M3，M6，M7触发了告警，而M1，M13处于未触发状态。对于情况1）来说，都是正常告警，现在网络节点4的告警域可以表示为Domain(ND4)⊆MR，同理可以得出Domain(ND6)⊆MR，Domain(ND10)⊆ MR，Domain(ND12)⊆MR。根据多故障定位算法可以得到｛ND4，ND6，ND10，ND12｝属于故障设备FC（Faulty Component）；对于情况2），有一个误告警，那么找到的告警集合就会多出｛（1，1，0，0，0），（1，0，1，0，0），（0，1，1，0，0）｝；对于情况3），告警集合就会多出｛（1，1，1，1，0），（1，1，1，0，1）｝；对于情况4），就会多出｛（0，1，1，1，0），（0，1，1，0，1），（1，0，1，1，0），（1，0，1，0，1），（1，1，0，1，0），（1，1，0，0，1）｝几个告警集合，然后分别运行多故障定位算法来进行定位。

3 仿真性能比较

C.Mas对于WDM光网络的故障探测和定位研究做了探讨，并且仿真性能证明了二叉树模型是一种快速有效的故障定位算法[1]。但是随着网络节点和故障数目的增加，二叉树的枝叶数和各个根节点的数目会迅速增长，所以需要超大的存储空间，并且在最终故障定位的准确度方面有待提高。本文提出的算法主要是针对以上特点进行全面的考虑，在接收到一个告警编码时，考虑了所有漏告警和误告警的情况，找到每种情况下可能出现的OBS网络故障设备数目，然后对其求均值；同理找到传统二叉树定位算法的故障设备数目的均值，对两个定位算法进行比较，性能比较如图2和图3所示。

通过分析C.Mas二叉树故障定位算法的运行过程，得出如下结论：

1）网络依赖模型二叉树的建立过程（即预计算过程）复杂，网络中告警设备的种类和数量不能太少，否则就没有足够的告警信息进行关联，无法准确地进行故障定位。如果输入的告警信息为0001010000000时，这种算法获取单个故障定位的结果不是唯一的，导致了多个故障和漏（误）告警情况下故障定位的准确率降低。

2）如果告警设备集中只有一个告警设备告警，当发生漏告警时，将无法定位网络中发生故障的设备。

3）这种基于信道编码的方法中，每个信道的最后一个设备的告警设备集总是为空，如果这些设备发生故障，就无法对其进行定位。而基于探测圈的故障定位算法在考虑漏（误）告警的同时，因为借鉴了集覆盖中的自适应贪婪优化算法，所以在以上几方面都有很大的改善，只需要找到告警域中包含最多响铃告警的故障设备即可。

由图2和图3比较可以看出两种算法在同样考虑漏告警和误告警的情况下，基于探测圈的故障定位算法无论在单一故障还是多故障时，其最终找到的故障设备数目要小，使得故障管理人员缩小故障搜索范围，达到准确定位。

4 小结

本文根据OBS网络拓扑等特点，提出一种基于探测圈覆盖的故障定位方案。此方案主要针对OBS网络链路和节点进行双重定位，使得故障定位更加准确。对于一个网络拓扑首先利用最短长度m圈算法建立故障监视器与网络拓扑中的节点、链路建立相关性模型，然后分别对其进行多故障定位，并且考虑了漏告警与误告警等常见干扰的情况。由仿真结果可以看出，在同样考虑干扰告警的情况下，本文提出的基于探测圈的故障定位算法相对与传统的二叉树故障定位算法拥有较精确的定位范围，能够最终实现OBS网络的快速有效的故障定位。

[1]MAS C，THIRAN P.An efficient algorithm for locating soft and hard failures in WDM networks[J].IEEE Journal on Selected Areas in Communications，2000，18（10）：1900-1911.

[2]NAYEK P，PAL S，CHOUDHURY B，et al.Optimal monitor placement scheme for single fault detection in optical network[C]//Proc.IEEE 2005 7th International Conference on Transparent Optical Networks.Barcelona，Spain：IEEE Press，2005，1：433-436.

[3]WANG Ruyan，CHANG Jiaofa，LONG Keping.A fault detection and location mechanism for optical burst switching networks[J].Journal of Optoelectronics Laser，2006，17（12）：1477-1481.

[4]HOCHBAUM D S.Approximation algorithms for NP-hard problems[M].[S.l.]：Course Technology，1996.

[5]江城，张重阳，余松煜.基于异常检测与双流编码的视频监控系统设计[J].电视技术，2011，35（1）：111-114.

[6]CARR R D，DODDI S，KONJEVOD G，et al.On the red-blue set cover problem[EB/OL].[2010-10-09].http：//portal.acm.org/citation.cfm?id=338219.338271.