文 /杨滟 黄小红 马严

园区网络指在有限的地理区域内由多个局域网相互连接组成的网络，作为用户接入互联网的基础，当园区网络发生异常时必须快速准确定位故障根源才能有效保证用户上网体验。然而随着园区网络规模日益增大，网络复杂化、设备多样化等因素使得告警间的关系也变得错综复杂。同时，由于网络故障具有传播性，单一故障会引发与之直接或间接关联的节点故障，造成大量衍生告警，使得故障根源的定位更加困难。

告警关联规则挖掘技术由于其贴合网络告警时间相关性的特点，成为近年来兴起的网络故障根源分析方法之一。但是往往存在不同程度的问题。为了解决以上问题，本文提出基于园区网络拓扑的告警关联规则挖掘算法（Topo C-OPT算法）；即增加园区网络拓扑作为挖掘依据，根据告警实体间的跳数定量分析空间关联性，计算得到拓扑关联因子，并基于此进一步建立置信度优化模型，有效挖掘出时间相关性虽弱但正确的告警关联规则，同时增强对时间相关性虽强但无效的规则的识别，从而提升园区网络告警分析场景下挖掘结果集的正确率。

原有算法回顾

SDH-AARM算法（以下简称原有算法）同时具备了WINEPI的时序相关性以及FP-Growth的挖掘高效性，因此本文选用此算法为基础算法，在该算法的基础上进行研究改进。告警关联规则挖掘算法的目的是在一个给定的时序集合中挖掘出所有强告警关联规则。强告警关联规则指支持度和置信度均高于阈值的告警关联规则。原有算法包括以下步骤：

1.采用滑动窗口方法构建告警事务库；

2.基于支持度挖掘频繁告警序列；

3.加入告警时序特征，生成告警关联规则及置信度；

4.基于置信度筛选强告警关联规则。

置信度是评价某一事件正确概率的一种度量，表示该事件的可靠程度。告警关联规则A=＞ B中A称为前件，B称为后件；A=＞ B的置信度(con)计算公式表示为

其中s(AB)为AB的支持度，表示A、B同时出现的概率；s(A)表示A出现的概率。支持度计算公式如下：

由于构建告警事务库后，窗口总数为确定值，所以根据上述置信度及支持度计算公式可知，原有算法中的置信度是单纯基于支持数计算得到的，忽略了空间关系的定量影响，导致其准确度与实际情况存在偏差；当应用于园区网络告警关联规则挖掘时往往造成漏选正确规则，同时错选错误规则的现象。

综上可知，置信度的准确性对最终强告警关联规则结果集的正确率具有决定性作用。因此，本文所提出的Topo C-OPT算法中，关键改进点在于引入园区网络拓扑优化告警关联规则的置信度，提高规则置信度的准确性从而达到提升强告警关联规则挖掘结果集正确率的目的。

Topo C-OPT算法

Topo C-OPT算法在网络拓扑关联性与告警时间相关性相互独立的前提下提出，忽略网络拓扑距离对告警传输时延的影响。

Topo C-OPT算法主要包含以下六个步骤。

1.采用滑动时间窗口方法处理告警源数据，得到告警事务库；由于园区网络中的关联告警必定在相近时间发生，所以该方法具有实际意义。

2.采用FP-growth算法挖掘频繁告警序列；

3.基于频繁告警序列，加入告警的时序特征生成告警关联规则及其置信度；时序特征包括顺序关系、并列关系及混合关系。

4.构造拓扑关联因子算法，计算告警实体在园区网络拓扑中的关联性。

5.构造置信度优化模型；基于上一步骤获得的拓扑关联因子进一步构造置信度优化模型，优化步骤2中原有置信度，提升置信度值的准确性。

6.基于优化后置信度筛选强告警关联规则。

其中，步骤4和5中提出的拓扑关联因子算法及置信度优化模型为本研究的关键改进点，弥补了单纯从时间维度计算置信度造成其偏差较大的不足，增强对正确规则的识别能力，提升强告警关联规则挖掘结果集的正确率。

拓扑关联因子算法

