第14卷第1期 智能系统学报 Vol.14 No.I 2019年1月 CAAI Transactions on Intelligent Systems Jan.2019 D0:10.11992/tis.201804062 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20181026.1639.002.html 多层信息网络故障定位综述 齐小刚，牛红曼，刘兴成，王晓琳'，刘立芳2 (1.西安电子科技大学数学与统计学院，陕西西安710126；2.西安电子科技大学计算机学院，陕西西安 710071) 摘要：本文对多层网络（覆盖网、虚拟网等）故障定位问题进行了分析和总结。讨论了多层网络探测故障信息 获取策略和故障定位模型的发展状况，即介绍了被动监测、主动探测、主被动结合探测和终端用户观察等探测 信息获取策略，以及基于图论故障传播模型、依赖矩阵模型、症状-故障-行动模型等故障传播模型的原理以及 其优缺点。从故障定位模型、探测信息获取策略、故障定位计算、网络异构性、运行效率与成本多个方面重点 综述了多层网络故障定位方法，讨论了每种方法的优点和局限性。最后，对多层网络故障定位研究的不足和亟 待进一步研究解决的问题进行了探讨。 关键词：多层网络：故障管理；故障诊断；故障定位：故障传播模型；节点故障；链路故障：虚拟网络；覆盖网 中图分类号：TP393文献标志码：A文章编号：1673-4785(2019)01-0044-13 中文引用格式：齐小刚，牛红曼，刘兴成，等.多层信息网络故障定位综述.智能系统学报，2019,14(1)：44-56. 英文引用格式：QI Xiaogang,NIU Hongman,LIU Xingcheng,.ctal.Survey of fault localization in multilayer information networksJ CAAI transactions on intelligent systems,2019,14(1):44-56. Survey of fault localization in multilayer information networks QI Xiaogang',NIU Hongman',LIU Xingcheng',WANG Xiaolin',LIU Lifang (1.School of Mathematics and Statistics,Xidian University,Xi'an 710126,China;2.School of Computer Science and Technology, Xidian University,Xi'an 710071,China) Abstract:This study analyzes and summarizes the problems of fault localization in multilayer networks(e.g.,overlay network and virtual network).First,the latest developments in fault detection information acquisition technologies and fault localization models for multilayer network are discussed.The detection information acquisition technologies for passive monitoring,active detection,active-passive detection,and end-user observation are introduced,as well as the fault localization models such as dependency matrix model,graph-based propagation model,and symptom-fault-action model.The principles,advantages,and disadvantages of these technologies and models are presented as well.The meth- ods of multilayer network fault localization are summarized,considering fault localization strategy model,fault detec- tion calculation technique,network heterogeneity,operational efficiency,and cost,and then the merits and demerits of each method are highlighted.Finally,some pressing issues that need further study are discussed. Keywords:multilayer network;fault management;fault diagnosis;fault localization;fault propagation model;node fault:link fault:virtual network;overlay network 近年来，通信网络的规模和复杂性呈现急剧严重挑战，其核心问题是故障管理。故障在大规 增长势头，这给网络管理系统NMS)运行带来了 模通信网络中是不可避免的，因此实时地检测和 收稿日期：2018-04-28.网络出版日期：2018-10-29 定位故障对于网络的可靠运行至关重要，而故 基金项目：国家自然科学基金项目(61572435,61472305,6147 3222):宁波市自然科学基金项目(2016A610035,2017 障管理系统的功能就是检测、定位网络中的故 A6101I9):复杂电子系统仿真重点实验室基础研究 基金项目(DXZT-JC-ZZ-2015-015). 障以及启动故障恢复机制来防止网络性能的退 通信作者：牛红曼.E-mail:1450772363@qq.com. 化2
DOI: 10.11992/tis.201804062 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20181026.1639.002.html 多层信息网络故障定位综述 齐小刚1 ，牛红曼1 ，刘兴成1 ，王晓琳1 ，刘立芳2 （1. 西安电子科技大学 数学与统计学院，陕西 西安 710126; 2. 西安电子科技大学 计算机学院，陕西 西安 710071） 摘 要：本文对多层网络 (覆盖网、虚拟网等) 故障定位问题进行了分析和总结。讨论了多层网络探测故障信息 获取策略和故障定位模型的发展状况，即介绍了被动监测、主动探测、主被动结合探测和终端用户观察等探测 信息获取策略，以及基于图论故障传播模型、依赖矩阵模型、症状-故障-行动模型等故障传播模型的原理以及 其优缺点。从故障定位模型、探测信息获取策略、故障定位计算、网络异构性、运行效率与成本多个方面重点 综述了多层网络故障定位方法，讨论了每种方法的优点和局限性。最后，对多层网络故障定位研究的不足和亟 待进一步研究解决的问题进行了探讨。 关键词：多层网络；故障管理；故障诊断；故障定位；故障传播模型；节点故障；链路故障；虚拟网络；覆盖网 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2019)01−0044−13 中文引用格式：齐小刚, 牛红曼, 刘兴成, 等. 多层信息网络故障定位综述[J]. 智能系统学报, 2019, 14(1): 44–56. 英文引用格式：QI Xiaogang, NIU Hongman, LIU Xingcheng, et al. Survey of fault localization in multilayer information networks[J]. CAAI transactions on intelligent systems, 2019, 14(1): 44–56. Survey of fault localization in multilayer information networks QI Xiaogang1 ，NIU Hongman1 ，LIU Xingcheng1 ，WANG Xiaolin1 ，LIU Lifang2 (1. School of Mathematics and Statistics, Xidian University, Xi’an 710126, China; 2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China) Abstract: This study analyzes and summarizes the problems of fault localization in multilayer networks (e.g., overlay network and virtual network). First, the latest developments in fault detection information acquisition technologies and fault localization models for multilayer network are discussed. The detection information acquisition technologies for passive monitoring, active detection, active-passive detection, and end-user observation are introduced, as well as the fault localization models such as dependency matrix model, graph-based propagation model, and symptom-fault-action model. The principles, advantages, and disadvantages of these technologies and models are presented as well. The methods of multilayer network fault localization are summarized, considering fault localization strategy model, fault detection calculation technique, network heterogeneity, operational efficiency, and cost, and then the merits and demerits of each method are highlighted. Finally, some pressing issues that need further study are discussed. Keywords: multilayer network; fault management; fault diagnosis; fault localization; fault propagation model; node fault; link fault; virtual network; overlay network 近年来，通信网络的规模和复杂性呈现急剧 增长势头，这给网络管理系统 (NMS) 运行带来了 严重挑战，其核心问题是故障管理。故障在大规 模通信网络中是不可避免的，因此实时地检测和 定位故障对于网络的可靠运行至关重要，而故 障管理系统的功能就是检测、定位网络中的故 障以及启动故障恢复机制来防止网络性能的退 化 [1-2]。 收稿日期：2018−04−28. 网络出版日期：2018−10−29. 基金项目：国家自然科学基金项目 (61572435，61472305，6147 3222)；宁波市自然科学基金项目 (2016A610035，2017 A610119)；复杂电子系统仿真重点实验室基础研究 基金项目 (DXZT-JC-ZZ-2015-015). 通信作者：牛红曼. E-mail：1450772363@qq.com. 第 14 卷第 1 期 智 能 系 统 学 报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019
第1期 齐小刚，等：多层信息网络故障定位综述 ·45· 故障管理过程包括2个部分：故障诊断和故 5)高动态环境下的网络管理 障恢复。故障诊断分为3个步骤：故障探测、故 由SDN和网络功能虚拟化(network function 障定位以及故障测试。故障探测是通过观测网络 virtualization,NFV)部件构成的高动态环境基础 症状来确定网络部件是否发生故障的过程。故障 设施的频繁变化给网络管理系统带来了新的挑 定位是使用一组观测到的症状来推断网络中故障 战。其中一些挑战与以下因素有关：①SDN配置 出现的精确位置。故障测试是通过检查推断出的 更改的规模和频繁程度：②业务和用户需求依 部件来验证该部件是否发生故障的过程。故障诊 赖的NFV部件动态添加和删除：③所跟踪的资 断是故障管理的重要组成部分。故障诊断的目标 源波动情况：④所监控资源利用率等。另一个挑 是及时精确地定位网络故障，故障恢复是故障部 战性的问题是，跟踪所有频繁变化的网络服务， 件被识别后恢复正常的过程。在故障诊断的3个 并在此基础上进行管理决策。 步骤中，由于故障定位的复杂性，故障定位是最 6)网络环境的复杂性 具挑战性的。 随着新的网络环境部署，在很长一段时间内， 有别于传统观念中需要大量人工干预，逐一 已有的或遗存的网络环境仍然会与新技术共存。 排除故障的方法，目前较多文献研究的目的是以 在过渡时期内，网络管理方案应该能够管理网络 极少的人工干预以及网络负载实现快速精确的故 的复杂性。此外，基于网络的服务通常会穿越已 障定位，主要定位节点故障和链路故障。当前该 有的与新的网络中物理的和虚拟的网络部件。因 领域面临的挑战如下： 此，信息网络的共存需要从端到端的角度实现网 1)精确的网络模型 管系统的无缝管理。 网络的类型以及所建立的网络模型决定了模 本文对多层信息网络故障定位过程中采用的 型中使用的信息可能是静态或动态的，而动态信 探测信息获取策略，和基于资源映射关系的网络 息的存在使得该问题更具有挑战性，因为当网络 故障定位模型进行了分析和总结，综述了多层网 运行时更多的信息将被纳入模型之中。此外，片 络故障定位方法。主要创新点与贡献如下： 面、不完全、不准确的信息可能会延误诊断过程 1)对多层网络故障探测信息获取策略进行了 或影响诊断的准确性。 分类与总结，讨论了不同探测信息获取策略的优 2)计算复杂性 缺点以及面临的挑战。 概率推理固有的高时空复杂度，使面向大 2)讨论和总结了现有的基于资源映射关系的 型、复杂通信网络的故障定位计算变得更为棘 网络故障定位模型，并对其优缺点进行分析。 手，而且这些计算需要反复执行，以便持续监测 3)从故障定位模型、探测信息获取方式、故 网络。 障定位计算、网络异构性、运行效率与成本多个 3)故障定位技术 方面综述了多层网络故障定位方法。 分布式的技术有助于减少故障检测的时间和 4)讨论了多层网络故障定位研究的不足和面 解决集中式管理节点的瓶颈，然而这会增加网络 临的挑战，并对未来更进一步的研究指出可能的 的控制开销。此外，改变网络管理系统的监控目 方向。 标可能需要在节点上完成一定数量的手工配置， 1多层网络故障的定义 而这种配置过程进一步使得分布式的定位方案变 得更为复杂。 1.1故障的定义 4)新型网络中的故障定位 故障是指网络发生问题的根源所对应的网络 软件定义网络(software defined network,SDN) 事件。网络中一个设备的故障有可能导致其他设 是一种新型的网络体系结构，通过将网络控制与 备的故障。故障可能发生在硬件设备（如路由 网络转发解耦合构建开放可编程的网络体系结 器、链路等)或者软件（如路由表、网络服务等） 构。SDN控制器配置问题可以映射为在传统的 上。在网络中症状是故障的外在表现形式。症状 网络中放置一个集中式网络管理系统NMS的问 可以以不同的方式被观测到，如网络告警、人为 题。虽然集中控制可以帮助提供更好的诊断和 观测，或者使用主动监测机制。在网络设备上可 监测能力，然而SDN环境也给网络管理系统带来 以放置监测代理，当网络设备观测到任何异常 了一些新的故障类型。 时，网络设备上的监测代理会以告警的方式向网
故障管理过程包括 2 个部分：故障诊断和故 障恢复。故障诊断分为 3 个步骤：故障探测、故 障定位以及故障测试。故障探测是通过观测网络 症状来确定网络部件是否发生故障的过程。故障 定位是使用一组观测到的症状来推断网络中故障 出现的精确位置。故障测试是通过检查推断出的 部件来验证该部件是否发生故障的过程。故障诊 断是故障管理的重要组成部分。故障诊断的目标 是及时精确地定位网络故障，故障恢复是故障部 件被识别后恢复正常的过程。在故障诊断的 3 个 步骤中，由于故障定位的复杂性，故障定位是最 具挑战性的。 有别于传统观念中需要大量人工干预，逐一 排除故障的方法，目前较多文献研究的目的是以 极少的人工干预以及网络负载实现快速精确的故 障定位，主要定位节点故障和链路故障。当前该 领域面临的挑战如下： 1) 精确的网络模型 网络的类型以及所建立的网络模型决定了模 型中使用的信息可能是静态或动态的，而动态信 息的存在使得该问题更具有挑战性，因为当网络 运行时更多的信息将被纳入模型之中。此外，片 面、不完全、不准确的信息可能会延误诊断过程 或影响诊断的准确性。 2) 计算复杂性 概率推理固有的高时空复杂度，使面向大 型、复杂通信网络的故障定位计算变得更为棘 手，而且这些计算需要反复执行，以便持续监测 网络。 3) 故障定位技术 分布式的技术有助于减少故障检测的时间和 解决集中式管理节点的瓶颈，然而这会增加网络 的控制开销。此外，改变网络管理系统的监控目 标可能需要在节点上完成一定数量的手工配置， 而这种配置过程进一步使得分布式的定位方案变 得更为复杂。 4) 新型网络中的故障定位 软件定义网络 (software defined network，SDN) 是一种新型的网络体系结构，通过将网络控制与 网络转发解耦合构建开放可编程的网络体系结 构。SDN 控制器配置问题可以映射为在传统的 网络中放置一个集中式网络管理系统 NMS 的问 题 [3]。虽然集中控制可以帮助提供更好的诊断和 监测能力，然而 SDN 环境也给网络管理系统带来 了一些新的故障类型。 5) 高动态环境下的网络管理 由 SDN 和网络功能虚拟化 (network function virtualization，NFV) 部件构成的高动态环境基础 设施的频繁变化给网络管理系统带来了新的挑 战。其中一些挑战与以下因素有关：①SDN 配置 更改的规模和频繁程度[4] ；②业务和用户需求依 赖的 NFV 部件动态添加和删除[5] ；③所跟踪的资 源波动情况；④所监控资源利用率等。另一个挑 战性的问题是，跟踪所有频繁变化的网络服务， 并在此基础上进行管理决策。 6) 网络环境的复杂性 随着新的网络环境部署，在很长一段时间内， 已有的或遗存的网络环境仍然会与新技术共存。 在过渡时期内，网络管理方案应该能够管理网络 的复杂性。此外，基于网络的服务通常会穿越已 有的与新的网络中物理的和虚拟的网络部件。因 此，信息网络的共存需要从端到端的角度实现网 管系统的无缝管理。 本文对多层信息网络故障定位过程中采用的 探测信息获取策略，和基于资源映射关系的网络 故障定位模型进行了分析和总结，综述了多层网 络故障定位方法。主要创新点与贡献如下： 1) 对多层网络故障探测信息获取策略进行了 分类与总结，讨论了不同探测信息获取策略的优 缺点以及面临的挑战。 2) 讨论和总结了现有的基于资源映射关系的 网络故障定位模型，并对其优缺点进行分析。 3) 从故障定位模型、探测信息获取方式、故 障定位计算、网络异构性、运行效率与成本多个 方面综述了多层网络故障定位方法。 4) 讨论了多层网络故障定位研究的不足和面 临的挑战，并对未来更进一步的研究指出可能的 方向。 1 多层网络故障的定义 1.1 故障的定义 故障是指网络发生问题的根源所对应的网络 事件。网络中一个设备的故障有可能导致其他设 备的故障。故障可能发生在硬件设备 (如路由 器、链路等) 或者软件 (如路由表、网络服务等) 上。在网络中症状是故障的外在表现形式。症状 可以以不同的方式被观测到，如网络告警、人为 观测，或者使用主动监测机制。在网络设备上可 以放置监测代理，当网络设备观测到任何异常 时，网络设备上的监测代理会以告警的方式向网 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·45·
·46· 智能系统学报 第14卷 络产生通告。告警表示网络部件观测到该部件不 障节点和虚拟层故障链路。 能正常运行，如丢包、连接失败或者链路故障。 本文称在虚拟层网络中由虚拟层节点和虚拟 这些告警被看作网络可能发生故障的症状。使用 层链路连接而成的端到端的虚拟层最短路径为多 这些告警诊断网络中的故障涉及的挑战是实际的 层网络服务。 故障可能出现在网络的任何位置。 多层网络中的症状可能由故障的节点、链路 用图1来解释1个故障情形。客户尝试使用 或服务异常产生。服务的状态反映了它所通过的 安全外壳协议(S$H)来连接到远程服务器（服务 虚拟层部件的状态。多层网络中节点或链路故障 器2)。在端路由器上有多个人口到服务器2上， 产生的告警和观察到的端到端服务异常状态称为 在它的转发表上有不同的转发端口，在转发表上 负面症状，观察到的端到端服务正常状态称为正 总是选择第一个人口。如图1所示，关于目的地 面症状。 服务器2的S$H请求被错误地转发到服务器 在多层网络中虚拟层部件和底层部件存在映 1上，服务器1把相应的SSH请求丢弃，并产生告 射关系，包括节点映射和链路映射。节点映射表 警。客户没有接收到SSH请求的应答，最终超 示一个虚拟层节点映射到底层网络中的一个底层 时，产生告警（即连接失败）报告给网络管理员。 节点上。图2是多层网络中虚拟层网络映射到底 这个例子表明故障部件可以引起远程位置的服务 层网络的一个例子，图中overlay网络中的虚拟节 点A映射到底层节点N,上。链路映射表示一条虚 中断。本文把网络中的客户机、服务器和路由器 拟层链路映射到底层网络中的一条路径上，即一 等网络设备抽象为节点，把连接相邻节点的路径 条虚拟层链路可能跨越多个底层链路。如图2所 设备抽象为链路，并把节点和链路统称为网络部 示多层网络中的虚拟层链路(D,C)映射到底层路 件。本文研究的故障类型为节点故障和链路故 径N4→N,→N上o 障，并称由故障的节点或链路产生的告警为症状。 虚拟层网络 症状/告警： 故障：连接远程服 故障：SSH与服 务器2的接口存在 务器2的连接无 由于目的地错 错误，导致数据包 法建立，即连接 误导致数据包 被转发到错误的目 失败 丢弃 的地服务器1上 症状告警：不 能收到服务器2 的应答 服务器1 四 底层网络 目的地： 路由器 服务器2 客户机 服务器2 N,@ ©No 图1故障及症状警告举例 图2多层网络中虚拟层网络映射到底层网络的例子 Fig.1 Examples of failures and symptoms/alarms Fig.2 Mapping between virtual layer network and sub- 1.2多层网络故障的定义 strate network in multilayer networks 本文把覆盖网(Overlay网络)、虚拟网等通过 在多层网铬中，互联网服务提供者(SP)被分 底层网络资源的抽象和隔离而虚拟出来的网络称 为两类：基础设施提供者(InP)和服务提供者 为虚拟层网络。把底层网络和由它虚拟出来的虚 (SP)。服务提供者为用户提供定制的端到端服 拟层网络称为多层网络。 务。InP把底层网络资源租给SP,通过这种方式 本文把多层网络表示为无向图G=(VE),其 提高了底层网络资源的利用率，但是由于多层网 中：V是节点集，包括底层节点Vs剑和虚拟层节点 络赋予底层网络新的功能，多层网络故障增加了 Vx;E是链路集，包括底层链路EsN和虚拟层链路 传统网络的故障形式，给故障诊断带来挑战，具 Ev。称虚拟层节点和虚拟层链路为虚拟部件，底 体分析如下。 层节点和底层链路为底层部件。 1)底层网络信息不可获得性和信息的不完全 多层网络故障包括底层部件故障和虚拟层部 性与不准确性。底层网络通常不愿与虚拟层网络 件故障。其中，底层故障部件包括底层故障节点 共享详细的网络信息，例如：底层网络的症状，虚 和底层故障链路。虚拟层故障部件包括虚拟层故 拟层网络和底层网络的映射关系，底层网络的先
络产生通告。告警表示网络部件观测到该部件不 能正常运行，如丢包、连接失败或者链路故障。 这些告警被看作网络可能发生故障的症状。使用 这些告警诊断网络中的故障涉及的挑战是实际的 故障可能出现在网络的任何位置。 用图 1 来解释 1 个故障情形。客户尝试使用 安全外壳协议 (SSH) 来连接到远程服务器 (服务 器 2)。在端路由器上有多个入口到服务器 2 上， 在它的转发表上有不同的转发端口，在转发表上 总是选择第一个入口。如图 1 所示，关于目的地 服务器 2 的 SSH 请求被错误地转发到服务器 1 上，服务器 1 把相应的 SSH 请求丢弃，并产生告 警。客户没有接收到 SSH 请求的应答，最终超 时，产生告警 (即连接失败) 报告给网络管理员。 这个例子表明故障部件可以引起远程位置的服务 中断。本文把网络中的客户机、服务器和路由器 等网络设备抽象为节点，把连接相邻节点的路径 设备抽象为链路，并把节点和链路统称为网络部 件。本文研究的故障类型为节点故障和链路故 障，并称由故障的节点或链路产生的告警为症状。 服务器 2 服务器 1 路由器 目的地： 服务器2 客户机 Internet 症状/告警： 由于目的地错 误导致数据包 丢弃 故障：连接远程服 务器2的接口存在 错误，导致数据包 被转发到错误的目 的地服务器1上 故障: SSH与服 务器2的连接无 法建立, 即连接 失败 症状/告警：不 能收到服务器2 的应答 图 1 故障及症状/警告举例 Fig. 1 Examples of failures and symptoms/alarms 1.2 多层网络故障的定义 本文把覆盖网 (Overlay 网络)、虚拟网等通过 底层网络资源的抽象和隔离而虚拟出来的网络称 为虚拟层网络。把底层网络和由它虚拟出来的虚 拟层网络称为多层网络。 G = (V,E) V VSN VVN E ESN EVN 本文把多层网络表示为无向图 ，其 中： 是节点集，包括底层节点 和虚拟层节点 ； 是链路集，包括底层链路 和虚拟层链路 。称虚拟层节点和虚拟层链路为虚拟部件，底 层节点和底层链路为底层部件。 多层网络故障包括底层部件故障和虚拟层部 件故障。其中，底层故障部件包括底层故障节点 和底层故障链路。虚拟层故障部件包括虚拟层故 障节点和虚拟层故障链路。 本文称在虚拟层网络中由虚拟层节点和虚拟 层链路连接而成的端到端的虚拟层最短路径为多 层网络服务。 多层网络中的症状可能由故障的节点、链路 或服务异常产生。服务的状态反映了它所通过的 虚拟层部件的状态。多层网络中节点或链路故障 产生的告警和观察到的端到端服务异常状态称为 负面症状，观察到的端到端服务正常状态称为正 面症状。 N1 (D,C) 在多层网络中虚拟层部件和底层部件存在映 射关系，包括节点映射和链路映射。节点映射表 示一个虚拟层节点映射到底层网络中的一个底层 节点上。图 2 是多层网络中虚拟层网络映射到底 层网络的一个例子，图中 overlay 网络中的虚拟节 点 A 映射到底层节点 上。链路映射表示一条虚 拟层链路映射到底层网络中的一条路径上，即一 条虚拟层链路可能跨越多个底层链路。如图 2 所 示多层网络中的虚拟层链路 映射到底层路 径 N4→ N9 → N3 上。 D A B C 虚拟层网络 E 底层网络 N4 N1 N9 N8 N3 N7 N5 N10 N2 N6 图 2 多层网络中虚拟层网络映射到底层网络的例子 Fig. 2 Mapping between virtual layer network and substrate network in multilayer networks 在多层网络中，互联网服务提供者 (ISP) 被分 为两类：基础设施提供者 (InP) 和服务提供者 (SP)。服务提供者为用户提供定制的端到端服 务。InP 把底层网络资源租给 SP，通过这种方式 提高了底层网络资源的利用率，但是由于多层网 络赋予底层网络新的功能，多层网络故障增加了 传统网络的故障形式，给故障诊断带来挑战，具 体分析如下。 1) 底层网络信息不可获得性和信息的不完全 性与不准确性。底层网络通常不愿与虚拟层网络 共享详细的网络信息，例如：底层网络的症状，虚 拟层网络和底层网络的映射关系，底层网络的先 ·46· 智 能 系 统 学 报 第 14 卷
第1期 齐小刚，等：多层信息网络故障定位综述 ·47· 验概率等，这对于故障诊断是十分关键的。此 包的发送端和接收端。如果在探测路径发送端发 外，完全地监控所有底层网络和虚拟层网络是不 送的探测包可以被接收端接收，则表明该探测路 可行的，故障诊断必须依赖于不准确和不完全的 径是连通的，测试结果表示为“1”，即该探测路径 信息，这就导致了故障诊断的不确定性。 通过的节点都是正常的；反之，该探测路径是不 2)动态症状-故障因果关系。虚拟节点和链 连通的，测试结果表示为“0”，即该探测路径上至 路与底层节点映射的灵活性和动态性使得虚拟层 少存在一个故障节点。与被动监测相比，主动探 网络和底层网络的因果关系变得不可预测。在多 测中探测包的使用有助于NMS对于大量的网络 层网络中作为故障诊断基础的症状-故障因果关 故障事件反应更快、更精确，这与传统的被动接 系是动态和不可预测的。 收告警的方法有着极大不同。由于探测站配置和 3)多层故障。多层网络服务性能的下降可能 探测路径选择的过程可以控制，所以主动探测是 由于虚拟层或底层网络的部件故障引起的。由于 灵活的。 底层网络部件和虚拟层网络部件存在映射关系， 主动探测包括2种：预计划探测策略和适应 底层网络部件故障会导致对应的虚拟层网络部件 性探测策略。预计划探测策略首次由Brodie等例 故障。虚拟层网络部件和底层网络部件的映射关 提出，Brodie等解决的是单节点故障定位问题，通 系使得多层网络故障定位变得更加复杂。因此， 过使用依赖矩阵来解释探测选择问题，依赖矩阵 本文把虚拟层故障分为独立虚拟层故障和相关虚 D是r×矩阵，其中，r是网络中探测路径的数量， 拟层故障。在虚拟层网络中由于软件错误引起的 n是网络中节点的数量。如果探测P经过节点W;, 故障称为独立虚拟层故障。相关虚拟层故障是由 矩阵元素D(i,》=1,否则D(i,》=0。预计划探测 底层部件的故障而引起的虚拟层故障，如果底层 策略需要解决的问题是：如何在给定的网络拓扑 故障部件恢复正常了，相关虚拟层故障也就不存 中构建合适的探测路径，使得网络中的每条节点 在了。 发生故障时能够返回不同的测试结果。考虑花费 问题，尽量少地部署探测站和构造探测路径也 2多层网络探测信息获取策略 此类问题的考虑方向。然而，Brodie等使用的预 计划探测策略存在一些限制：只假设单个节点发 2.1被动监测策略 生故障，未考虑测试结果丢失、虚假测试结果以 被动监测策略通过在网络设备上放置监测代 及动态的探测路径等的影响。随后，Tapoleai等o1 理来监测网络。网络中的任意部件的故障将会由 采用预计划探测策略针对全光网络中的单链路和 监测代理产生告警，接着告警被NMS作为负面 多链路故障提出多种故障定位方法。然而，这些 症状来分析网络中故障部件的精确位置。由于NMS 方法只适用于小型网络。Xuan等山采用预计划 被动地等待监测代理发送告警，所以这种方法是 探测策略提出的算法解决了大型网络中多个链路 被动性的。与传统网络相比，多层网络不仅具有 故障定位问题。由于多层网络具有多层故障，且 底层网络还有抽象的虚拟层网络，因此多层网络 底层部件的故障会导致虚拟层部件的故障，多层 的被动监测可逐层进行，即分别在底层网络和虚 网络的预计划探测策略可逐层进行，即分别在底 拟层网络采用被动监测策略建立模型，以此来定 层网络和虚拟层网络采用预计划探测策略建立模 位出底层网络故障部件和虚拟层网络故障部件。 型。首先，在底层网络中采用预计划探测策略定 噪声的干扰会造成被动监测症状的丢失，或 位出底层故障部件。其次，对底层故障部件进行 虚假症状的存在，因此多层网络的被动监测策略 故障恢复，则相关虚拟故障部件也被恢复。最 面临着如何获得和保持准确信息的挑战，6-，因 后，在虚拟层网络中采用预计划探测策略来定位 为故障定位的准确性直接取决于所建模型中信息 出独立虚拟层故障。适应性探测策略的使用在文 的准确性。 献[9]中定义，由Natu等6进行了深入探究和 22主动探测策略 论述，并在此基础上提出了基于确定性模型以及 主动探测策略与被动监测不同，通过在多个 非确定性模型的适应性探测算法。在这种探测策 网络节点上配置探测站并沿着探测路径发送数据 略中，不是发送探测包来定位所有可能的故障， 包（探测包）来测量探测站节点之间（端到端）的 而是首先发送少量探测包来监测所有的网络部件 连通性以获取探测路径通过的网络部件的二进制 的状态。这些探测包可以监测是否有故障发生， 状态信息⑧。探测路径两端的探测站节点为探测 但不能够定位故障的确切位置。基于探测结果
验概率等，这对于故障诊断是十分关键的。此 外，完全地监控所有底层网络和虚拟层网络是不 可行的，故障诊断必须依赖于不准确和不完全的 信息，这就导致了故障诊断的不确定性。 2) 动态症状–故障因果关系。虚拟节点和链 路与底层节点映射的灵活性和动态性使得虚拟层 网络和底层网络的因果关系变得不可预测。在多 层网络中作为故障诊断基础的症状–故障因果关 系是动态和不可预测的。 3) 多层故障。多层网络服务性能的下降可能 由于虚拟层或底层网络的部件故障引起的。由于 底层网络部件和虚拟层网络部件存在映射关系， 底层网络部件故障会导致对应的虚拟层网络部件 故障。虚拟层网络部件和底层网络部件的映射关 系使得多层网络故障定位变得更加复杂。因此， 本文把虚拟层故障分为独立虚拟层故障和相关虚 拟层故障。在虚拟层网络中由于软件错误引起的 故障称为独立虚拟层故障。相关虚拟层故障是由 底层部件的故障而引起的虚拟层故障，如果底层 故障部件恢复正常了，相关虚拟层故障也就不存 在了。 2 多层网络探测信息获取策略 2.1 被动监测策略 被动监测策略通过在网络设备上放置监测代 理来监测网络。网络中的任意部件的故障将会由 监测代理产生告警，接着告警被 NMS 作为负面 症状来分析网络中故障部件的精确位置。由于 NMS 被动地等待监测代理发送告警，所以这种方法是 被动性的。与传统网络相比，多层网络不仅具有 底层网络还有抽象的虚拟层网络，因此多层网络 的被动监测可逐层进行，即分别在底层网络和虚 拟层网络采用被动监测策略建立模型，以此来定 位出底层网络故障部件和虚拟层网络故障部件。 噪声的干扰会造成被动监测症状的丢失，或 虚假症状的存在，因此多层网络的被动监测策略 面临着如何获得和保持准确信息的挑战 [1, 6-7] ，因 为故障定位的准确性直接取决于所建模型中信息 的准确性。 2.2 主动探测策略 主动探测策略与被动监测不同，通过在多个 网络节点上配置探测站并沿着探测路径发送数据 包 (探测包) 来测量探测站节点之间 (端到端) 的 连通性以获取探测路径通过的网络部件的二进制 状态信息[8]。探测路径两端的探测站节点为探测 包的发送端和接收端。如果在探测路径发送端发 送的探测包可以被接收端接收，则表明该探测路 径是连通的，测试结果表示为“1”，即该探测路径 通过的节点都是正常的；反之，该探测路径是不 连通的，测试结果表示为“0”，即该探测路径上至 少存在一个故障节点。与被动监测相比，主动探 测中探测包的使用有助于 NMS 对于大量的网络 故障事件反应更快、更精确，这与传统的被动接 收告警的方法有着极大不同。由于探测站配置和 探测路径选择的过程可以控制，所以主动探测是 灵活的。 r ×n r n Pi Nj D(i, j) = 1 D(i, j) = 0 主动探测包括 2 种：预计划探测策略和适应 性探测策略。预计划探测策略首次由 Brodie 等 [9] 提出，Brodie 等解决的是单节点故障定位问题，通 过使用依赖矩阵来解释探测选择问题，依赖矩阵 D 是 矩阵，其中， 是网络中探测路径的数量， 是网络中节点的数量。如果探测 经过节点 ， 矩阵元素 ，否则 。预计划探测 策略需要解决的问题是：如何在给定的网络拓扑 中构建合适的探测路径，使得网络中的每条节点 发生故障时能够返回不同的测试结果。考虑花费 问题，尽量少地部署探测站和构造探测路径也是 此类问题的考虑方向。然而，Brodie 等使用的预 计划探测策略存在一些限制：只假设单个节点发 生故障，未考虑测试结果丢失、虚假测试结果以 及动态的探测路径等的影响。随后，Tapolcai 等 [10-13] 采用预计划探测策略针对全光网络中的单链路和 多链路故障提出多种故障定位方法。然而，这些 方法只适用于小型网络。Xuan 等 [11]采用预计划 探测策略提出的算法解决了大型网络中多个链路 故障定位问题。由于多层网络具有多层故障，且 底层部件的故障会导致虚拟层部件的故障，多层 网络的预计划探测策略可逐层进行，即分别在底 层网络和虚拟层网络采用预计划探测策略建立模 型。首先，在底层网络中采用预计划探测策略定 位出底层故障部件。其次，对底层故障部件进行 故障恢复，则相关虚拟故障部件也被恢复。最 后，在虚拟层网络中采用预计划探测策略来定位 出独立虚拟层故障。适应性探测策略的使用在文 献[9]中定义，由 Natu 等 [6, 13-14]进行了深入探究和 论述，并在此基础上提出了基于确定性模型以及 非确定性模型的适应性探测算法。在这种探测策 略中，不是发送探测包来定位所有可能的故障， 而是首先发送少量探测包来监测所有的网络部件 的状态。这些探测包可以监测是否有故障发生， 但不能够定位故障的确切位置。基于探测结果， 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·47·
·48 智能系统学报 第14卷 首先识别出可能的故障区域，其次发送额外的探 试结果是已存的症状集Sv和不存在的症状集 测包来精确定位故障的位置。适应性探测的主要 S。基于行动返回的结果，对应的保真度值可能 目标是通过发送最少数目的探测包来精确地定位 被增加或减少。如果新计算的保真度满足条件， 故障部件的位置。同样地，多层网络的适应性探 那么推理过程终止，否则So、S作为故障推理模 测策略可逐层进行。主动探测策略本质上是通过 块的新输人来生成一个新的假设。这个过程一直 测试端到端路径上的部件状态，与被动监测策略 重复直到找到具有高保真度的假设。 相比对故障响应更快，更灵活性，因此多层网络 多层网络具有多层故障，且底层部件的故障 采用主动探测策略定位故障效率更高。主动探测 会导致虚拟层部件的故障，因此多层网络的主被 策略具有明显的优势，但是在实际的使用过程中， 动结合探测策略可逐层进行，即分别在底层网络 网络需要发送大量的管理所需的流量，由于并不 和虚拟层网络采用主被动结合探测策略来定位出 是所有的故障同时发生，所以大量的流量是浪费 底层网络故障部件和独立虚拟层故障部件。行动 的。此外，发送较多数目的探测会产生延迟，很 选择的使用减少了由于噪声存在引起的症状丢失 难得到最优的探测路径集合以及收集到精确的测 或虚假症状存在的可能性，主被动结合探测策略 试结果。上述缺点将导致故障定位率降低以及故 最小化探测的使用而且提高了多层网络故障定位 障定位时间增加，因此综合考虑探测效率、探测 的准确率。 代价的主动探测策略成为进一步亟待解决的问题。 2.4终端用户观察策略 2.3主被动结合探测策略 大多数多层网络探测信息获取策略要么需要 主被动结合探测策略同时使用被动监测策略 网络监测代理被动搜集到的大量告警信息，要么 和主动探测策略，弥补了单一一种探测策略的不 使用探测来主动监控网络。然而，被动监控需要 足。Tang等s1采用主被动结合探测策略提出了 大量关于底层网络部件后验或先验故障概率信 主动集成故障推理(AIR)框架。如图3所示，主 息，这在实际实践中限制了其有效性。采用主动 动集成故障推理过程包括3个功能模块：故障推 探测策略监控网络会产生额外的流量消耗，这会 理、保真度评价和行动选择。 给多层网络带来负担。因此，越来越多的研究者 采用基于终端用户观察的探测信息获取策略620。 故障推理 终端用户观察不需要知道多层网络的先验或后验 <> 故障概率信息，仅仅使用终端用户观察到的服务 保真度评价 负面症状找出可能发生的故障部件。 虽然多层网络的终端用户观察策略不需要网 保度满足要求么仁 Y 络监测代理被动搜集到的大量信息，或者使用探 h,S>IN 结论 测来主动监控网络，但是由于并不是所有的终端 症状得到验证 用户都愿意共享服务状态信息，且可能存在恶意 N 的终端用户共享错误的服务状态信息，因此不充 行为选择 足的终端用户观察和恶意终端用户会降低故障定 <SSt 位的精度。如何处理不充足的终端用户观察和识 图3主动集成故障推理流程 别出恶意的终端用户是该策略进一步的研究方向。 Fig.3 Flow chart of AIR framework 表1是各种探测信息获取策略在探测信息获 故障推理模块把被动观察到的症状作为输入 取方式，是否增加网路流量及花费，优缺点和面 返回故障假设集Φ作为输出。故障假设集Φ包括 临的挑战等方面对现有的多种探测信息获取策略 一列假设{h,h2,…,h,,其中每一个假设包括可以 进行的比较分析。 解释所有观察到的症状的故障集。然后把Φ发送 3多层网络故障定位模型 到保真度评价模块来检验任意的假设：∈Φ是否 具有高保真度，如果具有高保真度，那么故障推 3.1依赖矩阵模型 理过程终止。否则，有助于解释具有最高保真度 多层网络依赖矩阵模型描述了采用主动探测 h,的一列未观察到的症状S被发送到行动选择模 策略时底层网络和虚拟层网络中探测路径与其通 块来确定哪个症状已经发生。因此，保真度评价 过的网络部件状态（节点或链路）之间关系。根 值h,相应地调整。执行的行动返回测试结果，测 据网络部件状态是否为二进制状态（正常“0”，或
首先识别出可能的故障区域，其次发送额外的探 测包来精确定位故障的位置。适应性探测的主要 目标是通过发送最少数目的探测包来精确地定位 故障部件的位置。同样地，多层网络的适应性探 测策略可逐层进行。主动探测策略本质上是通过 测试端到端路径上的部件状态，与被动监测策略 相比对故障响应更快，更灵活性，因此多层网络 采用主动探测策略定位故障效率更高。主动探测 策略具有明显的优势，但是在实际的使用过程中， 网络需要发送大量的管理所需的流量，由于并不 是所有的故障同时发生，所以大量的流量是浪费 的。此外，发送较多数目的探测会产生延迟，很 难得到最优的探测路径集合以及收集到精确的测 试结果。上述缺点将导致故障定位率降低以及故 障定位时间增加，因此综合考虑探测效率、探测 代价的主动探测策略成为进一步亟待解决的问题。 2.3 主被动结合探测策略 主被动结合探测策略同时使用被动监测策略 和主动探测策略，弥补了单一一种探测策略的不 足。Tang 等 [15]采用主被动结合探测策略提出了 主动集成故障推理 (AIR) 框架。如图 3 所示，主 动集成故障推理过程包括 3 个功能模块：故障推 理、保真度评价和行动选择。 结论 故障推理 保真度评价 保真度满足要求 症状得到验证 行为选择 N Y Y N 图 3 主动集成故障推理流程 Fig. 3 Flow chart of AIR framework Φ Φ { h1,h2,··· ,hp } Φ hi ∈ Φ S N hi 故障推理模块把被动观察到的症状作为输入 返回故障假设集 作为输出。故障假设集 包括 一列假设 ，其中每一个假设包括可以 解释所有观察到的症状的故障集。然后把 发送 到保真度评价模块来检验任意的假设 是否 具有高保真度，如果具有高保真度，那么故障推 理过程终止。否则，有助于解释具有最高保真度 hi 的一列未观察到的症状 被发送到行动选择模 块来确定哪个症状已经发生。因此，保真度评价 值 相应地调整。执行的行动返回测试结果，测 S V S U S O、S U 试结果是已存的症状集 和不存在的症状集 。基于行动返回的结果，对应的保真度值可能 被增加或减少。如果新计算的保真度满足条件， 那么推理过程终止，否则 作为故障推理模 块的新输入来生成一个新的假设。这个过程一直 重复直到找到具有高保真度的假设。 多层网络具有多层故障，且底层部件的故障 会导致虚拟层部件的故障，因此多层网络的主被 动结合探测策略可逐层进行，即分别在底层网络 和虚拟层网络采用主被动结合探测策略来定位出 底层网络故障部件和独立虚拟层故障部件。行动 选择的使用减少了由于噪声存在引起的症状丢失 或虚假症状存在的可能性，主被动结合探测策略 最小化探测的使用而且提高了多层网络故障定位 的准确率。 2.4 终端用户观察策略 大多数多层网络探测信息获取策略要么需要 网络监测代理被动搜集到的大量告警信息，要么 使用探测来主动监控网络。然而，被动监控需要 大量关于底层网络部件后验或先验故障概率信 息，这在实际实践中限制了其有效性。采用主动 探测策略监控网络会产生额外的流量消耗，这会 给多层网络带来负担。因此，越来越多的研究者 采用基于终端用户观察的探测信息获取策略[16-20]。 终端用户观察不需要知道多层网络的先验或后验 故障概率信息，仅仅使用终端用户观察到的服务 负面症状找出可能发生的故障部件。 虽然多层网络的终端用户观察策略不需要网 络监测代理被动搜集到的大量信息，或者使用探 测来主动监控网络，但是由于并不是所有的终端 用户都愿意共享服务状态信息，且可能存在恶意 的终端用户共享错误的服务状态信息，因此不充 足的终端用户观察和恶意终端用户会降低故障定 位的精度。如何处理不充足的终端用户观察和识 别出恶意的终端用户是该策略进一步的研究方向。 表 1 是各种探测信息获取策略在探测信息获 取方式，是否增加网路流量及花费，优缺点和面 临的挑战等方面对现有的多种探测信息获取策略 进行的比较分析。 3 多层网络故障定位模型 3.1 依赖矩阵模型 多层网络依赖矩阵模型描述了采用主动探测 策略时底层网络和虚拟层网络中探测路径与其通 过的网络部件状态 (节点或链路) 之间关系。根 据网络部件状态是否为二进制状态 (正常“0”，或 ·48· 智 能 系 统 学 报 第 14 卷
第1期 齐小刚，等：多层信息网络故障定位综述 ·49· 故障“1”)，可以将多层网络的依赖矩阵模型分为 测路径状态是正常的当且仅当这条路径上的所有 二进制依赖矩阵模型212和非二进制依赖矩阵模 部件都是正常状态。非二进制依赖矩阵模型不仅 型242刃。二进制依赖矩阵模型假设多层网络部件 可以定位出多层网络故障部件而且可以判定多层 和探测路径只有正常和故障2种状态，且假设探 网络节点、链路的拥塞程度或链路延迟。 表1各种探测信息获取策略的比较 Table 1 Comparison of various detection information acquisition techniques 被动监测 主动探测 主被动结合探测 终端用户观察 由NMS被动接受告警通过在探测路径上发送使用被动监测和主动探使用终端用户观察到的 探测信息获取策略来分析网络中故障的具探测包诊断和定位网络测找出网络中高保真度负面症状找出可能发生 体位置 中的故障节点和链路 的故障假设集 的故障部件 图论技术（故障传播模 预计划探测策略适应性 Dempster-Shafer理论约 方法和路线 AIR框架、O-AIR框架 型) 探测策略 束满足问题 增加少量网络流量和花 不增加网络流量，增加网 网络流量及花费 不增加网络流量 增加网络流量和花费 费 络花费 响应时间 事件-驱动 事件-驱动 事件-驱动 事件-驱动 可以同时诊断多个故障 可以同时诊断多个故障 灵活、诊断时间短、精 可以同时诊断多个故障 优点 部件，诊断时间短，精度 部件 度高 部件 较高 只假设单个节点故障， 精度低，需要知道部件 需要知道部件故障以及 未考虑丢失探测，节点 需要把监测代理安装在 缺点 故障以及故障一症状之 故障-症状之间因果关系 故障的假症状，动态的 每个overlay节点上 间因果关系的先验知识 的先验知识 探测路径 获得和保持准确信息虚探测站的配置选择最小 探测站的配置选择最小终端用户观察不充足，恶 挑战 假、丢失症状存在 的探测集 的探测集 意终端用户 3.2基于图论的故障传播模型 或经由这些路径的链路之间的依赖关系，其影响 多层网络基于图论的故障传播模型(fault 的大小用条件概率表示。每个节点是多值的随机 propagation model,.FPM)描述了采用被动监测策 变量，其表达的意思是每个路径或链路可能有多 略时所有可能发生在底层网络和虚拟层网络故障 种故障类型，如延迟、大量的包丢失、完全不连通 和症状之间的关系。该模型需要具备底层网络 等。这种情形在故障传播模型中可以被表示为每 和虚拟层网络部件故障状态和告警与其他部件的 条路径和链路在贝叶斯网络模型中对应于多个路 故障。 径和链路节点，其中每个节点表示不同的故障类 建立状态和告警之间相互关联的先验知识。 型。FPM也可以建模为二部图模型。尽管在真 为了建立这样的模型，需要很好地了解每一层网 实网络中故障和症状间的关系通常比二部图表示 络部件间的依赖关系。故障定位算法的高效性和 的关系更为复杂，但许多故障定位方法仍然使用 精确性依赖于先验知识的精确性。FPM的常见 二分PM6列，原因如下：1)执行具有复杂表示形 模型有依赖图模型或贝叶斯网络模型。依赖图模 式的故障定位模型是困难的；2)详细模型通常可 型是有向图，其中节点表示事件，边表示事件间 以通过一系列的图规约操作降为二分模型；3)模 的关系。每一条有向边通过条件概率来标记，其 型建立需要对网络有深厚知识的积累，而症状 表达的意思是：由于起始节点的故障导致了终点 一故障映射关系可以通过外在的观测来获得。因 节点的故障。依赖图的每个节点既可以表示网络 此，在许多真实的问题中使用二分的症状-故障 节点的故障，也可以表示网络链路的故障。关于使 模型是可行的。 用依赖图模型的故障诊断方法的一些工作见文 为了减少由于使用大规模贝叶斯网络模型计 献[6,28-29]。贝叶斯网络模型又称信任网络模 算复杂度，Bennacer等o提出了混合模型，结合了 型，是一个有向无环图，其中，节点表示网络链路 贝叶斯网络模型(BN)和基于实例的推理机制 状态或端到端路径状态，有向边表示端到端路径 (case based reasoing,CBR)的使用。这个模型的基
故障“1”)，可以将多层网络的依赖矩阵模型分为 二进制依赖矩阵模型[21-23]和非二进制依赖矩阵模 型 [24-27]。二进制依赖矩阵模型假设多层网络部件 和探测路径只有正常和故障 2 种状态，且假设探 测路径状态是正常的当且仅当这条路径上的所有 部件都是正常状态。非二进制依赖矩阵模型不仅 可以定位出多层网络故障部件而且可以判定多层 网络节点、链路的拥塞程度或链路延迟。 3.2 基于图论的故障传播模型 多层网络基于图论的故障传播模型 (fault propagation model，FPM) 描述了采用被动监测策 略时所有可能发生在底层网络和虚拟层网络故障 和症状之间的关系。该模型需要具备底层网络 和虚拟层网络部件故障状态和告警与其他部件的 故障。 建立状态和告警之间相互关联的先验知识。 为了建立这样的模型，需要很好地了解每一层网 络部件间的依赖关系。故障定位算法的高效性和 精确性依赖于先验知识的精确性。FPM 的常见 模型有依赖图模型或贝叶斯网络模型。依赖图模 型是有向图，其中节点表示事件，边表示事件间 的关系。每一条有向边通过条件概率来标记，其 表达的意思是：由于起始节点的故障导致了终点 节点的故障。依赖图的每个节点既可以表示网络 节点的故障，也可以表示网络链路的故障。关于使 用依赖图模型的故障诊断方法的一些工作见文 献[6, 28-29]。贝叶斯网络模型又称信任网络模 型，是一个有向无环图，其中，节点表示网络链路 状态或端到端路径状态，有向边表示端到端路径 或经由这些路径的链路之间的依赖关系，其影响 的大小用条件概率表示。每个节点是多值的随机 变量，其表达的意思是每个路径或链路可能有多 种故障类型，如延迟、大量的包丢失、完全不连通 等。这种情形在故障传播模型中可以被表示为每 条路径和链路在贝叶斯网络模型中对应于多个路 径和链路节点，其中每个节点表示不同的故障类 型。FPM 也可以建模为二部图模型。尽管在真 实网络中故障和症状间的关系通常比二部图表示 的关系更为复杂，但许多故障定位方法仍然使用 二分 FPM[4, 6, 9] ，原因如下：1) 执行具有复杂表示形 式的故障定位模型是困难的；2) 详细模型通常可 以通过一系列的图规约操作降为二分模型；3) 模 型建立需要对网络有深厚知识的积累，而症状 −故障映射关系可以通过外在的观测来获得。因 此，在许多真实的问题中使用二分的症状−故障 模型是可行的。 为了减少由于使用大规模贝叶斯网络模型计 算复杂度，Bennacer 等 [30]提出了混合模型，结合了 贝叶斯网络模型 (BN) 和基于实例的推理机制 (case based reasoing，CBR) 的使用。这个模型的基 表 1 各种探测信息获取策略的比较 Table 1 Comparison of various detection information acquisition techniques 被动监测 主动探测 主被动结合探测 终端用户观察 探测信息获取策略 由NMS被动接受告警 来分析网络中故障的具 体位置 通过在探测路径上发送 探测包诊断和定位网络 中的故障节点和链路 使用被动监测和主动探 测找出网络中高保真度 的故障假设集 使用终端用户观察到的 负面症状找出可能发生 的故障部件 方法和路线 图论技术(故障传播模 型) 预计划探测策略适应性 探测策略 AIR 框架、O-AIR 框架 Dempster-Shafer理论约 束满足问题 网络流量及花费 不增加网络流量 增加网络流量和花费 增加少量网络流量和花 费 不增加网络流量，增加网 络花费 响应时间 事件−驱动 事件−驱动 事件−驱动 事件−驱动 优点 可以同时诊断多个故障 部件 灵活、诊断时间短、精 度高 可以同时诊断多个故障 部件，诊断时间短，精度 较高 可以同时诊断多个故障 部件 缺点 精度低，需要知道部件 故障以及故障−症状之 间因果关系的先验知识 只假设单个节点故障， 未考虑丢失探测，节点 故障的假症状，动态的 探测路径 需要知道部件故障以及 故障−症状之间因果关系 的先验知识 需要把监测代理安装在 每个 overlay 节点上 挑战 获得和保持准确信息虚 假、丢失症状存在 探测站的配置选择最小 的探测集 探测站的配置选择最小 的探测集 终端用户观察不充足，恶 意终端用户 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·49·
·50· 智能系统学报 第14卷 本思想是，通过使用CBR减少基于BN相关的故 系：对于每个行动，与之联系起来的是行动顶点 障诊断方法的内在复杂性来简化和优化故障诊断 a,∈A;对于每个症状，与之联系起来的是症状顶 过程。在诊断过程中，BN结构的子集通过 点s∈S;对于每个故障，与之联系起来的是故障 CBR来识别，在子集中只推理观测到变化的节 顶点f∈F;对于每个故障，与之关联的边的权重 点。CBR的使用有助于利用先前学到的情况来 等于p(s),表示症状s,由它造成。对于每个行动 解决目前的以及未来的问题。随着时间的推移， ,与之关联的边的权重等于行动花费，表示行动 CBR的知识库不断更新，有助于提高诊断的效 验证症状存在的可能性。故障-症状-行动模型采 率。通过使用混合模型加速了故障诊断过程以及 用了主被动结合探测策略，弥补了单一探测的不足。 减少了与推理相关的计算复杂度。 使用基于图论的故障传播模型的故障定位方 法面临着如何获得和保持准确信息的挑战6，因 为故障定位的准确性直接取决于模型中信息的准 确性。一些研究人员B1利用建立非确定性故障 传播模型将信息的动态相关性纳入模型中。 0.3 0.9 0.9 0.3 Rish等B和Steiner等建立动态贝叶斯网络模型 0.4 0.3 0.6 0.3 0.9 来表示网络部件状态随时间的变化情况。动态 BN网络模型通过引入时间片的概念和时间片之 0.01 0.02 0.01 间的转移概率P(XX-)对静态BN网络模型进行 图4症状-故障-行动模型 扩展，X=(x,,…,)表示节点在时间片t的状态 Fig.4 Flow chart of AlR framework 向量。然而，“动态”表示动态的系统，而不是随 4多层网络故障诊断与定位方法 时间变化的系统，DBN模型是非时变的，DBN 模型具有马尔科夫特性，即给定当前的状态，网 4.1 O-AIR 络将来的状态与它过去的状态是独立的。时间片 与文献[15]的AIR类似，Overlay网络故障集 内的依赖关系用静态贝叶斯模型来描述。DBN 成推理(O-AIR)B采用主被动结合探测策略。该 模型是一个平稳过程，即转移概率和时间片内依 方法假定网络监测代理驻留在每个覆盖网络节点 赖关系不随时间的变化而变化。 上，监测代理监控链路并收集关于网络部件故障 旦给定动态的BN模型，基于先验概率分 概率的信息和传统观察对应覆盖网症状的概率， 布P(X-1)以及在时间片t的观测值，可以应用标 收集的探测信息用来构造集中式的基于查询的信 准的BN模型推断算法来计算P(XX-,Y),其中 息系统称为覆盖网络配置(overlay network profile, Y是在时间t观测到的症状集。由于DBN模型的 ONP)。进而将相关端到端症状和故障用于建立 时间复杂度很高，文献[35]提出了高效的近似算 overlay故障-症状模型。然而，观察到的症状可 法来解决这个问题。为了减少控制开销，应用网 能不足以识别网络中的所有故障，因此需要采用 络分区策略。目前的分区策略包括基于分簇的策 主动探测策略执行一组监测行动来确定发生故障 略和基于图分割的策略，这些策略的使用有助于 的根源，在此基础上建立overlay网络症状-故障- 减少通信开销和控制开销。Li等通过使用分簇 行动(O-SFA)模型来定位出所有的故障部件。 策略建立动态贝叶斯网络模型来减少故障推理的 O-AR包括3个功能模块：症状挖掘、故障推 时间复杂度，即使用DBN模型来表示大型P网 理和行动选择。基于ONP,症状挖掘模块使用观 络的状态，将故障节点划分为独立的分簇来减少 察到的overlay症状来动态地创建O-SFA模型。 诊断时间。由于故障节点间的条件具有独立性， 故障推理模块把O-SFA作为输入，返回故障假设 对故障节点进行分簇是可行的。然而分簇的使用 h作为输出。故障假设h包括一组能解释所有观察 降低了故障诊断的准确性。 到的症状的部件。选择对应的overlay行动来验 3.3症状-故障-行动模型 证假设。如果h中的所有故障都得到验证，那么 症状-故障-行动模型(SFA模型)是一个5元 overlay故障诊断过程终止并进行故障汇报。反 组(S,F,A,E,E2),其中故障集F、症状集S、行动集 之，基于行动结果，通过除去不能解释的over- A是3个互相独立的顶点集。 lay症状和不相关的部件并且增加新的症状及与 如图4所示，症状-故障-行动模型表示的关 之相关的部件来更新之前创建的O-SFA。该过程
本思想是，通过使用 CBR 减少基于 BN 相关的故 障诊断方法的内在复杂性来简化和优化故障诊断 过程。在诊断过程中， B N 结构的子集通 过 CBR 来识别，在子集中只推理观测到变化的节 点。CBR 的使用有助于利用先前学到的情况来 解决目前的以及未来的问题。随着时间的推移， CBR 的知识库不断更新，有助于提高诊断的效 率。通过使用混合模型加速了故障诊断过程以及 减少了与推理相关的计算复杂度。 P ( X t |X t−1 ) X t = ( x t 1 , x t 2 ,··· , x t n ) t 使用基于图论的故障传播模型的故障定位方 法面临着如何获得和保持准确信息的挑战[6, 14] ，因 为故障定位的准确性直接取决于模型中信息的准 确性。一些研究人员[31-33]利用建立非确定性故障 传播模型将信息的动态相关性纳入模型中。 Rish 等 [34]和 Steiner 等 [31]建立动态贝叶斯网络模型 来表示网络部件状态随时间的变化情况。动态 BN 网络模型通过引入时间片的概念和时间片之 间的转移概率 对静态 BN 网络模型进行 扩展， 表示节点在时间片 的状态 向量。然而，“动态”表示动态的系统，而不是随 时间变化的系统，DBN 模型是非时变的，DBN 模型具有马尔科夫特性，即给定当前的状态，网 络将来的状态与它过去的状态是独立的。时间片 内的依赖关系用静态贝叶斯模型来描述。DBN 模型是一个平稳过程，即转移概率和时间片内依 赖关系不随时间的变化而变化。 P ( X t−1 ) t Y t P ( X t |X t−1 ,Y t ) Y t t 一旦给定动态的 BN 模型，基于先验概率分 布 以及在时间片 的观测值 ，可以应用标 准的 BN 模型推断算法来计算 ，其中 是在时间 观测到的症状集。由于 DBN 模型的 时间复杂度很高，文献[35]提出了高效的近似算 法来解决这个问题。为了减少控制开销，应用网 络分区策略。目前的分区策略包括基于分簇的策 略和基于图分割的策略，这些策略的使用有助于 减少通信开销和控制开销。Li 等 [36]通过使用分簇 策略建立动态贝叶斯网络模型来减少故障推理的 时间复杂度，即使用 DBN 模型来表示大型 IP 网 络的状态，将故障节点划分为独立的分簇来减少 诊断时间。由于故障节点间的条件具有独立性， 对故障节点进行分簇是可行的。然而分簇的使用 降低了故障诊断的准确性。 3.3 症状–故障–行动模型 (S,F,A,E1,E2) F S A 症状–故障–行动模型 (SFA 模型) 是一个 5 元 组 ，其中故障集 、症状集 、行动集 是 3 个互相独立的顶点集。 如图 4 所示，症状–故障–行动模型表示的关 ai ∈ A si ∈ S fi ∈ F fi p(si | fi) si ai 系：对于每个行动，与之联系起来的是行动顶点 ；对于每个症状，与之联系起来的是症状顶 点 ；对于每个故障，与之联系起来的是故障 顶点 ；对于每个故障 ，与之关联的边的权重 等于 ，表示症状 由它造成。对于每个行动 ，与之关联的边的权重等于行动花费，表示行动 验证症状存在的可能性。故障–症状–行动模型采 用了主被动结合探测策略，弥补了单一探测的不足。 a1 a2 a3 a4 s1 s2 s3 s4 f1 f2 f3 0.9 0.3 0.4 0.3 0.9 0.3 0.9 0.6 0.3 1 2 2 1 1 2 1 1 0.01 0.02 0.01 图 4 症状–故障–行动模型 Fig. 4 Flow chart of AIR framework 4 多层网络故障诊断与定位方法 4.1 O-AIR 与文献[15]的 AIR 类似，Overlay 网络故障集 成推理 (O-AIR)[37]采用主被动结合探测策略。该 方法假定网络监测代理驻留在每个覆盖网络节点 上，监测代理监控链路并收集关于网络部件故障 概率的信息和传统观察对应覆盖网症状的概率， 收集的探测信息用来构造集中式的基于查询的信 息系统称为覆盖网络配置 (overlay network profile， ONP)。进而将相关端到端症状和故障用于建立 overlay 故障–症状模型。然而，观察到的症状可 能不足以识别网络中的所有故障，因此需要采用 主动探测策略执行一组监测行动来确定发生故障 的根源，在此基础上建立 overlay 网络症状–故障– 行动 (O-SFA) 模型来定位出所有的故障部件。 h h h O-AIR 包括 3 个功能模块：症状挖掘、故障推 理和行动选择。基于 ONP，症状挖掘模块使用观 察到的 overlay 症状来动态地创建 O-SFA 模型。 故障推理模块把 O-SFA 作为输入，返回故障假设 作为输出。故障假设 包括一组能解释所有观察 到的症状的部件。选择对应的 overlay 行动来验 证假设。如果 中的所有故障都得到验证，那么 overlay 故障诊断过程终止并进行故障汇报。反 之，基于行动结果，通过除去不能解释的 overlay 症状和不相关的部件并且增加新的症状及与 之相关的部件来更新之前创建的 O-SFA。该过程 ·50· 智 能 系 统 学 报 第 14 卷
第1期 齐小刚，等：多层信息网络故障定位综述 ·51· 直重复直到找到可验证的假设。 分overlay链路的状态来最小化监控overlay网络 图5是对应于图1中overlay网络中的over- 的总花费。通过适当地组合底层链路和over- lay链路和overlay路径。图5中的overlay网络 lay链路可以推出整个overlay网络链路的状态。 有2条overlay路径：在overlay节点D和E之间的 虚拟网络的被动故障诊断方法使用代表底层 路径Poe和在overlay节点A和B之间的路径PAso 网络、虚拟网络故障和症状关系的网络模型。相 overlay路径Poe包含2条overlay链路loc和lee;类 应的故障诊断问题可以阐述为概率推理问题，在 似地，overlay路径Pas包含2条overlay链路lac和 给定观测症状的情况下识别在底层网络中的故 IcBo Npc、NcE、NAc、Ncg表示底层网络部件。图6 障。然而，这些方法忽略了在虚拟层独立存在的 表示的是对应于图5的overlay网络的O-SFA模 故障。Yan等建立了分层模型，提供了虚拟网 型。O-SFA模型中，O表示每一条overlay路径对 络环境中可能发生的3种故障。在底层发生的故 应的症状，S,表示每条overlay链路对应的路径， 障被称为底层故障(SF),它可能导致对应虚拟节 F表示overlay或其对应的underlay节点的故障， 点和链路的故障，称之为相关虚拟故障(CVF)。 a,表示验证症状的行动节点。 由于虚拟层软件错误发生的故障称为独立虚拟故 D 障(VF)。当底层故障得到修复时，对应的相关虚 overlay链路 拟故障也会自动被修复。为此，Yan等在文献[39] overlay路径 中描述了基于症状-故障关系和所观测的症状来 Nc& 底层网络 a 定位出所有虚拟故障的方法，基于CVF和SF的 映射关系定位底层故障$F,提出了过滤算法来区 图5 overlay网络中的overlay链路和overlay路径 分CVF和IVF。文献[15]假设选择算法从过滤过 Fig.5 overlay network showing overlay paths and links 的故障中推出可以解释观察到的症状的故障假设 0={0} 集合，然而他们却忽略了CVF和IVF交集非空的 S(S) 可能，导致故障定位不完全，诊断率不高。 F-(F) 4={a} 刘娜等提出一种针对网络虚拟化环境下虚 拟网和底层网的分层模型。采用多层监控方法， 通过虚拟网信任评估算法来提高故障诊断的准确 Fa 率降低误报率。张顺利提出了网络虚拟化环境 下的服务故障传播模型。为了提高诊断算法的性 能，提出了基于症状内在相关性的多层虚拟网服 a 务故障诊断算法，该算法能够很好地解决底层网 图6 overlay网络的O-SFA模型 络信息对服务提供商可见性造成的虚拟网服务故 Fig.6 Symptom-fault-action model for overlay network 障难以定位的问题，可以有效地降低诊断算法的 可以看出，上述模型具有很强的优越性，但在 误报率，减少诊断算法的诊断时间。 实际应用中还需要进一步改进和完善：1)定位模 由于底层网络信息对服务提供商不可见性造 型框架中不仅使用网络监测代理被动收集的大量 成虚拟网服务故障难以定位，又由于每个底层网 信息，同时还需借助使用探测包主动监测网络状 络上同时承载的虚拟网络数量较多，导致症状集 态以克服现有方法的局限性；2)被动监测需要大 中包含的症状和故障集中包含的故障较多，因此 量有关底层网络部件后验或先验故障概率的网络 多层监控方法的故障诊断性能较低。 知识，这在实际中限制了该方法的有效性，同时 4.3 基于终端用户观察策略的方法 探测带来的额外流量也增加了基础网络负担： 终端用户观察策略不需要知道虚拟网络的全 3)模型的假设较强，需要增加对于关联故障或多 部知识，仅仅使用终端用户观察到的负面症状找 故障情形的适应能力。 出可能发生的故障部件。Tang等提出了over- 4.2多层监控方法 lay故障诊断框架DigOver。这里终端用户观察到 在overlay网铬中，通过测量所有的overlay节 的负面症状对应于一条overlay路径上的所有部 点对之间的路径来监控所有overlay网络链路是 件的集合。使用负面症状作为证据构造可能发生 十分笨重且花费巨大代价的。Demirci等提出 的故障部件集合，即故障假设集。使用Dempster-. 了多层监控方法，监控部分底层网络的链路和部 Shafer理论评价故障假设集中的每个故障进而使
一直重复直到找到可验证的假设。 D E PDE A B PAB PDE lDC lCE PAB lAC lCB NDC、NCE、NAC Oi S j Fk al 图 5 是对应于图 1 中 overlay 网络中的 overlay 链路和 overlay 路径。图 5 中的 overlay 网络 有 2 条 overlay 路径：在 overlay 节点 和 之间的 路径 和在 overlay 节点 和 之间的路径 。 overlay 路径 包含 2 条 overlay 链路 和 ；类 似地，overlay 路径 包含 2 条 overlay 链路 和 。 、NCB 表示底层网络部件。图 6 表示的是对应于图 5 的 overlay 网络的 O-SFA 模 型。O-SFA 模型中， 表示每一条 overlay 路径对 应的症状， 表示每条 overlay 链路对应的路径， 表示 overlay 或其对应的 underlay 节点的故障， 表示验证症状的行动节点。 D E A B C NDC NAC NCE NCB 底层网络 overlay 路径 overlay 链路 图 5 overlay 网络中的 overlay 链路和 overlay 路径 Fig. 5 overlay network showing overlay paths and links ODE OAB SDC SAC SCE SCB FD FDC FA FAC FC FCE FE FCB FB a1 a2 a3 a4 a5 O={Oi} S={Si} F={Fi} A={ai} 图 6 overlay 网络的 O-SFA 模型 Fig. 6 Symptom-fault-action model for overlay network 可以看出，上述模型具有很强的优越性，但在 实际应用中还需要进一步改进和完善：1) 定位模 型框架中不仅使用网络监测代理被动收集的大量 信息，同时还需借助使用探测包主动监测网络状 态以克服现有方法的局限性；2) 被动监测需要大 量有关底层网络部件后验或先验故障概率的网络 知识，这在实际中限制了该方法的有效性，同时 探测带来的额外流量也增加了基础网络负担； 3) 模型的假设较强，需要增加对于关联故障或多 故障情形的适应能力。 4.2 多层监控方法 在 overlay 网络中，通过测量所有的 overlay 节 点对之间的路径来监控所有 overlay 网络链路是 十分笨重且花费巨大代价的。Demirci 等 [38]提出 了多层监控方法，监控部分底层网络的链路和部 分 overlay 链路的状态来最小化监控 overlay 网络 的总花费。通过适当地组合底层链路和 overlay 链路可以推出整个 overlay 网络链路的状态。 虚拟网络的被动故障诊断方法使用代表底层 网络、虚拟网络故障和症状关系的网络模型。相 应的故障诊断问题可以阐述为概率推理问题，在 给定观测症状的情况下识别在底层网络中的故 障。然而，这些方法忽略了在虚拟层独立存在的 故障。Yan 等 [39]建立了分层模型，提供了虚拟网 络环境中可能发生的 3 种故障。在底层发生的故 障被称为底层故障 (SF)，它可能导致对应虚拟节 点和链路的故障，称之为相关虚拟故障 (CVF)。 由于虚拟层软件错误发生的故障称为独立虚拟故 障 (IVF)。当底层故障得到修复时，对应的相关虚 拟故障也会自动被修复。为此，Yan 等在文献[39] 中描述了基于症状–故障关系和所观测的症状来 定位出所有虚拟故障的方法，基于 CVF 和 SF 的 映射关系定位底层故障 SF，提出了过滤算法来区 分 CVF 和 IVF。文献[15]假设选择算法从过滤过 的故障中推出可以解释观察到的症状的故障假设 集合，然而他们却忽略了 CVF 和 IVF 交集非空的 可能，导致故障定位不完全，诊断率不高。 刘娜等[40]提出一种针对网络虚拟化环境下虚 拟网和底层网的分层模型。采用多层监控方法， 通过虚拟网信任评估算法来提高故障诊断的准确 率降低误报率。张顺利[41]提出了网络虚拟化环境 下的服务故障传播模型。为了提高诊断算法的性 能，提出了基于症状内在相关性的多层虚拟网服 务故障诊断算法，该算法能够很好地解决底层网 络信息对服务提供商可见性造成的虚拟网服务故 障难以定位的问题，可以有效地降低诊断算法的 误报率，减少诊断算法的诊断时间。 由于底层网络信息对服务提供商不可见性造 成虚拟网服务故障难以定位，又由于每个底层网 络上同时承载的虚拟网络数量较多，导致症状集 中包含的症状和故障集中包含的故障较多，因此 多层监控方法的故障诊断性能较低。 4.3 基于终端用户观察策略的方法 终端用户观察策略不需要知道虚拟网络的全 部知识，仅仅使用终端用户观察到的负面症状找 出可能发生的故障部件。Tang 等 [18]提出了 overlay 故障诊断框架 DigOver。这里终端用户观察到 的负面症状对应于一条 overlay 路径上的所有部 件的集合。使用负面症状作为证据构造可能发生 的故障部件集合，即故障假设集。使用 DempsterShafer 理论评价故障假设集中的每个故障进而使 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·51·
·52· 智能系统学报 第14卷 用评价的不确定性来量化部件故障发生的可能 lay节点的配置也对overlay的诊断能力起重大作 性。Dempster-.Shafer理论的使用使得其与其他基 用。图7是3个节点的overlay网络在底层网络 于贝叶斯理论的概率故障诊断方法不同。在贝叶 上的不同配置的例子。对于overlay ABC,底层节 斯推理中需要主动监控或网络监测代理搜集的大 点X的故障可以在路径AB上被观察到。然而， 量信息。然而DigOver不需要这样的先验信息， 由于2个底层链路和1个底层节点都可能是故障 仅仅需要网络拓扑信息。尽管DigOver具有较高 的根源，因此故障部件集合不能被降低为1个部 的准确性，但是评价故障可能性的时间花费过 件。另一方面，对于overlay配置ABC'可以在 长，特别是当负面症状集中于少量的故障部件 3个端到端路径上观察到故障节点X,且故障节点 时。为此，Wang等提出了一个故障诊断方法 可以被唯一地定位。通常情况下诊断能力和底层 DiaEO,DiaEO将终端用户观察到的负面症状进 部件的压力（对于底层节点，压力是映射到其上 行筛选，把负面症状矩阵筛选成多个子矩阵，并 的overlay节点数；对于底层链路，其压力是通过 在每个子矩阵上分析症状来减少推理时间。Gillani 它的overlay链路数)之间存在权衡，即较高的诊 等20提出另外一种基于终端用户观察的故障诊断 断能力通常会以底层网络的压力为代价。over- 方法。终端用户之间通过汇报他们观察到的数据 lay配置方法基于以下思想。 包丢失和路由信息共享服务异常信息（即负面症 l)增加共享1个底层链路的平均overlay路 状)。文献[23]的贡献在于创建一个基于约束的模 径数：端到端路径共享1个底层部件越多，可以观 型探测器来准确定位大规模网络的数据包丢失， 察到该部件发生故障的症状数越多，这有助于定 且这个过程不需要任何主动探测或网络监测代 位故障。 理。这个模型利用终端用户负面症状之间的相关 2)限制一个部件上的最大压力：底层节点或 性（归因于共享的症状和路径片段）和观察到的 链路由过多overlay节点或链路共享将会带来拥 网络数据包丢失特性，使用可满足性模理论(sat- 塞或资源耗尽的风险。 isfiability modulo theories,.SMT)对约束进行编 3)限制几乎完全重叠的overlay路径数：两个 码。高级SMT解答器如Z3和Yices可以解决数 完全重叠的端到端路径会观察到同一个症状，不 千的约束条件和数百万的变量回。这种方法对于 会比与之重合的单个overlay路径提供更多有价 大量症状和网络部件具有扩展性。文中的模型探 值的信息。 测器可以识别满足终端用户观察和网络数据包丢 失的网络部件根源的最小集。然而，由于不充足 的终端用户观察，该故障诊断系统具有低精确度 风险。此外，一些终端用户可能是恶意的，并向 其他终端用户分享虚假观察。选择性请求合适的 终端用户发送网络探测信息来解决不充足的观 图7 overlay网络的2种可能的配置 察。这些探测仅仅瞄准可能发生故障部件的很小 Fig.7 Sample topology with two possible placements of an 的子集。同时，已有的文献证明了需要发送的探 overlay network 测仅仅消耗极少的流量，进而通过识别并把它们 综合这3种思想，配置算法的目标是最大化 汇报的虚假观察从系统中除去来解决恶意终端用 配置质量即度量q。算法始于overlay到底层网络 户问题。 的随机配置，通过作一些较小的调整来逐渐提高 虽然终端用户观察不需要网络监测代理被动 q。这个方法利用了overlay设计的灵活性来最大 搜集到的大量信息，或者使用探测来主动监控网 化overlay网络的诊断能力。 络，但是不充足的终端用户观察和恶意终端用户 4.5动态贝叶斯模型 会降低故障诊断系统的精度。 为了保证在网络虚拟化环境下诊断算法的性 4.4高效的overlay网络配置 能，克服强动态性特点带来的问题，Rahman等 Demirci等4提出了高效的节点配置来加快 综合考虑动态环境对网络模型、网络状态、故障 故障诊断速度并最优化overlay监控。一个新术 先验概率等方面的影响，采用动态贝叶斯网络模 语诊断能力被定义为overlay网络使用最小的花 型对网络虚拟化环境下的故障诊断问题进行建 费来精确诊断可能发生的故障的特性。诊断能力 模，提出动态环境下的虚拟网故障诊断算法。算 很大程度上依赖于底层网络拓扑。此外，over- 法的主要过程包括时间信息处理、噪声处理、故
用评价的不确定性来量化部件故障发生的可能 性。Dempster-Shafer 理论的使用使得其与其他基 于贝叶斯理论的概率故障诊断方法不同。在贝叶 斯推理中需要主动监控或网络监测代理搜集的大 量信息。然而 DigOver 不需要这样的先验信息， 仅仅需要网络拓扑信息。尽管 DigOver 具有较高 的准确性，但是评价故障可能性的时间花费过 长，特别是当负面症状集中于少量的故障部件 时。为此，Wang 等 [19]提出了一个故障诊断方法 DiaEO，DiaEO 将终端用户观察到的负面症状进 行筛选，把负面症状矩阵筛选成多个子矩阵，并 在每个子矩阵上分析症状来减少推理时间。Gillani 等 [20]提出另外一种基于终端用户观察的故障诊断 方法。终端用户之间通过汇报他们观察到的数据 包丢失和路由信息共享服务异常信息 (即负面症 状)。文献[23]的贡献在于创建一个基于约束的模 型探测器来准确定位大规模网络的数据包丢失， 且这个过程不需要任何主动探测或网络监测代 理。这个模型利用终端用户负面症状之间的相关 性 (归因于共享的症状和路径片段) 和观察到的 网络数据包丢失特性，使用可满足性模理论 (satisfiability modulo theories，SMT) 对约束进行编 码。高级 SMT 解答器如 Z3 和 Yices 可以解决数 千的约束条件和数百万的变量[42]。这种方法对于 大量症状和网络部件具有扩展性。文中的模型探 测器可以识别满足终端用户观察和网络数据包丢 失的网络部件根源的最小集。然而，由于不充足 的终端用户观察，该故障诊断系统具有低精确度 风险。此外，一些终端用户可能是恶意的，并向 其他终端用户分享虚假观察。选择性请求合适的 终端用户发送网络探测信息来解决不充足的观 察。这些探测仅仅瞄准可能发生故障部件的很小 的子集。同时，已有的文献证明了需要发送的探 测仅仅消耗极少的流量，进而通过识别并把它们 汇报的虚假观察从系统中除去来解决恶意终端用 户问题。 虽然终端用户观察不需要网络监测代理被动 搜集到的大量信息，或者使用探测来主动监控网 络，但是不充足的终端用户观察和恶意终端用户 会降低故障诊断系统的精度。 4.4 高效的 overlay 网络配置 Demirci 等 [43]提出了高效的节点配置来加快 故障诊断速度并最优化 overlay 监控。一个新术 语诊断能力被定义为 overlay 网络使用最小的花 费来精确诊断可能发生的故障的特性。诊断能力 很大程度上依赖于底层网络拓扑。此外，overlay 节点的配置也对 overlay 的诊断能力起重大作 用。图 7 是 3 个节点的 overlay 网络在底层网络 上的不同配置的例子。对于 overlay ABC，底层节 点 X 的故障可以在路径 AB 上被观察到。然而， 由于 2 个底层链路和 1 个底层节点都可能是故障 的根源，因此故障部件集合不能被降低为 1 个部 件。另一方面，对于 overlay 配置 ABC′可以在 3 个端到端路径上观察到故障节点 X，且故障节点 可以被唯一地定位。通常情况下诊断能力和底层 部件的压力 (对于底层节点，压力是映射到其上 的 overlay 节点数；对于底层链路，其压力是通过 它的 overlay 链路数) 之间存在权衡，即较高的诊 断能力通常会以底层网络的压力为代价。overlay 配置方法基于以下思想。 1) 增加共享 1 个底层链路的平均 overlay 路 径数：端到端路径共享 1 个底层部件越多，可以观 察到该部件发生故障的症状数越多，这有助于定 位故障。 2) 限制一个部件上的最大压力：底层节点或 链路由过多 overlay 节点或链路共享将会带来拥 塞或资源耗尽的风险。 3) 限制几乎完全重叠的 overlay 路径数：两个 完全重叠的端到端路径会观察到同一个症状，不 会比与之重合的单个 overlay 路径提供更多有价 值的信息。 C' A B X C 图 7 overlay 网络的 2 种可能的配置 Fig. 7 Sample topology with two possible placements of an overlay network q q 综合这 3 种思想，配置算法的目标是最大化 配置质量即度量 。算法始于 overlay 到底层网络 的随机配置，通过作一些较小的调整来逐渐提高 。这个方法利用了 overlay 设计的灵活性来最大 化 overlay 网络的诊断能力。 4.5 动态贝叶斯模型 为了保证在网络虚拟化环境下诊断算法的性 能，克服强动态性特点带来的问题，Rahman 等 [44] 综合考虑动态环境对网络模型、网络状态、故障 先验概率等方面的影响，采用动态贝叶斯网络模 型对网络虚拟化环境下的故障诊断问题进行建 模，提出动态环境下的虚拟网故障诊断算法。算 法的主要过程包括时间信息处理、噪声处理、故 ·52· 智 能 系 统 学 报 第 14 卷
第1期 齐小刚，等：多层信息网络故障定位综述 ·53· 障定位、计算后验概率和执行更新。算法的步骤 考察与验证状态或节点之间的独立性，建立面向 如下。 实际网络的通用故障定位技术，提高故障定位算 1)时间信息处理。假设时间片1的模型 法的运行速度和准确性，将成为本研究领域的核 为FoM(F,S,PF,Ps),时间片2的模型为 心问题。 FDM2(F2,S2,PF2,PF2s2),最终合成的期望模型为 5开放性研究问题和未来研究方向 FDM(Fi Si PFi PFuSi) 2)噪声处理。去除噪声共分为2个步骤：先 综合上述分析，现有故障定位技术相关研究 根据症状与故障之间的关系，过滤掉虚假故障： 的不足和亟待进一步研究解决的问题如下。 再根据症状之间的关系，过滤掉被动症状。 1)现有的故障定位模型对于资源映射特性的 3)诊断算法。通过分析观测到的症状S。.,找 考虑有待完善，研究虚拟网络的故障定位模型还 出一系列可能解释当前症状的假设集合（一组 非常有限。已有的研究工作仍然缺乏对信息获取 故障的集合)，通过计算假设集合的信度B(H,S), 和模型建立过程的研究。由于信息获取的复杂性 输出信度最大的一个或者多个假设的集合作为最 以及与之相关的诸多问题，建立精确的网络模型 终定位结果。 被认为是一个独立的过程，而且大多数的研究方 4)计算后验概率和执行更新。为了提高动态 案假设上述模型是事先存在的。随着新的网络环 环境下的故障诊断算法性能，在每个时间片诊断 境部署，在很长一段时间内，已有的或遗存的网 结束后，修正每个时间窗口内的先验故障概率。 络环境仍然会与新技术共存，网络管理方案应该 对于每一个故障节点，使用贝叶斯公式计算其后 能够管理网络的异构性。此外，基于网络的服务 验概率，利用后验概率和传播概率，更新当前节 通常会穿越已有的或新的网络、物理的或虚拟的 点故障的概率，将本次计算结果作为下一个时间 网络部件，因此异构网络部件的共存需要从端到 片的先验概率，然后进入下一个时间片继续处理。 端的角度实现网管系统的无缝管理。 使用动态贝叶斯模型的故障诊断方法面临的 2)网络的动态性、探测效率、探测代价、网络 挑战如下。 开销等约束关系难以权衡，研究高动态网络特性 1)故障探测中考虑时间信息处理的动态贝叶 的故障探测信息获取技术仍然是一个空白区域。 斯模型计算复杂度高。使用基于时间信息处理的 使用探测来诊断网络需要在网络中的一个或多个 动态贝叶斯模型在时间片内是静态贝叶斯网络模 位置上放置探测站，接着选择探测瞄准不同的网 型。这种方法可以处理各种不同的动态系统，但 络节点和链路。探测站需要探测编码的安装、操 是静态贝叶斯网络模型本身的复杂度会增加动态 作、维护，探测包的发送需要额外的网络流量花 贝叶斯网络模型的计算复杂度。 费以及收集、存储和分析测试结果，探测站和探 2)故障诊断精度不高的问题。在DBN模型 测路径的部署增加了网络管理的花费。未来的可 中，可以拆分故障节点为独立的簇来减少诊断时 行方法是优化探测站的选择和探测路径数量的设 间和进行推断。然而簇的使用降低了故障诊断的 定并最小化监测花费，提出综合考虑探测效率 精度。 探测代价的探测信息获取技术。为了适应基础设 3)网络虚拟化的动态性特点容易造成网络模 施的频繁变化，有必要建立基于预测思想的下 型知识不准确、网络信息传输时噪声增大等问 代网络管理系统。该系统不仅具有检测和定位的 题，给故障诊断带来挑战。 功能，还应当从最近的网络部件状态信息中捕捉 可以看出，现有工作在研究面向高动态网络 和预防故障的发生，提供更好的网络稳定性和服 的故障管理与定位方面充分考虑了状态的迁移、 务交付，以及网络管理（如资源提供、监控、分析 故障节点间的条件独立性、网络的规模和时间复 与通知等)一体化解决方案。 杂度等方面。然而，过于复杂的定位技术在实际 3)现有的故障定位中的独立性假设较强，设 的网络管理和故障定位中并不具备通用性，并且 计面向不同定位需求的通用故障定位算法仍然充 已有方法均基于探测到的故障信息和事先收集的 满挑战。近年来，虽然已经出现了多种近似的解 症状-故障关系以及假定网络状态或故障节点之 决方案，但权衡网络故障诊断准确性和网络控制 间是独立的，而这些与实际信息网络的状态累积 开销仍然是一个挑战性的问题。目前为止，还没 (如拥塞导致的故障)和网络互联（如网络中存在 有直接的证据证明网络状态前后之间或故障节点 的数据流)的本质有些是不相符的。因此，重新 之间的独立性假设的合理性，更没有建立面向实
障定位、计算后验概率和执行更新。算法的步骤 如下。 FDM1 ( Fi,1,S i,1,PFi,1,PFi,1,S i,1 ) FDM2 ( Fi,2,S i,2,PFi,2,PFi,2,S i,2 ) FDM ( Fi,t ,S i,t ,PFi,t ,PFi,t,S i,t ) 1 ) 时间信息处理。假设时间 片 1 的模型 为 ，时间 片 2 的模型为 ，最终合成的期望模型为 。 2) 噪声处理。去除噪声共分为 2 个步骤：先 根据症状与故障之间的关系，过滤掉虚假故障； 再根据症状之间的关系，过滤掉被动症状。 H t i B ( H t i ,S o,t ) 3) 诊断算法。通过分析观测到的症状 So，t，找 出一系列可能解释当前症状的假设集合 (一组 故障的集合)，通过计算假设集合的信度 ， 输出信度最大的一个或者多个假设的集合作为最 终定位结果。 4) 计算后验概率和执行更新。为了提高动态 环境下的故障诊断算法性能，在每个时间片诊断 结束后，修正每个时间窗口内的先验故障概率。 对于每一个故障节点，使用贝叶斯公式计算其后 验概率，利用后验概率和传播概率，更新当前节 点故障的概率，将本次计算结果作为下一个时间 片的先验概率，然后进入下一个时间片继续处理。 使用动态贝叶斯模型的故障诊断方法面临的 挑战如下。 1) 故障探测中考虑时间信息处理的动态贝叶 斯模型计算复杂度高。使用基于时间信息处理的 动态贝叶斯模型在时间片内是静态贝叶斯网络模 型。这种方法可以处理各种不同的动态系统，但 是静态贝叶斯网络模型本身的复杂度会增加动态 贝叶斯网络模型的计算复杂度。 2) 故障诊断精度不高的问题。在 DBN 模型 中，可以拆分故障节点为独立的簇来减少诊断时 间和进行推断。然而簇的使用降低了故障诊断的 精度。 3) 网络虚拟化的动态性特点容易造成网络模 型知识不准确、网络信息传输时噪声增大等问 题，给故障诊断带来挑战。 可以看出，现有工作在研究面向高动态网络 的故障管理与定位方面充分考虑了状态的迁移、 故障节点间的条件独立性、网络的规模和时间复 杂度等方面。然而，过于复杂的定位技术在实际 的网络管理和故障定位中并不具备通用性，并且 已有方法均基于探测到的故障信息和事先收集的 症状–故障关系以及假定网络状态或故障节点之 间是独立的，而这些与实际信息网络的状态累积 (如拥塞导致的故障) 和网络互联 (如网络中存在 的数据流) 的本质有些是不相符的。因此，重新 考察与验证状态或节点之间的独立性，建立面向 实际网络的通用故障定位技术，提高故障定位算 法的运行速度和准确性，将成为本研究领域的核 心问题。 5 开放性研究问题和未来研究方向 综合上述分析，现有故障定位技术相关研究 的不足和亟待进一步研究解决的问题如下。 1) 现有的故障定位模型对于资源映射特性的 考虑有待完善，研究虚拟网络的故障定位模型还 非常有限。已有的研究工作仍然缺乏对信息获取 和模型建立过程的研究。由于信息获取的复杂性 以及与之相关的诸多问题，建立精确的网络模型 被认为是一个独立的过程，而且大多数的研究方 案假设上述模型是事先存在的。随着新的网络环 境部署，在很长一段时间内，已有的或遗存的网 络环境仍然会与新技术共存，网络管理方案应该 能够管理网络的异构性。此外，基于网络的服务 通常会穿越已有的或新的网络、物理的或虚拟的 网络部件，因此异构网络部件的共存需要从端到 端的角度实现网管系统的无缝管理。 2) 网络的动态性、探测效率、探测代价、网络 开销等约束关系难以权衡，研究高动态网络特性 的故障探测信息获取技术仍然是一个空白区域。 使用探测来诊断网络需要在网络中的一个或多个 位置上放置探测站，接着选择探测瞄准不同的网 络节点和链路。探测站需要探测编码的安装、操 作、维护，探测包的发送需要额外的网络流量花 费以及收集、存储和分析测试结果，探测站和探 测路径的部署增加了网络管理的花费。未来的可 行方法是优化探测站的选择和探测路径数量的设 定并最小化监测花费，提出综合考虑探测效率、 探测代价的探测信息获取技术。为了适应基础设 施的频繁变化，有必要建立基于预测思想的下一 代网络管理系统。该系统不仅具有检测和定位的 功能，还应当从最近的网络部件状态信息中捕捉 和预防故障的发生，提供更好的网络稳定性和服 务交付，以及网络管理 (如资源提供、监控、分析 与通知等) 一体化解决方案。 3) 现有的故障定位中的独立性假设较强，设 计面向不同定位需求的通用故障定位算法仍然充 满挑战。近年来，虽然已经出现了多种近似的解 决方案，但权衡网络故障诊断准确性和网络控制 开销仍然是一个挑战性的问题。目前为止，还没 有直接的证据证明网络状态前后之间或故障节点 之间的独立性假设的合理性，更没有建立面向实 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·53·
