基于最小生成树的网络故障定位算法研究

韩瑞东，殷圣忠，李 萍

(1.运城学院计算机科学与技术系，山西运城044000；2.中国新闻社，北京100037)

基于最小生成树的网络故障定位算法研究

韩瑞东1，殷圣忠2，李 萍1

(1.运城学院计算机科学与技术系，山西运城044000；2.中国新闻社，北京100037)

针对网络中某一个设备故障可能会使其他设备产生告警甚至影响整个网络运行的这种情况，提出一种基于最小生成树的网络故障定位算法以找出故障源。该算法包括时间关联分析和空间关联分析，时间关联分析通过压缩、过滤、计数和抑止规则对告警信息进行处理以减少冗余。空间关联分析通过预处理、告警分析、调整最小生成树和链路关联四部分对进行冗余处理后的告警信息进行处理以确定出真正的故障源。算法结果表明，其可以有效支持校园网络的故障管理，帮助网络管理员快速找出故障设备，以提高工作效率。

网络故障；关联分析；定位；故障源

随着互联网的快速发展，网络规模不断扩大，网络中出现的故障可能会影响整个网络，甚至会给社会带来巨大损失，网络安全问题变得重要[1]。当网络中某一个设备产生故障时，可能会使其他正常的网元也发生告警，从而使整个网络产生大量的告警信息，在这些告警信息中，要找出真正的故障源，就需要对这些告警信息进行关联分析[2]。传统的算法是基于方法库的，把产生故障的情况在方法库中找到最类似的情况排查故障(情况相似度至少高达90%)，实现难度较大，复杂度高，且效率低。因此，提出一种基于最小生成树的网络故障定位算法。

1 算法原理

由于一台设备故障时，不仅会使自身产生重复告警，也会使其他正常的设备发出相同或相关的告警，要确定具体的故障源，就需要先对重复或相关的告警进行冗余，然后通过具体的网络拓扑结构来定位出真正的故障源。所以，提出的算法包含两方面：时间关联分析和空间关联分析。

1.1 时间关联分析

在网络运行过程中，当某一个网元产生告警信息时，在一段时间内可能会产生大量相同的或相关的告警信息，为了减少冗余，首先对这些告警信息进行时间关联分析。根据网络实际运行情况设定时间窗口T(两个告警事件产生的时间差不能大于该值)，然后利用下面四种规则进行关联分析，以减少冗余[3]。

(1)压缩(Compression)

针对某一台设备会产生大量的重复告警信息，而在规定的时间窗口内只需要保留一条即可，其他的自动丢掉，就需要使用压缩规则。其规则如下所示：

该规则中，Ei代表的是第i个告警事件，Ti代表的是第i个告警事件发生的时间，根据IP地址来判断是不是同一个设备发出的相同告警事件，用“= =”表示。

(2)过滤(Fliltering)

网络中产生的大量告警信息有些并不是我们所关心的，对网络运行也不会产生影响，那就在时间段内直接过滤，针对此情况，就需要使用过滤规则。其规则如下：

该规则中，A代表的是告警条件，S(Ei)代表的是第i个事件发生时所带参数是否符合A的条件。

(3)计数(Counting)

针对某一个网元在设定的时间窗口内可能只产生一次或几次告警，就需要使用计数规则。根据网络实际情况，在这设定一个值M，超过该值时，保留；否则舍掉。其规则如下：

该规则中，M为根据网络实际情况设置的预定值，N为总事件个数，count为计算相同事件的参数。

(4)抑止(Suppression)

网络运行过程中某一个网元(如路由器、交换机等)发生告警信息时，其每个端口都会产生告警信息，根据每个端口告警信息的优先级(以告警信息的严重程度来判断)来进行关联分析，丢掉优先级低的，保留高的。针对该情况，就需要使用抑止规则。其规则如下：

该规则中，sIP代表的是同一台设备不同端口发出的告警信息，S代表的是严重级别。

1.2 空间关联分析

空间关联分析主要是根据网络的拓扑结构来进行的，通过利用最小生成树的相关知识分析被管网元之间的关系来寻找出故障源[4]。图1所示为告警关联流程图，利用实际网络的拓扑结构，可以看做是图，再利用相关算法实现最小生成树，在最小生成树中利用设备之间的关系来判断出故障事件，以达到目的。

由于现实网络中并不是所有的设备都两两相连，所以可以把网络拓扑看做是一个稀疏图，用邻接表来存储。这样就能很好地节省空间，并且能够支持算法的实现。该算法是根据网络拓扑模块提供的相关信息找出一个最小生成树，然后再根据这个最小生成树对故障信息进行关联分析。对于最小生成树来说，若两个节点在相同的子树上，则这两个节点之间有且只有一条链路。通过数据结构知识中最小生成树的性质，保留关键的信息，消除一些不必要的链路信息。当收到告警信息时，算法就会判断是否为链路故障信息，如果是最小生成树的路径，就把该最小生成树拆成两个不同的子树，算法就会搜索这两个子树的所有节点，查出不包含的网络监控的子树，就会过滤掉这棵子树所有节点的告警信息，只保留关键路径告警信息。数据结构中，最小生成树有两种经典算法，普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法，Prim算法的时间复杂度为O(n2)，而Kruskal算法的时间复杂度为O(eloge)[5]。对比这两个算法，Kruskal算法主要是针对边来展开，边数越少越有效，对稀疏图有优势；而Prim算法对稠密图会更好一些。根据对比，本算法的实现采用Kruskal算法。