本研究所提出的拓扑关联因子定义为：描述告警关联规则前后件在网络拓扑中的关联性，关联性越高，则拓扑关联因子值越大。本算法采用告警实体在网络拓扑中的距离，即从源实体到目的实体所需经过的最小链路数，作为衡量关联性的参数。

根据告警关联规则的定义可知，规则前后件均为告警项集合，集合中的告警项为并列关系，前后件间具有因果关系。为了研究拓扑关联性对因果关系的影响，本算法中将前件和后件分别视为整体，计算两者的关联性，即为拓扑关联因子。

拓扑关联因子算法包含以下三个步骤：

1.计算前后件中告警实体在网络拓扑中的距离；

2.将前件、后件分别视为整体，计算前件与后件的告警实体集之间的平均距离。

3.基于告警关联规则前后件的平均距离，计算拓扑关联因子。

第一，计算源-目的告警实体对距离

计算源实体(Sv )与目的实体(Dv )距离的算法如下：

输入：网络拓扑 ( G( V, E ))，源-目的实体对([vS,vD])

输出：源-目的实体对的距离(d)算法描述：

(1) 建立队列sq，d初始赋值为0，将vS从队尾加入sq；

如图1 ，给定一个网络，该网络中源实体 v1到目的实体 v6的最短路径为，则 v1v2的距离计为2。

图1 一个典型的网络拓扑图

第二，计算规则前后件的平均距离

输入：网络拓扑 (G( V, E))，A′，B′

算法描述：

(1) 取B′中任意未标记实体 vk，计算vk与A′中所有实体的距离，并相加求平均值得到 vk与A′的平均距离；同时标记 vk；平均距离计算公式如公式(3), 其中 nA'表示A′中的实体个数：

③

(2) 重复步骤(1)，直到B′中所有的实体均被标记；

(3) 将B′中所有实体的平均距离值相加求平均值，即可计算出A′与B′的平均距离，计算公式如公式(4)，其中 n B'表示B′中的实体个数：

第三，计算拓扑关联因子

本研究定义拓扑关联因子与规则前后件平均距离成负相关关系。告警关联规则前后件在园区网络拓扑中的平均距离越小，可推测前后件的告警项集具备因果关系的可能性越大，则定义该规则的拓扑关联因子值越大。拓扑关联因子计算公式如下：

由上述公式可得到拓扑关联因子与前后件平均距离的关系曲线，如图2所示。随着平均距离的增大，拓扑关联因子呈下降趋势，两者成负相关关系；拓扑关联因子取值范围为(0,1]。

置信度优化模型

图2 拓扑关联因子与前后件平均距离关系曲线，表示园区网内最大距离

按上述算法计算得到的拓扑关联因子，本研究进一步提出置信度优化模型，根据拓扑关联因子值对告警关联规则的原有置信度(con)进行修正，从而得到准确度更高的新置信度( 'con)。根据园区网络中告警的空间相关性可知，告警关联规则前后件的拓扑关联性越强，则该规则的可信程度越高；反之，拓扑关联性越弱，则可信程度越低。设最小置信度阈值为min，置信度优化模型公式如下⑥：

模型中a、b、c均为基于con的变量，后文将详细描述； k1、 k2、 k3为三个临界点，且满足 0＜k1＜k2＜k3＜1；三个临界点将topo的取值划分为四个阶段，分别为C1、C2、C3、C4，每个阶段具有不同的优化模型；本研究中 k1、 k2、 k3值根据实际故障处理经验手动设置。

为了更直观地说明置信度优化模型对告警关联规则置信度的不同优化策略以及优化后的效果，图3展示了topo分别与 con'、con的函数关系，并对比了 con'与con曲线。

图3 'con与con对比图

由图3可知，原置信度值不受拓扑关联因子的影响，完全由时间相关性计算得到，未考虑拓扑关联因素。而新置信度值是在原置信度值基础上根据拓扑关联因子优化得到，同时参考了时间相关性及拓扑关联性，旨在提高准确性。下面将详细阐述置信度优化模型各阶段的优化策略。

C1阶段，topo的取值为 (0,k1]，表示告警关联规则前后件在园区网络拓扑中的关联性非常弱，故在原有置信度的基础上降低其值。但由于规则在时间维度上的相关性仍然具有重要参考意义，故本研究采用控制原置信度下降范围的方式保证时间相关性和空间相关性的平衡。当con=1时，根据其计算公式可知每一次前件发生时后件均发生，本研究规定，该情况下即使前后件拓扑关联性非常弱，该规则也为强告警关联规则；因此本研究中将下降范围控制为，则C1阶段优化后 con'的取值为。

C2阶段，topo的取值为 (k1, k2]，表示告警关联规则前后件拓扑关联性较弱，但强于C1阶段；故降低原置信度值。本模型定义：在 (k1, k2]范围内topo的值越小，表示前后件的拓扑关联性越弱，则对置信度的负向影响程度越大，原有置信度下降程度越大。故本阶段采用对数模型， con'的值域为。本阶段公式中b和c均为基于con的变量，公式如下：

C3阶段，topo的取值为 (k2, k3]，表示告警关联规则前后件的拓扑关联性既不强也不弱，故保持原有置信度值不变，即为con。

C4阶段中，topo的取值为 (k3,1],表示告警关联规则前后件在园区网络拓扑中的关联性非常强，故在原有置信度的基础上提升其值。本模型定义：在 (k3,1] 范围内，topo的值越大，表示前后件的拓扑关联性越强，对置信度的正向影响程度越大，则原置信度提升的程度越大。故本阶段采用指数型增长模型， con'值域为(c on, h]，h值为当即拓扑关联性最高时 con'的取值。根据置信度的定义，置信度描述关联规则的可信程度，取值范围为[0,1]；取值为0时表示该规则完全不可信；取值为1时表示该规则完全可信。原有置信度依据告警的时间相关性计算得到，根据其计算公式可知，表示并非每一次规则前件发生时后件均发生；本研究规定：该情况下即使拓扑关联性达到最高值1，该规则也不可称为完全可信，故con'的取值为h(h＜1)。

同时，由于时间维度的相关性依然是置信度计算的重要参考因素，故本研究根据实际故障处理经验将最大提升空间控制为原有置信度的四分之一，由此可得到以下h值计算公式⑨：

以上详细阐述了置信度优化模型中topo值处于不同阶段时的优化策略，下面通过实验验证模型的有效性。

实验结果与分析

为了对所提出方案的有效性进行验证，本研究选用某高校校园网络中2016年6月～2017年4月期间经过初步数据处理后的10000条网络告警数据作为数据源，并将其按照时间顺序平均划分为5个源告警数据库。

本研究在2核CPU、4G内存的LAMP环境下采用PHP语言开发。实验过程如下：首先，分别对5组源告警数据采用滑动窗口方法处理生成5组源告警事务库。其次，编程实现原有算法与Topo C-OPT算法，并使用两种算法挖掘相同源告警事务库，分别得到强告警关联规则结果集R与R'。最后，采用人工标记法标记出R与R'中所有正确规则。对一条规则而言：正确标记为1，错误标记为0；分别统计R与R'中正确规则的数量，计算并对比正确率。

实验中设置时间窗口为10min、滑动步长为5min；由于在时间窗口和滑动步长确定的情况下，告警事务库的窗口总数为确定值，根据支持度计算公式(2)可知，此处设定最小支持数阈值即可，故设定1-项最小支持数阈值为10，n-项集最小支持数阈值为5(1＞n)；最小置信度阈值为0.80。分别采用原有算法和Topo C-OPT算法挖掘5组源告警事务库，得到结果数据如表1所示。

表1 结果集数量及正确率

由以上实验结果可知，在设置参数均相同的情况下，采用Topo C-OPT算法挖掘5组源告警事务库得到的强告警关联规则结果集的正确率均明显高于原有算法。由此可证明，本研究所提出的Topo C-OPT算法在提升强告警关联规则结果集的正确率方面具有明显优势。

对于研究提出的拓扑关联因子算法中，园区网络拓扑关联性的计算目前只选取了距离作为依据，下一步研究可考虑加入网络设备层级关系等因子，进一步提高拓扑关联性计算结果的准确度。