﻿ 网络中多节点故障定位的探测路径选择算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2021, Vol. 16 Issue (4): 766-773  DOI: 10.11992/tis.202010007 0

### 引用本文

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. DOI: 10.11992/tis.202010007.

### 文章历史

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

Probing path selection algorithm for multi-node failure localization in networks
QI Xiaogang 1, WANG Zhiping 1, LI Jiahui 1, LIU Lifang 2
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.
Key words: multi-node failure localization    active probing    probing path selection    greedy path selection    tabu link search    successful localization ratio    probing cost

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

1 基本概念 1.1 问题描述

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

 $w\left( p \right) = \frac{{\displaystyle \sum\limits_{l \in L\left( p \right)} {n\left( l \right)} }}{{\left| {M\left( p \right)} \right|}},p \in {\rm{CP}}$ (1)

2 探测路径选择算法 2.1 贪婪路径选择

1)初始化未覆盖节点集合NPN=V−PS，DP=Ø，n(l)=0，lE

2)对每一个探测站节点vi∈PS，使用Dijkstra最短路径算法计算节点vi到节点vj(ij)的最短路径pij，并将其加入到候选路径集CP中；

3)当NPN≠Ø时，从CP中选择权值最小的候选路径p

4)将路径p加入到探测路径集DP中；

5)从NPN中移除路径p上的所有节点；

6) for $\forall$ lL(p)

7) n(l)=n(l)+1

8) end for

9) end while

 Download: 图 2 选择探测路径进行故障检测 Fig. 2 Selecting probing paths for fault detection
2.2 禁忌链路搜索

1)初始化故障节点集Nf = Ø，正常节点集No = Ø，未知节点集Nu = Ø，n(l) = 0，lE，禁忌表T为空；

2)将正常探针经过的节点和故障探针经过的节点分别加入到正常节点集No和可疑节点集Ns中；

3) Ns=NsNo

4) while Ns≠Ø，生成探测站节点到所有可疑节点的候选路径集CP并计算每条候选路径的权重w(p)；

5) for $\forall$ nNs

6) if 节点n不在任何候选路径上，将节点n加入到Nu中；

7) end if

8) end for

9) Ns=NsNu

10) while Ns≠Ø & CP≠Ø

11) 选择具有最小权重w(p)的候选路径p，并沿路径p发送一个探针进行探测；

12) for $\forall$ lL(p)

13) n(l)=n(l)+1

14) end for

15) 从CP中移除候选路径p并根据探针结果更新NoNfNs

16) end while

17) for $\forall$ nNf

18)将所有与n关联的边加入禁忌表T中；

19) end for

20) end while

 Download: 图 3 选择探测路径进行故障定位 Fig. 3 Selecting probing paths for fault localization
3 实验与分析

3.1 BA无标度网络上的实验

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

 Download: 图 5 本文算法在不同规模网络中的探测成本 Fig. 5 Probing cost of the algorithm in this paper in different scale networks
 Download: 图 6 本文算法在不同规模网络中的性能 Fig. 6 Performance of the algorithm in this paper in different scale networks
3.2 真实网络上的实验

4 结束语

 [1] DUSIA A, SETHI A S. Recent Advances in Fault Localization in Computer Networks[J]. IEEE communications surveys & tutorials, 2016, 18(4): 3030-3051. (0) [2] 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. (0) [3] STEINDER M Ł, SETHI A S. A survey of fault localization techniques in computer networks[J]. Science of computer programming, 2004, 53(2): 165-194. DOI:10.1016/j.scico.2004.01.010 (0) [4] NATU M, SETHI A S, LLOYD E L. Efficient probe selection algorithms for fault diagnosis[J]. Telecommunication systems, 2008, 37(1/3): 109-125. DOI:10.1007/s11235-008-9069-1 (0) [5] NATU M, SETHI A S. Probabilistic fault diagnosis using adaptive probing[C]//Proceedings of the 18th IEEE International Workshop on Distributed Systems: Operations and Management. San José, USA, 2007: 38−49. (0) [6] 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. (0) [7] 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. DOI:10.1109/TC.2011.244 (0) [8] 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. (0) [9] 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. (0) [10] 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. (0) [11] DUSIA A, SETHI A S. Probe generation for active probing[J]. International journal of network management, 2018, 28(4): e2021. DOI:10.1002/nem.2021 (0) [12] 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. DOI:10.1007/s10922-020-09514-3 (0) [13] 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. (0) [14] 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. DOI:10.1109/TNET.2010.2096429 (0) [15] 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. DOI:10.1364/JOCN.10.000344 (0) [16] 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. DOI:10.1109/JLT.2011.2131120 (0) [17] ALI M L, HO P H, TAPOLCAI J. SRLG failure localization using nested m-trails and their application to adaptive probing[J]. Networks, 2015, 66(4): 347-363. DOI:10.1002/net.21653 (0) [18] 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. DOI:10.1109/TCOMM.2013.012313.110645 (0) [19] 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. DOI:10.1109/TNET.2014.2328668 (0) [20] 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. (0) [21] 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. DOI:10.1109/TNET.2016.2581176 (0) [22] 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. DOI:10.1109/TNET.2019.2931047 (0) [23] 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. DOI:10.1016/j.peva.2015.06.003 (0) [24] The internet topology zoo[EB/OL]. (2017-07-18) [2020-01-01] http://www.topology-zoo.org/dataset.html. (0) [25] Rocketfuel: An ISP topology mapping engine[EB/OL]. [2020-01-01] http://research.cs.washington.edu/networking/rocketfuel/. (0) [26] 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. (0)