全光网中定位故障链路的探测选择算法

doi:10.3969/j.issn.1001-2400.2018.02.013

Abstract

Abstract:

This paper studies the probe selection problem in all-optical networks for achieving unambiguous faulty links localization. The existing random walk algorithm can find feasible solutions for localizing the faulty link unambiguously, but it consumes a large number of probes and wavelengths in large-size networks. First, monitoring paths are set up for failure detection. Second, the probing signals are sent out through all monitoring paths, and then the failure localization is performed on every faulty path. The proposed scheme proves that the problem of the minimal monitoring path set is NP-complete and can be solved by the heuristic monitoring path selection algorithm. It is also proved that a network must be k+1 edge connectivity for localizing k faulty links with one monitoring node. Compared with random walk, the probe selection algorithm greatly shortens the number of probes and consumed wavelengths per link.

Key words: failure detection, failure localization, monitoring path, probe, faulty links

QI Xiaogang;WANG Xiaolin;LIU Lifang. Probe selection algorithm for faulty links localization in all-optical networks[J].Journal of Xidian University, 2018, 45(2): 71-76+115.

References

［1］熊余, 董先存, 李圆圆, 等. 软件定义光网络中基于最小点覆盖的控制平面跨层生存性设计［J］. 电子与信息学报, 2016, 38(5): 1211-1218.
XIONG Yu, DONG Xiancun, LI Yuanyuan, et al. The Cross-layer Survivable Design of Control Plane Based on Minimum Point Covering in Software Defined Optical Network［J］. Journal of Electronics & Information Technology, 2016, 38(5): 1211-1218.
［2］ HARVEY N J A, PATRASCU M, WEN Y G, et al. Non-adaptive Fault Diagnosis for All-optical Networks via Combinatorial Group Testing on Graphs［C］//Proceedings of the 2007 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 697-705.
［3］ 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.
［4］ XUAN Y, SHEN Y, 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.
［5］ ALI M L, HO P H, TAPOLCAI J. A Novel M-trail Allocation Method for SRLG Fault Localization in All-optical Networks［J］. Optical Switching and Networking, 2017, 23(2): 179-188.
［6］ TAPOLCAI J, RONYAI L, HOSSZU E, et al. Signaling Free Localization of Node Failures in All-optical Networks［C］//Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway: IEEE, 2014: 1860-1868.
［7］刘英挺, 朱睿杰, 杜晓明, 等. 全光网中采用可信度模型的故障定位技术［J］. 西安电子科技大学学报, 2016, 43(6): 152-157.
LIU Yingting, ZHU Ruijie, DU Xiaoming, et al. Mechanism for Fault Location Based on the Credibility Model of All Optical Networks［J］. Journal of Xidian University, 2016, 43(6): 152-157.
［8］ NATU M, SETHI A S, LLOYD E L. Efficient Probe Selection Algorithms for Fault Diagnosis［J］. Telecommunication Systems, 2008, 37(1/3): 109-125.
［9］张新, 常义林, 孙方涛, 等. 一种改进的网络故障监测算法［J］. 西安电子科技大学学报, 2006, 33(3): 416-421.
ZHANG Xin, CHANG Yilin, SUN Fangtao, et al. An Improved Algorithm for Monitoring the Network Fault［J］. Journal of Xidian University, 2006, 33(3): 416-421.
［10］ ALBERT R, BARABASI A L. Statistical Mechanics of Complex Networks［J］. Quantitative Biology, 2001, 74(1): 47-97.
［11］ THAI M T. Group Testing Theory in Network Security: Advanced Solution［M］. New York: Springer, 2012: 3-4.
［12］ ALI M L, HO P H, TAPOLCAI J. SRLG Fault Localization Using Nested M-trails［J］. Computer Networks, 2015, 85: 63-79.
［13］ WANG B, HO P H. Energy-efficient Routing and Bandwidth Allocation in OFDM-based Optical Networks［J］. Journal of Optical Communications and Networking, 2016, 8(2): 71-84.

[1]	WANG Jianxiao;YANG Lin;GONG Shuxi;FU Demin;FENG Xueyong;WANG Yi . Study of wide-angle scanning phased array antenna measurement [J]. J4, 2015, 42(2): 40-44.
[2]	LI Yong;JIANG Hui;WANG Xiao-yi;LIU Zheng. Design of the broadband dual-polarized probe array [J]. J4, 2009, 36(3): 468-479.
[3]	DAI Xian-ying1;WANG Wei1;ZHANG He-ming1;HE Lin2;ZHANG Jing2;HU Hui-yong1;Lü Yi1. Measurement of doping concentration in strained Si_1-xGe_x with four-probe array [J]. J4, 2003, 30(2): 255-258.
[4]	TIAN Wen-chao;JIA Jian-yuan. Overview of the mechanisms and applications of the scanning probe microscope series [J]. J4, 2003, 30(1): 108-112.

Probe selection algorithm for faulty links localization in all-optical networks

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 10