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

doi:10.11772/j.issn.1001-9081.2018010155

计算机应用 ›› 2018, Vol. 38 ›› Issue (7): 2005-2008.DOI: 10.11772/j.issn.1001-9081.2018010155

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

范晓波, 李兴明

电子科技大学通信与信息工程学院, 成都 611731

收稿日期:2018-01-18 修回日期:2018-03-16 发布日期:2018-07-12 出版日期:2018-07-10
通讯作者: 范晓波
作者简介:范晓波(1988-),男,湖南邵阳人,博士研究生,主要研究方向:网络性能推理、网络层析、信号处理;李兴明(1956-),男,云南昆明人,教授,博士生导师,博士,主要研究方向:现代通信网理论、光传送网及智能光网络、电信网中高速传输技术及网络技术、网络管理和网络优化。
基金资助:
国家自然科学基金资助项目（61671112）。

Network faulty link identification based on linear programming relaxation method

FAN Xiaobo, LI Xingming

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-12 Published:2018-07-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61671112).

摘要/Abstract

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

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

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

中图分类号:

TP393.06

范晓波, 李兴明. 基于线性松弛方法的网络故障链路诊断[J]. 计算机应用, 2018, 38(7): 2005-2008.

FAN Xiaobo, LI Xingming. Network faulty link identification based on linear programming relaxation method[J]. Journal of Computer Applications, 2018, 38(7): 2005-2008.

参考文献

[1] DHAMDHERE A, TEIXEIRA R, DOVROLIS C, et al. NetDiagnoser:troubleshooting network unreachabilities using end-to-end probes and routing data[C]//Proceedings of the 2007 International Conference on Emerging Networking Experiments and Technologies. New York:ACM, 2007:1251-1264.
[2] COATES M, HERO A, NOWAK R, et al. Internet tomography[J]. IEEE Signal Processing Magazine, 2002, 19(3):47-65.
[3] FAN X B, LI X M. Network tomography via sparse Bayesian learning[J]. IEEE Communications Letters, 2017, 21(4):781-784.
[4] PADMANABHAN V N, QIU L L, WANG H J. Server-based inference of Internet performance[C]//Proceedings of the 2003 International Conference on Computer Communications. Piscataway, NJ:IEEE, 2003:1281-1291.
[5] DUFFIELD N. Network tomography of binary network performance characteristics[J]. IEEE Transactions on Information Theory, 2006, 52(12):5373-5388.
[6] NGUYEN H X, THIRAN P. The Boolean solution to the congested IP link location problem:theory and practice[C]//Proceedings of the 2007 International Conference on Computer Communications. Piscataway, NJ:IEEE, 2007:2117-2125.
[7] 吕香玲,张志勇,胡光岷.基于因子图-和积算法的故障链路诊断[J].计算机应用,2012,32(2):343-346.(LYU X L, ZHANG Z Y, HU G M. Faulty link identification based on factor graph and sum product algorithm[J]. Journal of Computer Applications, 2012, 32(2):343-346.)
[8] MA L, HE T, SWAMI A, et al. Network capability in localizing node failures via end-to-end path measurements[J]. IEEE/ACM Transactions on Networking, 2017, 25(1):434-450.
[9] JOSHI S, BOYD S. Sensor selection via convex optimization[J]. IEEE Transactions on Signal Processing, 2009, 57(2):451-462.
[10] MALIOUTOV D, MALYUTOV M. Boolean compressed sensing:LP relaxation for group testing[C]//Proceedings of the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ:IEEE, 2012:3305-3308.
[11] KLEER J D. Hitting set algorithms for model-based diagnosis[C]//Proceedings of the 2011 International Workshop on Principles of Diagnosis. New York:ACM, 2011:2311-2319.
[12] BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge:Cambridge University Press, 2004:561-615.
[13] SPRING N, MAHAJAN R, WETHERALL D. Measuring ISP topologies with Rocketfuel[C]//Proceedings of the 2002 ACM Special Interest Group on Data Communication. New York:ACM, 2002:133-146.

[1]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[2]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[3]	高培根, 锁斌. 基于加权犹豫模糊集的实验设计与分阶段PSO-Kriging建模[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2144-2150.
[4]	郑志强, 段海滨. 基于有限忍耐度鸽群优化的无人机近距空战机动决策[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1401-1407.
[5]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[6]	韦修喜, 彭茂松, 黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1009-1017.
[7]	唐睿, 岳士博, 张睿智, 刘川, 庞川林. UAV协助下非正交多址接入使能的数据采集系统中能效优化机制[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1209-1218.
[8]	陈雅琴, 王鹏. 基于优化算法量子动力学框架的势垒估计准则[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1180-1186.
[9]	郭玲玲, 李志强, 段孟环. 量子近似优化算法在精确覆盖问题中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 849-854.
[10]	任帅, 纪元法, 孙希延, 韦照川, 林子安. 基于改进灰狼优化与支持向量回归的滑坡位移预测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 972-982.
[11]	杜晓昕, 周薇, 王浩, 郝田茹, 王振飞, 金梅, 张剑飞. 智能算法的亚群优化策略综述[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 819-830.
[12]	王震, 张珊珊, 邬斌扬, 苏万华. 基于自适应粒子群优化算法的串联复合涡轮储能优化策略[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 611-618.
[13]	彭鹏, 倪志伟, 朱旭辉, 陈千. 改进萤火虫群算法协同差分隐私的干扰轨迹发布[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 496-503.
[14]	刘勇, 杨锟. 新能源汽车电池回收网点竞争选址模型及算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 595-603.
[15]	余家宸, 杨晔. 基于裁剪近端策略优化算法的软机械臂不规则物体抓取[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3629-3638.

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

Network faulty link identification based on linear programming relaxation method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics