多层信息网络故障定位综述（西安电子科技大学：齐小刚、牛红曼、刘兴成、王晓琳、刘立芳）

第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 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) 运行带来了 严重挑战，其核心问题是故障管理。故障在大规 模通信网络中是不可避免的，因此实时地检测和 定位故障对于网络的可靠运行至关重要，而故 障管理系统的功能就是检测、定位网络中的故 障以及启动故障恢复机制来防止网络性能的退 化 [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 sub￾strate 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 结论 测来主动监控网络，但是由于并不是所有的终端 症状得到验证 用户都愿意共享服务状态信息，且可能存在恶意 <So Su> 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 个功能模块：故障推 理、保真度评价和行动选择。 结论 故障推理 保真度评价 保真度满足要求 症状得到验证 行为选择 <Φ> <h, SN> <SO, SU> <SV , SU> <h, ϕ> 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 卷