Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 2005-2008.

### Network faulty link identification based on linear programming relaxation method

1. School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
• Received:2018-01-18 Revised:2018-03-16 Online:2018-07-10 Published:2018-07-12
• Supported by:
This work is partially supported by the National Natural Science Foundation of China (61671112).

### 基于线性松弛方法的网络故障链路诊断

1. 电子科技大学 通信与信息工程学院, 成都 611731
• 通讯作者: 范晓波
• 作者简介:范晓波(1988-),男,湖南邵阳人,博士研究生,主要研究方向:网络性能推理、网络层析、信号处理;李兴明(1956-),男,云南昆明人,教授,博士生导师,博士,主要研究方向:现代通信网理论、光传送网及智能光网络、电信网中高速传输技术及网络技术、网络管理和网络优化。
• 基金资助:
国家自然科学基金资助项目（61671112）。

Abstract: Concerning the NP (Nondeterministic Polynomial)-hard problem of localizing link failures from end-to-end measurement in communication network, a new tomography method which relaxes the Boolean constraints was proposed. Firstly, the relationship between path state and link state in a network was modeled as Boolean algebraic equations, and the essence of localizing failures was treated as an optimization problem under the constraints of these equations. Then the NP property was derived from the binary states (normal/failed) of link state in the optimization problem. Therefore, by relaxing the Boolean constraints, the proposed method simply transformed the problem into a Linear Programming (LP) problem, which can be easily solved by any LP solver to get the set of failed links. Simulation experiments were conducted to identity link failures in real network topologies. The experimental results show that the false negative rate of the proposed method is 5%-30% lower than that of the classical heuristic algorithm TOMO (TOMOgraphy).

CLC Number: