网络中多节点故障定位的探测路径选择算法

齐小刚，汪直平，李家慧，刘立芳

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

有效的故障管理方法是保证网络可靠运行的基础。在大规模网络中，由于故障的负面影响，一个设备的故障可能会导致多个设备相继发生故障。及时检测并定位出故障是进行故障恢复的前提，能够减少故障造成的代价。现有的故障检测技术主要分为3 类：被动监测、主动探测和网络层析成像。被动监测技术通过部署在网络设备上的监视代理产生警报来为网络管理系统提供故障信息。主动探测技术通过发送称为探针的数据包来执行网络监视，能够检测网络的异常并及时定位异常的根源。主动探测又分为预计划探测与自适应探测两种[1-5]。自适应探测将故障诊断过程划分为故障检测和故障定位。在故障检测过程中，探测站发送的探针能够检查网络中所有组件的健康状况。确定了可疑的故障区域，将发送额外的探针达到故障定位的目的。与预计划探测相比，自适应探测更加灵活且开销较小。网络层析成像技术是一种用于监测链路性能的方法。该方法通过端到端测量来识别加性链路指标，如延迟、损失率等，为网络监测、负载均衡和故障诊断提供了高效的方式。

Natu 等[4]最先提出了基于自适应探测技术的探针选择算法。该算法主要包括贪婪故障检测算法GFD 和贪婪故障定位算法GFL，能够很好地用于检测和定位网络中的少量节点故障。Lu 等[6]提出了一种新的故障检测方法，目的是为了减轻基于主动探测引起的网络开销。该方法将整个网络的检测过程分为几个阶段。在每个阶段，只使用少量探针检测网络中的部分节点。Zheng 等[7]提出了一种最小化探测成本的探测路径选择方法。该方法选择一组探测路径，这些路径对于实现可识别性和覆盖无法识别的目标链路最有用。Gyimothi 等[8-9]研究了单节点故障定位的探测路径分配问题，提出了递归匹配收缩算法 RMCA 来定位网络中的任何单个节点故障。Lin 等[10]考虑最小化探针的数量和链路负载，并提出了一种选择探测路径的新方法。该方法对贪婪算法进行参数化，用来在探针数量和网络组件负载这两个目标上面达到平衡。Dusia 等[11]提出了一种探针生成算法来生成候选探针集，从算法生成的候选探针集里选择探针能够降低监视网络的成本。在最近的研究中，Tayal 等[12]认为应该将探针的长度限制在某个常数K上以减少探针的往返时间，并提出了根据网络中的链路流量测量结果动态地选择探针进行故障检测。

在多故障定位的研究中，Wu 等[13-17]针对全光网络中的共享风险链路组(shared risk link group,SRLG)故障定位问题提出了几种方法。然而，这些方法只适用于小规模网络中的链路故障定位。Xuan 等[18]提出了随机游走算法RWL 来解决大规模网络中的多链路故障定位问题。该算法可扩展到多节点故障定位问题中，通过随机游走构造一个探测路径与节点相关的d-分离矩阵，然后使用探针定位多节点故障。然而这种非适应性方法造成的误判率和探测成本较高，无法满足多节点故障定位的要求。Ma 等[19]首先研究了使用网络层析成像的方法来识别通信网络中所有链路的问题，并提出了最少监视器布置算法MMP。在此基础上，大量研究[20-22]将监视器放置问题扩展到静态和动态通信网络中的优先链路层析成像。此外，Ma 等[23]将网络层析成像技术运用于多节点故障定位的监视器布置问题中。

本文针对现有故障定位算法在多节点故障定位中准确率低、探测成本高的问题，提出了基于主动探测的探测路径选择算法。该算法结合了贪婪路径选择和禁忌链路搜索两种方法，能够根据每次的探测结果更新候选路径集以选择最合适的探测路径进行故障定位。在故障检测过程中，使用贪婪路径选择算法为探针选择探测路径减少故障检测的成本。在故障定位过程中，使用禁忌链路搜索算法为每个可疑节点选择最合适的探测路径提高成功定位率。

1 基本概念

1.1 问题描述

假设网络拓扑是已知的，并将其建模为无向连通图G=(V,E)，其中V，E分别表示节点集和边集。网络中一些节点被选择为探测站节点用来放置探测站，能够发送被称为探针的探测数据包并收集探测结果。探测站布置的基本要求是能够发送探针探测到所有节点。用于故障检测和定位的探针能够沿着指定的探测路径进行传输并检测路径上的所有节点。在主动探测方法中，探针的长度决定了探针探测的往返时间。在实际网络中，探针的长度应该根据实际需求进行限制以减少探测时间。显然地，探针长度的阈值K的值越大，探测成本可能越小，但是探测时间会增加。我们假设所有的探测站节点都为正常节点，并且探测数据包对节点的影响可以忽略不计。我们定义多节点故障定位的问题如下所示，其中探测成本定义为用于故障检测和定位的探测路径的数量。

定义1(多节点故障定位) 给定无向连通图G=(V,E)和一组探测站节点PS，其中V表示节点集，E表示边集。假设V中的k(k>1)个节点发生故障，选择一组最少数量的探测路径并发送探针来识别出所有故障节点。

图1 显示了在不同网络中使用现有探测路径选择算法选择探测路径识别目标节点。在图1(a)中，当节点4、5 和8 发生故障时，探测站节点1和2 沿着探测路径p18(1-5-8)和p28(2-4-6-8)发送探针无法定位出节点8 的故障。然而，探测站节点3 沿着探测路径p37(3-7-8)可以明确定位出节点8 的故障。在图1(b)中，选择不合适的探测路径p25(2-3-4-5)和p65(6-4-5)进行故障定位会导致节点5 的状态无法被识别出，因为在选择的探测路径上存在故障节点4。

图1 选择探测路径识别目标节点Fig.1 Selecting probing paths to identify the target node

1.2 候选路径权重

在选择探测站节点后，可以通过计算探测站节点到其余节点的最短路径生成候选路径集CP。在以往的方法中，使用了最大搜索、最小搜索和二进制搜索从候选路径中选择探测路径，忽略了探测数据包对链路负载的影响。因此，从候选路径集中选择探测路径之前，我们首先定义探测路径p的权重：

式中：n(l)代表当前已选择探测路径经过边l的次数；L(p)代表路径p上的所有链路集合。在故障检测过程中，|M(p)|代表候选探测路径p上所有未被覆盖节点的数量。在故障定位过程中，|M(p)|代表候选探测路径p上所有可疑节点的数量。

2 探测路径选择算法

2.1 贪婪路径选择

故障检测是网络中故障诊断的第一步。为了保证网络的正常运行，需要快速、准确的故障检测方法。在自适应探测方法中，故障检测的目地是找到网络中可能出现故障的区域，从而减少用于准确定位故障节点的探针数量。应该选择适当的探测路径，以便在网络中存在故障时，发送的探针可以检测到故障。探测路径选择问题是NP难的，常用贪婪算法来近似求解。

算法1 给出了用于故障检测的贪婪路径选择算法。该算法使用Dijkstra 最短路径算法计算所有可能的候选探测路径。对于每条候选探测路径，使用式(1)为其计算一个权重。在每次选择探测路径过程中，选择的探测路径具有最小的权重。探针的传输会对网络中的节点和链路造成额外的开销。权重较小的探测路径意味着发送的探针对网络中的节点和链路产生较小的干扰，且能够尽可能多地覆盖未覆盖的节点。算法迭代地选择探测路径直到网络中的所有节点都至少被一条路径所覆盖。沿着探测路径发送的探针能够检测出故障可能发生的区域。如果一个节点故障，则通过该节点的所有探针将失效。

算法1 故障检测的贪婪路径选择算法

图2 显示了在包含6 个节点的简单网络中使用贪婪路径选择算法选择探测路径进行故障检测，其中节点1 和4 为探测站节点。通过Dijkstra 最短路径算法计算出了一组候选路径CP={p12,p13,p14,p15,p16,p42,p43,p45,p46}，其中pij表示探测站节点vi到节点vj的最短路径。算法首先选择具有最小权重的候选路径p45(4-3-6-5)。为了覆盖剩余未覆盖的节点1 和2，从剩余候选路径集中选择权重最小的路径p12(1-2)。此时，所有节点都被选定的探测路径覆盖。因此，沿探测路径p45和p12发送的两个探针可以检测该网络中的任何节点。

图2 选择探测路径进行故障检测Fig.2 Selecting probing paths for fault detection

2.2 禁忌链路搜索

在以前的方法中，使用最大搜索或最小搜索选择的探测路径仅适用于定位单节点故障。当故障节点较多时，所选探测路径可能会遍历多个故障节点，导致发送的探针无法准确定位多个节点故障。

考虑到一些难以被识别的节点，以前的探测路径选择方法不能满足多节点故障定位的要求。一种可能的解决方案是根据探测结果不断更新候选探测路径集并选择更合适的探测路径。如果沿着选定的探测路径发送的探针能够识别出所有故障节点，那么算法将停止并返回故障节点。否则，为剩余可疑节点生成新的候选路径集并选择探测路径，直到识别出所有故障节点或新的候选路径集为空。

算法2 给出了用于故障定位的禁忌链路搜索算法。网络中的所有节点可以被分为3 类：正常节点、故障节点和未知节点。在故障检测中，使用算法1 选择一组探测路径并发送探针来检测网络中的所有节点。故障检测的探针结果将作为故障定位算法的输入。首先将正常探针和故障探针经过的节点分别加入到正常节点集No和可疑节点集Ns中。故障定位的任务就是从可疑节点集中识别故障的节点。算法通过计算每个探测站节点到每个可疑节点的最短路径来生成候选路径集CP 并使用式(1) 计算每条候选路径的权重。如果某些可疑节点不能被任何候选路径经过，则这些可疑节点是未知节点，例如孤立节点。为了尽可能多地识别出故障节点，算法依次选择具有最小权重的候选路径来发送探针。根据故障节点的判定条件，如果故障探针经过的节点中只有一个可疑节点，则该可疑节点必为故障节点。确定一部分故障节点后，将网络中所有与故障节点关联的边加入到禁忌表T中。在下一次的候选路径生成中，算法为剩余的可疑节点生成更合适的候选路径。总之，禁忌链路搜索算法通过禁止搜索与故障节点相连的链路来多次生成候选路径集并选择探测路径，以实现多节点故障定位的目的。

算法2 故障定位的禁忌链路搜索算法

图3 显示了在包含8 个节点的网络中使用禁忌链路搜索算法选择探测路径进行故障定位的过程，其中节点2 是探测站。假设网络中的节点4、5 和7 发生故障。最初，故障节点的位置和数目是未知的。故障检测阶段的探测结果显示了节点4、5 和7 为可疑节点。如图3(a)所示，通过计算探测站节点到可疑节点的最短路径生成候选路径集CP={p24,p25,p27}。算法首先选择权值最小的候选路径p27(2-4-7)。沿该路径发送的探针无法识别节点4 和节点7。然后，算法依次选择路径p24(2-4)和p25(2-5)分别将节点4 和节点5 识别为故障节点。此时，候选路径集CP=Ø，可疑节点集Ns={7}。为了识别可疑节点7，算法生成一个新的候选路径集。如图3(b) 所示，算法将链路l1、l2、l3和l4加入到禁忌表T中，并生成一个新的候选路径集CP={p27}。通过选择探测路径p27(2-3-6-8-7)来达到识别故障节点7 的目的。因此，故障节点集Nf={4,5,7}。对于复杂的大规模网络，探测路径选择算法为识别大量故障节点提供了可能。

图3 选择探测路径进行故障定位Fig.3 Selecting probing paths for fault localization

3 实验与分析

为了验证探测路径选择算法的有效性，本文在随机生成的网络拓扑和真实网络拓扑上仿真并比较了以下3 种算法。1) 探测路径选择算法(PPSA)：本文提出的一种结合贪婪路径选择和禁忌链路搜索的自适应故障定位算法。2) 随机游走算法(RWL)：Xuan 等[18]提出的一种通过随机游走生成探测路径的非适应性故障定位算法。3)贪婪故障定位算法(GFL)：Natu 等[4]提出的一种用于定位少量节点故障的自适应故障定位算法。本文设置探针长度的阈值为K=8 并选择两个节点作为探测站节点，使得探测站节点能够在8 跳以内到达最多数量的其余节点且探测站节点的度最大。

3.1 BA 无标度网络上的实验

