第16卷第4期 智能系统学报 Vol.16 No.4 2021年7月 CAAI Transactions on Intelligent Systems Jul.2021 D0:10.11992/tis.202010007 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20210408.1611.004html 网络中多节点故障定位的探测路径选择算法 齐小刚，汪直平1，李家慧，刘立芳 (1.西安电子科技大学数学与统计学院，陕西西安710126；2.西安电子科技大学计算机学院，陕西西安 710071) 摘要：针对现有故障定位技术不能满足多节点故障定位的要求，尤其当网络中存在大量故障节点时，提出了 一种基于主动探测的探测路径选择算法。该算法主要包括用于故障检测的贪焚路径选择算法和用于故障定位 的禁忌链路搜索算法。在故障检测阶段，使用贪婪路径选择算法迭代地选择具有最小权重的探测路径覆盖网 络中的节点。在故障定位阶段，使用禁忌链路搜索算法多次生成候选路径集以选择最合适的探测路径来解决 多节点故障定位问题。在随机网络拓扑和真实网络拓扑上的仿真结果表明，与现有的节点故障定位算法相比， 探测路径选择算法具有更高的成功定位率和更低的探测成本。 关键词：多节点故障定位；主动探测；探测路径选择；贪婪路径选择；禁忌链路搜索；成功定位率；探测成本 中图分类号：TP393文献标志码：A文章编号：1673-4785(2021)04-0766-08 中文引用格式：齐小刚，汪直平，李家慧，等.网络中多节点故障定位的探测路径选择算法J小.智能系统学报，2021,16(4)： 766-773. 英文引用格式：QI Xiaogang,.VANG Zhiping,.LI Jiahui,etal.Probing path selection algorithm for multi-node failure localization in networks J.CAAI transactions on intelligent systems,2021,16(4):766-773. Probing path selection algorithm for multi-node failure localization in networks QI Xiaogang',WANG Zhiping',LI Jiahui',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:A probing path selection algorithm based on active probing is proposed to solve the problem of existing fault localization algorithms'inability to meet the requirements of multi-node failure localization,especially when a large number of failed nodes are present in the network.The algorithm mainly includes the greedy path selection algorithm for fault detection,which is used to iteratively select the probing path with the minimum weight to cover the nodes in the network,and the tabu link search algorithm for fault localization,which is used to generate the candidate path set mul- tiple times to select the most suitable probing paths and thus solve the problem of multi-node failure localization.Simu- lation results on random network topologies and real network topologies show that the probing path selection algorithm has a higher successful localization ratio and lower probing cost than the existing node failure localization algorithms. Keywords:multi-node failure localization;active probing;probing path selection;greedy path selection;tabu link search;successful localization ratio;probing cost 有效的故障管理方法是保证网络可靠运行的 收稿日期：2020-10-13.网络出版日期：2021-04-09. 基金项目：国家自然科学基金项目(61877067.61572435)：西安 基础。在大规模网络中，由于故障的负面影响， 市科技创新项目(201805029YD7CG13-6):近地面探 测实验室科学技术基金项目(61424140402). 一个设备的故障可能会导致多个设备相继发生故 通信作者：汪直平.E-mail:1083150353@qq.com. 障。及时检测并定位出故障是进行故障恢复的前
DOI: 10.11992/tis.202010007 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20210408.1611.004.html 网络中多节点故障定位的探测路径选择算法 齐小刚1 ，汪直平1 ，李家慧1 ，刘立芳2 （1. 西安电子科技大学 数学与统计学院，陕西 西安 710126; 2. 西安电子科技大学 计算机学院，陕西 西安 710071） 摘 要：针对现有故障定位技术不能满足多节点故障定位的要求，尤其当网络中存在大量故障节点时，提出了 一种基于主动探测的探测路径选择算法。该算法主要包括用于故障检测的贪婪路径选择算法和用于故障定位 的禁忌链路搜索算法。在故障检测阶段，使用贪婪路径选择算法迭代地选择具有最小权重的探测路径覆盖网 络中的节点。在故障定位阶段，使用禁忌链路搜索算法多次生成候选路径集以选择最合适的探测路径来解决 多节点故障定位问题。在随机网络拓扑和真实网络拓扑上的仿真结果表明，与现有的节点故障定位算法相比， 探测路径选择算法具有更高的成功定位率和更低的探测成本。 关键词：多节点故障定位；主动探测；探测路径选择；贪婪路径选择；禁忌链路搜索；成功定位率；探测成本 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2021)04−0766−08 中文引用格式：齐小刚, 汪直平, 李家慧, 等. 网络中多节点故障定位的探测路径选择算法 [J]. 智能系统学报, 2021, 16(4): 766–773. 英文引用格式：QI Xiaogang, WANG Zhiping, LI Jiahui, et al. Probing path selection algorithm for multi-node failure localization in networks[J]. CAAI transactions on intelligent systems, 2021, 16(4): 766–773. Probing path selection algorithm for multi-node failure localization in networks QI Xiaogang1 ，WANG Zhiping1 ，LI Jiahui1 ，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: A probing path selection algorithm based on active probing is proposed to solve the problem of existing fault localization algorithms’ inability to meet the requirements of multi-node failure localization, especially when a large number of failed nodes are present in the network. The algorithm mainly includes the greedy path selection algorithm for fault detection, which is used to iteratively select the probing path with the minimum weight to cover the nodes in the network, and the tabu link search algorithm for fault localization, which is used to generate the candidate path set multiple times to select the most suitable probing paths and thus solve the problem of multi-node failure localization. Simulation results on random network topologies and real network topologies show that the probing path selection algorithm has a higher successful localization ratio and lower probing cost than the existing node failure localization algorithms. Keywords: multi-node failure localization; active probing; probing path selection; greedy path selection; tabu link search; successful localization ratio; probing cost 有效的故障管理方法是保证网络可靠运行的 基础。在大规模网络中，由于故障的负面影响， 一个设备的故障可能会导致多个设备相继发生故 障。及时检测并定位出故障是进行故障恢复的前 收稿日期：2020−10−13. 网络出版日期：2021−04−09. 基金项目：国家自然科学基金项目 (61877067，61572435)；西安 市科技创新项目 (201805029YD7CG13-6)；近地面探 测实验室科学技术基金项目 (61424140402). 通信作者：汪直平. E-mail：1083150353@qq.com. 第 16 卷第 4 期 智 能 系 统 学 报 Vol.16 No.4 2021 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2021
第4期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·767· 提，能够减少故障造成的代价。现有的故障检测 模网络中的多链路故障定位问题。该算法可扩展 技术主要分为3类：被动监测、主动探测和网络 到多节点故障定位问题中，通过随机游走构造一 层析成像。被动监测技术通过部署在网络设备上 个探测路径与节点相关的山分离矩阵，然后使用 的监视代理产生警报来为网络管理系统提供故障 探针定位多节点故障。然而这种非适应性方法造 信息。主动探测技术通过发送称为探针的数据包 成的误判率和探测成本较高，无法满足多节点故 来执行网络监视，能够检测网络的异常并及时定 障定位的要求。Ma等首先研究了使用网络层 位异常的根源。主动探测又分为预计划探测与自 析成像的方法来识别通信网络中所有链路的问 适应探测两种1。自适应探测将故障诊断过程 题，并提出了最少监视器布置算法MMP。在此基 划分为故障检测和故障定位。在故障检测过程 础上，大量研究202将监视器放置问题扩展到静 中，探测站发送的探针能够检查网络中所有组件 态和动态通信网络中的优先链路层析成像。此 的健康状况。确定了可疑的故障区域，将发送额 外，Ma等2)将网络层析成像技术运用于多节点 外的探针达到故障定位的目的。与预计划探测相 故障定位的监视器布置问题中。 比，自适应探测更加灵活且开销较小。网络层析 本文针对现有故障定位算法在多节点故障定 成像技术是一种用于监测链路性能的方法。该方 位中准确率低、探测成本高的问题，提出了基于 法通过端到端测量来识别加性链路指标，如延 主动探测的探测路径选择算法。该算法结合了贪 迟、损失率等，为网络监测、负载均衡和故障诊断 婪路径选择和禁忌链路搜索两种方法，能够根据 提供了高效的方式。 每次的探测结果更新候选路径集以选择最合适的 Natu等最先提出了基于自适应探测技术的 探测路径进行故障定位。在故障检测过程中，使 探针选择算法。该算法主要包括贪婪故障检测算 用贪婪路径选择算法为探针选择探测路径减少故 法GFD和贪婪故障定位算法GFL,能够很好地用 于检测和定位网络中的少量节点故障。Lu等 障检测的成本。在故障定位过程中，使用禁忌链 提出了一种新的故障检测方法，目的是为了减轻 路搜索算法为每个可疑节点选择最合适的探测路 基于主动探测引起的网络开销。该方法将整个网 径提高成功定位率。 络的检测过程分为几个阶段。在每个阶段，只使 1基本概念 用少量探针检测网络中的部分节点。Zheng等可 提出了一种最小化探测成本的探测路径选择方 1.1 问题描述 法。该方法选择一组探测路径，这些路径对于实 假设网络拓扑是已知的，并将其建模为无向 现可识别性和覆盖无法识别的目标链路最有用。 连通图G=(V,E),其中V,E分别表示节点集和边 Gyimothi等.y研究了单节点故障定位的探测路 集。网络中一些节点被选择为探测站节点用来放 径分配问题，提出了递归匹配收缩算法RMCA来 置探测站，能够发送被称为探针的探测数据包并 定位网络中的任何单个节点故障。Lin等o考虑 收集探测结果。探测站布置的基本要求是能够发 最小化探针的数量和链路负载，并提出了一种选 送探针探测到所有节点。用于故障检测和定位的 择探测路径的新方法。该方法对贪婪算法进行参 探针能够沿着指定的探测路径进行传输并检测 数化，用来在探针数量和网络组件负载这两个目 路径上的所有节点。在主动探测方法中，探针的 标上面达到平衡。Dusia等]提出了一种探针生 长度决定了探针探测的往返时间。在实际网络 成算法来生成候选探针集，从算法生成的候选探 中，探针的长度应该根据实际需求进行限制以减 针集里选择探针能够降低监视网络的成本。在最 少探测时间。显然地，探针长度的阈值K的值越 近的研究中，Tayal等认为应该将探针的长度 大，探测成本可能越小，但是探测时间会增加。 限制在某个常数K上以减少探针的往返时间，并 我们假设所有的探测站节点都为正常节点，并且 提出了根据网络中的链路流量测量结果动态地选 探测数据包对节点的影响可以忽略不计。我们定 择探针进行故障检测。 义多节点故障定位的问题如下所示，其中探测成 在多故障定位的研究中，Wu等：针对全光 本定义为用于故障检测和定位的探测路径的 网络中的共享风险链路组(shared risk link group, 数量。 SRLG)故障定位问题提出了几种方法。然而，这 定义1（多节点故障定位）给定无向连通图 些方法只适用于小规模网络中的链路故障定位。 G=(V,E)和一组探测站节点PS,其中V表示节点 Xuan等I阁提出了随机游走算法RWL来解决大规 集，E表示边集。假设V中的k(心1)个节点发生
提，能够减少故障造成的代价。现有的故障检测 技术主要分为 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) 个节点发生 第 4 期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·767·
·768· 智能系统学报 第16卷 故障，选择一组最少数量的探测路径并发送探针 2探测路径选择算法 来识别出所有故障节点。 图1显示了在不同网络中使用现有探测路径 2.1贪婪路径选择 选择算法选择探测路径识别目标节点。在图l(a) 故障检测是网络中故障诊断的第一步。为了 中，当节点4、5和8发生故障时，探测站节点1 保证网络的正常运行，需要快速、准确的故障检 测方法。在自适应探测方法中，故障检测的目地 和2沿着探测路径P1s(1-5-8)和p2x(2-4-6-8)发送探 是找到网络中可能出现故障的区域，从而减少用 针无法定位出节点8的故障。然而，探测站节点 于准确定位故障节点的探针数量。应该选择适当 3沿着探测路径P3(3-7-8)可以明确定位出节点 的探测路径，以便在网络中存在故障时，发送的 8的故障。在图1(b)中，选择不合适的探测路径 探针可以检测到故障。探测路径选择问题是NP P2(2-3-4-5)和P6s(6-4-5)进行故障定位会导致节 难的，常用贪婪算法来近似求解。 点5的状态无法被识别出，因为在选择的探测路 算法1给出了用于故障检测的贪婪路径选择 径上存在故障节点4。 算法。该算法使用Dijkstra最短路径算法计算所 有可能的候选探测路径。对于每条候选探测路 径，使用式()为其计算一个权重。在每次选择 探测路径过程中，选择的探测路径具有最小的权 重。探针的传输会对网络中的节点和链路造成额 外的开销。权重较小的探测路径意味着发送的探 针对网络中的节点和链路产生较小的干扰，且能 7 够尽可能多地覆盖未覆盖的节点。算法迭代地选 择探测路径直到网络中的所有节点都至少被一条 (a)识别成功 路径所覆盖。沿着探测路径发送的探针能够检测 出故障可能发生的区域。如果一个节点故障，则 通过该节点的所有探针将失效。 算法1故障检测的贪婪路径选择算法 输入网络G=(V,E),探测站PS; 输出一组用于故障检测的探测路径DP。 1)初始化未覆盖节点集合NPN=V-PS,DP-O, (b)识别失败 n(0=0,1eE; 2)对每一个探测站节点v,∈PS,使用Dijk 图1选择探测路径识别目标节点 Fig.1 Selecting probing paths to identify the target node stra最短路径算法计算节点，到节点v(i)的最 1.2候选路径权重 短路径P,并将其加人到候选路径集CP中； 在选择探测站节点后，可以通过计算探测站 3)当NPN≠O时，从CP中选择权值最小的候 节点到其余节点的最短路径生成候选路径集CP。 选路径p: 在以往的方法中，使用了最大搜索、最小搜索和 4)将路径p加入到探测路径集DP中； 二进制搜索从候选路径中选择探测路径，忽略了 5)从NPN中移除路径p上的所有节点； 探测数据包对链路负载的影响。因此，从候选路 6)for lEL(p) 径集中选择探测路径之前，我们首先定义探测路 7)(0=)+1 径p的权重： 8)end for n0 9)end while leL(p) 图2显示了在包含6个节点的简单网络中使 w(p)= Mpl,P∈CP (1) 用贪婪路径选择算法选择探测路径进行故障检 式中：n()代表当前已选择探测路径经过边I的次 测，其中节点1和4为探测站节点。通过Djk 数；L(p)代表路径p上的所有链路集合。在故障 stra最短路径算法计算出了一组候选路径CP= 检测过程中，M(P代表候选探测路径p上所有未 {P12,P13,P14P1s,P16,P2,P4,P4s,P6},其中Pg表示探 被覆盖节点的数量。在故障定位过程中，M(P代 测站节点’，到节点y的最短路径。算法首先选择 表候选探测路径p上所有可疑节点的数量。 具有最小权重的候选路径P4s(4-3-6-5)。为了覆盖
故障，选择一组最少数量的探测路径并发送探针 来识别出所有故障节点。 图 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。 2 1 5 6 4 8 3 7 (a) 识别成功 5 8 3 1 2 6 7 4 (b) 识别失败 图 1 选择探测路径识别目标节点 Fig. 1 Selecting probing paths to identify the target node 1.2 候选路径权重 在选择探测站节点后，可以通过计算探测站 节点到其余节点的最短路径生成候选路径集 CP。 在以往的方法中，使用了最大搜索、最小搜索和 二进制搜索从候选路径中选择探测路径，忽略了 探测数据包对链路负载的影响。因此，从候选路 径集中选择探测路径之前，我们首先定义探测路 径 p 的权重： w(p) = ∑ l∈L(p) n(l) |M (p)| , p ∈ CP (1) 式中：n(l) 代表当前已选择探测路径经过边 l 的次 数；L(p) 代表路径 p 上的所有链路集合。在故障 检测过程中，|M(p)|代表候选探测路径 p 上所有未 被覆盖节点的数量。在故障定位过程中，|M(p)|代 表候选探测路径 p 上所有可疑节点的数量。 2 探测路径选择算法 2.1 贪婪路径选择 故障检测是网络中故障诊断的第一步。为了 保证网络的正常运行，需要快速、准确的故障检 测方法。在自适应探测方法中，故障检测的目地 是找到网络中可能出现故障的区域，从而减少用 于准确定位故障节点的探针数量。应该选择适当 的探测路径，以便在网络中存在故障时，发送的 探针可以检测到故障。探测路径选择问题是 NP 难的，常用贪婪算法来近似求解。 算法 1 给出了用于故障检测的贪婪路径选择 算法。该算法使用 Dijkstra 最短路径算法计算所 有可能的候选探测路径。对于每条候选探测路 径，使用式 (1) 为其计算一个权重。在每次选择 探测路径过程中，选择的探测路径具有最小的权 重。探针的传输会对网络中的节点和链路造成额 外的开销。权重较小的探测路径意味着发送的探 针对网络中的节点和链路产生较小的干扰，且能 够尽可能多地覆盖未覆盖的节点。算法迭代地选 择探测路径直到网络中的所有节点都至少被一条 路径所覆盖。沿着探测路径发送的探针能够检测 出故障可能发生的区域。如果一个节点故障，则 通过该节点的所有探针将失效。 算法 1 故障检测的贪婪路径选择算法 输入 网络 G=(V, E)，探测站 PS； 输出 一组用于故障检测的探测路径 DP。 1) 初始化未覆盖节点集合 NPN=V−PS，DP=Ø， n(l)=0，l∈E； 2) 对每一个探测站节点 vi∈PS，使用 Dijkstra 最短路径算法计算节点 vi 到节点 vj (i≠j) 的最 短路径 pij，并将其加入到候选路径集 CP 中； 3) 当 NPN≠Ø时，从 CP 中选择权值最小的候 选路径 p； 4) 将路径 p 加入到探测路径集 DP 中； 5) 从 NPN 中移除路径 p 上的所有节点； 6) for ∀ l∈L(p) 7) n(l)=n(l)+1 8) end for 9) end while 图 2 显示了在包含 6 个节点的简单网络中使 用贪婪路径选择算法选择探测路径进行故障检 测，其中节点 1 和 4 为探测站节点。通过 Dijkstra 最短路径算法计算出了一组候选路径 CP= {p12, p13, p14, p15, p16, p42, p43, p45, p46}，其中 pij 表示探 测站节点 vi 到节点 vj 的最短路径。算法首先选择 具有最小权重的候选路径 p45(4-3-6-5)。为了覆盖 ·768· 智 能 系 统 学 报 第 16 卷
第4期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·769· 剩余未覆盖的节点1和2，从剩余候选路径集中 一部分故障节点后，将网络中所有与故障节点关 选择权重最小的路径P12(1-2)。此时，所有节点都 联的边加入到禁忌表T中。在下一次的候选路径 被选定的探测路径覆盖。因此，沿探测路径 生成中，算法为剩余的可疑节点生成更合适的候 P4s和P2发送的两个探针可以检测该网络中的任 选路径。总之，禁忌链路搜索算法通过禁止搜索 何节点。 与故障节点相连的链路来多次生成候选路径集并 选择探测路径，以实现多节点故障定位的目的。 算法2故障定位的禁忌链路搜索算法 输入故障检测的正常探针集NP和故障探 针集FP; 输出故障节点集N。 1)初始化故障节点集N,=O,正常节点集N。= O,未知节点集Nm=O.n(0=0,1∈E,禁忌表T为空； 2)将正常探针经过的节点和故障探针经过的 节点分别加入到正常节点集N。和可疑节点集N中； 3)N=N-N。 图2选择探测路径进行故障检测 4)while M,0,生成探测站节点到所有可疑节 Fig.2 Selecting probing paths for fault detection 点的候选路径集CP并计算每条候选路径的权重 2.2禁忌链路搜索 w(p): 在以前的方法中，使用最大搜索或最小搜索选 5)for VneN 择的探测路径仅适用于定位单节点故障。当故障 节点较多时，所选探测路径可能会遍历多个故障节 6)if节点n不在任何候选路径上，将节点 n加入到N.中； 点，导致发送的探针无法准确定位多个节点故障。 考虑到一些难以被识别的节点，以前的探测 7)end if 路径选择方法不能满足多节点故障定位的要求。 8)end for 一种可能的解决方案是根据探测结果不断更新候 9)N,=N,-N 选探测路径集并选择更合适的探测路径。如果沿 10)while NO&CP≠O 着选定的探测路径发送的探针能够识别出所有故 11)选择具有最小权重w(p)的候选路径p,并 障节点，那么算法将停止并返回故障节点。否则， 沿路径p发送一个探针进行探测； 为剩余可疑节点生成新的候选路径集并选择探测 12)forY1∈Lp) 路径，直到识别出所有故障节点或新的候选路径 13)n(0=n(0+1 集为空。 14)end for 算法2给出了用于故障定位的禁忌链路搜索 15)从CP中移除候选路径p并根据探针结果 算法。网络中的所有节点可以被分为3类：正常 更新N。、N和N; 节点、故障节点和未知节点。在故障检测中，使 16)end while 用算法1选择一组探测路径并发送探针来检测网 17)for Yn∈N 络中的所有节点。故障检测的探针结果将作为故 18)将所有与n关联的边加入禁忌表T中； 障定位算法的输入。首先将正常探针和故障探针 19)end for 经过的节点分别加入到正常节点集N。和可疑节 20)end while 点集N,中。故障定位的任务就是从可疑节点集 图3显示了在包含8个节点的网络中使用禁 中识别故障的节点。算法通过计算每个探测站节 忌链路搜索算法选择探测路径进行故障定位的过 点到每个可疑节点的最短路径来生成候选路径 程，其中节点2是探测站。假设网络中的节点4 集CP并使用式(I)计算每条候选路径的权重。 5和7发生故障。最初，故障节点的位置和数目是 如果某些可疑节点不能被任何候选路径经过，则 未知的。故障检测阶段的探测结果显示了节点 这些可疑节点是未知节点，例如孤立节点。为了 4、5和7为可疑节点。如图3(a)所示，通过计算 尽可能多地识别出故障节点，算法依次选择具有 探测站节点到可疑节点的最短路径生成候选路径 最小权重的候选路径来发送探针。根据故障节点 集CP={P24,P2s,P27}。算法首先选择权值最小的候 的判定条件，如果故障探针经过的节点中只有一 选路径P2,(2-4-7)。沿该路径发送的探针无法识别 个可疑节点，则该可疑节点必为故障节点。确定 节点4和节点7。然后，算法依次选择路径P2(2
剩余未覆盖的节点 1 和 2，从剩余候选路径集中 选择权重最小的路径 p12(1-2)。此时，所有节点都 被选定的探测路径覆盖。因此，沿探测路 径 p45 和 p12 发送的两个探针可以检测该网络中的任 何节点。 2 5 6 3 4 1 图 2 选择探测路径进行故障检测 Fig. 2 Selecting probing paths for fault detection 2.2 禁忌链路搜索 在以前的方法中，使用最大搜索或最小搜索选 择的探测路径仅适用于定位单节点故障。当故障 节点较多时，所选探测路径可能会遍历多个故障节 点，导致发送的探针无法准确定位多个节点故障。 考虑到一些难以被识别的节点，以前的探测 路径选择方法不能满足多节点故障定位的要求。 一种可能的解决方案是根据探测结果不断更新候 选探测路径集并选择更合适的探测路径。如果沿 着选定的探测路径发送的探针能够识别出所有故 障节点，那么算法将停止并返回故障节点。否则， 为剩余可疑节点生成新的候选路径集并选择探测 路径，直到识别出所有故障节点或新的候选路径 集为空。 算法 2 给出了用于故障定位的禁忌链路搜索 算法。网络中的所有节点可以被分为 3 类：正常 节点、故障节点和未知节点。在故障检测中，使 用算法 1 选择一组探测路径并发送探针来检测网 络中的所有节点。故障检测的探针结果将作为故 障定位算法的输入。首先将正常探针和故障探针 经过的节点分别加入到正常节点集 No 和可疑节 点集 Ns 中。故障定位的任务就是从可疑节点集 中识别故障的节点。算法通过计算每个探测站节 点到每个可疑节点的最短路径来生成候选路径 集 CP 并使用式 (1) 计算每条候选路径的权重。 如果某些可疑节点不能被任何候选路径经过，则 这些可疑节点是未知节点，例如孤立节点。为了 尽可能多地识别出故障节点，算法依次选择具有 最小权重的候选路径来发送探针。根据故障节点 的判定条件，如果故障探针经过的节点中只有一 个可疑节点，则该可疑节点必为故障节点。确定 一部分故障节点后，将网络中所有与故障节点关 联的边加入到禁忌表 T 中。在下一次的候选路径 生成中，算法为剩余的可疑节点生成更合适的候 选路径。总之，禁忌链路搜索算法通过禁止搜索 与故障节点相连的链路来多次生成候选路径集并 选择探测路径，以实现多节点故障定位的目的。 算法 2 故障定位的禁忌链路搜索算法 输入 故障检测的正常探针集 NP 和故障探 针集 FP； 输出 故障节点集 Nf。 1) 初始化故障节点集 Nf = Ø，正常节点集 No = Ø，未知节点集 Nu = Ø，n(l) = 0，l∈E，禁忌表 T 为空； 2) 将正常探针经过的节点和故障探针经过的 节点分别加入到正常节点集 No 和可疑节点集 Ns 中； 3) Ns=Ns−No 4) while Ns≠Ø，生成探测站节点到所有可疑节 点的候选路径集 CP 并计算每条候选路径的权重 w(p)； 5) for ∀ n∈Ns 6) if 节点 n 不在任何候选路径上，将节点 n 加入到 Nu 中； 7) end if 8) end for 9) Ns=Ns−Nu 10) while Ns≠Ø & CP≠Ø 11) 选择具有最小权重 w(p) 的候选路径 p，并 沿路径 p 发送一个探针进行探测； 12) for ∀ l∈L(p) 13) n(l)=n(l)+1 14) end for 15) 从 CP 中移除候选路径 p 并根据探针结果 更新 No、Nf 和 Ns； 16) end while 17) for ∀ n∈Nf 18) 将所有与 n 关联的边加入禁忌表 T 中； 19) end for 20) end while 图 3 显示了在包含 8 个节点的网络中使用禁 忌链路搜索算法选择探测路径进行故障定位的过 程，其中节点 2 是探测站。假设网络中的节点 4、 5 和 7 发生故障。最初，故障节点的位置和数目是 未知的。故障检测阶段的探测结果显示了节点 4、5 和 7 为可疑节点。如图 3(a) 所示，通过计算 探测站节点到可疑节点的最短路径生成候选路径 集 CP={p24, p25, p27}。算法首先选择权值最小的候 选路径 p27(2-4-7)。沿该路径发送的探针无法识别 节点 4 和节点 7。然后，算法依次选择路径 p24(2- 第 4 期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·769·
·770· 智能系统学报 第16卷 4)和P2s(2-5)分别将节点4和节点5识别为故障 假阳性率和探测成本。仿真结果图中的每个点都 节点。此时，候选路径集CP=O,可疑节点集N,= 是在不同网络拓扑上进行共20次实验之后取平 {7}。为了识别可疑节点7，算法生成一个新的候 均值绘制而成的。 选路径集。如图3(b)所示，算法将链路1、12、13 图4显示3种算法在节点故障率为0.01~0.1 和1，加入到禁忌表T中，并生成一个新的候选路 下的成功定位率、假阳性率和探测成本比较。生 径集CP={P27}。通过选择探测路径P2,(2-3-6-8- 成的网络拓扑都包含200个节点，且平均节点度 )来达到识别故障节点7的目的。因此，故障节 为3。可以看出，随着故障节点数的增加，探测路 点集N={4,5,7}。对于复杂的大规模网络，探测 径选择算法比随机游走算法具有更高的成功定位 路径选择算法为识别大量故障节点提供了可能。 率和更低的假阳性率。除此之外，由于随机游走 算法是一种非适应性故障定位算法，探测成本远 高于探测路径选择算法。与已有的贪婪故障定位 算法相比，本文提出的算法在多故障节点的成功 定位率上有了很大的提升，但是探测成本也略微 增加。如图4(a)所示，当节点故障率增加时，本 文提出的算法与贪婪故障定位算法相比能够将节 点故障的成功定位率提升10%以上。 (a)第一次路径选择 1.0 -PPSA(=200) 0.6 -RWL(=200) 。-GFL(=200) 0.4 0.010.020.030.040.050.060.070.080.090.10 节点故障率a (a)成功定位率 (b)第二次路径选择 0.3 -PPSA(=200) 图3选择探测路径进行故障定位 e-RWL(=200) 0.2 4-GFL(=200) Fig.3 Selecting probing paths for fault localization 3实验与分析 0 为了验证探测路径选择算法的有效性，本 0.010.020.030.040.050.060.070.080.090.10 节点故障率α 文在随机生成的网络拓扑和真实网络拓扑上仿真 (b)假阳性率 并比较了以下3种算法。1)探测路径选择算法 800 (PPSA):本文提出的一种结合贪婪路径选择和禁 700 ◆-PPSA(=200) 忌链路搜索的自适应故障定位算法。2)随机游 -。-RWL(m=200 600 -GFL(=200) 走算法(RWL):Xuan等8)提出的一种通过随机 游走生成探测路径的非适应性故障定位算法。 400 3)贪婪故障定位算法(GFL):Natu等提出的一 300 种用于定位少量节点故障的自适应故障定位算 200 法。本文设置探针长度的阈值为K=8并选择两 100 个节点作为探测站节点，使得探测站节点能够在 0.010.020.030.040.050.060.070.080.090.10 8跳以内到达最多数量的其余节点且探测站节点 节点故障率α 的度最大。 (c)探测成本 3.1BA无标度网络上的实验 图43种算法的比较结果 我们比较了3种算法在随机生成的BA无标 Fig.4 Comparison results of the three algorithms 度网络中的性能。BA无标度网络具有现实世界 图5显示了在不同规模的网络中探测路径选 中的大多数网络的增长方式，能够反映真实网络 择算法的探测成本随节点故障率的变化情况。随 的特性。性能比较使用的指标有：成功定位率， 着故障节点数目的增加，在故障定位阶段选择的
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}。对于复杂的大规模网络，探测 路径选择算法为识别大量故障节点提供了可能。 1 2 3 6 4 7 8 5 (a) 第一次路径选择 (b) 第二次路径选择 1 2 3 6 4 7 8 5 l1 l2 l4 l3 图 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% 以上。 节点故障率 α 成功定位率 PPSA (n=200) RWL (n=200) GFL (n=200) 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10 1.0 0.8 0.6 0.4 (a) 成功定位率 节点故障率 α 假阳性率 PPSA (n=200) RWL (n=200) GFL (n=200) 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10 0.3 0.2 0.1 0 (b) 假阳性率 节点故障率 α PPSA (n=200) RWL (n=200) GFL (n=200) 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10 0 (c) 探测成本 100 200 300 400 500 600 700 800 探测成本 图 4 3 种算法的比较结果 Fig. 4 Comparison results of the three algorithms 图 5 显示了在不同规模的网络中探测路径选 择算法的探测成本随节点故障率的变化情况。随 着故障节点数目的增加，在故障定位阶段选择的 ·770· 智 能 系 统 学 报 第 16 卷
第4期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·771· 探测路径也会增加。为了验证探测路径选择算法 3.2真实网络上的实验 在不同节点数量的网络中的性能，接下来在随机 为了展示本文算法可以很好地扩展到真实网 生成的节点数为100~1000，平均节点度分别为3、 络上，本文使用了阿德莱德大学开发的网络拓扑 4和5的网络中进行实验，其中节点故障率被设 结构数据集2中的2个网络拓扑(GEANT、GTS 置为0.1。图6(a)中的结果显示，当节点故障率 CE)和华盛顿大学的火箭燃料项目2s2导出的 为0.1时，探测路径选择算法在不同规模的网络 6个网络拓扑(AS3967、AS1755、AS1221、 中的成功定位率均能保持在90%以上。当网络 AS6461、AS3257、AS1239)进行实验。这些拓扑 平均节点度较大时，故障定位的成功率也较高。 反映了互联网的真实连通性，被广泛应用于相关 图6(b)显示了探测路径选择算法在不同规模的网 研究中。表1显示了每个拓扑的节点数、链路数 络中故障定位的探测成本的变化情况。可以看 和平均度。 出，对于节点度较大的网络，算法的探测成本也 表1真实网络拓扑 较高。 Table 1 Real network topologies 1000 a=0.02 拓扑 节点数 边数 平均度 900 800 885 GEANT 40 61 3.05 700 600 GTS CE 149 193 2.59 500 AS3967 79 147 3.72 400 300 AS1755 87 161 3.70 200 100 AS1221 108 153 2.83 1002003004005006007008009001000 AS6461 141 374 5.30 节点数目 AS3257 161 328 4.07 图5本文算法在不同规模网络中的探测成本 AS1239 315 972 6.17 Fig.5 Probing cost of the algorithm in this paper in differ- ent scale networks 在这8个真实网络拓扑中，仿真验证了3种 1.0 算法的成功定位率和探测成本。对于每一个拓 扑，将节点故障率设置为0.1。表2和表3分别给 0.9 出了3种算法在8个真实网络拓扑上的成功定位 平均节点度为3 0.8 平均节点度为4 率和探测成本。可以看出，本文提出的探测路径 一一平均节点度为5 选择算法与其他算法相比具有较高的成功定位率 0. 和较低的探测成本。虽然探测成本稍微高于贪婪 1002003004005006007008009001000 节点数量 故障定位算法，但是成功定位率却大大提升。 (a)成功定位率 表2算法的成功定位率比较 1000 Table 2 Comparison of successful localization ratios of al- 900 。一平均节点度为3 gorithms 800 +一平均节点度为4 拓扑 700 *一平均节点度为5 PPSA RWL GFL 600 GEANT 0.95 0.90 0.85 500 400 GTS CE 0.91 0.87 0.73 300 AS3967 0.97 0.91 0.87 200 100 AS1755 0.95 0.88 0.82 1002003004005006007008009001000 AS1221 0.96 0.89 0.86 节点数量 (b)探测成本 AS6461 0.95 0.90 0.87 图6本文算法在不同规模网络中的性能 AS3257 0.96 0.89 0.86 Fig.6 Performance of the algorithm in this paper in dif- AS1239 0.94 0.89 0.84 ferent scale networks
探测路径也会增加。为了验证探测路径选择算法 在不同节点数量的网络中的性能，接下来在随机 生成的节点数为 100~1 000，平均节点度分别为 3、 4 和 5 的网络中进行实验，其中节点故障率被设 置为 0.1。图 6(a) 中的结果显示，当节点故障率 为 0.1 时，探测路径选择算法在不同规模的网络 中的成功定位率均能保持在 90% 以上。当网络 平均节点度较大时，故障定位的成功率也较高。 图 6(b) 显示了探测路径选择算法在不同规模的网 络中故障定位的探测成本的变化情况。可以看 出，对于节点度较大的网络，算法的探测成本也 较高。 节点数目 0 100 200 300 400 500 600 700 800 900 1 000 探测成本 α=0.02 α=0.03 α=0.04 α=0.05 100 200 300 400 500 600 700 800 900 1 000 图 5 本文算法在不同规模网络中的探测成本 Fig. 5 Probing cost of the algorithm in this paper in different scale networks 平均节点度为 3 平均节点度为 4 平均节点度为 5 平均节点度为 3 平均节点度为 4 平均节点度为 5 节点数量 成功定位率 100 200 300 400 500 600 700 800 900 1 000 1.0 0.9 0.8 0.7 (a) 成功定位率 节点数量 0 100 200 300 400 500 600 700 800 900 1 000 探测成本 100 200 300 400 500 600 700 800 900 1 000 (b) 探测成本 图 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 拓扑 节点数 边数 平均度 GEANT 40 61 3.05 GTS CE 149 193 2.59 AS3967 79 147 3.72 AS1755 87 161 3.70 AS1221 108 153 2.83 AS6461 141 374 5.30 AS3257 161 328 4.07 AS1239 315 972 6.17 在这 8 个真实网络拓扑中，仿真验证了 3 种 算法的成功定位率和探测成本。对于每一个拓 扑，将节点故障率设置为 0.1。表 2 和表 3 分别给 出了 3 种算法在 8 个真实网络拓扑上的成功定位 率和探测成本。可以看出，本文提出的探测路径 选择算法与其他算法相比具有较高的成功定位率 和较低的探测成本。虽然探测成本稍微高于贪婪 故障定位算法，但是成功定位率却大大提升。 表 2 算法的成功定位率比较 Table 2 Comparison of successful localization ratios of algorithms 拓扑 PPSA RWL GFL GEANT 0.95 0.90 0.85 GTS CE 0.91 0.87 0.73 AS3967 0.97 0.91 0.87 AS1755 0.95 0.88 0.82 AS1221 0.96 0.89 0.86 AS6461 0.95 0.90 0.87 AS3257 0.96 0.89 0.86 AS1239 0.94 0.89 0.84 第 4 期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·771·
·772· 智能系统学报 第16卷 表3算法的探测成本比较 national Workshop on Distributed Systems:Operations and Table 3 Comparison of probing costs of algorithms Management.San Jose,USA,2007:38-49 拓扑 PPSA RWL GFL [6]LU Lu,XU Zhengguo,WANG Wenhai,et al.A new fault detection method for computer networks[J].Reliability en- GEANT 28 112 29 gineering system safety,2013,114:45-51. GTS CE 139 356 131 [7]ZHENG Qiang,CAO Guohong.Minimizing probing cost AS3967 210 68 and achieving identifiability in probe-based network link AS1755 86 262 72 monitoring[J].IEEE transactions on computers,2013, 62(3):510-523. AS1221 108 325 98 [8]GYIMOTHI L.HOSSZU E,TAPOLCAI J.Constructions AS6461 124 380 120 for unambiguous node failure localization in grid topolo- AS3257 150 420 134 gies[C]//Proceedings of the 7th International Workshop on AS1239 287 648 272 Reliable Networks Design and Modeling(RNDM).Mu- nich,Germany,2015:222-228. [9]GYIMOTHIL,TAPOLCAI J.A heuristic algorithm for 4结束语 network-wide local unambiguous node failure localization[Cl/ 本文提出了一种有效的探测路径选择算法来 Proceedings of the 16th International Conference on High Performance Switching and Routing (HPSR).Budapest, 解决网络中的多节点故障定位问题。该算法实现 Hungary,2016:1-6. 的原理是基于主动探测技术为故障检测和故障定 [10]LIN S,RAMACHANDRAN V.ZINYAMA T.Balan- 位选择最合适的探测路径。用于故障检测的贪婪 cing overhead-minimization objectives in network prob- 路径选择算法在选择最少数量探测路径进行故障 ing-path selection[C]//IEEE Symposium on Computers 检测的同时减少探测数据包对链路负载的影响。 and Communications(ISCC).Heraklion,Greece,2017: 用于故障定位的禁忌链路搜索算法通过构造禁忌 353-358. 表多次生成候选路径集，能够显著提高故障节点 [11]DUSIA A,SETHI A S.Probe generation for active prob- 的成功定位率。在BA无标度网络上的仿真结果 ing[J].International journal of network management, 表明，与现有故障定位算法相比，本文算法能够 2018,28(4ye2021. 显著提高多节点故障的成功定位率并降低探测成 [12]TAYAL A,SHARMA N.HUBBALLI N.et al.Traffic 本。在真实网络拓扑上的仿真验证了探测路径选 dynamics-aware probe selection for fault detection in net- 择算法能够很好地扩展到实际网络中。在之后的 works[J].Journal of network and systems management. 2020,28(4):1055-1084 研究中，将在故障检测和定位中引入探针长度和 [13]WU Bin,HO P H,TAPOLCAI J,et al.Optimal alloca- 节点负载等参数以满足实际故障诊断需求。 tion of monitoring trails for fast SRLG failure localiza- 参考文献 tion in all-optical networks[C]//IEEE Global Telecommu- nications Conference GLOBECOM 2010.Miami,USA. [1]DUSIA A.SETHI A S.Recent Advances in Fault Localiz- 2010:1-5. ation in Computer Networks[J].IEEE communications sur- [14]BABARCZI P,TAPOLCAI J,HO P H.Adjacent link veys&tutorials,2016,18(4):3030-3051 failure localization with monitoring trails in all-optical [2]BRODIE M,RISH I,MA Sheng.Optimizing probe selec- mesh networks[J].IEEE/ACM transactions on network- tion for fault localization[Cl//Proceedings of the 12th Inter- ing,2011,19(3):907-920. national Workshop on Distributed Systems:Operations and [15]CHENG Zijing,ZHANG Xiaoning,SHEN Shaohui,et al. Management.Nancy,France,2001:88-98. T-Trail:link failure monitoring in software-defined optic- [3]STEINDER ML,SETHI A S.A survey of fault localiza- al networks[J].Journal of optical communications and tion techniques in computer networks[J].Science of com- networking,2018.10(4):344-352 puter programming,2004,53(2):165-194 [16]TAPOLCAI J,HO P H,RONYAI L,et al.Failure localiz- [4]NATU M.SETHI A S,LLOYD E L.Efficient probe selec- ation for shared risk link groups in all-optical mesh net- tion algorithms for fault diagnosis[J].Telecommunication works using monitoring trails[J].Journal of lightwave systems,2008,371/3):109-125. technology,2011,2910:1597-1606. [5]NATU M.SETHI A S.Probabilistic fault diagnosis using [17]ALI ML.HO P H.TAPOLCAI J.SRLG failure localiza- adaptive probing[Cl//Proceedings of the 18th IEEE Inter- tion using nested m-trails and their application to adapt-
表 3 算法的探测成本比较 Table 3 Comparison of probing costs of algorithms 拓扑 PPSA RWL GFL GEANT 28 112 29 GTS CE 139 356 131 AS3967 72 210 68 AS1755 86 262 72 AS1221 108 325 98 AS6461 124 380 120 AS3257 150 420 134 AS1239 287 648 272 4 结束语 本文提出了一种有效的探测路径选择算法来 解决网络中的多节点故障定位问题。该算法实现 的原理是基于主动探测技术为故障检测和故障定 位选择最合适的探测路径。用于故障检测的贪婪 路径选择算法在选择最少数量探测路径进行故障 检测的同时减少探测数据包对链路负载的影响。 用于故障定位的禁忌链路搜索算法通过构造禁忌 表多次生成候选路径集，能够显著提高故障节点 的成功定位率。在 BA 无标度网络上的仿真结果 表明，与现有故障定位算法相比，本文算法能够 显著提高多节点故障的成功定位率并降低探测成 本。在真实网络拓扑上的仿真验证了探测路径选 择算法能够很好地扩展到实际网络中。在之后的 研究中，将在故障检测和定位中引入探针长度和 节点负载等参数以满足实际故障诊断需求。 参考文献： DUSIA A, SETHI A S. Recent Advances in Fault Localization in Computer Networks[J]. IEEE communications surveys & tutorials, 2016, 18(4): 3030–3051. [1] BRODIE M, RISH I, MA Sheng. Optimizing probe selection for fault localization[C]//Proceedings of the 12th International Workshop on Distributed Systems: Operations and Management. Nancy, France, 2001: 88−98. [2] STEINDER M Ł, SETHI A S. A survey of fault localization techniques in computer networks[J]. Science of computer programming, 2004, 53(2): 165–194. [3] NATU M, SETHI A S, LLOYD E L. Efficient probe selection algorithms for fault diagnosis[J]. Telecommunication systems, 2008, 37(1/3): 109–125. [4] NATU M, SETHI A S. Probabilistic fault diagnosis using adaptive probing[C]//Proceedings of the 18th IEEE Inter- [5] national Workshop on Distributed Systems: Operations and Management. San José, USA, 2007: 38−49. LU Lu, XU Zhengguo, WANG Wenhai, et al. A new fault detection method for computer networks[J]. Reliability engineering & system safety, 2013, 114: 45–51. [6] ZHENG Qiang, CAO Guohong. Minimizing probing cost and achieving identifiability in probe-based network link monitoring[J]. IEEE transactions on computers, 2013, 62(3): 510–523. [7] GYIMÓTHI L, HOSSZU É, TAPOLCAI J. Constructions for unambiguous node failure localization in grid topologies[C]//Proceedings of the 7th International Workshop on Reliable Networks Design and Modeling (RNDM). Munich, Germany, 2015: 222−228. [8] GYIMÓTHI L, TAPOLCAI J. A heuristic algorithm for network-wide local unambiguous node failure localization[C]// Proceedings of the 16th International Conference on High Performance Switching and Routing (HPSR). Budapest, Hungary, 2016: 1−6. [9] LIN S, RAMACHANDRAN V, ZINYAMA T. Balancing overhead-minimization objectives in network probing-path selection[C]//IEEE Symposium on Computers and Communications (ISCC). Heraklion, Greece, 2017: 353−358. [10] DUSIA A, SETHI A S. Probe generation for active probing[J]. International journal of network management, 2018, 28(4): e2021. [11] TAYAL A, SHARMA N, HUBBALLI N, et al. Traffic dynamics-aware probe selection for fault detection in networks[J]. Journal of network and systems management, 2020, 28(4): 1055–1084. [12] WU Bin, HO P H, TAPOLCAI J, et al. Optimal allocation of monitoring trails for fast SRLG failure localization in all-optical networks[C]//IEEE Global Telecommunications Conference GLOBECOM 2010. Miami, USA, 2010: 1−5. [13] BABARCZI P, TAPOLCAI J, HO P H. Adjacent link failure localization with monitoring trails in all-optical mesh networks[J]. IEEE/ACM transactions on networking, 2011, 19(3): 907–920. [14] CHENG Zijing, ZHANG Xiaoning, SHEN Shaohui, et al. T-Trail: link failure monitoring in software-defined optical networks[J]. Journal of optical communications and networking, 2018, 10(4): 344–352. [15] TAPOLCAI J, HO P H, RONYAI L, et al. Failure localization for shared risk link groups in all-optical mesh networks using monitoring trails[J]. Journal of lightwave technology, 2011, 29(10): 1597–1606. [16] ALI M L, HO P H, TAPOLCAI J. SRLG failure localization using nested m-trails and their application to adapt- [17] ·772· 智 能 系 统 学 报 第 16 卷
第4期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·773· ive probing[J].Networks,2015,66(4):347-363 ing/rocketfuel/ [18]XUAN Ying,SHEN Yilin,NGUYEN N P,et al.Effi- [26]MAHAJAN R,SPRING N,WETHERALL D,et al.Infer- cient multi-link failure localization schemes in all-optical ring link weights using end-to-end measurements[C]//Pro- networks[J].IEEE transactions on communications,2013, ceedings of the 2nd ACM SIGCOMM Workshop on In- 61(3:11441151. [19]MA Liang,HE Ting,LEUNG KK,et al.Inferring link ternet Measurement.Marseille,France,2002:231-236. metrics from end-to-end path measurements:Identifiabil- 作者简介： ity and monitor placement[J].IEEE/ACM transactions on 齐小刚，教授，博士生导师，主要 networking,2014,22(4)1351-1368 研究方向为复杂系统建模与仿真，网 [20]GAO Yi,DONG Wei,WU Wenbin,et al.Scalpel:Scal- 络算法设计与应用。申请专利47件 able preferential link tomography based on graph trim- (授权19件)，登记软件著作权4件。 ming[J].IEEE/ACM transactions on networking,2015, 发表学术论文100余篇。 24(3):1392-1403 [21]DONG Wei.GAO Yi.WU Wenbin,et al.Optimal monit- or assignment for preferential link tomography in commu- 汪直平，硕士研究生，主要研究方 nication networks[J].IEEE/ACM transactions on net- 向为网络优化算法研究与故障诊断。 working,.2017,25(1):210-223. [22]LI Huikang,GAO Yi,DONG Wei,et al.Preferential link tomography in dynamic networks[J].IEEE/ACM transac- tions on networking,2019,27(5):1801-1814. [23]MA Liang.HE Ting,SWAMI A,et al.On optimal monit- or placement for localizing node failures via network 李家慧，硕土研究生，主要研究方 tomography[J].Performance evaluation,2015,91:16-37. 向为网络故障检测与定位。 [24]The internet topology zoo[EB/OL].(2017-07-18)[2020- 01-01]http://www.topology-zoo.org/dataset.html. [25]Rocketfuel:An ISP topology mapping engine[EB/OL]. [2020-01-01]http://research.cs.washington.edu/network-
ive probing[J]. Networks, 2015, 66(4): 347–363. XUAN Ying, SHEN Yilin, NGUYEN N P, et al. Efficient multi-link failure localization schemes in all-optical networks[J]. IEEE transactions on communications, 2013, 61(3): 1144–1151. [18] MA Liang, HE Ting, LEUNG K K, et al. Inferring link metrics from end-to-end path measurements: Identifiability and monitor placement[J]. IEEE/ACM transactions on networking, 2014, 22(4): 1351–1368. [19] GAO Yi, DONG Wei, WU Wenbin, et al. Scalpel: Scalable preferential link tomography based on graph trimming[J]. IEEE/ACM transactions on networking, 2015, 24(3): 1392–1403. [20] DONG Wei, GAO Yi, WU Wenbin, et al. Optimal monitor assignment for preferential link tomography in communication networks[J]. IEEE/ACM transactions on networking, 2017, 25(1): 210–223. [21] LI Huikang, GAO Yi, DONG Wei, et al. Preferential link tomography in dynamic networks[J]. IEEE/ACM transactions on networking, 2019, 27(5): 1801–1814. [22] MA Liang, HE Ting, SWAMI A, et al. On optimal monitor placement for localizing node failures via network tomography[J]. Performance evaluation, 2015, 91: 16–37. [23] The internet topology zoo[EB/OL]. (2017-07-18) [2020- 01-01] http://www.topology-zoo.org/dataset.html. [24] Rocketfuel: An ISP topology mapping engine[EB/OL]. [2020-01-01] http://research.cs.washington.edu/network- [25] ing/rocketfuel/. MAHAJAN R, SPRING N, WETHERALL D, et al. Inferring link weights using end-to-end measurements[C]//Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement. Marseille, France, 2002: 231−236. [26] 作者简介： 齐小刚，教授，博士生导师，主要 研究方向为复杂系统建模与仿真，网 络算法设计与应用。申请专利 47 件 (授权 19 件)，登记软件著作权 4 件。 发表学术论文 100 余篇。 汪直平，硕士研究生，主要研究方 向为网络优化算法研究与故障诊断。 李家慧，硕士研究生，主要研究方 向为网络故障检测与定位。 第 4 期 齐小刚，等：网络中多节点故障定位的探测路径选择算法 ·773·