<-上一篇/Previous Article 下一篇/Next Article->

[1]齐小刚,汪直平,李家慧,等.网络中多节点故障定位的探测路径选择算法[J].智能系统学报,2021,16(4):766-773.[doi:10.11992/tis.202010007]
　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]

点击复制

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

PDF下载 HTML

《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷: 16 期数: 2021年第4期页码: 766-773 栏目: 学术论文—人工智能基础出版日期: 2021-07-05

Title:: Probing path selection algorithm for multi-node failure localization in networks

作者:: 齐小刚¹, 汪直平¹, 李家慧¹, 刘立芳²; 1. 西安电子科技大学数学与统计学院，陕西西安 710126;
2. 西安电子科技大学计算机学院，陕西西安 710071

Author(s):: 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

关键词:: 多节点故障定位; 主动探测; 探测路径选择; 贪婪路径选择; 禁忌链路搜索; 成功定位率; 探测成本

Keywords:: multi-node failure localization; active probing; probing path selection; greedy path selection; tabu link search; successful localization ratio; probing cost

分类号:: TP393

DOI:: 10.11992/tis.202010007

摘要:: 针对现有故障定位技术不能满足多节点故障定位的要求，尤其当网络中存在大量故障节点时，提出了一种基于主动探测的探测路径选择算法。该算法主要包括用于故障检测的贪婪路径选择算法和用于故障定位的禁忌链路搜索算法。在故障检测阶段，使用贪婪路径选择算法迭代地选择具有最小权重的探测路径覆盖网络中的节点。在故障定位阶段，使用禁忌链路搜索算法多次生成候选路径集以选择最合适的探测路径来解决多节点故障定位问题。在随机网络拓扑和真实网络拓扑上的仿真结果表明，与现有的节点故障定位算法相比，探测路径选择算法具有更高的成功定位率和更低的探测成本。

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.

参考文献/References:: [1] DUSIA A, SETHI A S. Recent Advances in Fault Localization in Computer Networks[J]. IEEE communications surveys & tutorials, 2016, 18(4): 3030-3051.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11] DUSIA A, SETHI A S. Probe generation for active probing[J]. International journal of network management, 2018, 28(4): e2021.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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/networking/rocketfuel/.
[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.

备注/Memo

收稿日期:2020-10-13。
基金项目:国家自然科学基金项目(61877067，61572435)；西安市科技创新项目(201805029YD7CG13-6)；近地面探测实验室科学技术基金项目(61424140402)
作者简介:齐小刚，教授，博士生导师，主要研究方向为复杂系统建模与仿真，网络算法设计与应用。申请专利47件(授权19件)，登记软件著作权4件。发表学术论文100余篇;汪直平，硕士研究生，主要研究方向为网络优化算法研究与故障诊断;李家慧，硕士研究生，主要研究方向为网络故障检测与定位
通讯作者:汪直平.E-mail:1083150353@qq.com

更新日期/Last Update: 1900-01-01

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

备注/Memo

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

PDF下载 HTML