我们比较了3 种算法在随机生成的BA 无标度网络中的性能。BA 无标度网络具有现实世界中的大多数网络的增长方式，能够反映真实网络的特性。性能比较使用的指标有：成功定位率，假阳性率和探测成本。仿真结果图中的每个点都是在不同网络拓扑上进行共20 次实验之后取平均值绘制而成的。

图4 显示3 种算法在节点故障率为0.01～0.1下的成功定位率、假阳性率和探测成本比较。生成的网络拓扑都包含200 个节点，且平均节点度为3。可以看出，随着故障节点数的增加，探测路径选择算法比随机游走算法具有更高的成功定位率和更低的假阳性率。除此之外，由于随机游走算法是一种非适应性故障定位算法，探测成本远高于探测路径选择算法。与已有的贪婪故障定位算法相比，本文提出的算法在多故障节点的成功定位率上有了很大的提升，但是探测成本也略微增加。如图4(a)所示，当节点故障率增加时，本文提出的算法与贪婪故障定位算法相比能够将节点故障的成功定位率提升10%以上。

图4 3 种算法的比较结果Fig.4 Comparison results of the three algorithms

图5 显示了在不同规模的网络中探测路径选择算法的探测成本随节点故障率的变化情况。随着故障节点数目的增加，在故障定位阶段选择的探测路径也会增加。为了验证探测路径选择算法在不同节点数量的网络中的性能，接下来在随机生成的节点数为100～1 000，平均节点度分别为3、4 和5 的网络中进行实验，其中节点故障率被设置为0.1。图6(a)中的结果显示，当节点故障率为0.1 时，探测路径选择算法在不同规模的网络中的成功定位率均能保持在90%以上。当网络平均节点度较大时，故障定位的成功率也较高。图6(b)显示了探测路径选择算法在不同规模的网络中故障定位的探测成本的变化情况。可以看出，对于节点度较大的网络，算法的探测成本也较高。

图5 本文算法在不同规模网络中的探测成本Fig.5 Probing cost of the algorithm in this paper in different scale networks

图6 本文算法在不同规模网络中的性能Fig.6 Performance of the algorithm in this paper in different scale networks

3.2 真实网络上的实验

为了展示本文算法可以很好地扩展到真实网络上，本文使用了阿德莱德大学开发的网络拓扑结构数据集[24]中的2 个网络拓扑(GEANT、GTS CE) 和华盛顿大学的火箭燃料项目[25-26]导出的6 个网络拓扑(AS3967、AS1755、AS1221、AS6461、AS3257、AS1239)进行实验。这些拓扑反映了互联网的真实连通性，被广泛应用于相关研究中。表1 显示了每个拓扑的节点数、链路数和平均度。

表1 真实网络拓扑Table 1 Real network topologies

在这8 个真实网络拓扑中，仿真验证了3 种算法的成功定位率和探测成本。对于每一个拓扑，将节点故障率设置为0.1。表2 和表3 分别给出了3 种算法在8 个真实网络拓扑上的成功定位率和探测成本。可以看出，本文提出的探测路径选择算法与其他算法相比具有较高的成功定位率和较低的探测成本。虽然探测成本稍微高于贪婪故障定位算法，但是成功定位率却大大提升。

表2 算法的成功定位率比较Table 2 Comparison of successful localization ratios of algorithms

表3 算法的探测成本比较Table 3 Comparison of probing costs of algorithms

4 结束语

本文提出了一种有效的探测路径选择算法来解决网络中的多节点故障定位问题。该算法实现的原理是基于主动探测技术为故障检测和故障定位选择最合适的探测路径。用于故障检测的贪婪路径选择算法在选择最少数量探测路径进行故障检测的同时减少探测数据包对链路负载的影响。用于故障定位的禁忌链路搜索算法通过构造禁忌表多次生成候选路径集，能够显著提高故障节点的成功定位率。在BA 无标度网络上的仿真结果表明，与现有故障定位算法相比，本文算法能够显著提高多节点故障的成功定位率并降低探测成本。在真实网络拓扑上的仿真验证了探测路径选择算法能够很好地扩展到实际网络中。在之后的研究中，将在故障检测和定位中引入探针长度和节点负载等参数以满足实际故障诊断需求。