[1]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]
Copy

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

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 16 Number of periods: 2021 4 Page number: 766-773 Column: 学术论文—人工智能基础 Public date: 2021-07-05
Title:
Probing path selection algorithm for multi-node failure localization in networks
Author(s):
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
Keywords:
multi-node failure localization; active probing; probing path selection; greedy path selection; tabu link search; successful localization ratio; probing cost
CLC:
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems