Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 2005-2008.DOI: 10.11772/j.issn.1001-9081.2018010155

Previous Articles     Next Articles

Network faulty link identification based on linear programming relaxation method

FAN Xiaobo, LI Xingming   

  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-),男,云南昆明人,教授,博士生导师,博士,主要研究方向:现代通信网理论、光传送网及智能光网络、电信网中高速传输技术及网络技术、网络管理和网络优化。
  • 基金资助:

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).

Key words: faulty link identification, end-to-end measurement, Linear Programming (LP) relaxation, optimization algorithm

摘要: 为解决通信网络中端到端测量定位故障链路的NP难问题,提出了一种新的松弛布尔约束的诊断方法。首先将网络中的路径状态和链路状态的关系建模为布尔代数方程,而故障定位的本质即满足该布尔方程条件的优化求解;然后,依据该优化表达式判断其NP性来源于链路状态的布尔约束(正常/故障),通过将布尔约束松弛为线性约束,所提方法将问题简单地转换为线性规划(LP)问题,线性规划问题非常容易求解并可以由任何LP求解器来得到故障链路集合。在真实网络拓扑中进行了链路故障诊断仿真实验,实验结果表明,所提方法与现有的经典启发式算法——TOMO相比,降低了5%~30%的误诊率。

关键词: 故障链路诊断, 端到端测量, 线性规划松弛, 优化算法

CLC Number: