多层信息网络故障定位综述

齐小刚，牛红曼，刘兴成，王晓琳，刘立芳

（1. 西安电子科技大学 数学与统计学院，陕西 西安 710126; 2. 西安电子科技大学 计算机学院，陕西 西安710071）

近年来，通信网络的规模和复杂性呈现急剧增长势头，这给网络管理系统(NMS)运行带来了严重挑战，其核心问题是故障管理。故障在大规模通信网络中是不可避免的，因此实时地检测和定位故障对于网络的可靠运行至关重要，而故障管理系统的功能就是检测、定位网络中的故障以及启动故障恢复机制来防止网络性能的退化[1-2]。

故障管理过程包括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来解释1个故障情形。客户尝试使用安全外壳协议(SSH)来连接到远程服务器(服务器2)。在端路由器上有多个入口到服务器2上，在它的转发表上有不同的转发端口，在转发表上总是选择第一个入口。如图1所示，关于目的地服务器2的SSH请求被错误地转发到服务器1上，服务器1把相应的SSH请求丢弃，并产生告警。客户没有接收到SSH请求的应答，最终超时，产生告警(即连接失败)报告给网络管理员。这个例子表明故障部件可以引起远程位置的服务中断。本文把网络中的客户机、服务器和路由器等网络设备抽象为节点，把连接相邻节点的路径设备抽象为链路，并把节点和链路统称为网络部件。本文研究的故障类型为节点故障和链路故障，并称由故障的节点或链路产生的告警为症状。

图 1 故障及症状/警告举例Fig. 1 Examples of failures and symptoms/alarms

.2 多层网络故障的定义

本文把覆盖网(Overlay网络)、虚拟网等通过底层网络资源的抽象和隔离而虚拟出来的网络称为虚拟层网络。把底层网络和由它虚拟出来的虚拟层网络称为多层网络。

本文把多层网络表示为无向图 G=(V,E)，其中： V 是节点集，包括底层节点 VSN和虚拟层节点VVN； E 是链路集，包括底层链路 ESN和虚拟层链路EVN。称虚拟层节点和虚拟层链路为虚拟部件，底层节点和底层链路为底层部件。

多层网络故障包括底层部件故障和虚拟层部件故障。其中，底层故障部件包括底层故障节点和底层故障链路。虚拟层故障部件包括虚拟层故障节点和虚拟层故障链路。

本文称在虚拟层网络中由虚拟层节点和虚拟层链路连接而成的端到端的虚拟层最短路径为多层网络服务。

多层网络中的症状可能由故障的节点、链路或服务异常产生。服务的状态反映了它所通过的虚拟层部件的状态。多层网络中节点或链路故障产生的告警和观察到的端到端服务异常状态称为负面症状，观察到的端到端服务正常状态称为正面症状。

在多层网络中虚拟层部件和底层部件存在映射关系，包括节点映射和链路映射。节点映射表示一个虚拟层节点映射到底层网络中的一个底层节点上。图2是多层网络中虚拟层网络映射到底层网络的一个例子，图中overlay网络中的虚拟节点A映射到底层节点 N1上。链路映射表示一条虚拟层链路映射到底层网络中的一条路径上，即一条虚拟层链路可能跨越多个底层链路。如图2所示多层网络中的虚拟层链路 (D,C)映射到底层路径 N4→ N9→ N3上。

图 2 多层网络中虚拟层网络映射到底层网络的例子Fig. 2 Mapping between virtual layer network and substrate network in multilayer networks

在多层网络中，互联网服务提供者(ISP)被分为两类：基础设施提供者(InP)和服务提供者(SP)。服务提供者为用户提供定制的端到端服务。InP把底层网络资源租给SP，通过这种方式提高了底层网络资源的利用率，但是由于多层网络赋予底层网络新的功能，多层网络故障增加了传统网络的故障形式，给故障诊断带来挑战，具体分析如下。

1)底层网络信息不可获得性和信息的不完全性与不准确性。底层网络通常不愿与虚拟层网络共享详细的网络信息，例如：底层网络的症状，虚拟层网络和底层网络的映射关系，底层网络的先验概率等，这对于故障诊断是十分关键的。此外，完全地监控所有底层网络和虚拟层网络是不可行的，故障诊断必须依赖于不准确和不完全的信息，这就导致了故障诊断的不确定性。

2)动态症状-故障因果关系。虚拟节点和链路与底层节点映射的灵活性和动态性使得虚拟层网络和底层网络的因果关系变得不可预测。在多层网络中作为故障诊断基础的症状-故障因果关系是动态和不可预测的。

3)多层故障。多层网络服务性能的下降可能由于虚拟层或底层网络的部件故障引起的。由于底层网络部件和虚拟层网络部件存在映射关系，底层网络部件故障会导致对应的虚拟层网络部件故障。虚拟层网络部件和底层网络部件的映射关系使得多层网络故障定位变得更加复杂。因此，本文把虚拟层故障分为独立虚拟层故障和相关虚拟层故障。在虚拟层网络中由于软件错误引起的故障称为独立虚拟层故障。相关虚拟层故障是由底层部件的故障而引起的虚拟层故障，如果底层故障部件恢复正常了，相关虚拟层故障也就不存在了。

2 多层网络探测信息获取策略

2.1 被动监测策略

被动监测策略通过在网络设备上放置监测代理来监测网络。网络中的任意部件的故障将会由监测代理产生告警，接着告警被NMS作为负面症状来分析网络中故障部件的精确位置。由于NMS被动地等待监测代理发送告警，所以这种方法是被动性的。与传统网络相比，多层网络不仅具有底层网络还有抽象的虚拟层网络，因此多层网络的被动监测可逐层进行，即分别在底层网络和虚拟层网络采用被动监测策略建立模型，以此来定位出底层网络故障部件和虚拟层网络故障部件。

噪声的干扰会造成被动监测症状的丢失，或虚假症状的存在，因此多层网络的被动监测策略面临着如何获得和保持准确信息的挑战[1,6-7]，因为故障定位的准确性直接取决于所建模型中信息的准确性。

2.2 主动探测策略

主动探测策略与被动监测不同，通过在多个网络节点上配置探测站并沿着探测路径发送数据包(探测包)来测量探测站节点之间(端到端)的连通性以获取探测路径通过的网络部件的二进制状态信息[8]。探测路径两端的探测站节点为探测包的发送端和接收端。如果在探测路径发送端发送的探测包可以被接收端接收，则表明该探测路径是连通的，测试结果表示为“1”，即该探测路径通过的节点都是正常的；反之，该探测路径是不连通的，测试结果表示为“0”，即该探测路径上至少存在一个故障节点。与被动监测相比，主动探测中探测包的使用有助于NMS对于大量的网络故障事件反应更快、更精确，这与传统的被动接收告警的方法有着极大不同。由于探测站配置和探测路径选择的过程可以控制，所以主动探测是灵活的。

主动探测包括2种：预计划探测策略和适应性探测策略。预计划探测策略首次由Brodie等[9]提出，Brodie等解决的是单节点故障定位问题，通过使用依赖矩阵来解释探测选择问题，依赖矩阵D是 r×n矩 阵，其中，r是网络中探测路径的数量，n 是网络中节点的数量。如果探测 Pi经 过节点 Nj，矩阵元素 D(i,j)=1， 否则 D(i,j)=0。预计划探测策略需要解决的问题是：如何在给定的网络拓扑中构建合适的探测路径，使得网络中的每条节点发生故障时能够返回不同的测试结果。考虑花费问题，尽量少地部署探测站和构造探测路径也是此类问题的考虑方向。然而，Brodie等使用的预计划探测策略存在一些限制：只假设单个节点发生故障，未考虑测试结果丢失、虚假测试结果以及动态的探测路径等的影响。随后，Tapolcai等[10-13]采用预计划探测策略针对全光网络中的单链路和多链路故障提出多种故障定位方法。然而，这些方法只适用于小型网络。Xuan等[11]采用预计划探测策略提出的算法解决了大型网络中多个链路故障定位问题。由于多层网络具有多层故障，且底层部件的故障会导致虚拟层部件的故障，多层网络的预计划探测策略可逐层进行，即分别在底层网络和虚拟层网络采用预计划探测策略建立模型。首先，在底层网络中采用预计划探测策略定位出底层故障部件。其次，对底层故障部件进行故障恢复，则相关虚拟故障部件也被恢复。最后，在虚拟层网络中采用预计划探测策略来定位出独立虚拟层故障。适应性探测策略的使用在文献[9]中定义，由Natu等[6,13-14]进行了深入探究和论述，并在此基础上提出了基于确定性模型以及非确定性模型的适应性探测算法。在这种探测策略中，不是发送探测包来定位所有可能的故障，而是首先发送少量探测包来监测所有的网络部件的状态。这些探测包可以监测是否有故障发生，但不能够定位故障的确切位置。基于探测结果，首先识别出可能的故障区域，其次发送额外的探测包来精确定位故障的位置。适应性探测的主要目标是通过发送最少数目的探测包来精确地定位故障部件的位置。同样地，多层网络的适应性探测策略可逐层进行。主动探测策略本质上是通过测试端到端路径上的部件状态，与被动监测策略相比对故障响应更快，更灵活性，因此多层网络采用主动探测策略定位故障效率更高。主动探测策略具有明显的优势，但是在实际的使用过程中，网络需要发送大量的管理所需的流量，由于并不是所有的故障同时发生，所以大量的流量是浪费的。此外，发送较多数目的探测会产生延迟，很难得到最优的探测路径集合以及收集到精确的测试结果。上述缺点将导致故障定位率降低以及故障定位时间增加，因此综合考虑探测效率、探测代价的主动探测策略成为进一步亟待解决的问题。

2.3 主被动结合探测策略

主被动结合探测策略同时使用被动监测策略和主动探测策略，弥补了单一一种探测策略的不足。Tang等[15]采用主被动结合探测策略提出了主动集成故障推理(AIR)框架。如图3所示，主动集成故障推理过程包括3个功能模块：故障推理、保真度评价和行动选择。

3 多层网络故障定位模型

图 3 主动集成故障推理流程Fig. 3 Flow chart of AIR framework

故障推理模块把被动观察到的症状作为输入返回故障假设集 Φ作为输出。故障假设集 Φ包括一列假设 h1,h2,···,hp，其中每一个假设包括可以解释所有观察到的症状的故障集。然后把 Φ发送到保真度评价模块来检验任意的假设 hi∈Φ是否具有高保真度，如果具有高保真度，那么故障推理过程终止。否则，有助于解释具有最高保真度hi的一列未观察到的症状 SN被发送到行动选择模块来确定哪个症状已经发生。因此，保真度评价值 hi相应地调整。执行的行动返回测试结果，测试结果是已存的症状集 SV和不存在的症状集SU。基于行动返回的结果，对应的保真度值可能被增加或减少。如果新计算的保真度满足条件，那么推理过程终止，否则 SO、SU作为故障推理模块的新输入来生成一个新的假设。这个过程一直重复直到找到具有高保真度的假设。

多层网络具有多层故障，且底层部件的故障会导致虚拟层部件的故障，因此多层网络的主被动结合探测策略可逐层进行，即分别在底层网络和虚拟层网络采用主被动结合探测策略来定位出底层网络故障部件和独立虚拟层故障部件。行动选择的使用减少了由于噪声存在引起的症状丢失或虚假症状存在的可能性，主被动结合探测策略最小化探测的使用而且提高了多层网络故障定位的准确率。

2.4 终端用户观察策略

大多数多层网络探测信息获取策略要么需要网络监测代理被动搜集到的大量告警信息，要么使用探测来主动监控网络。然而，被动监控需要大量关于底层网络部件后验或先验故障概率信息，这在实际实践中限制了其有效性。采用主动探测策略监控网络会产生额外的流量消耗，这会给多层网络带来负担。因此，越来越多的研究者采用基于终端用户观察的探测信息获取策略[16-20]。终端用户观察不需要知道多层网络的先验或后验故障概率信息，仅仅使用终端用户观察到的服务负面症状找出可能发生的故障部件。

虽然多层网络的终端用户观察策略不需要网络监测代理被动搜集到的大量信息，或者使用探测来主动监控网络，但是由于并不是所有的终端用户都愿意共享服务状态信息，且可能存在恶意的终端用户共享错误的服务状态信息，因此不充足的终端用户观察和恶意终端用户会降低故障定位的精度。如何处理不充足的终端用户观察和识别出恶意的终端用户是该策略进一步的研究方向。

表1是各种探测信息获取策略在探测信息获取方式，是否增加网路流量及花费，优缺点和面临的挑战等方面对现有的多种探测信息获取策略进行的比较分析。

3.1 依赖矩阵模型

多层网络依赖矩阵模型描述了采用主动探测策略时底层网络和虚拟层网络中探测路径与其通过的网络部件状态(节点或链路)之间关系。根据网络部件状态是否为二进制状态(正常“0”，或故障“1”)，可以将多层网络的依赖矩阵模型分为二进制依赖矩阵模型[21-23]和非二进制依赖矩阵模型[24-27]。二进制依赖矩阵模型假设多层网络部件和探测路径只有正常和故障2种状态，且假设探测路径状态是正常的当且仅当这条路径上的所有部件都是正常状态。非二进制依赖矩阵模型不仅可以定位出多层网络故障部件而且可以判定多层网络节点、链路的拥塞程度或链路延迟。

表 1 各种探测信息获取策略的比较Table 1 Comparison of various detection information acquisition techniques

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)的使用。这个模型的基本思想是，通过使用CBR减少基于BN相关的故障诊断方法的内在复杂性来简化和优化故障诊断过程。在诊断过程中，BN结构的子集通过CBR来识别，在子集中只推理观测到变化的节点。CBR的使用有助于利用先前学到的情况来解决目前的以及未来的问题。随着时间的推移，CBR的知识库不断更新，有助于提高诊断的效率。通过使用混合模型加速了故障诊断过程以及减少了与推理相关的计算复杂度。

使用基于图论的故障传播模型的故障定位方法面临着如何获得和保持准确信息的挑战[6,14]，因为故障定位的准确性直接取决于模型中信息的准确性。一些研究人员[31-33]利用建立非确定性故障传播模型将信息的动态相关性纳入模型中。Rish等[34]和Steiner等[31]建立动态贝叶斯网络模型来表示网络部件状态随时间的变化情况。动态BN网络模型通过引入时间片的概念和时间片之间的转移概率 P(Xt|Xt-1)对静态BN网络模型进行扩展， Xt=(xt1,xt2,···,xnt)表示节点在时间片t的状态向量。然而，“动态”表示动态的系统，而不是随时间变化的系统，DBN模型是非时变的，DBN模型具有马尔科夫特性，即给定当前的状态，网络将来的状态与它过去的状态是独立的。时间片内的依赖关系用静态贝叶斯模型来描述。DBN模型是一个平稳过程，即转移概率和时间片内依赖关系不随时间的变化而变化。布 P(Xt-1) 以及在时间片t 的 观测值 Yt，可以应用标准的BN模型推断算法来计算 P(Xt|Xt-1,Yt)，其中

一旦给定动态的BN模型，基于先验概率分Yt是在时间t观测到的症状集。由于DBN模型的时间复杂度很高，文献[35]提出了高效的近似算法来解决这个问题。为了减少控制开销，应用网络分区策略。目前的分区策略包括基于分簇的策略和基于图分割的策略，这些策略的使用有助于减少通信开销和控制开销。Li等[36]通过使用分簇策略建立动态贝叶斯网络模型来减少故障推理的时间复杂度，即使用DBN模型来表示大型IP网络的状态，将故障节点划分为独立的分簇来减少诊断时间。由于故障节点间的条件具有独立性，对故障节点进行分簇是可行的。然而分簇的使用降低了故障诊断的准确性。

3.3 症状-故障-行动模型

症状-故障-行动模型(SFA模型)是一个5元组(S,F,A,E1,E2)， 其中故障集 F 、症状集S、行动集A是3个互相独立的顶点集。

如图4所示，症状-故障-行动模型表示的关系：对于每个行动，与之联系起来的是行动顶点ai∈A；对于每个症状，与之联系起来的是症状顶点 si∈S；对于每个故障，与之联系起来的是故障顶点 fi∈F ；对于每个故障fi，与之关联的边的权重等于 p(si|fi)， 表示症状 si由它造成。对于每个行动ai，与之关联的边的权重等于行动花费，表示行动验证症状存在的可能性。故障-症状-行动模型采用 了主被动结合探测策略，弥补了单一探测的不足。

图 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)模型来定位出所有的故障部件。

O-AIR包括3个功能模块：症状挖掘、故障推理和行动选择。基于ONP，症状挖掘模块使用观察到的overlay症状来动态地创建O-SFA模型。故障推理模块把O-SFA作为输入，返回故障假设h作 为输出。故障假设 h包括一组能解释所有观察到的症状的部件。选择对应的overlay行动来验证假设。如果 h中的所有故障都得到验证，那么overlay故障诊断过程终止并进行故障汇报。反之，基于行动结果，通过除去不能解释的overlay症状和不相关的部件并且增加新的症状及与之相关的部件来更新之前创建的O-SFA。该过程一直重复直到找到可验证的假设。

图5是对应于图1中overlay网络中的overlay链路和overlay路径。图5中的overlay网络有2条overlay路径：在overlay节点 D 和 E之间的路径 PDE和在overlay节点 A 和 B 之间的路径 PAB。overlay路径 PDE包含2条overlay链路 lDC和 lCE；类似地，overlay路径 PAB包 含2条overlay链路 lAC和lCB。 NDC、NCE、NAC、NCB表示底层网络部件。图6表示的是对应于图5的overlay网络的O-SFA模型。O-SFA模型中， Oi表示每一条overlay路径对应的症状， Sj表示每条overlay链路对应的路径，Fk表示overlay或其对应的underlay节点的故障，al表示验证症状的行动节点。

图 5 overlay网络中的overlay链路和overlay路径Fig. 5 overlay network showing overlay paths and links

图 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路径上的所有部件的集合。使用负面症状作为证据构造可能发生的故障部件集合，即故障假设集。使用Dempster-Shafer理论评价故障假设集中的每个故障进而使用评价的不确定性来量化部件故障发生的可能性。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路径提供更多有价值的信息。

图 7 overlay网络的2种可能的配置Fig. 7 Sample topology with two possible placements of an overlay network

综合这3种思想，配置算法的目标是最大化配置质量即度量q。算法始于overlay到底层网络的随机配置，通过作一些较小的调整来逐渐提高q。这个方法利用了overlay设计的灵活性来最大化overlay网络的诊断能力。

4.5 动态贝叶斯模型

为了保证在网络虚拟化环境下诊断算法的性能，克服强动态性特点带来的问题，Rahman等[44]综合考虑动态环境对网络模型、网络状态、故障先验概率等方面的影响，采用动态贝叶斯网络模型对网络虚拟化环境下的故障诊断问题进行建模，提出动态环境下的虚拟网故障诊断算法。算法的主要过程包括时间信息处理、噪声处理、故障定位、计算后验概率和执行更新。算法的步骤如下。

1)时间信息处理。假设时间片1的模型为FFDDMMF2(D(FMFi1,ti,,(2S F,Sii,,t1i,,,2P S,PFi,i1F,t,,i,P2P,FFPii,,1Ft,,Si,P2i,,tS)Fi。i,,21),S，i,1最)，终时合间成片的2期的望模模型型为为

2)噪声处理。去除噪声共分为2个步骤：先根据症状与故障之间的关系，过滤掉虚假故障；再根据症状之间的关系，过滤掉被动症状。

3)诊断算法。通过分析观测到的症状So，t，找出

故障

一

的

系

集

列合可)能，

通

解过释计当算前假症设状集的合假的设信集度合

B

H(H

it(it,一So

组

,t)，输出信度最大的一个或者多个假设的集合作为最终定位结果。

4)计算后验概率和执行更新。为了提高动态环境下的故障诊断算法性能，在每个时间片诊断结束后，修正每个时间窗口内的先验故障概率。对于每一个故障节点，使用贝叶斯公式计算其后验概率，利用后验概率和传播概率，更新当前节点故障的概率，将本次计算结果作为下一个时间片的先验概率，然后进入下一个时间片继续处理。

使用动态贝叶斯模型的故障诊断方法面临的挑战如下。

1)故障探测中考虑时间信息处理的动态贝叶斯模型计算复杂度高。使用基于时间信息处理的动态贝叶斯模型在时间片内是静态贝叶斯网络模型。这种方法可以处理各种不同的动态系统，但是静态贝叶斯网络模型本身的复杂度会增加动态贝叶斯网络模型的计算复杂度。

2)故障诊断精度不高的问题。在DBN模型中，可以拆分故障节点为独立的簇来减少诊断时间和进行推断。然而簇的使用降低了故障诊断的精度。

3)网络虚拟化的动态性特点容易造成网络模型知识不准确、网络信息传输时噪声增大等问题，给故障诊断带来挑战。

可以看出，现有工作在研究面向高动态网络的故障管理与定位方面充分考虑了状态的迁移、故障节点间的条件独立性、网络的规模和时间复杂度等方面。然而，过于复杂的定位技术在实际的网络管理和故障定位中并不具备通用性，并且已有方法均基于探测到的故障信息和事先收集的症状-故障关系以及假定网络状态或故障节点之间是独立的，而这些与实际信息网络的状态累积(如拥塞导致的故障)和网络互联(如网络中存在的数据流)的本质有些是不相符的。因此，重新考察与验证状态或节点之间的独立性，建立面向实际网络的通用故障定位技术，提高故障定位算法的运行速度和准确性，将成为本研究领域的核心问题。

5 开放性研究问题和未来研究方向

综合上述分析，现有故障定位技术相关研究的不足和亟待进一步研究解决的问题如下。

1)现有的故障定位模型对于资源映射特性的考虑有待完善，研究虚拟网络的故障定位模型还非常有限。已有的研究工作仍然缺乏对信息获取和模型建立过程的研究。由于信息获取的复杂性以及与之相关的诸多问题，建立精确的网络模型被认为是一个独立的过程，而且大多数的研究方案假设上述模型是事先存在的。随着新的网络环境部署，在很长一段时间内，已有的或遗存的网络环境仍然会与新技术共存，网络管理方案应该能够管理网络的异构性。此外，基于网络的服务通常会穿越已有的或新的网络、物理的或虚拟的网络部件，因此异构网络部件的共存需要从端到端的角度实现网管系统的无缝管理。

2)网络的动态性、探测效率、探测代价、网络开销等约束关系难以权衡，研究高动态网络特性的故障探测信息获取技术仍然是一个空白区域。使用探测来诊断网络需要在网络中的一个或多个位置上放置探测站，接着选择探测瞄准不同的网络节点和链路。探测站需要探测编码的安装、操作、维护，探测包的发送需要额外的网络流量花费以及收集、存储和分析测试结果，探测站和探测路径的部署增加了网络管理的花费。未来的可行方法是优化探测站的选择和探测路径数量的设定并最小化监测花费，提出综合考虑探测效率、探测代价的探测信息获取技术。为了适应基础设施的频繁变化，有必要建立基于预测思想的下一代网络管理系统。该系统不仅具有检测和定位的功能，还应当从最近的网络部件状态信息中捕捉和预防故障的发生，提供更好的网络稳定性和服务交付，以及网络管理(如资源提供、监控、分析与通知等)一体化解决方案。

3)现有的故障定位中的独立性假设较强，设计面向不同定位需求的通用故障定位算法仍然充满挑战。近年来，虽然已经出现了多种近似的解决方案，但权衡网络故障诊断准确性和网络控制开销仍然是一个挑战性的问题。目前为止，还没有直接的证据证明网络状态前后之间或故障节点之间的独立性假设的合理性，更没有建立面向实际网络的通用故障定位技术。同时针对不同的业务需求，需要进一步降低概率推理近似算法的复杂度，提高故障定位算法的运行速度和准确性仍旧充满挑战。

因此，针对上述问题未来可研究面向虚拟异构信息网络的故障诊断方法。从故障定位模型、信息获取方式、故障定位计算、网络异构性、运行效率与成本等方面入手，设计一个面向异构多层信息网络的故障探测与定位体系。需要充分考虑信息获取的复杂性、网络新老技术的共存性和故障定位模型的真实性，建立面向虚拟网络的故障定位新模型；将优化探测站的选择和探测路径数量的设定，研究综合考虑探测效率、探测代价、网络开销等约束的高动态虚拟网络故障探测信息获取新技术；此外，研究并验证状态或节点之间的关系，设计面向不同业务需求的通用故障定位算法，进一步提高故障定位算法的运行速度和准确性。在上述体系结构下，可以致力于基于预测思想的下一代网络管理系统，该系统不仅具有故障监测和定位的功能，还应当从最近的网络部件状态信息中捕捉和预防故障的发生。

6 结束语

本文总结和研究了多层信息网络的定位问题，从故障定位模型、信息获取方式、故障定位计算、网络异构性、运行效率与成本等方面入手，充分研究了多层网络故障定位方法，分析了各种方法的优缺点。最后，对现有故障定位方法相关研究的不足和亟待进一步研究解决的问题进行了总结，并指出了未来的研究方向。