（计算机科学与技术专业论文）基于贝叶斯网的ip网络故障定位算法的研究和实现.pdf

基于贝叶斯网的ip 网络故障定位算法的研究和实现 摘要 故障定位作为故障管理系统中的一个核心模块，对于保障网络的 正常运作和业务的可持续性有着重要的意义。伴随着i p 网络规模的不 断扩大，各类业务应用的大量部署，以及用户对服务质量要求的不断 提高，如何在网络和业务出现故障的时候进行快速的定位并解决故障 从而保障业务的正常运作成为现i p 网络故障管理领域的核心问题。现 今用户对服务的要求越来越高，高质量的服务依赖于对故障快速、准 确的反应，故障定位必然会扮演着更加重要的角色。同时伴随着网络 规模的扩大、业务的部署，i p 网络中的故障定位问题呈现出复杂化、 不确定性的特点，对于如何进行及时、准确的故障定位提出了很大的 挑战。因此，如何在一个复杂、大规模、含有噪声、故障根源具有不 确定性的环境中进行有效的故障定位成为当前故障定位算法研究的 重点。 贝叶斯网是目前不确定知识表达和推理领域最有效的理论模型 之一，它不仅能都对网络低层确定性的故障和症状之间的确定性的推 理关系进行建模，而且对于协议栈上层出现的故障和症状间不确定的 推理关系也提供了很好的建模方法，从而可以确保准确的反应出一个 具体i p 网络中各类实体间的关系信息。再者，贝叶斯网络采用图的形 式的网络结构去表达变量的联合概率分布及其条件独立性，能大量地 节约概率推理计算时间，对复杂、大型i p 网络中定位推理是非常有用 的。所以基于贝叶斯网络的故障定位方法很适合于应用在现今部署了 大量业务的i p 网络中进行故障定位。 本文从一个具体的应用场景出发，分析i p 网络中故障定位出现的 一些新需求，并通过对原有的基于贝叶斯网的推理算法的研究，在其 基础上进行改进，提出了一个改进的基于贝叶斯网络的故障定位的算 法。该算法引入最大同时发生的故障数的限制，采用一种新的限制性 的近似推理机制，在保障故障定位准确度的前提下能够更加快速的定 位故障的根源；由于能够同时利用表征网络或业务应用处于正常状态 和不正常状态的症状信息，并引入了解释门限进行噪声过滤，有着较 好的抗噪声能力。最后，在仿真实验中，与其他故障定位算法进行各 项性能指标的对比，本算法保持着与这些算法相近的诊断精确度的前 提下，其在时间复杂度方面表现出来很大的优势，且具有良好的抗噪 声能力，十分适合于应用在大型、复杂i p 网络中。 关键词：故障定位贝叶斯网故障传播模型概率推理 r e s e a r c ha n d 姗l e m 匠n 1 j a t i o no f f a u i jl o c a l i z a t i o na l g o r i t h mf o r 口一b a s e dn e t w o r k su s i n gb a y e s i a nn e t w o r k s a b s t r a c t a sas i g n i f i c a n tf u n c t i o no fn e t w o r km a n a g e m e n t ，f a u l tl o c a l i z a t i o n h a sp l a y e da ni n c r e a s i n g l yi m p o r t a n tr o l ei nt h ei p - b a s e dn e t w o r k st o g u a r a n t e et h ea v a i l a b i l i t yo ft h en e t w o r ka n dt h ec o n t i n u o u so ft h e e n t e r p r i s es e r v i c e i np a r t i c u l a r , w i t ht h er a p i dd e v e l o p m e n to fi p - b a s e d n e t w o r k s ，v a r i o u se n t e r p r i s es e r v i c e sa n dt h ec o n t i n u o u si m p r o v e d d e m a n df o rs e r v i c eq u a l i t y , h o wt ol o c a t et h er o o tc a u s eo ft h ef a u l tm o r e q u i c k l ya n dm o r ep r e c i s e l ys oa st os o l v et h ep r o b l e mw h e nf a u l t sa p p e a r i ss u r et ob et h ek e yp r o b l e mo ft h en e t w o r km a n a g e m e n ts y s t e m c u r r e n t l y , u s e r sd e m a n d sf o rs e r v i c eq u a l i t yh a v ei m p r o v e dal o t ，a n d h i g h q u a l i t ys e r v i c ed e p e n d so nt h ef a s ta n da c c u r a t er e s p o n s eo ft h ef a u l t ， s of a u l tl o c a l i z a t i o ni ss u r et ob ea l l i n c r e a s i n g l yi m p o r t a n tr o l e a c c o m p a n i e db yt h ee x p a n s i o no ft h en e t w o r ka n dt h ee n t e r p r i s es e r v i c e ， i p b a s e dn e t w o r k ss h o w ss o m en e wc h a r a c t e r i s t i c ss u c ha su n c e r t a i n t y , c o m p l i c a t i o na n ds oo n ，w h i c hm o u n tn e wc h a l l e n g e st ot h er a p i da n d a c c u r a t ef a u l tl o c a l i z a t i o n t h e r e f o r eh o wt od oe f f e c t i v ef a u l tl o c a t i o ni n ac o m p l e x ，l a r g e s c a l e ，n o i s ea n du n c e r t a i nn e t w o r kw i l lb et h ef o c u so f t h er e s e a r c ho ff a u l tl o c a l i z a t i o na l g o r i t h m b a y e s i a nn e t w o r k sc a nm o d e lb o t hd e t e r m i n i s t i ca n dp r o b a b i l i s t i c d e p e n d e n c i e sa m o n gm a n yt y p e so ft h ef a u l t sa n dt h es y m p t o m s ，s ot h a t i tc a na c c u r a t e l yr e s p o n s et h ev a r i o u sr e l a t i o n s h i p sb e t w e e nt h ee n t i t i e si n t h ei p b a s e dn e t w o r k s f u r t h e r m o r e ，t h eb a y e s i a nn e t w o r k su s e st h e g r a p h - s t r u c t u r et oe x p r e s st h ej o i n tp r o b a b i l i s t i cd i s t r i b u t i o no fv a r i a b l e s a n dc o n d i t i o n so fi n d e p e n d e n c e ，w h i c hc a l lg r e a t l ys i m p l i f yt h ei n f e r e n c e c o m p l e x i t ye v e ni nl a r g e - s c a l ei pn e t w o r k s ob a y e s i a nn e t w o r k si s e s p e c i a l l ys u i t a b l ef o rr e a s o n i n ga b o u tf a i l u r e si nt h ei p - b a s e dn e t w o r k s w h i c hh a sal o to fe n t e r p r i s es e r v i c e b a s e do na l la p p l i c a t i o ns c e n a r i o s ，t h i sp a p e rp r o p o s e san e wf a u l t l o c a l i z a t i o na l g o r i t h mb a s e do nb a y e s i a nn e t w o r k sb yt h er e s e a r c ho fn e w n e e d i n g so ff a u l tl o c a l i z a t i o ni nt h ei p b a s e dn e t w o r k sa n dd o i n ga m e n d t ot h ee x i s ta l g o r i t h m t h i sa l g o r i t h mi n t r o d u c e st h el i m i tn u m b e ro f s i m u l t a n e o u sf a u l t sa n dd o e sa na p p r o x i m a t ei n f e r e n c es ot h a ti tc a n s p e e du pt h ef a u l tl o c a l i z a t i o np r o c e s s ，a n da tt h es a m et i m ei tp r o v i d e s n i c el o c a l i z a t i o na c c u r a c y b e c a u s et h i sa l g o r i t h mc a ns i m u l t a n e o u s l yu s e b o t hp o s i t i v ea n dn e g a t i v es y m p t o m sa n di n t r o d u c eat e c h n i q u ec a l l e d a n a l y s i st h r e s h o l dt of i l t e rs p u r i o u ss y m p t o m s ，i th a s n i c en o i s er e s i s t i n g a b i l i t y a tl a s ti nt h ee x p e r i m e n t sw ec o m p a r e o u ra l g o r i t h mw i t hap r i o r a l g o r i t h mi h u ( w e a l s oi m p l e m e n tt h i sa l g o r i t h mw i t hj a v at op r o c e s st h e e x p e r i m e n t ) r e s u l t ss h o wt h a to u ra l g o r i t h mg e t ss i m i l a ra c c u r a c ya s i h ub u tw i t hm u c hl e s sl o c a l i z a t i o nt i m e ，o u ra l g o r i t h mp e r f o r m sb e t t e r i nr e a l i s t i cn o i s yn e t w o r k s i tc o u l db es e e nt h a to u rm e t h o di sm o r e s u i t a b l et ob eu s e di nt h el a r g e s c a l ei p b a s e dc o m p l e xn e t w o r k s k e yw o r d s ：f a u l tl o c a l i z a t i o n ；b a y e s i a nn e t w o r k s ；f a u l tp r o p a g a t i o n m o d e l ；p r o b a b i l i s t i cr e a s o n i n g 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：蔓均缝本人签名：蔓塑丝 本人承担一切相关责任。 日期：圣垒唑三：卫 关于论文使用授权的说明 本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校 可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名：望渔焦本人签名：翌渔塑日期：她川7 导师签名：j 孕型匕l 日期：二坦4 三正i _ 一 i i 课题背景 第一章引言 伴随着网络应用的日益普及，各类企业大型网络的迅速部署，网络规模不断 扩大、网络的复杂性的不断增加、各类复杂的企业业务应用的部署，网络管理维 护的工作越来越复杂，特别是伴随着用户对服务要求的进一步的提高，如何保障 各类企业业务应用的正常运作成为网络管理系统中的一个核心问题。对于当前的 企业使用的i p 网络，保障各类业务应用的正常运行是其部署网络管理系统所关 注的重点。所以其对网路管理系统提出的重要需求之一就是要保证本企业网络上 的各种企业业务应用正常的运行，而故障定位作为保证此需求被实现的一个核心 功能，在现今大型i p 网络中必然会发挥着越来越大的作用。特别是伴随着当今 互联网的飞速发展，各类企业应用在网络上的大量部署，故障定位系统不再仅局 限于诊断协议栈底层的物理故障，同时诊断协议栈上层的各类业务应用的故障也 逐步的成为我们更加关注的重点。而上层各类业务应用故障的出现，在大型复杂 网络中则是由多种不同原因导致的并且具有很大的不确定性，这对准确的故障定 位也提出了新的要求：在实际应用的故障诊断系统中，当端到端的业务故障的发 生，故障定位系统应能够迅速定位是那些具体的故障影响了这些业务应用。 目前，已经从计算机科学的不同领域中派生出多种多样的方法被应用于故障 定位。基于规则n 1 、基于模型瞳1 和基于案例1 的技术均是广泛使用的故障诊断技 术，这些方法都是基于当故障发生时，故障必然导致一定的外在状态的出现，因 此这些方法也被称为确定性故障定位方法。但是随着网络规模的扩大、复杂企业 业务应用的部署，网络中出现的大量故障和症状之间的关系表现出越来越多的不 确定性h 1 ，因此出现了很多基于图论技术晦1 、神经网络的不确定性推理技术1 ， 而基于贝叶斯斯网络的推理技术则是其中一类比较可行的故障定位技术。贝叶斯 网络不仅能都对网络低层故障和症状之间的确定性的推理关系进行建模，而且对 于协议栈上层出现的故障和症状间不确定的推理关系也提供了很好的建模方法， 所以基于贝叶斯网络的故障定位方法很适合于应用在现今部署了大量业务的i p 网络中进行故障定位。， 基于贝叶斯网的故障定位方法的核心是贝叶斯推理算法，如何根据建立起来 的模型进行推导，根据接收到的信息去定位根源故障的所在，这是贝叶斯推理要 解决的核心问题，同时还要考虑到实际应用的故障定位系统中，大型企业的i p 网络的规模往往是巨大、复杂的，一个成功的故障定位系统必然对推理时间有很 高的要求，以满足实时推理、及时解决问题的需求。为了解决基于贝叶斯网络的 推理问题，已经出现了许多推理算法，整体上可以分为两大类：精确推理算法和 近似推理算法。具有代表性的精确推理算法有变量消元算法n 引，团树传播算法n 铂 和迭代信度传播算法n 5 1 等。由于精确推理算法的复杂度高( 一般都是指数级别) ， 不能满足大规模贝叶斯网的推理需求，也难以满足实际使用的要求( 高时间复杂 度使得难以迅速的给出定位结果，从而结果不具有很好的时效性，难以指导运维 人员解决问题) ，许多研究者把目光转向了贝叶斯网的近似推理方法，以牺牲精 确度为代价换取推理时间复杂度的降低，以求达到一个推理精确度和推理时间复 杂度的平衡。主要的近似推理算法有随即抽样算法n 刖，有环的迭代信度传播算法 n7 1 、i h u 算法n 町和s h r i n k 推理算法n 钔。但是上边的算法还存在着在大型i p 网络 中定位时过长、抗噪声能力不强或定位准确度过低的缺点，因此需要进行进一步 的改进，以满足实际应用中的系统的需求，达到一个平衡状态，以满足实际使用 的要求。 1 2 本文要解决的问题与创新点 本课题的任务是：学习和研究现有的各类故障定位技术，并总结其优缺点， 然后基于当前部署了大量企业业务应用的i p 网络这个特殊场景进行相关故障定 位技术的研究，从而选取了一个适合此情景的故障定位技术的作为研究方向：基 于贝叶斯网的故障定位方法。通过对现今流行的各类基于贝叶斯网的故障定位推 理算法的研究，总结各种推理算法优缺点，本文提出了一种新的基于贝叶斯网的 故障定位算法，一定程度上解决了定位时间过长、抗噪声能力低、定位不准确的 问题，最后基于j 越，a 语言给出算法的具体实现过程，并进行仿真实验，比较、 验证本算法的各种性能指标，同时在现有的故障定位系统中实现了此算法。 研究内容包括： 一 研究现有的各类故障定位技术的基本原理、使用方法，进行算法比较， 并分析其优缺点； 一 通过对一个具体的口网络系统的分析，提出贝叶斯网适合于m 网络故 障定位的观点，并研究现有的比较流行的基于贝叶斯网的推理算法的基 本原理，分析各算法的局限性，提出改进方向； 一 在对以往基于贝叶斯网的推理算法的研究的基础上，提出一种新的基于 贝叶斯网的故障定位算法； 一 对新提出的原始算法进行算法改进，进一步提高算法的抗噪声能力； 2 一 本故障定位算法的编程实现、仿真实验、性能比较。 创新点包括： 一 提出了一种新的基于贝叶斯网的故障定位算法：在算法中采用了限制性 的近似推理的方法，大大的降低了算法的时间复杂度，减少了故障定位 所需要的时间；在算法中引入解释门限以处理噪声；在算法中引入最大 同时发生的故障数的限制，结合本算法的采用新的处理机制。 1 3 研究生期间工作 研究生阶段，本人深入了解了网络管理方面相关的原理规范和技术，并对告 警管理相关知识进行了更加深入的研究，同时实际参与到一些大型的i t 网管项 目的开发工程中，主要包括： 主要包括： 1 )综合故障管理系统。作为后台模块的总负责人，负责本系统后台各模 块的设计和实现，主要包括：南向系统( 各接入系统) 适配模块、告警处理模块、 系统监控模块、告警关联性分析模块( 均使用j a v a 开发) 。通过此项目对于网络 管理中的告警管理各功能有了更加深入的认识和理解。 2 ) 综合资源管理系统。作为项目的主要设计和开发人员，设计和参与实 现了系统中资源基本管理部分。 3 ) 故障定位算法的研究。在上述综合故障管理系统的告警关联性分析模 块的基础上，进一步研究各类故障定位技术，结合项目的特点和当前故障定位中 出现的新需求，并通过对贝叶斯网络模型的研究，探索基于贝叶斯网络的故障定 位方法。本文是此项工作的总结。 1 4 论文结构 本文共分五章，内容安排如下： 第一章引言，介绍本课题的背景、意义、本文主要的工作和创新点、本人 研究生期间的主要工作； 第二章故障定位技术的介绍，并进行各类故障定位技术的比较，提出当今 故障定位领域面临的一些主要问题； 第三章通过对一个具体场景的介绍、分析、总结，分析了i p 网络中故障定 位的一些具体问题，针对此场景挖掘出故障定位的新需求，并结合 现有的基于贝叶斯网的推理算法的特点，说明贝叶斯网适合于用于 i p 网络故障定位的原因，并对已有的推理算法进行简单介绍和总结 改进，最终提出自己的算法，主要包括：1 故障传播模型的建：2 一种新的基于贝叶斯网的故障定位算法的提；3 算法改进； 第四章本算法的具体实现过程，仿真实验； 第五章结束语，对本文工作进行全面总结，给出本文所取得的成果，指出 存在的不足和改进方向。 4 第二章故障定位技术的研究现状 2 1故障定位中的相关概念 故障定位中的一些通用概念，其中有些还没有标准的定义，下面给出本文使 用到的一些基本概念的常规定义： 故障f ： 导致网络处于非正常状态、业务应用处于非可用状态或者性能下降状态的根 本性的原因，即自身不会是其他故障表现出来的外在现象，故障通常是不会直接 被网管系统直接观测到的，往往通过一些外在现象表现出来。故障根据其持续时 间可以分为下述三类： 1 ) 永久性故障，它是指一些持续性的故障。在网络管理中，永久性故障常 常是不可自动恢复的，往往一直持续到一项维修活动的结束为止。 2 ) 间歇性故障，它是指不连续或周期性的故障。间歇性故障的主要原因是 网络设备软硬件的不稳定性引起的，间歇性故障会导致网络性能和业务应用性能 的短期下降，但是频繁的间歇性故障会严重影响网络和业务应用的正常运作。 3 ) 短暂性故障，由于临时的环境因素而导致的短时间的故障，这类故障也 称为“软故障。短暂性故障会对网络和业务应用会造成临时、部分的影响，但 是其能够自动恢复。 症状s ： 症状是故障的外在表现，故障定位通常是根据症状信息来进行的。症状在实 际的网络管理系统中往往是以告警的形式出现的，由监控系统通过对网络、业务 应用潜在的故障或者已经发生的故障的外在表现检测来获取并提供给故障定位 系统的。 s n ( n e g a t i v es y m p t o m s ) ： 反映网络或者企业业务应用出现故障的那部分症状信息。 s p ( p o s i t i v es y m p t o m s ) ： 与s n 部分的症状信息相反的那部分症状信息和未观测到的那部分症状信息。 故障传播模型： 反映物理网络及业务应用中所有可能的故障和症状及其之间的关联关系的 模型。 5 2 - 2 常用的故障定位技术 基于规则、基于模型和基于案例的技术都是广泛使用的故障定位技术，这些 方法的共同的特点是：它们均假设当某个故障发生时，此故障必然导致一定的外 在状态的出现，也即只要观测到特定的症状信息，就认为某个特定的故障一定发 生，因此这些方法被称为确定性故障定位方法。但是随着网络规模的不断扩大、 复杂企业业务应用的广泛部署，故障和症状之间的关系表现出来越来越多的不确 定性，从而逐渐出现了很多基于图论技术、神经网络、贝叶斯网、编码本的不确 定性推理技术。 2 2 1 确定性的故障定位技术 2 2 1 1 基于规则的方法( r u l e - b a s e dm e t h o d ) 基于规则的故障定位方法是最简单的故障定位方法，它使用“i ft h e n 的 规则形式捕获人类问题求解的行为特征，并通过“认识一行动 的方法来解决问 题，其表现形式符合人的思维习惯，便于人们理解，有利于知识的提取和形式化 表示。规则推理的应用过程符合人的认知过程，容易实现，有利于问题求解和专 家系统的开发。 基于规则的诊断不需要对系统底层的体系结构和操作原理有深入的了解，因 此比较容易制定和使用。但是基于规则的诊断系统的下述缺点决定其难以应用在 复杂的口网络中。首先，规则的维护和升级方面：当规则数量达到一定量时， 知识库的维护会变得越来越困难；多数基于规则的故障定位系统没有自我学习能 力，主要从专家那里获取，知识的获取也是基于规则的故障定位方法的一个很大 的瓶颈。再者，基于规则的系统很难处理不精确的信息：由于基于规则的诊断系 统不需要了解系统的体系结构，因此很难由不精确的信息进行推理。最后，基于 规则的诊断系统虽然能够自动通过统计方法分析规则之间的相关性，但是一旦被 诊断系统的物理结构或逻辑系统结构发生了变化，要重新生成所有规则之间的相 关性。 典型的基于规则的诊断系统有：h p 公司九十年代研制的e c s ( e v e n t c o r r e l a t i o ns e r v i c e s ) 睁3 ，它是o p t v i e w 的重要组成部分。 2 2 1 2 基于模型的方, 去( m o d e l b a s e dm e t h o d ) 基于模型的故障定位方法，对根源故障的定位建立在面向对象的模型基础之 上。首先，该类方法会充分利用现有的系统知识，将被管系统的各类物理实体和 6 业务应用逻辑实体建模为诊断对象，诊断对象之间的关联关系也会被清晰地描 述，从而建立起一个反映了实际系统的结构和行为的模型n 训。然后，基于模型的 故障定位的主要是通过分析模型和实际系统的差异来进行的。一个系统由多个功 能不同的被管对象组成，这些对象之间有着一定的连接关系，并且对象本身要遵 循一定的逻辑以实现系统的部分功能。而模型是对现实系统物理实体、逻辑实体 的理想描述，因此构成模型的基本成分也是会满足一定的理想规则的。由于故障 的出现，系统的实际行为和理想模型必然会出现一定的偏差，此时定位系统通过 比较分析两者的差别，从而定位实际系统错误的根源。 由于模型能够反映系统底层的细节，因此这种方法具有解决一些新出现的故 障的潜力1 ，但当出现的问题超出模型的知识范围时，其故障诊断的准确将大大 下降。同时，基于模型的故障定位方法需要详细的系统底层知识，对于不同的目 标系统，它们的网络拓扑、业务拓扑结构都不相同，因此导致模型的知识难以获 得和保持持续更新；同时在现今大型复杂口网络中还部署了大量的复杂业务， 进一步使得模型更加难以获取，从而使得在实际应用中对模型的操作变得非常复 杂的1 引。 i b m 研究中心在2 0 0 0 年提出的y e m n a j a 系统啪3 采用了基于模型的诊断方法， 能有效的将底层网络事件和高层应用告警关联。 2 2 1 3 基于案例的方法( c a s e b a s e dm e t h o d ) 基于案例的故障定位方法是通过对过去求解相似问题的经验和知识的总结 和学习去获得解决当前问题的方法的一种推理模式。过去发生的案例被储存、检 索，并被用来解决新的问题。由于解决新问题的经验构成新的案例，系统将新的 案例加入到数据库中，为将来使用。这样系统可以通过自己的方法来获取知识而 不必从通信专家那里获取知识。另外一个特点是基于案例的故障定位方法可以根 据出现的错误来自动改正将来的行为，而且基于案例的故障定位方法可以通过调 整过去的案例来构建新的定位方法，用于处理出现的新情况。 尽管本类方法具有学习能力，但专家仍要在优化推理方法方面做一些事情， 而不是只依赖与预先定义的过程。基于案例的故障定位方法的事件效率也存在问 题，分析处理过程将是复杂和费时的，但当系统启动和运行后，一个快速有效的 系统将会逐渐进化处理，这个过程对网络规模和配置的改变具有一定的弹性。 l e w i s 等研究了故障定位问题中的案例自适应问题瞳。d e r o 等研究了故障定 位问题中的对旧案例知识的抽取和初始化案例库的问题口引。 7 2 2 2 不确定性的故障定位技术 2 2 2 1 基于神经网络的方法( n e u m ln e t w o r k - b a s e dm e t h o d ) 神经网络由一系列模拟人脑思维方式的神经元组成，它具有多层反馈网络特 性，因此它具有预测一般非线性动态系统未知性能和模式辨识能力。应用神经网 络技术解决故障定位问题的主要步骤包括：根据诊断问题组织学习样本，根据问 题和样本构造神经网络，选择合适的学习算法和参数。神经网络能够从输入数据 中找出模式、规律和关联性，并通过输出对其进行解释。 基于神经网络的故障定位方法的缺点是，在将输入模式和输出模式结合起来 之前，它需要透彻、长时间的训练。由于必须要进行这种学习过程，因此在网络 管理领域会带来一些不方便的地方，例如当故障产生的所有告警不被检测或者根 本符合要求出现不能应用于学习过程的的情况时会带来很大不便。 北京理工大学的采用神经网络技术实现了网络告警信息的关联，能处理不确 定信息和抑制噪声馏3 j 。 2 2 2 2 基于因果图模型的方法( c a u s a l i t yg r a p hm o d e l - b a s e dm e t h o d ) 在网络管理系统中，故障往往不是显而易见的。监控系统能够监测到的往往 是一些故障的外在表现( 下边称之为症状) ，但很难根据这些症状信息来直接定位 故障源，这些都是由于网络中被管对象之间的相互依赖关系导致故障传播的结 果。为解决这些问题，一个自然的解决方法就是寻求网络被管对象故障和症状间 的因果关联性，因果图部分满足了这种需求。 因果关系图可以表示为直连的无环图g c ( e ，c ) ，其中节点元素e 表示网络 被管对象或网络事件，边c 描述了事件间的因果关系，若有向边佾，e ! i ) c ， 表示事件e i 的发生将导致事件e i 的发生，表示为e i e ! im 1 。在因果图可以为节 点和有向有向边设置一个对应的概率值，表示症状和故障的发生概率以及它们之 间的因果关系的强度。故障定位器在此模型的基础上利用一定的推理算法来分析 网管监控系统采集到的症状信息信息，从而找到故障根源的所在。 对于现今复杂i p 网络，故障和症状信息之间的因果关系表现出来了越来越 多的不确定性，基于因果图模型的方法可以通过引入概率边的方式来解决关系的 不确定性的问题，能够进一步的提高在复杂网络环境下的定位准确度。但是在实 际网络环境中，症状信息中还包含着大量的噪声，而算法本身很难对噪声进行很 好的处理，导致在此情形下的故障定位准确度大大折扣。 典型基于因果图的故障定位系统如i b mn e t v i e w 中解决网络故障和告警相 关的n e t f a c t 系统啤1 。 2 2 2 3 编码方法( c o d e b o o k s b a s e dm e t h o d ) 基于编码本的故障定位技术使用因果图作为故障传播模型，并利用信息论的 方法对网络系统故障和症状之间的关系进行编码。该技术方案由s a y c m i m 等 提出并在s m a r t si n c h a r g e 系统中首先应用西1 。编码方法涵1 的基本思想是：每 个故障的产生都会引起大量的症状事件的发生，每个对象产生的症状信息可能是 该对象自身的故障引发的，也可能是有关联关系的其他对象出现故障，传播过来 而引发的症状。处理这些由故障而引发症状信息的方法是把症状看成一个标识故 障的“密码刀，故障定位的过程就是对症状信息进行解码的过程，最终确定密码 标识的、出现症状事件的那些故障。如果不能得到确定性模型，这种方法还允许 引入概率统计模型，这种方法在现今上层业务应用相关的故障定位中得到了广泛 的应用，进一步的提高了故障定位的准确度。 基于编码的故障定位方法通过对网络知识进行预处理，根据可观察到的告警 集合对故障进行编码，成为编码手册( c o d e b o o k ) ，并且保证在能区分故障的前提 下，尽可能减小编码手册的大小，降低故障定位的复杂性。基于编码本的故障 定位方法在性能上和健壮性方面都是一种较好的选择，但它对网络管理对象的模 型构建要求很高，所以对于复杂性很高的网络不建议采用这种方法。 i n c h a r g e 啦副系统是一种采用编码技术的比较成功的故障定位系统，它是 s m a r t s 公司为解决网络中实时故障定位而开发的系统。 2 2 2 4 基于贝叶斯理论的故障定位方, - 去( b a y e s i a nn e t w o 水) 贝叶斯网又称为信度网络( b e l i e f n e t w o r k s ) ，是目前不确定知识表达和推理领 域最有效的理论模型之一，其特点决定其在处理协议栈高层业务应用相关故障有 着巨大的优势，同时也可以很好的定位协议栈低层的网络故障。自1 9 8 8 年p e d 给出明确定义后，对其的研究和应用成为学术界的一个热点之一。贝叶斯网本身 是一种有向无环图( d a g ) 。图中节点代表随机变量，节点间的有向边代表了节 点间的依赖关系( 由父节点指向其后代节点) 。每个节点有一个对应的条件概率矩 阵表达节点间依赖关系的强度，没有父节点的节点( 最高节点) 则使用先验概率进 行信息表达。 基于贝叶斯网的故障定位方法通过在故障的外在表现( 称之为症状信息) 和 故障的根源之间建立一种基于概率的因果关系，并通过对历史数据的学习，获取 故障发生的先验概率，同时获取当故障发生时症状信息出现的后验概率啪】。当监 9 控系统观测到某些症状信息时，通过应用贝叶斯规则或贝叶斯推理，确定贝叶斯 网中某个故障节点或者某些故障节点发生的概率，找出具有最大后验概率值的故 障或故障集合。 基于贝叶斯网的故障定位方法，通过收集监控系统采集到的症状信息来计算 所需节点的相关概率，而节点相关概率的计算被证明是是n p h a r d 的问题。虽 然通过采用恰当的启发式算法，可以在可接受的时间内完成几千个节点的计算， 但贝叶斯网边界概率计算效率仍是一个有待解决的问题。虽然也提出了一些近似 推理算法，但是还是未在时间复杂度和定位准确度之间取得一个良好的平衡。 m s t e i n d e r 等研究了以贝叶斯网为推理引擎，解决了端到端的故障诊断问题 和噪声网络中的故障定位问题，提出了一种基于贝叶斯网的故障定位算法 i n c r e m e n t a lh y p o t h e s i su p d a t i n g ( i h u ) 1 钔。 2 3 算法比较 文献 2 8 】， 2 9 1 对上述两大类算法进行了一定的比较，下边对上述算法进行了 进一步比较分析。 基于规则的故障定位方法适合于配置和结构很少发生变化的网络，对于经常 变化的网络本方法的效率会大大降低。而且在实际应用中，规则往往是不断变化 和发展的，对维护性提出了很高的要求。再者，规则的数量与网络规模和网络复 杂性成指数级数增长，同时过多的故障定位规则还会影响分析故障定位的效率和 准确性。同时，在网络变化比较大的情况下，规则也会发生很多的变化，如何确 认哪些规则是无效的，也是一个非常困难的过程。通过人工来维护大量的故障定 位规则非常困难，因此基于规则的方法很难适应大规模的和技术复杂的通信网络 模型。 基于模型的故障定位方法依赖于准确的模型的定义，当出现的问题超出模型 的范畴时，其定位准确度将会大大的下降。当网络结构发生变化时，往往需要对 模型做进一步的修正以便反映网络的最新变化以提高定位的准确度，但是于不同 的目标系统( 变化后的系统) ，它们的模型基本都不相同，而且模型的知识难以 获得和保持更新，对模型进行操作时的计算是非常复杂的。因此此类方法也适合 于网络变化不是特别频繁和网络模型较易建模的简单通信网络中。 基于案例的故障定位方法是一种解决问题的策略。它与专家系统的不同，此 类方法是基于过去的经验和案例来解决新发生故障定位问题而不是通过该问题 域中一般化的知识。基于案例的方法的一个很大欠缺是，它总是与某个特定应用 领域紧密相关，而不存在一个通用的案例方法。它对于网络变化处理反应不敏感， 处理过程较复杂且费时，对于要求实时性高的故障定位系统，此类算法难以及时 l o 地提供故障定位结果。 基于神经网络的方法具有良好的学习能力，而且对输入的数据具有较好的容 错性。但神经网络需要过多的训练，在通信网络中很难找到较好的训练数据。 基于因果图模型的方法通过引入概率边的方法较好的解决了关系的不确定 性的问题，一定程度上解决了协议栈上层应用服务故障和症状之间的不确定关系 的问题，提高了定位的准确度。但是在实际网络环境中，症状信息中包含噪声的 情况下，很难对噪声进行很好的处理，导致在次情形下的故障定位准确度大大下 降。 基于编码的故障定位方法通过对时间知识模型的预处理，降低故障定位的复 杂性。根据可观察到的告警集合对故障进行编码，成为编码手册( c o d e b o o k ) 。在 能区分故障的前提下，编码手册要尽可能小，这可以减少监控对象，提高效率。 在性能上和健壮性方面基于编码的方法都是一种较好的选择，但它对网络管理对 象的模型构建要求很高，所以对于复杂性很高的网络不建议采用这种方法。 基于贝叶斯网络的故障定位方法，通过收集监控系统采集到的症状信息来计 算所需节点的相关概率，而节点相关概率的计算被证明是是一个n p - h a r d 的问题 2 7 o 通过采用恰当的启发式算法，可以在可接受的时间内完成几千个节点的计算， 但贝叶斯网络边界概率计算效率仍是一个有待解决的问题。虽然也提出了一些近 似推理算法，但是还是未在时间复杂度和定位准确度之间取得一个良好的平衡， i h u n 叫取得了很好的定位准确度，但是定位时间难以满足实际应用系统的需求， 特别是在大型口通信网络中，其定位时间过长；s h r i n kn 踟能够迅速的定位故障 的根源，但是其定位准确度却大打折扣。 2 4 故障定位技术面临的主要问题 上述介绍的故障定位方法一定程度上解决了故障定位中出现的一些关键问 题，各类方法均有其擅长的应用场景，同时由于定位方法的本身特性也导致其在 特定应用环境上出现了一些重要的应用缺陷，但是结合实际应用场景的不同，上 述的故障定位方法还是在其擅长的场景中发挥了重要的作用的。 总的说来，这些故障定位方法逐步的解决了故障定位中的一些难点问题并在 现今的故障定位系统中得到了广泛的应用，但是随着m 网络的发展，大量业务 应用的广泛部署，已有的故障定位方法也出现了越来越多的问题，主要表现在： 1 ) 对于确定性的故障推理方法，这些方法的故障定位时间非常短，对于协 议栈低层的网络故障具有较高的定位准确度，但是其难以准确地定位协议栈上层 业务应用故障的根源，难以满足现今业务相关的故障定位的需求。 2 ) 已经出现不确定性推理算法一定程度上解决了协议栈上层应用故障定位 难的问题，但是这些方法往往具有很高的算法复杂度，难以应用于实际网络中。 对于不确定性推理，如果使用精确推理算法，其可以保持很高的推理准确度，但 是由于算法复杂度较高，所以当实际应用于故障定位系统中时，往往需要很长的 时间进行推理，特别是对于大规模i p 网络，往往会分析超时，在实际使用中难 以得到应用，达不到实时分析的去求；如果使用近似推理算法，虽然可以较为迅 速的寻找到故障的根源，但是其定位的准确度却大打折扣，因此需要在此两者之 间寻找一个平衡，寻求一种合适的故障定位方法。 3 ) 在网络含有噪声的情况下，故障定位准确度往往较低，即便通过噪声处 理提高了定位准确度，但是这类算法往往受外界因素的影响比较大，需要进一步 加强处理噪声的能力，提高故障定位的准确度和稳定性。 此外，如何对于变化较为频繁的口网络进行故障传播模型的建模，并实现 模型的动态学习和自适应也对现今的故障定位技术提出了很大的挑战，同时如何 在模型和症状信息不准确的前提下进一步的提出新的故障定位算法从而提高定 位准确度也是将来的一个重点。 2 5 本章小结 本章概述了现今比较流行的故障定位的方法，并简要介绍各方法的基本原 理、应用状况，同时对各类算法进行比较，分析当前故障定位算法的主要问题， 从而确定本文的主要研究方向研究基于贝叶斯网的故障定位算法。综上所述， 贝叶斯网是各类故障定位方法中能够较好的满足现今大量部署了业务应用一类 故障定位方法，能够很好的解决协议栈上层业务应用故障定位难的问题，同时近 似推理算法也一定程度上解决了时间复杂度过高的问题，算法中引入噪声处理提 高了抗噪声能力。下面章节通过研究贝叶斯的基础知识出发，深入研究现有的基 于贝叶斯网的推理算法，并致力于提出一种新的基于贝叶斯网的故障定位方法， 解决m 网络中故障定位的问题，同时进一步的提高算法的抗噪声能力、诊断准 确度。 1 2 第三章基于贝叶斯网的i p 网络快速故障定位算法 本章通过分析一个具体的网络场景出发，分析现今口网络中出现的一些 新特点、新需求，然后引入基于贝叶斯网的故障定位算法，分析其适合口网络 故障定位的原因，并指出现有推理算法的局限性，最后从现有算法出发，提出一 种新的基于贝叶斯网的故障定位方法。 3 1i p 丽络中的故障定位 3 11i p 网络中故障的特点 口网络最初提出的目的主要是数据传输、数据共享，但是现夸越来越多的各 类企业业务应用部署到口网络中，实现各类的业务应用逐步成为邛网络的新的 重要特征。对于企业为了实现各类具体业务需求而部署的口网络，部署于其上 的网络管理系统的一个重要的目标就是保障各类业务应用的正常运作，故障定位 作为实现此功能的核心功能，也必然需要满足一些新出现的特性，下边基于一个