（计算机科学与技术专业论文）基于事件关联和数据挖掘的网络故障管理技术的研究.pdf

f a u l tm a n a g e m e n tb a s e do ne v e n t c o r r e l a t i o na n dd a t am i n i n g s p e c i a l t y ： 一c o m p u t e r s o f t w a r ea n d t h e o r y _ 一 m a s t e rd e g r e ec a n d i d a t e ： s u p e r v i s o r ： h a i t a oy u e p r o f j i el i s c h o o lo fi n f o r m a t i o ns c i e n c ea n d e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c h i n a 5肼ijiii8 眦im 7 wi-舢y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：勉壹逸 日期：! 尘一年月! 日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 作者签名：鉴鱼；塑导师签名日期：丝31 年上月卫 摘要 在当今信息时代，计算机网络在人们的日常生产、生活中扮演越 来越重要的角色。一旦网络中发生故障，总是要求网络工程师和网络 管理人员能迅速、准确的对故障的类型以及故障的根源做出判断，以 便下一步采取相应的修复措施。本文立足于事件关联和数据挖掘技 术，在网络故障管理方面进行了如下研究。 对传统的基于规则的网络故障管理专家系统的规则库进行改进， 通过引入规则元的概念，实现不同规则之间相同规则元的共享，达到 对规则库进行压缩的目的。同时也方便对规则元进行排序、建立分组、 建立索引以及对常见规则元建立缓存，加速了规则元的查找过程，提 高了查找效率。另外在事实与规则进行匹配时也是以规则元为单位进 行，减小了匹配代价以及无用匹配的发生，提高了推理机的推理效率。 提出了一种基于位置索引矩阵的关联规则挖掘算法，通过扫描告 警事务数据库一次，将其转换成候选项集矩阵，并在矩阵中保存了频 繁项的位置信息，实现对候选模式的跨越式搜索，加速了频繁项集的 生成，因此算法具有较好的效率。 提出了一种适合网络告警数据特点的序列模式挖掘算法，算法基 于序列矩阵s m ，全面考虑各种类型告警数据，通过设定不同的时间 窗口，进行序列模式的挖掘，具有较好的效率。另外，算法中引入了 拓扑约束进行有效剪枝，进一步加速了序列模式挖掘。 把事件关联和数据挖掘应用于网络故障管理，设计出了一个完整 的基于规则的网络故障管理系统模型，它能够同时支持对关联规则和 序列模式的推理。对故障管理系统的数据库进行了详细设计。编程实 现了规则推理模块，验证了规则改造后系统在关联规则和序列模式推 理上的正确性。 关键词网络故障管理，专家系统，事件关联，数据挖掘，故障定位， 故障预测 a b s t r a c t i nt h i si n f o r m a t i o na g e ，t h ec o m p u t e rn e t w o r kp l a y sam o r ea n d m o r ei m p o r t a n tr o l ei np e o p l e sp r o d u c t i o na c t i v i t i e sa n dd a i l yl i f e o n c e af a u l to c c u r r e di nt h en e t w o r k ，n e t w o r ke n g i n e e r sa n dn e t w o r km a n a g e r s s h o u l dm a k eq u i c ka n da c c u r a t ej u d g m e n t sa b o u tt h et y p ea n dt h es o u r c e o ft h ef a u l ti no r d e rt om a k eap l a nf o rr e c o v e r al o to fr e s e a r c ho n n e t w o r kf a u l tm a n a g e m e n ti sc o n d u c t e di nt h i sp a p e r , b a s i n go ne v e n t c o r r e l a t i o na n dd a t am i n i n gt e c h n o l o g y t h ec o n c e p t i o no fr u l ee l e m e n ti si n t r o d u c e di n t ot r a d i t i o n a l r u l e b a s e dn e t w o r kf a u l tm a n a g e m e n ts y s t e mt os h a r et h es a m er u l e e l e m e n tb e t w e e nd i f f e r e n tr u l e sa n dc o m p r e s st h er u l eb a s e a tt h es a m e t i m ei ta l s of a c i l i t a t e sr u l ee l e m e n t ss o r t i n g ，g r o u pc r e a t i o n ，i n d e x c r e a t i o na n dc o m m o nr u l ee l e m e n t sb u f f e r i n g a l lt h i sc a ni m p r o v et h e s p e e da n de f f i c i e n c yo fr u l ee l e m e n tq u e r y b e s i d e st h a t ，r u l ee l e m e n ti s u s e di n s t e a do fr u l et om a t c hw i t hf a c t s t h i sr e d u c e st h ec o s to f m a t c h i n g a n dt h eo c c u r r e n c eo fu s e l e s sm a t c h i n g t h e r e f o r ei t i m p r o v e st h e e f f i c i e n c yo f i n f e r e n c ee n g i n e an e wa s s o c i a t i o nr u l em i n i n ga l g o r i t h mi s p r o p o s e db a s i n go n a d d r e s si n d e xm a t r i x i tg o e st h r o u g ht h ea l a r mt r a n s a c t i o nd a t a b a s eo n c e t oc o n v e r ti ti n t om a t r i xa n ds a v et h ea d d r e s so ff r e q u e n ti t e m t h r o u g h t h i s ，t h es p e e da n de f f i c i e n c yo fq u e r yi si m p r o v e d an e ws e q u e n c er u l e m i n i n ga l g o r i t h mi sp r o p o s e db a s i n go n s e q u e n c em a t r i xs m a l lk i n d so f a l a r md a t aa r et a k e ni n t oa c c o u n ti nt h i s a l g o r i t h m i tm i n e st h es e q u e n t i a lp a t t e r nb ys e t t i n gd i f f e r e n tt i m e w i n d o w s b e s i d e st h a t ，t h ei n t r o d u c t i o no ft o p o l o g i c a lc o n s t r a i n tf o r e f f e c t i v ep r u n i n ga l s os p e e d su ps e q u e n t i a lp a t t e mm i n i n g b ya p p l y i n ge v e n tc o r r e l a t i o na n dd a t am i n i n gt on e t w o r kf a u l t m a n a g e m e n t ，w ed e s i g nac o m p l e t er u l ei n f e r e n c eb a s e dn e t w o r kf a u l t m a n a g e m e n ts y s t e mm o d e l ，w h i c hs u p p o r tb o t ha s s o c i a t i o nr u l e a n d s e q u e n c er u l ef o ri n f e r e n c e i na d d i t i o n ，ad e t a i l e dd e s i g ni sm a d e a tl a s t ， t h er u l e b a s e d r e a s o n i n g m o d u l ei s d e v e l o p e d ，a n d i t p r o v e d t h e e f f e c t i v e n e s so fa s s o c i a t i o nr u l ea n ds e q u e n c er u l er e a s o n k e y w o r d s ：n e t w o r k f a u l t m a n a g e m e n t ，e x p e r ts y s t e m ，e v e n t c o r r e l a t i o n ，d a t am i n i n g ，f a u l tl o c a l i z a t i o n ，f a u l tp r e d i c a t i o n i i i 目录 第一章绪论l 1 1研究背景和意义1 1 2 国内外研究现状1 1 2 1事件关联技术l 1 2 2数据挖掘技术4 1 3研究内容5 1 4本文结构6 第二章基于事件关联和数据挖掘的故障管理7 2 1故障管理概述7 2 1 1告警的概念7 2 1 2网络告警的分类8 2 1 3 网络故障的概念8 2 1 4 网络故障的分类8 2 1 5网络故障的性质8 2 1 6网络故障处理的流程9 2 1 7 故障告警与网络故障的关系一1 0 2 2事件关联技术1 0 2 2 1 定义1 0 2 2 2事件关联的类型1 0 2 2 3 事件关联分析的难点1 2 2 3 数据挖掘知识介绍一1 3 2 3 1什么是数据挖掘1 3 2 3 2数据挖掘常用的技术1 3 2 3 3数据挖掘的步骤1 3 2 3 4 数据挖掘的特点一1 4 2 4 事件关联和数据挖掘技术在网络故障管理中的优势体现1 5 2 5规则的改进和知识库的改造1 7 2 6本章小节19 第三章 故障管理中关联规则挖掘一2 0 3 1 关联规则在网络故障管理中的应用2 0 3 2关联规则2 1 3 2 1 关联规则的基本概念一2 1 3 2 2 a 皿o r i 算法2 3 i v 3 2 3f p g r o w t h 算法2 6 3 3一种基于位置索引矩阵的关联规则挖掘算法2 7 3 - 3 1弓i 言2 7 3 3 2 基本概念和性质2 8 3 3 3基于位置索引矩阵的关联规则挖掘算法2 9 3 3 4实验及性能评价3 3 3 3 5算法小结3 5 3 4本章小结3 5 第四章故障管理中序列模式挖掘3 6 4 1序列模式在网络故障管理中的应用3 6 4 2序列模式3 6 4 2 1序列模式的基本定义3 6 4 2 2序列模式的分类3 7 4 2 3经典序列模式发现算法介绍3 8 4 3一种新型网络告警序列挖掘算法的提出4 2 4 3 1引言4 2 4 3 2基本概念和性质4 2 4 3 3基于序列矩阵s m 的序列挖掘算法介绍4 3 4 3 4算法分析及评价4 7 4 4 本章小结4 7 第五章基于规则的网络故障管理系统的设计与实现一4 8 5 1模型设计4 8 5 2事件收集一4 9 5 2 1 网管工作站主动轮询4 9 5 2 2 t r a p 告警5 0 5 2 3 s y s l o gr 志收集。5 1 5 3事件预处理51 5 3 1事件规范化5 2 5 3 2事件过滤5 2 5 4知识库的设计与实现5 5 5 4 1知识的获取5 5 5 4 2 知识的表达一5 5 5 4 3 知识的管理和维护：5 7 5 5推理机的设计与实现5 8 v 5 6 数据库的设计与实现6 0 5 7基于规则的网络故障管理系统的实现6 5 5 8 本章小结6 8 第六章总结与展望：6 9 6 1研究总结6 9 6 2 进一步的工作一7 0 参考文献7 1 致 射一7 7 攻读学位期间主要的研究成果7 8 硕士学位论文第一章绪论 1 1 研究背景和意义 第一章绪论弟一早三百下匕 随着信息技术同新月异的发展，计算机网络已经渗透到人们生活的各个领 域，极大地改变了人们的生活方式和改善人们的生活水平，同时也对社会经济发 展也起着巨大的推动作用。当前计算机网络的发展特点是网络规模不断扩大，网 络复杂性不断增加，网络异构性不断提高i l 】。与此同时，计算机网络中还运行着 众多网络软件提供的各种应用服务。面对如此复杂的软硬件环境，一旦网络发生 故障，与故障相关的逻辑或者物理设备将产生大量的、重复的相关告警事件，而 且告警事件经网络进行传输，大量的告警事件将会形成告警风暴【2 1 ，这使得网络 管理变成一项非常具有挑战性的工作。 故障管理是网络管理的重要组成部分，主要用于告警分析和故障诊断。当网 络中的设备出现故障的时候，快速定位故障和进行故障修复是保证网络安全、可 靠运行的关键，也是网络管理的迫切任务。在实际网络中，当故障发生后很难确 定网络中故障发生的确切位置。因为在一个复杂、异构的网络中，各个网元 ( n e t w o r ke l e m e n t ，简称n e ) 设备之间相互影响相互制约，一个网元发生了故障， 与之相关的网元也会产生告警，甚至会处于故障状态。当网络出现故障或者性能 瓶颈的时候，网络管理人员常会被一系列突发的、大量的对确定网络故障根源没 有意义的告警信息所“淹没 ，使得网络故障的定位显得更加困难。 通过对网络故障所引发的告警事件进行事件关联f 3 8 】，可以将多个告警事件 归结成较少的告警事件，过滤了大量无用、无意义、不相关的告警，丰富了告警 包含的信息，加快了推理机推理的速度，提高了故障定位【9 j 和故障预测的准确性。 网络告警是对网络故障的描述，通过采用数据挖掘【1 0 , 1 l 】技术对历史告警事件 进行挖掘，发现隐含在大量的告警事件背后潜在的知识，并把挖掘出来的的关联 规则和序列规则添加到基于规则推理的网络故障管理系统的知识库中，增加了系 统知识获取的途径，增强了系统故障处理的能力，提高了系统的智能性【l 2 1 。 1 2 国内外研究现状 1 2 1 事件关联技术 事件关联技术发展到今天已经取得了巨大的发展，国内外的众多科研机构也 先后提出了许多种事件关联技术。这些事件关联技术涵盖了计算机科学的众多研 l 硕+ 学位论文第一章绪论 究领域，包括人工智能1 4 2 1 、神经网络、自动控制论图论、信息论及图论。如图 1 1 所示事件关联事件关联技术的分类1 1 3 l ： 事件天联技术 人工智能技术il 模型遍历技术li 放障传播模型 基于事例的推理 基于规则的推理 摹于模型的推理 神经网络 决策树 代码本技术 贝叶斯网络 图1 - 1 事件关联技术分类 短语结构文法 依赖圈 因果图 事件关联技术的研究方法【l6 r 7 】很多，较为常用的事件关联技术有如下几种： 1 基于规则的相关性分析 基于规则的( r u l e b a s e d ) 相关性分析i i8 l 是把告警相关性知识总结为一组相关 性规则集，规则的形式为：i fc o n d i t i o nt h e na c t i o n 。利用收集到的网络中产生 的实时告警，系统通过将其与规则库中规则进行比较来对网络故障的类型以及根 源作出判断以及预测。基于规则的相关性分析一般由三部分组成：工作存储区、 规则库、推理引擎。工作存储区保存网络的拓扑信息l i5 j 以及收集到的实时告警 事件。规则库用于保存告警相关性规则。推理引擎则根据工作存储区中拓扑结构 信息和告警信息以及规则库中的规则进行规则推理，实现对故障的定位及预测。 基于规则的方法的优点是直观，比较符合人们的思维习惯，便于理解。但是 这种方法的问题在于：( 1 ) 当规则的数量达到一定的规模时，规则库的管理和维 护将变得十分困难；( 2 ) 基于规则的相关性分析同样存在着知识获取的瓶颈；( 3 ) 规则不能适应网络拓扑结构以及网络配置的变化；( 4 ) 缺乏记忆性也是基于规则 的相关性分析的一个主要限制。由于没有充分利用过去的经验，即使同样的情况 再次出现，系统也要从成千上万的规则中去查找，严重影响了系统的工作效率。 e c s i 旧l 是惠普公司开发的一个基于规则的实时相关性处理系统，它包括输 入、输出、过滤、延时、计算、组合、更改等。e c s 通过建立网络模型实现告警 事件之间动态评价，通过构件来实现告警相关性分析和告警过滤，通过模块间的 不同的组合来实现不同的功能，适应不同网络的实际情况。 2 基于事例的相关性分析 基于事例 拘( c a s e b a s e d l 相关性分析1 2 0 j 是通过利用过去的经验和方法解决新 2 硕十学位论文第一章绪论 出现的问题。在基于事例的推理系统中，过去解决问题的经验都是以事例的形式 存放在事例库中，当遇到新问题时就从事例库中寻找相同或相似的事例，通过对 该事例的修正去解决新问题，同时解决新问题的经验又作为新的事例被添加到事 例库中。事例库的维护主要按照遗忘曲线理论，即长期不用的信息将会被遗忘， 所以需要删除长期不用的事例。 基于事例的推理具有很好的自学习能力，因此系统具有较强的适应能力，同 时基于事例的推理能够根据出现的错误来对将来的行为自动作出纠j 下，通过对过 去事例的调整来解决新问题。但是基于事例的推理总是和具体的应用相关的，缺 乏通用性，同时基于事例的推理在实时性上也要差一些。 l e w i s 曾经设计实现了一个基于事例推理的故障追踪系统c r i t t e r l 2 1 ，2 2 1 。在 c r i t t e r 中，系统会对每一个发生的故障产生一个故障清单( t r o u b l et i c k e 0 ，故 障的解决方案总是和故障清单一起保存到系统事例库中。当系统发生故障的时， 首先生成其故障清单，然后从事例库中寻找相似的故障清单，提出解决方法，并 把新的故障清单和其解决方案添加到事例库中。 3 基于模型的相关性分析 基于模型( m o d e l b a s e d ) 的相关性分析1 2 3 】通过建立网络模型来对网络的行为 进行推理。网络模型主要包括网络结构信息( 如网元类型、网络拓扑、包含的约 束等) 和网络行为信息( 如告警相关性分析的动态过程) 。基于模型的相关性分析系 统对新的故障具有一定的分析能力，但当处理超出其知识范畴的问题时，系统的 性能将显著下降。 i m p a c t l 2 4 】是g t e 实验室开发的一个典型的基于模型推理的系统，它用于 固定和移动通信网络的告警相关性分析。i m p a c t 在相关性规则的触发条件中考 虑到了事件之间的时序关系，它同时引入了相关性窗口和活动周期。除了告警相 关性规则外，i m p a c t 提供了规则接口，领域专家可以自定义相关性规则。 4 基于代码本的相关性分析 基于代码本的相关性( c o d e b o o kb a s e da p p r o a c h ) 分析1 2 5 】的基本思想是：对于 每一种告警，可以看做是产生该告警的故障的特征，将其编码为该故障的特征向 量。特征向量的每一维元素表示该故障对应的某类告警是否发生，用0 或l 表示， 所有故障的特征向量一起构成了代码本，从本质上讲代码本就是一个症状矩阵。 建立代码本后，相关性分析的过程就是一个解码的过程。对于当前的故障，为其 建立起特征向量，然后与代码本上的各个特征向量进行比较，计算当前特征向量 与己知故障的特征向量之间的汉明距离，选择距离最小的特征向量对应的故障作 为当前的故障。 基于代码本的相关性分析方法通过对告警知识模型的预处理减少了实时告 3 硕士学位论文第一章绪论 警相关性分析的复杂性，因此具有更高的效率。另外，对故障的确定是基于最小 距离而不是严格的特征匹配，因而增强了系统的鲁棒性。但是，在实际网络中， “问题和“征兆”往往比较复杂，数据量很大，进行有效编码以获得最优代码 书非常困难，另外代码书技术也不具备自学习能力。 5 基于神经网络的相关性分析 神经网络i 2 8 1 ( n e u r a ln e t w o r k s ) 是由许多存在着简单输入、输出关系的神经元 相互连接而构成的系统，它能够实现并行计算，克服了一般串行计算所带来的瓶 颈问题。对于一些复杂的没有算法或者算法非常慢的问题，神经网络通常是一个 比较理想的选择。 利用神经网络进行告警相关性分析，首先要经历一个训练的过程，即把每一 种网络故障和对应于该故障的网络告警信息分别作为神经网络的输入和输出，通 过反复训练来调整神经元之间连接的权值。通过一定量的训练后，神经网络便可 根据当前的告警信息对可能发生的故障做出判断。 。 神经网络的优点是具有很好的自学习能力，同时对包含噪声的告警信息也能 进行很好的相关性处理。w i e t g r e f e l 2 9 】等将神经网络应用于对g s m 网络中的告警 相关性问题的研究。苏利敏【3 0 l 等利用神经网络分析告警相关性问题，并对告警 的不确定性和抑制噪声进行了重点研究。王新苗p l j 等提出了一种改进的自适应 遗传算法训练多层前向神经网络并用于故障识别和告警相关性分析。m a r i l l y t 3 2 j 等通过神经网络把告警信息转换为信号形式，采用信息处理方法提取相关故障信 息。神经网络的缺点是在实际应用之前必须经过大量的训练，以便存储所有故障 相关的模式，否则会对学习的性能产生影响，另外为其寻找一个较好的训练数据 集合也是一个比较困难的事情。 1 2 2 数据挖掘技术 数据挖掘f 2 6 9 r l ( d a t am i n i n g ，也称知识发现) 是从大量的、不完整的、有噪音 的、模糊的、随机的数据中智能地、自动地抽取隐含的、先前未知的、对决策有 潜在价值的知识和规则。它是基于过去事例泛化的一种归纳学习。一般来说，数 据挖掘可以用来解决许多类问题：包括分类、聚类、关联规则挖掘和时间序列分 析等。 通过数据挖掘来获取告警相关性知识是当前网络中的一个研究热点，国内外 许多学者也提出了一系列基于数据挖掘的研究方法，提高了告警相关性分析的能 力和水平。h e i k k im a n n i l a 等提出了对大量历史告警数据中频繁出现的关联规则 挖掘的w i n e p i 算法【3 3 1 ，并应用于t a s a 系统【3 4 i 。g a r ymw e i s s l 3 5 j 等在通信告警 数据库的基础上提出了预测小概率时间序列模式的t i m e w e a v e 算法，并用于 4 硕士学位论文 第一章绪论 a n s w e r 系统中进行故障预测1 3 6 l 中。g a r d n e r l 3 7 l 等在对s d h 网络告警数据进行 分析的基础上，设计出了一个基于数据挖掘的告警相关系统框架。郑庆副3 8 1 基 于w i n e p i 算法框架，提出了一种针对告警数据中噪声问题的改进算法，并在 g s m 网络告警数据中进行应用。基于告警事件跨度约束，姚伟力【3 9 l 提出了告警 时序模型，该模型可以过滤大量无用告警。单莘i 5 j 在对发生的重大网络告警进行 研究的基础上提出了一种支持向量机的算法。 1 3 研究内容 本文立足于事件关联和数据挖掘技术，在网络故障管理方面进行了如下研 究。 1 针对传统的基于规则的网络故障管理专家系统存在着当规则数量增多时 引起规则的管理和维护比较困难以及系统缺乏记忆性导致推理效率低等问题对 规则进行了改造。通过引入规则元的概念，实现了不同规则之间相同规则元的共 享，达到对规则库进行压缩的目的。另外通过实现对规则元进行排序、分组、建 立索引以及常用规则元建立缓存等操作，加快了规则元的查找过程和查找效率， 缓解了基于规则的网络故障管理专家系统由于缺乏记忆性所带来的规则查询效 率低下的问题，从而提高了推理效率。 2 对常见的关联规则挖掘算法进行了研究，并提出了一种基于位置索引矩 阵的关联规则挖掘算法。算法通过对告警事务数据库进行一次扫描，将告警事务 数据库转换成为位置索引矩阵，并在矩阵中保存了频繁项的位置信息，实现对候 选模式的跨越式搜索，加速了频繁模式的发现，因此算法具有较好的效率。 3 对现有的几种经典的序列模式挖掘算法进行了研究，结合网络告警数据 的特点，提出了一种基于序列矩阵s m 的序列模式挖掘算法。算法综合考虑各种 告警数据的特点，并将历史告警数据还原成告警数据流，通过设定的时间窗口， 进行序列模式挖掘，具有较好的效率。同时算法中还引入了网络拓扑约束进行剪 枝，进一步加速了序列模式的挖掘。 4 设计出了一个完整的基于规则( 包括关联规则和序列模式) 的网络故障管 理系统，它包括告警事件的收集、告警事件的规范化、告警事件的过滤、实时告 警的管理和维护、知识的获取、知识的表达、知识的管理和维护、推理机的设计， 同时编程实现了根据告警事件和规则进行规则推理的功能，验证了规则改进后基 于规则的网络故障管理系统模型推理结果的正确性。 5 硕士学位论文 第一章绪论 1 4 本文结构 本论文共分为6 章。 第1 章为绪论，介绍了论文的研究背景、国内外研究现状及论文的主要研究 内容。 第2 章是本文研究的基础，首先介绍了网络告警的概念以及其分类，介绍了 网络故障的基本概念、分类、性质以及处理流程，给出了告警和故障的关系。接 着介绍了事件关联技术的定义、事件关联的类型以及事件关联分析的难点。接着 介绍了数据挖掘的相关概念、常用的挖掘技术以及挖掘的步骤。接着介绍了事件 关联和数据挖掘技术在网络故障管理中所具有的优势。然后通过引入规则元的概 念实现对传统规则的改造。最后介绍了基于事件关联和数据挖掘的网络故障管理 模型的设计。 第3 章对网络故障管理中关联规则挖掘进行了研究。首先介绍了关联规则在 网络故障管理中的应用，其次对关联规则进行了较为详细的介绍，并介绍了两种 常见的关联规则挖掘算法：a p r i o r i 算法和f p g r o w t h 算法。最后提出了一种新 的关联规则挖掘算法：一种基于位置索引矩阵的关联规则挖掘算法。 第4 章对网络故障管理中序列规则挖掘进行了研究。首先介绍了序列规则在 网络故障管理中的应用，其次对序列规则进行了较为详细的介绍，并介绍了四种 典型的序列挖掘算法：a p r i o r i a l l 算法、g s p 算法、f r e e s p a n 算法和p r e f i x s p a n 算法。最后提出了一种新的序列挖掘算法：一种新型网络告警序列挖掘算法。 第5 章详细介绍了基于规则的网络故障管理系统的设计与实现。首先给出一 个基于规则的网络故障管理系统的模型，然后分别给出了事实库、知识库和推理 机的设计以及实现，接着给出了基于规则的网络故障管理系统的数据库的设计， 最后通过实验证明了基于规则的网络故障管理系统规则推理的正确性。 第6 章对本文的工作进行总结，并指出本文工作的不足及以后研究的重点。 6 硕十学位论文 第二章基丁事件关联和数据挖掘的故障管理概述 第二章基于事件关联和数据挖掘的故障管理 随着网络规模不断扩大和网络异构程度的增加，现代网络形成了以各种复杂 模式互联的子网络群；与此同时，用户对网络性能以及网络提供的各种服务的要 求越来越高。网络的崩溃可能会造成灾难性的损失。因此，有效的进行网络故障 诊引删是网络正常运行的基本保证之一。 当网络出现故障的时候，外在表现形式上就会产生告警事件。由于网络故障 的传播性，一个故障源可能会引起众多告警事件，另外由于网络的传输问题，也 可能会造成告警事件丢失、延迟和重复，这些都会进一步增加故障诊断的难度。 2 1 故障管理概述 故障管理又称为失效管理，它是指网络中某个组成部分失效时，网络管理系 统能迅速定位故障的根源并能及时排除故障，保证网络的正常运行的能力，它是 网络管理的五大基本功能之一。 2 1 1 告警的概念 告警【3 , 5 , 6 1 是特定事件发生时产生的消息，它是网络异常状态的表现形式。从 故障管理的角度看，网络硬件设备或者软件模块的异常产生了故障，故障被检测 到后发出关于故障现象的描述性信息被称为告警，它是故障的外在表现，是从特 定的视角对故障进行的描述。 理想的网络告警应该包含有关故障的五个方面的信息( 5 w ) ，即： w h o ：产生告警信息的设备。 w h a t ：故障的征兆或现象。 w h e r e ：故障的位置信息。 w h e n ：故障发生的时间或被检测到的时间。 w h y ：发生故障的原因。 如果关于故障的五个方面的信息都能够获得，告警关联以及故障定位将是一 件非常轻松的事情。但实际是，每个设备对于除自身以外的网络情况只有非常局 限地了解甚至完全地不了解。网络上设备产生的大部分告警都只回答了w h o 、 w h a t 和w h e n 三个问题，但是对于故障定位起着决定性作用的w h e r e 和w h y 的信 息却没有提供。另外，网络传输延时、告警中央杂的噪声数据等问题都会进一步 增加了网络故障定位的难度。 7 硕十学位论文 第二章基于事件关联和数据挖掘的故障管理概述 2 1 2 网络告警的分类 告警按其性质可以分为： 连通性告警：由于管理工作站与被管网元的连接失败，被管网元不再具有网 络连通性，管理工作站无法与其通信。 性能告警：是指被管网元的连通性仍然存在，但其与故障管理相关的m i b 对象的值超过了设定的阈值而触发的告警。 2 1 3 网络故障的概念 所谓网络故障【3 1 ，是指被管网络及其部件出现硬件或者软件上的紊乱，使之 不能提供正常的服务4 1 ，如网络行为超过允许范围，网络功能低于规定的水平 等，它是产生告警事件的根源。 2 1 4 网络故障的分类 网络故障的可以从以下几个方面进行分类1 7 j ： 1 硬故障与软故障 硬故障是指网络设备失效或通信链路中断等突发性故障。软故障是指那些由 于网络性能逐步恶化而产生的故障( 如网络拥塞、资源耗尽、交换效率下降等) 。 2 间隙性故障和永久性故障 间隙性故障是指网元设备的某些性能指标经常性、短时间内超过设定的阈 值。永久性故障是指性能参数永久性超过阈值的故障。间歇性故障一般与网络的 配置不当有关，而永久性则是比较严重的一类故障，发生永久性故障设备一般无 法正常工作，通常需要进行外界干预才能恢复设备到正常状态。 3 内在故障与环境故障 内在故障是网元设备自身发生故障，如网络负载不均衡、路由表配置不当等 等。环境故障则是指由于网元周边环境出现的网络故障或链路故障、外部环境引 起网路传输介质产生的噪声、网络管理员的误操作等原因，导致了本地网元功能 上的不正常。 2 1 5 网络故障的性质 网络故障有如下性质1 7 j ： 1 传播性 所谓故障的传播性指一个网元故障会随着网络进行传播乃至扩散到整个网 8 硕士学位论文 第二章基于事件关联和数据挖掘的故障管理概述 络，引起与之相关的网元不同程度的性能下降同时引发大量的告警事件。 故障传播与网络拓扑结构有着非常紧密的关系。故障网元会沿着拓扑路线进 行传播，因此距离发生故障的网元越近的网元会受到的影响越大；反之，距离越 远受到的影响越小。当底层的网元发生故障时，往往会向高层传播。 2 时间性 受传播性的影响，故障在时间维上的体现是先后相继，一个故障的发生往往 触发了后继其他故障的产生，告警事件之间存在着时态关系( t e m p o r a l r e l a t i o n s h i p ) 。大量告警事件在发生时间上也是前后相继，呈现一定的规律性。 3 相关性 计算机网络是由若干子网络互连而成的，任何一个网元的故障都可能造成其 他网元不同程度的故障，这些故障彼此相关，具有一定的因果联系。 4 模糊性 为了得出网络故障的根源，通常要收集并分析大量告警事件，根据这些告警 事件进行推理。在有些情况下，由于知识的不完整性或者诊断推理方法以及所收 集的症状信息的不足，无法推出关于故障根源的精确结论，而只能得出一个故障 网元集合，在这个集合中，所有的网元或者链路都有可能是故障的根源，因此就 具有一定的模糊性。虽然网络故障的根源不能被唯一确定，但是需要进一步定位 的网络故障的根源的范围却被大大的缩小了。 5 随机性 网络故障的发生通常具有一定的随机性。影响网络故障随机性的因素是多方 面的，它与网元以及链路的独立失效概率、网元问的相互依赖关系、网络拓扑结 构以及特定的网络运行环境都存在着关联。 6 不确定性 不确定性的出现是由于故障检测的手段的局限性以及所收集的告警事件信 息量的不足引起的。需要说明的是，当网络出现故障以后，虽然不能准确定位故 障的根源并找出原因，但是网络管理员却清楚地意识到故障的确存在。 2 1 6 网络故障处理的流程 1 通过多种途径( t r a p 、轮询、s y s l o g 采集) 对网络中的告警事件进行收集。 2 对收集到的网络告警事件进行相关性处理，并进行规则推理，从而获取 已发生故障的根源或者预测可能发生的故障。 3 针对故障的类型给出相应的处理方案。 4 通知有关部门或有关人员进行必要的处理。 5 故障解决后，将故障以及故障的解决方案存档。 9 硕士学位论文第二章基丁事件关联和数据挖掘的故障管理概述 2 1 7 故障告警与网络故障的关系 需要指出的是告警仅仅是网络状况发生变化的征兆，是故障的外在表现形 式。与告警不同，故障发生在被管网络设备及其部件之内。当故障发生时，我们 往往是先通过故障所产生的告警获知它。正是由于故障的隐蔽性以及告警是故障 的外在表现形式，网络管理人员可以通过利用自己的知识、经验以及相关工具对 发生的告警进行分析达到故障定位以及故障预测的目的。 表面上看，告警可能是一个告警引起另一个告警或者一个告警引起一系列告 警的连锁反应。但是产生这种现象的本质原因正是由于故障之问的因果关系引起 的，而绝非告警之间因果关系引起的。因为，故障才是产生告警的根源，一个故 障可以引起其他故障的产生，但是一个告警永远不会引起其他告警的产生。 2 2 事件关联技术 2 2 1 定义 事件关联技术通过对告警事件在时间和空间上进行相关处理，将多条告警合 并和转化为一条具有更多信息量的告警，在压缩告警数量的同时保留了有用信 息。同时，通过关联能够增强告警包含的信息，从而有利于尽快找到产生告警的 根源或者可能的根源的集合。在网络故障管理系统中引入事件关联技术，有利于 故障的快速诊断和定位，从而对加快故障的恢复、提高网络服务质量、增强用户 对网络的满意度都有很大的帮助。 目前，在研究事件关联技术的大量参考文献中，有的称为“事件关联 ，有 的称为“告警关联 或者“告警相关性 ，他们在本质上是一致的1 7 j 。 事件关联的形式化定义【5 j 为：告警事件e 与告警事件集合 e l ，e 2 ，e l 【) 相关， 表示为e j e l ，e 2 9o 9 e k 或 e l ，e 2 ，e k ) j e 。前者表示根据 e l ，e 2 ，e k 确定反应 当前故障的根源告警e ；后者表示根据 e i ，e 2 ，e k ) 预测可能发生的故障，而e 则 表示代表该故障的重大告警。 2 2 2 事件关联的类型 事件关联操作有很多类型，较为重要的有以下几种【3 , 5 , 7 , 4 4 】： 1 告警压缩( c o m p r e s s i o n ) 在给定的时间窗口内，如果检测到有大量的相同告警事件重复发生时，我们 利用该告警事件加上其发生的次数来替代，形式化描述为：【e ，e , - - - , e j e 。正 是由于网络告警中包含大量的重复告警事件，所以需要进行告警压缩。 l o 硕士学位论文第二章基于事件关联和数据挖掘的故障管理概述 网络中产生重复告警事件的主要原因有：( 1 ) 网络中的某些设备或者检测系 统在短时间内进行多次轮询，当网络中的设备发生故障，那么相同的告警事件就 会被多次上报( 2 ) o a 于网络中的设备是互联的，网络故障发生后，故障可能被与 之相连的多个网元检测到，多个网元都