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

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

Network faulty link identification based on linear programming relaxation method

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