基于因子图—和积算法的故障链路诊断

doi:10.3724/SP.J.1087.2012.00343

计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 343-346.DOI: 10.3724/SP.J.1087.2012.00343

基于因子图—和积算法的故障链路诊断

吕香玲,张志勇,胡光岷

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

收稿日期:2011-07-28 修回日期:2011-09-23 发布日期:2012-02-23 出版日期:2012-02-01
通讯作者: 吕香玲
作者简介:吕香玲(1987-)，女，河南商丘人，硕士研究生，主要研究方向：故障链路诊断；
张志勇(1985-)，男，重庆万州人，博士研究生，主要研究方向：网络测量、网络性能监测；
胡光岷(1966-)，男，四川眉山人，教授，博士生导师，主要研究方向：网络信号处理、网络行为学及安全。
基金资助:
国家自然科学基金资助项目(61072080)

Faulty link identification based on factor graph and sum product algorithm

LV Xiang-ling,ZHANG Zhi-yong,HU Guang-min

School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China

Received:2011-07-28 Revised:2011-09-23 Online:2012-02-23 Published:2012-02-01
Contact: LV Xiang-ling

摘要/Abstract

摘要： 为求得网络内部链路的先验故障概率,提出一种估计链路状态分布的新方法。采用因子图模型描述链路状态和路径状态间的联合概率分布，并使用和积算法求得各链路状态的最大后验估计，然后利用估计出的链路故障概率和当前测量数据推断链路的当前状态。仿真结果表明，当网络规模达到400个节点时，所提方法的计算时间比联立方程组求解法低两个数量级以上，具有更好的可扩展性。

关键词: 端到端测量, 故障链路诊断, 最大后验估计, 因子图, 和积算法

Abstract: In order to estimate the prior probability of the link failure, the paper proposed a new method for estimating the link state distribution. The new scheme adopted the factor graph to describe the joint probability distribution between the link and the path, and used the sum-product algorithm to obtain the maximum posterior estimate of the state of the link, then used the failures probability of the link and the current measurement data to conclude the current state of the link. The simulation results show that, when the size of network reaches 400 nodes, the computation time of the new scheme is more than two orders of magnitude lower than the linear equations method, and has better scalability.

Key words: end-to-end measurement, faulty link identification, maximum posterior estimation, factor graph, sum product algorithm

中图分类号:

TP393.06

吕香玲张志勇胡光岷. 基于因子图—和积算法的故障链路诊断[J]. 计算机应用, 2012, 32(02): 343-346.

LV Xiang-ling ZHANG Zhi-yong HU Guang-min. Faulty link identification based on factor graph and sum product algorithm[J]. Journal of Computer Applications, 2012, 32(02): 343-346.

参考文献

[1]CASTRO R, COATES M, LIANG G, et al. Network tomography: Recent developments [J]. Statistical Science, 2004, 19(3): 499-517. [2]DUFFIELD N G, PRESTI F L, PAXSON V, et al. Network loss tomography using striped unicast probes [J]. IEEE/ACM Transactions on Networking, 2006, 14(4): 697-710. [3]CHEN AIYOU,CAO JIN,BU TIAN.Network tomography: Identifiability and Fourier domain estimation [C]// IEEE INFOCOM 2007:26th IEEE International Conference on Computer Communications.Piscataway:IEEE,2007:1875-1883. [4]ERIKSSON B, DASARATHY G, BARFORD P, et al. Toward the practical use of network tomography for Internet topology discovery [C]// IEEE INFOCOM 2010. Piscataway: IEEE, 2010:1-9. [5]DUFFIELD N G. Network tomography of binary network performance characteristics [J]. IEEE Transactions on Information Theory, 2006, 52(12): 5373-5388. [6]PADMANABHAN V N, QIU L, WANG H J. Server-based inference of Internet link lossiness [C]// INFOCOM 2003: Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE, 2003, 1: 145-155. [7]NGUYEN H X, THIRAN P. The boolean solution to the congested IP link location problem: theory and practice [C]// INFOCOM 2007: 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 2117-2125. [8]GHITA D, ARGYRAKI K, THIRAN P. Network tomography on correlated links [C]// IMC '10: Proceedings of the 10th Annual Conference on Internet Measurement. New York: ACM, 2010: 1-10. [9]NGUYEN H X, THRIAN P. Network loss inference with second order statistics of end-to-end flows [C]// IMC '07: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2007: 1-13. [10]GHITA D, NGUYEN H X, KURANT M, et al. Netscope: Practical network loss tomography [C]// IEEE INFOCOM 2010. Piscataway: IEEE, 2010:1-9. [11]MAO YONGYI, LI BAOCHUN. A factor graph approach to link loss monitoring in wireless sensor networks [J]. IEEE Journal on Selected Areas in Communications, 2006,23(4):820-829. [12]GUO DONG, WANG XIAODONG. Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction [J]. IEEE Transactions on Signal Processing, 2003, 51(8):2205-2218.

基于因子图—和积算法的故障链路诊断

Faulty link identification based on factor graph and sum product algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	李添正, 王春桃. 基于马尔可夫随机场的加密二值图像有损压缩算法[J]. 计算机应用, 2020, 40(5): 1354-1363.
[2]	吴婉婷, 朱燕, 黄定江. 在线投资组合选择的半指数梯度策略及实证分析[J]. 计算机应用, 2019, 39(8): 2462-2467.
[3]	范晓波, 李兴明. 基于线性松弛方法的网络故障链路诊断[J]. 计算机应用, 2018, 38(7): 2005-2008.
[4]	高军强, 汤霞清, 张环, 郭理彬. 基于因子图算法的INS/GPS信息滞后处理方法[J]. 计算机应用, 2018, 38(11): 3342-3347.
[5]	崔建华, 王忠勇, 张传宗, 张园园. 基于因子图和联合消息传递的无线网络协作定位算法[J]. 计算机应用, 2017, 37(5): 1306-1310.
[6]	颜斌贾霞王小明郭银景郝建军. 相关分块衰落信道下基于因子图EM算法的解码方法[J]. 计算机应用, 2013, 33(03): 607-610.
[7]	张菁. 基于两代树的低密度校验码校验矩阵构造方法[J]. 计算机应用, 2011, 31(04): 945-947.
[8]	耿蕾蕾蔚承建. 改进的最大和分散式协调算法[J]. 计算机应用, 2010, 30(8): 2073-2076.