图1 告警关联流程图

2 算法实现

算法由预处理、告警分析、调整最小生成树以及链路关联等组成，时间复杂度为O(eloge)，e是链路数。如图2所示。

图2 空间关联分析流程图

2.1 预处理

该阶段主要是通过拓扑发现模块得到网络拓扑结构用邻接表来存储，然后利用Kruskal算法实现最小生成树，流程图如图3所示。

图3 预处理流程图

2.2 告警分析

当接收到一个告警信息时，如果已经被上文提到的时间关联分析过滤掉的话，那就无需再对其进行空间关联分析了。若没有被规则关联掉，则判断其是否为拓扑告警，否的话就把它放到延迟队列等待下一步处理。是的话就需要再次判断该拓扑告警是否为最小生成树的链路告警，或判断是否为连接两棵不同的最小生成树的链路告警，判断是，则调整最小生成树，否则需要把其放入延迟队列等待下一步处理。其流程图如图4所示。

图4 告警分析流程图

2.3 调整最小生成树

调整最小生成树包括拆分与合并最小生成树两方面。

接收到告警信息时，如果其是最小生成树上的链路告警时，就将最小生成树拆成两个子树，再次运行Kruskal算法，寻找是否存在另外一条路径能够将这两棵子树相连，若存在，则调整最小生成树，把这个新的路径替换掉原来的那条路径并去除，然后把该告警信息放入延迟队列等待下一步处理。若不存在，就需要对其进行链路关联，如果主干链路故障，就把其产生的告警信息进行关联压抑，消除冗余。

如果收到的告警信息是一个恢复正常的链路信息时，且这个链路连接的是两个不同的最小生成树，则这个最小生成树也需要调整，将这两个最小生成树调整为一棵最小生成树，然后把告警信息放入延迟队列中等待下一步的关联处理。其流程图如图5所示。

图5 调整最小生成树流程图

2.4 链路关联

其主要目的是对由于链路故障产生的误报的告警信息进行关联压抑。当最小生成树被拆分成两棵子树时，算法会遍历这两个子树的所有节点，查找出网络监控节点所在的那个子树。然后查找延迟队列里的所有告警信息，将没有网络监控节点的那棵最小生成树上的所有节点的告警信息消除，把剩下的告警信息再放回到延迟队列等待进一步的关联分析。

3 算法验证

通过该算法，实现了对告警信息进行关联分析，能够定位出故障源。图6显示了该算法与传统算法所用时间的对比[6]。较之一般方法(引言中所提)，基于最小生成树的网络定位算法能够将告警过滤时间提升40%，降低了因为分析无关网络节点所浪费的时间。

图6 拓扑方法与一般方法时间对比图

从上图所示的数据对比与验证，证明了该算法的正确性及有效性，并能够快速地定位出故障源。

4 结语

在实际网络情况中，当某一网络设备发生故障时，可能会引起其他一些正常的设备也产生告警，为了能快速高效地查找出真正的故障源，本文提出一种基于最小生成树的网络故障定位算法。该算法根据具体的网络拓扑结构生成最小生成树并根据具体情况来调整最小生成树以定位出故障源。在基于空间关联分析之前，首先要对时间段内的告警信息进行时间关联分析以减少冗余。通过验证，该算法能够快速高效的定位出故障，与一般方法相比，具有一定的优势。并且极大地方便了网络管理员排查故障的困难性，提高了效率，减少了损失。

[1]郭军.网络管理(第三版)[M].北京:北京邮电大学出版社,2008.

[2]郑秋华.网络故障智能诊断关键技术研究[D].杭州:浙江大学,2007.

[3]杨洪涛,王继龙.网络事件管理系统中关联技术的选择及实现[J].计算机工程,2006,32(4):197-199.

[4]WANG Yingying,LI Qiuju,CHANG Ming,et al.Research on Fault Diagnosis Expert System Based on the Nerual Network and the Fault Tree Technology[J].Procedia Engineering,2012(31):1206-1210.

[5]程杰.大话数据结构[M].北京:清华大学出版社,2012.

[6]彭熙,李艳,王倩,等.基于网络拓扑结构的智能故障定位系统设计与实现[J].计算机工程,2005,31(2):219-231.

Research on Network Fault Location Algorithm Based on Minimum Spanning Tree

Han Rui-dong1,Yin Sheng-zhong2,Li Ping1
(1.Department of Computer Science and Technology,Yuncheng University,Yuncheng Shanxi,044000; 2.China News Service,Beijing,100037)

A network fault location algorithm based on minimum spanning tree(spatial correlation analysis)is proposed to identify the source of failure,aiming at the situation that a device failure in the network may cause the other devices to generate alarms and even affect the whole network operation.This algorithm includes time and spatial correlation analysis,using time correlation analysis by compressing,filtering,counting and suppressing rules to handle alarms to reduce redundancy.Using spatial correlation analysis to handle alarms of redundant processing to find the real source of failure by four parts:preprocessing,alarm analysis,adjusting the minimum spanning tree and link correlation.After the operation of the algorithm proved that it can support the campus network fault management effectively,help network administrators to identify the fault of the equipment quickly and improve efficiency.

network failure;correlation analysis;location;fault source

TP393

A

〔责任编辑 高海〕

1674-0874(2017)04-0010-04

2017-03-26

运城学院协同创新项目[CI-2015018]

韩瑞东(1988-)，男，山西运城人，硕士，助教，研究方向:软件技术开发。