（计算机科学与技术专业论文）主动自适应故障探测技术的研究与实现.pdf

北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 主动自适应故障探测技术的研究与实现 摘要 作为网络管理的核心功能之一，故障管理承担着保证网络业务正 常运行，迅速检测并定位故障的任务。当前故障管理普遍采用基于告 警事件关联的方式，随着网络规模和复杂性的增大，该方式暴露出以 下问题：1 ) 每个被管实体都会就自身感知的异常状况发出告警，从 而导致海量的告警信息产生，其中包含大量重复、冗余的告警，对管 理系统的计算能力形成挑战。2 ) 虚假告警、告警延迟和告警丢失影 响了故障诊断的准确性；3 ) 异构网络的存在影响了管理系统的可扩 展性。对于故障管理系统来说，告警是一种被动的信息收集方式，一 条告警反映了网络中某个事件的发生；而主动探测则是一种主动地获 取网络症状方式，每个探测可以实时地获取探测路径上的网络元素状 态。主动探测的主动性、自适应性能够弥补告警方式的上述缺陷，在 故障管理中具有很大的应用潜力。 本文研究了使用主动探测进行故障管理的基本原理，分析了相关 关键问题，并提出了某些新的问题解决方案；本文还通过实际的故障 管理系统展示如何使用探测技术进行有效的故障诊断。本文的主要内 容包括：1 ) 研究总结了故障管理中使用探测的方法及其关键问题， 包括流程和算法；2 ) 分析并改进了故障检测和故障定位阶段的探测 选择算法，提出一种高效的启发式算法来替代高复杂度的贝叶斯推理 算法；3 ) 分析并改进了建立探测依赖模型的方法，提出扩展依赖矩 阵的方法；4 ) 通过一个故障管理实验验证了主动探测在故障管理中 的应用，并对结果进行了比较分析。 关键字：网络管理故障诊断主动探测探测依赖模型 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 t h er es e a r cha n dr e a l i z a t i o n o f a ct i v e f a u l tp r o b i n gt e c h n o l o g y a bs t r a c t a so n eo ft h ec o r ef u n c t i o n so fn e t w o r km a n a g e m e n t ，f a u l t m a n a g e m e n ti st oa s s u r et h eg o o dp e r f o r m a n c eo fn e t w o r ka n dd e t e c ta n d l o c a t ef a u l ta ss o o na sp o s s i b l e t h ec u r r e n tf a u l tm a n a g e m e n tm e t h o d s a r em a i n l yb a s e do na l a r mc o r r e l a t i o n ，b u tw i t ht h ee n l a r g e m e n ta n d c o m p l e x i t y o ft h e n e t w o r k , t h e r e a r es e v e r a l p r o b l e m s f o rt h i s m e t h o d o l o g y ：1 ) e v e r yn e t w o r ke l e m e n t w i l ls e n do u ta l a r m st op r o d u c e n u m e r o u sa l a r m s ，m o s to fw h i c ha r eu s e l e s s ，a n dt h e nc h a l l e n g et h e m a n a g e m e n ts y s t e m 2 ) t h ee x i s t e n c eo ff a l s ea l a r ma n dd e l a y e da l a r m w i l li n t e r f e r ew i t ht h ea c c u r a t e n e s so ff a u l tl o c a t i o n 3 ) t h ee x i s t e n c eo f h e t e r o g e n e o u sn e t w o r km a k e st h ef a u l tm a n a g e m e n ts y s t e ms u f f e rf r o m b a da d a p t i v e n e s s f o rf a u l tm a n a g e m e n ts y s t e m ，a l a r mi sap a s s i v e i n f o r m a t i o nc o l l e c t i n gm e t h o da n da na l a r mc a no n l yr e f l e c ta l le v e n ti n t h en e t w o r k ，w h i l ea c t i v ep r o b ei sa l la c t i v em e t h o dt og e tn e t w o r k i n f o r m a t i o na n dap r o b ec a l lr e f l e c tt h er e a l - t i m ee l e m e n ts t a t u so nt h e p r o b ep a t h 。t h ea c t i v e n e s sa n da d a p t i v e n e s so f a c t i v ep r o b ec a nm a k eu p f o rt h ed i s a d v a n t a g e so fa l a r m ，a n dh a v eg r e a ta p p l i c a t i o np o t e n t i a li n f a u l tm a n a g e m e n t t h i sp a p e rm a k e sa no v e r a l ls t u d yo ft h ef u n d a m e n t a lp r i n c i p l eo f a c t i v ep r o b ei nf a u l td i a g n o s i s ，a n a l y s e st h ec o n c e r n e dk e yp r o b l e m s ，a n d p r o v i d es o m e n e ws o l u t i o nt ot h e s ep r o b l e m s t h i sp a p e ra l s os h o w sh o w t ou s ep r o b et om a k ef a u l td i a g n o s i st h r o u g hf a u l tm a n a g e m e n ts y s t e m c a s e t h ec o n t e n t so ft h i sp a p e ri n c l u d e s ：1 ) s t u d ya n ds u m m a r i z et h e g e n e r a lm e t h o do fu s i n gp r o b ei nf a u l tm a n a g e m e n t ，a n a l y z e ss o m eo f t h e k e yp r o b l e m s 2 ) a n a l y z ea n di m p r o v et h ep r o b es e l e c t i o na l g o r i t h mi n f a u l td e t e c t i o na n df a u l tl o c a t i o n ，a n dp r o p o s ea ne f f e c t i v e h e u r i s t i c a l g o r i t h mi nc o n t r a s tt ot h ec o m p l i c a t e db a y e sa l g o r i t h m 3 ) a n a l y z ea n d i m p r o v et h em o d e l i n gm e t h o d o fp r o b ed e p e n d e n c ym o d e l ，p r o p o s i n gt h e m e t h o do fe x t e n d e dd e p e n d e n c ym a t r i x 4 ) v a l i d a t et h ep r o b em e t h o d 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 t h r o u g haf a u l tm a n a g e m e n te x p e r i m e n t ，a n da n a l y z et h ed i a g n o s i sr e s u l t k e y w o r d sn e t w o r km a n a g e m e n tf a u l td i a g n o s ea c t i v e p r o b e p r o b i n gd e p e n d e n c ym o d e l i i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：j 够售；i ；售一日期：2 左 l 五扯 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：垄堕幽日期：趋参，墨! ! l 导师签名：叠缎【z日期：翟笪：! ! l2 北京邮电大学硕士研究生毕业论文 1 1 课题背景和意义 第一章概述弟一早慨尬 主动自适应故障探测技术的研究与实现 近年来，随着计算机与通信技术的发展与结合，各种网络服务和应用以很快 的速度发展和增长，并逐步进入对人类社会的各个领域，包括经济、社会活动乃 至日常生活，改变着人们的生活、学习和工作方式。与此同时，网络不再仅仅是 一个提供物理连接的简单设施，而是一个分布广泛的、提供各种服务的平台。一 方面随着对网络的广发应用，人们对网络的可靠性也提出了更高的要求；而另一 方面，随着网络的规模越来越大，结构越来越复杂，提供的服务也种类也越来越 多，网络的管理和维护工作也变得越来困难。网络管理包含五个功能域：配置管 理、性能管理、故障管理、安全管理和计费管理 1 2 】。五大功能既相互独立，又 存在着千丝万缕的联系。其中，故障管理是整个网络管理功能的核心部分，用于 保证网络能提供连续可靠的服务，减少网络服务中断对社会生产造成的影响和损 失。 故障诊断作为网络管理的一部分用来动态地维持网络服务水平并保证网络 有高度的可用性，它包括及时发现网络中发生的故障并找出故障根源原因，必要 时启动控制功能以排除故障或隔离故障根源以减少其造成的影响，其中故障检测 和定位是故障管理得重点。然而，随着网络规模不断扩大及其异构程度的不断增 加，网络故障的诊断与维护变得非常困难。诊断系统不仅要具备有关网络设备的 繁杂知识，而且必须在短时间内对海量且呈动态变化的有噪音或不完整信息做出 正确的决策。与此同时故障管理不再局限于网络层，逐渐扩展到应用层，分布式 的复杂业务系统同样需要网络管理来保证其良好运行。为了能够处理大量各种复 杂告警信息，一般采用告警事件关联的方法进行故障管理，但是当前广泛采用的 基于告警事件关联的故障管理方法存在着种种局限，探索新的方法正成为研究的 热点。 告警事件关联方法的基本原理是通过网络设备或主机s n m p 代理采集告警 信息，告警信息由网络设备或主机进程在状态改变或某些事件发生时发出，诊断 系统通过关联分析这些告警信息来推测根源告警。告警关联技术包括基于规则、 基于案例、基于神经网络和基于数据挖掘等。然而网络的快速发展暴露了该方法 的缺陷，主要表现在以下几个方面： ( 1 ) 告警数量激增：当前的网络管理系统中，所有网络节点，比如路由器、 交换机、主机、数据库和传感器等，都维护着自身的管理数据m i b 。所有的节 点都会发出告警，而有些告警比如性能告警，需要管理站频繁地访问m i b 并计 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 算获得。随着网络规模不断扩大，使得整个网络的告警数量激增，其中包含大量 冗余、重复的告警，这对网络本身形成负担，可能使本来存在故障的网络状况更 加恶化。 ( 2 ) 被动地接受告警：当前的故障管理系统都是被动地接受告警数据。故障 管理系统使用的算法需要的数据可分为以下几类：告警数据、网络的配置信息、 网络管理员指定或预先制定的规则，算法的设计都是在假定这些数据都是真实的 前提下进行的，而实际情况是这些数据的真实性、有效性并不能完全保证。告警 丢失、延迟或配置信息错误都会干扰故障管理系统得分析准确性。 ( 3 ) 可扩展性差：随着网络的发展，网络的构成复杂多样，并不断变化，比 如当网络中有个新类型的子网加入或新的网络设备加入时，其告警的采集方式或 数据格式往往会不一样，网络时间也不一定同步，网络结构的变化往往需要不同 程度地改动网络管理系统。 如上文所述，每个网络元素都会就自身感知到的异常状况而产生告警，一个 告警只能反映系统中某种事件的发生，告警具有某种模糊性和不确定性；而且一 个故障根源可能传播导致大量重复冗余的告警产生；而一个探测能够反映出系统 一条路径或一个部分的状态，探测所包含的信息量是较大的，而且探测的主动性 更能够准确地检测系统地状态，这也能增加故障定位的准确性。探测在故障管理 中具有很大的应用潜力。 本文题研究了使用主动探测进行故障管理的方法。所谓主动探测就是相对被 动接受告警而言，它采用探测主动地获取网络系统的状态信息 1 】。主动性可以 使我们可以更加有针对性地获取当前上下文我们所需要的信息，而不是接受海量 的上报告警，这能大大减少额外网络流量；主动性可以实时地获取目标状态，可 以避免告警延迟、重复告警、告警丢失和虚假告警造成的诊断错误；主动性还可 以使我们很容易地管理新的网络设备或业务系统，构造更具扩展性的故障管理系 统。 1 2 本文解决的问题和创新点 本文研究了主动探测的基本原理及其在故障管理中的应用方法，总结了在故 障诊断的故障检测和故障定位阶段如何使用探测来获取系统状态信息，并着重研 究了其中涉及的关键问题的解决方案，并通过一个诊断系统的实现和测试来证实 该方法的可行性及其效果。本文的贡献在于：( 1 ) 研究总结了使用主动探测进行 故障管理的基本原理和在故障故管理各个阶段探测使用的特点；( 2 ) 分析了使用 探测进行故障检测时如何选择探测及其涉及的问题；( 3 ) 分析了使用探测进行故 2 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 障定位时如何选择探测及其涉及的问题；( 4 ) 介绍了对网络和业务系统中建立探 测依赖模型的方法；( 5 ) 构造一个完整的使用诊断系统实例，对一个业务系统进 行故障诊断实验，并对结果进行了分析。 在总结研究当前研究成果的基础之上，本文对使用探测进行故障诊断所涉及 的一些问题进行了改进，并提出了一些新的方法，本文的创新点在于：( 1 ) 在故 障定位阶段，针对基于信息熵的探测选择算法的高复杂度，提出了一种启发式近 似算法；( 2 ) 针对使用探测技术的需求，提出了一种对业务系统建立探测依赖模 型的方法。 1 3 论文期间主要工作 本人在研究生期间主要参与了一个综合故障管理系统和综合资源管理系统 开发工作，包括需求分析、概要设计和编码实现整个过程，核心工作集中在拓扑 管理和告警关联性分析模块。通过充实的项目开发工作和大量的理论学习，本人 基本领会网络管理的基本原理，尤其通过综合故障管理系统中拓扑管理和告警关 联性分析模块的设计和实现，理解了各种故障管理的方法及其特点。 在此基础之上，我和项目组成员展开了基于主动探测的故障诊断的研究工 作。通过阅读大量相关文献和模拟实验，深刻理解了主动探测的思想及其应用方 法，着重研究了在故障管理中应用探测所涉及的关键问题，进行了改进尝试和实 验验证，并提出新的问题。 1 4 论文内容及结构综述 本文集中在主动探测在故障管理中的应用，包含的问题有探测站的选择、探 测的选择、故障诊断的流程和算法以及业务系统建立探测模型方式。本文的结构 如下： 第一章概述，简要介绍该课题的背景，本论文要解决的主要问题和创新点， 以及本人在论文期间做的主要工作。 第二章主动探测的原理，介绍了主动探测的基本原理原理，包括探测基本概 念、使用主动探测进行故障诊断的一般流程、探测依赖模型和各阶段涉及的问题 等，另外介绍该领域的研究现状。 第三章探测模型与算法，提出了本文建立探测依赖模型的新方法、对故障检 测算法的改进和对故障定位流程的改进。这部分涉及了在故障管理中使用探测的 几个核心问题的解决方案，是本文的理论核心，第四章的实现真是在这章研究 成果的基础之上的。 第四章使用探测进行故障管理的实现，该部分通过对一个w e b 业务系统进 3 北京邮电大学硕士研究生毕业论文 主动自适应故障探测技术的研究与实现 行建立探测依赖模型、故障检测和定位的流程实现和探测实施，完成一个完整使 用探测的故障管理系统实例。通过运行测试和诊断结果分析，验证了该方法的可 行性和效果。本章还简述了在实际的网络故障管理系统中结合使用告警和探测的 方式。 第五章是总结与展望，对该探测方法的使用涉及的问题进行了总结，指出了 有待改进的地方，对今后故障管理中探测方法的使用进行了展望。 4 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 第二章主动探测概述及其研究现状 2 1 被动式故障管理方法 故障管理作为网络管理的核心功能之一，承担着保证网络系统正常运行的任 务，需要在故障出现时迅速地检测到故障的存在，定位出故障根源并在可能的情 况下修复故障或隔离故障。为了完成这些任务，故障管理系统必须要以某种方式 来获取网络系统的状态信息，并基于这些信息进行分析推理。 当前普遍采用的信息收集办法是告警传递，告警是在特定的事件发生时被管 实体发出的通报构成的一种事件报告，用于传递告警信息。它们是一个系统发出 的短消息，表示其发生了某些事情或者异常。告警只是表示可能有故障发生，但 不一定有故障发生，被管实体可以发出告警事件作为对系统当前发生异常的响 应。告警事件包含被管实体状态的异常信息，一个告警信息通常包含以下信息： 有关发出告警设备的信息、故障的征兆以及告警产生的时间。但是，告警通常不 明显包含网络中的故障和问题根源的确切位置信息，仅仅是反映网络状况发生改 变的征兆。而且当网络中出现故障时，会引发一系列的告警，每个实体都以自身 感知的异常状况来发出告警。 由于每个被管实体都可能在感知到异常的状况下发出告警，故障的传播导致 一个故障就引起大量告警的产生，而且实体可能就某个异常反复发出告警，所以 在一个相当规模的网络系统中，告警信息的数量是很大的。管理系统一般通过告 警关联性分析来处理海量的告警。所谓告警关联性分析就是：通过对多个告警的 分析解释，从而提高了一个数量缩减后的告警集合的语义信息内容。告警相关性 分析是指对告警进行合并和转化，将多个告警合并成一条具有更多信息量的告 警，确定能反映故障根本原因的告警，从而准确定位故障。告警相关性可用于对 产生多个告警进行解释，这给最初定义的告警事件增加了新的含义。 告警相关性分析的算法种类有基于模型、基于规则、基于事例、基于神经网 络和基于二分图的分析方法等。由于每个实体都是单独地发送告警，因此大量的 冗余和重复告警的存在给故障管理系统的计算能力造成挑战；某些实体可能感知 到错误的异常从而会产生虚假告警，某些告警可能会丢失，会延迟到达这些情况 会干扰故障管理系统的分析；告警依赖于实体自身，如果该实体掉电则告警根本 不会产生；在大型、异构通信网络种没有统一的网络时间，这为告警事件的比较 和分析带来了无法克服的困难。 探测是由故障管理系统控制的主动对目标实体或网络发起的测试，由于它是 由管理系统统一控制的，所以可以很好地限制探测的总数和频度避免大量告警产 5 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 生的网络流量；探测具备实时的特点，能够避免告警延迟和丢失带来的影响，提 高告警的准确性。主动探测的特性能很好弥补告警的一些缺陷，对构造高校、可 扩展的故障管理系统来说具有很大的应用潜力。探测和告警都是获取系统症状或 状态信息的方式，不同的是一个由被管实体按预定义的方式依据自身的状态来上 报，另一个是由系统依据故障诊断的需要来主动执行。告警仅仅是以被管实体为 主体的症状，而探测是以管理系统为主体的症状，这种角度的转换会影响到诊断 的流程和故障定位的算法。探测和告警并不矛盾，而是能够弥补告警的缺陷，通 过将探测和告警相结合，能够相互补充。本文的主要内容是研究利用探测手段进 行故障管理的方法，将告警和探测相结合是将来的研究方向。 2 2 主动探测的基本原理 网络系统一个多层次系统，故障可能出现在不同的层次，故障也可能是或不 是f a i l s t o p 型( 指故障的存在是否使得相关的服务不可用，或只是性能降低) 1 2 】。同样随着分布式服务系统得广泛应用及其复杂性增加，维护这些系统同样 需要进行应用层故障诊断。伴随着系统的规模扩大和复杂性增加的是各种标准的 体系结构出现，比如j 2 e e ，为系统部件提供了高层的运行环境；从故障诊断的 角度来看，这个高层的运行环境就好像一个完整的网络环境，而系统部件，比如 数据库、e j b ，则对应于网络中的设备节点。网络故障诊断与分布式业务的故 障诊断具备一定程度的对称性，如果我们从完整的o s i 模型视角来看网络，那 么分布式业务的故障诊断就是网络应用层的故障诊断。 主动探测通过端到端的事务执行来提供分布式系统的状态信息，可以用于传 统的网络故障诊断也可以用于高层业务系统的故障诊断，本章主要讨论一般性的 使用主动探测的故障诊断方式。 2 2 1 相关概念介绍 在基于主动探测的故障诊断中，两个关键的概念就是“探测 和“探测依赖 模型 ，下面对这两个概念做详细的描述。 ( 1 ) 探测 所谓探测是一个端到端的事务，它的执行结果依赖于某些系统元素1 1 。在 一个分布式的系统中，探测是执行在某个主机上的一段程序，这段程序发送一个 指令或请求到目标网络元素或系统组件，并通过返回值来判断探测执行成功与 否。最常见的探测工具应该就是p i n g 和t r a c e r o u t e 命令了，这两个探测依 赖于相关的一些链路、主机和交换设备。其他的一些探测工具比如i b m 的端到 端探测平台e p p ，可以提供应用层的探测手段，可以发送邮件信息、w e b 请求 6 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 和数据查询请求来对应用服务系统进行探测。由于一个探测是一个端到端 ( e n d t o e n d ) 的事务，并不关注这个探测的执行步骤，非常适合用来检测端到 端的连接性或性能。 探测用于不同的系统层次和不同的粒度，p i n g 操作工作在网络层，可以用 来检测网络的连接性；其他一些探测可以用来检查网络的带宽、平均的口包大 小及丢包率等特性；更高层次的探测可以用来检测数据库服务器，h t r p 服务器 或e b j 服务器或磁盘服务器等。在软件系统中，可以深入到软件模块这个进行 探测和故障诊断。在哪个层次或以何种粒度进行探测完全取决于使用探测的目 的。探测执行后会有一个探测结果，探测结果可以简单地定义为成功或失败，或 在性能测试的情况下有更复杂的定义。 如前所述，一个探测依赖于某些系统元素，比如p i n g 探测依赖于一些口 网络元素( 主机、路由和链路) ，探测如果执行成功则在某种程度上说明这些元 素运行正常，而失败则在某种程度上表明某个依赖元素的状态异常。这里的“某 种程度用来涵盖系统中的某种不确定性，比如路由策略导致p i n g 经过不同的 路径或偶然的原因导致的p i n g 失败，在下文中有进一步的探讨。在一个由一组 相互联系的元素组成的系统中，比如通过链路相互连接的主机、路由器、交换机 组成的口网络，通过一组精心选择探测我们可以检测整个系统是否存在故障， 也可以推测出故障元素。 探测之间必须是相互独立的，因为如果一个探测的执行结果是由另一个探测 决定的，那么该探测就几乎没有包含什么信息量，探测的结果必须仅依赖于系统 中的组件。 ( 2 ) 探测依赖模型 上面的叙述表明，之所以能够通过探测结果检测和定位故障，是因为探测总 是依赖于一组系统组成元素，那么获得探测和系统元素之间的依赖关系就成为探 测技术的基础。为了描述探测和系统元素的关系，我们需要对系统进行建模，在 此这个某型一般叫做探测依赖模型。建模首先要把系统划分成一个元素集合，划 分方式往往依赖于系统自身的特性，有时是很直观的，有时却很抽象。比如i p 网络中，我们自然地把网络看作由主机、路由、交换机、链路组成的系统，而在 业务系统中我们抽取某些关键的进程、模块作为系统元素。关于“组件 、“元素 和“节点”这几种说法在本文中都是指诊断的组成目标网络或系统得实体，在不 同的上下文下采用了不同的说法，它们的意思都是一样的，下文不再指出。 为了直观描述探测和系统的依赖关系，参考文献 1 】提出依赖矩阵这一概念， 它用一个o 1 矩阵来标记探测和系统元素之间的依赖关系，如下图所示： 7 北京邮电大学硕士研究生毕业论文 表2 - 1 依赖矩阵示例 主动自适应故障探测技术的研究与实现 n ln 2n 3n 4 n 5 p l lol0o p 2 lo1oo p 3 lo1l 0 p 4 ll10l 矩阵的每一行代表一个探测，每- - n 代表一个系统元素，在位置 i ，j 1 处的0 表示p i 和n j 无关，而1 表示p i 依赖于n j 。上图表明p l 依赖于n 1 和n 3 。如 果这种依赖不是确定性的，而是某种概率依赖，则依赖矩阵也可方便地转换为二 分图概率模型。依赖矩阵是依赖模型一个比较简单和直观的形式，体现了探测对 系统元素的依赖关系，但没有体现依赖的顺序，比如在口网络中，一个探测往 往就是一条网络路径，那么依赖矩阵就忽视了路径上节点的顺序。0 1 矩阵的形 式也是一种确定式的依赖关系，可能在某些情况下并不能体现实际情况，应为网 络系统往往具备某种不确定性，探测的路径可能受到动态因素的影响，此时将 0 1 换成某个概率值能够体现这种不确定性，在第三章中本文会讨论这个方法。 2 2 2 使用探测的故障管理 故障管理作为网络管理五大功能域之一，其功能目标是在网络系统发生故障 时，能够迅速地检测故障并定位故障根源，并在可能的情况下在某种程度上修复 故障或给出修复建议，其中故障检测和故障定位是故障管理的两个关键部分。从 方法学上说，故障管理就是通过分析系统外部症状来隔离故障系统元素的过程。 故障诊断被运用在不同的网络层次，从底层网络到高层业务；也被用于不同的目 的或粒度，从简单的连接性到复杂的s l a 5 】。管理系统获取症状的传统方式主 要是告警采集，被动地等待被管实体发出告警信息，告警信息包含了告警来源、 时间、故障征兆和程度。探测是管理系统对网络系统发起的一次端到端的测试， 该测试揭示了探测所依赖的实体子集的一些信息。由从探测收集症状的途径以及 探测提供信息的方式与告警都是不一样的，因此使用探测技术进行故障诊断的方 式也不完全同于使用告警进行故障诊断的方式。 在告警方式下，故障诊断主要采用“告警关联分析”的方式，通过将海量的 告警经过过滤、压缩和关联，找出真正的根源告警，从而推断出故障点。这种方 式是由告警自身的特点所决定的，因为感知到该故障的实体都会发出告警，实体 自身也可能发出告警，通过对这些告警的处理得出那些告警是故障实体的告警， 从而揭示故障实体的位置。而探测不是由被管实体发出的，它是由管理系统控制 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 的对实体子集的一个测试，探测的结果揭示的不是某个实体感知的症状，而是它 所依赖的一组实体的状态，当然通过一个探测不可能获取这一组实体的准确状 态，必然要通过对一系列探测的综合分析来推断故障实体。 基于主动探测的方式就是通过对网络发送探测来检查网络的状态，这些探测 可以针对全网、网络局部甚至某个节点，因此更加的高效。为了获取网络状态， 我们必须选取一些探测来执行，将所有探测周期性地执行是缺乏效率的，因此如 何选择探测集是一个关键的问题。一般地说，我们有两种方式来执行探测，一是 预先静态地选择一组探测，然后周期性地执行；二是依据故障诊断的上下文，动 态地选择需要执行的探测 3 】。前者对网络施加固定的负荷，如果对所有探测如 此执行是极其低效的；后者可以有效地减少所需执行探测的数量，得到更好的时 效性和更低的额外网络流量。我们通过结合这两种方式来提高故障诊断的效率和 准确性。 一般性的故障诊断系统结构由图所示：诊断系统从功能上可划分为三个部 分，“探测信息模型”如2 2 1 所述，是整个目标系统的抽象模型，描述了所有探 测和系统元素之间的依赖关系：执行探测模块用来执行所选择的探测；故障分析 推理模块依据依赖信息模型和探测执行的结果来进行分析。 图2 1 故障探测诊断系统结构图 使用主动探测的故障诊断分为两个步骤，第一步是故障检测( f a u l t d e t e c t i o n ) ，第二步是故障定位( f a u l tl o c a l i z a t i o n ) 。故障检测是通过一系列的探 测来发现系统故障的存在与否，如果存在则触发故障定位步骤；故障定位通过进 一步的探测和分析推理来找到故障的根源失败的链路、主机。 ( 1 ) 故障检测 故障检测通过一些探测来检测系统是否存在故障。为了达到检测所有系统元 素的目的，要求这些探测覆盖所有的系统元素，同时为了提高效率，选取的探测 必须尽量的少。这一步骤对探测的选择一般采取的是静态选择的方式，根据系统 依赖信息模型选取一组固定、数量尽量少的、覆盖所有被管实体的探测来周期性 地检测网络。如何选取一组尽量少的探测来覆盖整个系统是一个“二分覆盖 问 9 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 题，从计算的复杂度来说也是n p 完全问题，在下文会探讨一些线性复杂度的近 似算法。 ( 2 ) 故障定位 如果“故障检测 步骤发现系统存在故障，那么故障定位步骤将启动。此时 我们已经得到一组探测的结果，将对这组探测结果进行分析。但这些探测结果只 是指明系统存在故障，并一定足以定位出故障根源，因此我们可能需要进一步发 送一些探测来测试系统。为了提高诊断的效率和准确性，此时探测的选择需要针 对当前已经获得的信息来选择探测，尽量以较少的探测来获得较为准确的诊断结 果。此种选择探测的方式就是上文所述的动态选择方式，一般来说就是要选择当 前最具信息量的探测来执行。如何判断探测的信息量与采取的故障推理算法相 关，关于动态选择相关的“信息量和算法问题，会在以下一章详细讨论。 2 3 基于主动探测的故障诊断研究现状 现有大量的网络测量工具使用主动探测来对监控网络的连接性，延迟和丢保 率 8 】；主动探测也被用于检测网络瓶颈和可用带宽。更细致的，比如路由协议 层次，延迟、丢失率统计也可通过主动探测来获得。当前i n t e m e t 领域对主动探 测的使用主要集中在拓扑，网络流量，性能和路由几个方面。 探测可用来确定应用数据流量的组成，数据包的大小分布，数据包的到达间 隔，数据包的时延，数据包的路径长度等。比较基本的方式是利用探测来计算端 到端的流量指标。探测同样可以用来跟踪和生成网络拓扑结构：像s k i t t e r 这样的 工具使用t r a c e r o u t e 探测来确定拓扑细节，骨干网络和流量交换节点。主动探测 还可以用来检测路由配置的改变对网络的影响，拓扑结构的改变对网络性能的影 响，和新的设备加入或移除对网络的影响。探测可以发现潜在的可以改善网络拥 塞，增加网络可靠性的区域。 主动探测为网络提供有效的故障诊断方法，在网络的不同层次提供监控和故 障定位的方案。目前对主动探测在故障管理中的尚处于研究实验阶段，没有特别 成熟和完善的诊断方法。在参考文献【6 中，描述了一种应用于口骨干网络的故 障诊断方式；参考文献 2 】研究了在网络中选择探测站的问题，并给出了选择算 法和评判标准；参考文献 1 】利用基于信息理论的方法来评判一个探测包含的信 息量以达到动态选择最有效探测目的，同时采用了基于贝页斯的推理算法；参考 文献 7 研究了有利于使用探测进行故障推理的模型：依赖矩阵，并探讨了其扩 展形式。 综合这些研究，目前故障管理中对主动探测的研究和使用主要集中在以下几 个方面：如何合理地选择探测站的位置来更好地获取整个网络系统各个元素的信 1 0 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 息；如何选择更少的探测更高效地检测故障；如何使用合适的故障定位流程和算 法来动态地选择更具信息量的探测来定位故障；如何在系统模型存在不准确性和 动态性的条件下进行故障定位和探测选择。存在的问题主要有：( 1 ) 基于信息论 的探测选择方法复杂度太高，而且考虑到模型的不确定性，在实际中的效果并不 理想；( 2 ) 对业务系统采用按软件模块划分的方式建立依赖模型的方式并不方便 于故障推理。 2 4 基于探测的故障管理的研究内容 主动探测作为一种监控手段，与传统的基于告警的被动的监控手段相比，具 备很大的灵活性、高效性和良好的可扩展性。主动探测的思想可用于许多领域， 包括硬件网络、电子机械设备、业务系统。当前在该领域已有相当的研究工作， 发展了主动探测的基本思路，探索了其中的一些问题。在故障诊断中使用探测涉 及许多新的问题，这些问题不仅影响到探测的选择，诊断采用的算法，和诊断的 流程，也影响到最终诊断的效率和准确性。下面就其中的主要因素进行一些讨论 分析。 2 4 1 探测站问题 探测站指探测发起的起始点或说探测进入系统的入口点 2 】，比如在一个口 网络中，需要选定一些主机来生成并发送探测到网络中。如果只能从一个固定节 点发起探测，那么有些节点将会成为阴影节点而无法到达。比如下图2 2 所示的 拓扑结构： o 图2 - 2 网络拓扑示意图 假设只有节点a 作为探测站，那么在节点d 出现故障时，节点e 的状态是 不可知的，因为探测不可能到达节点e 。如果d 节点或e 节点也作为探测站时， 这种情况就不会出现，但是我们不可能将所有的节点都作为探测站，假设我们要 将探测站的个数限制为k ，那么如何分布可以得出最好的探测效果。探测站的选 择与最大故障节点数的假设有关，评判探测站选择的好坏在于在存在故障节点条 件下，不可达节点的数目是多少。例如上例中，在只有一个故障节点的情况下， 不可达节点的数目是1 。参考文献 2 详细讨论了探测站选择的算法和分析。 北京邮电大学硕士研究生毕业论文 主动自适应故障探测技术的研究与实现 一般来说探测站的数目越多，我们能够执行的探测越多，那我们能够获取的 症状就越多，故障诊断的准确性也就可能越准确。但我们使用探测的目的之一就 是要减少额外的网络流量，有些探测可能和重复、冗余的告警一样，是没有信息 量的，所以探测数目过多和过少都是灾难。实际的探测站选择需受到许多实际情 况的限制，比如在一个骨干网络中，我们往往只能选择边缘的节点作为探测站。 同时由于我们一般需要在物理上一个统一的工作站进行故障诊断，因此工作站对 探测站的连接控制能力会限制我们的选择。在某些的情况下，并没有太多选择的 余地。同时，在其他非硬件网络环境下，比如业务系统环境下，探测站就没有任 何意义了。因此，本文并没有对该问题进行详细讨论。 2 4 2 最大并发故障数 网络最大并发故障数的预测或限制，对故障诊断的整个流程和算法都有较大 的影响 5 】。在单个故障的条件下，上一段素数探测站的选择问题将变得异常简 单，只要选几个与其他所有节点之间都存在可达路径的节点即可，如果存在某个 节点与所有节点都存在路径，那么可以选择该节点作为唯一的探测站。单故障的 条件也能大大简化故障的诊断，针对一个执行失败的探测，可以推测它所依赖的 节点中有且仅有一个故障点，那么采用一种类似折半查找的探测策略就可以进行 进一步的诊断 3 】。以下图表示的探测路径为例： 图2 3 探测路径示意图 假设探测1 ( 从节点a 到节点e ) 执行失败，那么我们可以判断在节点a 和 e 之间某个节点是故障节点；于是可以选取探测1 路径的中间节点c 作为目标， 执行探测2 从节点a 到节点c ：如果探测成功，我们可以推测故障在节点d 和 e 之间，执行探测3 一从节点a 到节点d ，如果探测3 成功，则可以判断故障节 点是e ，否则判断故障节节点是d ；反之，如果探测2 失败，那么我们选取探测 2 路径的中点b 作为目标，执行探测4 从节点a 到节点b ，如果探测4 成功则 判断故障节点为c 否则为b 。整个过程不超过3 个探测，算法简单，效率高。 在多个故障并发的条件下，故障诊断会复杂的多：在上例中，我们不可能凭 探测2 的失败判定故障之在a b c 之间，我们仍然需要进一步获取d e 的状态。 从信息论的角度来说，如果把系统的故障节点的组合作为一种故障状态，那么在 单故障的条件下，包含n 个实体的故障只有n 个状态；在最多包含k 个故障的 条件下，系统有台乙“种状态：如果对故障数不作任何限制，那么系统的状态数 1 2 北京邮电大学硕士研究生毕业论文主动自适应故障探测技术的研究与实现 是2 4 。对系统进行故障诊断某种程度上说是要找出当前系统所处的状态，状态 数的激增导致诊断的难度大大增加，从前面两个公式可以看出，这种复杂度与k 是呈指数相关的。 本文讨论的故障诊断方式是针对多故障的。现实中，我们很难有充分的理由 来把系统的最大并发故障数限制为1 ，但故障总是很少发生的，实际的并发故障 数总是趋向于0 或1 ；因此对单故障诊断的研究不但可作为研究的起点，也具有 实际的应用意义。 2 4 3 探测依赖模型的特性 探测依赖模型描述了探测和系统组成元素之间的关系，在基于主动探测的故 障诊断方式中处于核心地位。依赖模型的特性影响到了故障诊断的方方面面，包 括探测的选择，分析推理的算法等。 探测依赖模型可能是确定的( d e t e r m i n i s t i c ) 或基于概率的( p r o b a b i l i s t i c ) 。“确 定的是指每个探测的路径都是事先可以确定好的，不会发生动态的改变，或者 说探测对系统组件的依赖是静态的，不会随系统运行状态的变化而依赖于其他的 组件。这种信息模型使故障诊断的流程和算法更加简单和准确，因为成功的探测 能够确定某些节点的状态是正常的，失败的探测能够确定路径上某个节点存在故 障。然而路由策略的动态性、冗余功能模块的存在等因素会使得探测的路径存在 不确定性，在这种情况下，往往使用一种基于概率的探测依赖模型：探测以一定 的概率经过某些系统节点。此时对故障节点的分析推理将会困难很多，有许多基 于贝叶斯公式的推理方式被提出，比如参考文献 1 】 5 】都提出基于贝叶斯的推理 方式，而参考文献 6 】提出基于确定式推理方式的启发式推理算法。本文提出了 对后者的改进方法并通过试验加以验证。 探测依赖系统可能存在完整性和准确性的问题，可能由于模型过于精简，许 多网络组件没有被包含在模型种，这样发生在这些位置网络构件上的故障很可能 被认为是发生在其它已知的组件上。某些新的组件被加入或旧的组件被移除叶也 会导致原有依赖模型不准确，解决该问题需要某种迅速更新依赖模型的手段，通 过探测自身来跟踪系统发生的变化是一个研究方向，在拓扑发现、网络测量领域， 探测已经有很普遍的应用。 2 4 4 探测选择的算法 如2 1 2 所述，基于主动探测的故障管理的两个部分是故障检测和故障定位， 两步都需要发送一些探测来获取网络系统的状态。故障检测的目标是检测系统有 无故障存在，也即组成系统的组件集中有无故障组件的存在。因此当通过探测来 北京邮电大学硕士研究生毕业论文 主动自适应故障探测技术的研究与实现 进行故障检测时，首先要保证所有的组件都被探测到，其次为了提供尽量快得检 测速度，选择的探测数必须尽量的少。我们的目标是要选择一组尽量少的探测来 覆盖整个系统或网络，2 2 2 表明这阶段的探测选择问题是一个二分覆盖问题， 即n p 完全问题。参考文献【7 】描述了两种启发式近似算法贪婪增加算法和贪心减 法算法，两者都是基于贪婪思想的算法，前者将探测选择集初始化为空，不断地 选择能够覆盖最多尚未被覆盖节点的探测，直到所有的网络节点都已经被覆盖； 后者将探测选择集初始化为所有探测的全集，然后不断地尝试排除某个探测，如 果某个探测的排除并会导致某些节点不被覆盖，直至探测选择集中没有这样的探 测。本文在第三章提供了一个改进的算法。 故障定位部分的诊断算法直接影响到了探测的选择，依据故障检测阶段的探 测结果，我们已经能够对系统的状态做出初步的推测，进一步探测就是针对不确 定的部分，因此推理算法的整个流程和探测选择是交织在一起的。第三章会介绍 基于信息熵的探测选择法，并提供一种简单的启发式算法。 1 4 北京邮电大学硕士研究生毕业论文主