利用有限混合模型的高效网络拓扑推断算法

doi:10.3969/j.issn.1001-2400.2015.04.022

Abstract

Abstract:

The performance of the existing efficient topology inference algorithm is highly sensitive to the threshold. To address the problem, a finite mixture model based topology inference algorithm is proposed. Firstly, a leaf node is selected from the original leaf-node set, and then the similarities between the node and the other leaf nodes are measured, after which the original leaf-node set is roughly divided into several subsets using the finite mixture model based on the measured similarities. The internal nodes corresponding to each subset could be inferred afterwards. Subsequently, the above procedures are applied for each subset obtained from rough division, and the process is iterated until all of the internal nodes are found. Analysis and simulation show that the proposed algorithm needs less correlation data than the existing algorithm, and performs almost as well as the existing algorithm with the optimum threshold.

Key words: topology inference, network tomography, finite mixture model

ZHANG Runsheng;LIU Jian;LI Yanbin. Efficient topology inference algorithm using the finite mixture model[J].J4, 2015, 42(4): 133-139.

References

［1］ Zhang X, Phillips C. A Survey on Selective Routing Topology Inference through Active Probing［J］. IEEE Communications Surveys and Tutorials, 2012, 14(4): 1129-1141.
［2］张润生, 李艳斌, 李啸天. 基于合并分层聚类的网络拓扑推断算法［J］. 电子学报, 2013, 41(12): 2346-2352.
Zhang Runsheng, Li Yanbin, Li Xiaotian. Agglomerative Hierarchical Clustering Based Algorithm for Network Topology Inference ［J］. Acta Electronica Sinica, 2013, 41(12): 2346-2352.
［3］赵洪华, 陈鸣, 魏镇韩. 层析成像技术中的自适应网络拓扑推断算法［J］. 西安电子科技大学学报, 2009, 36(3): 547-552.
Zhao Honghua, Chen Ming, Wei Zhenhan. Self Adaptive Network Topology Inference Algorithm in Tomography［J］. Journal of Xidian University, 2009, 36(3): 547-552.
［4］ Castro R, Coates M, Nowak R. Likelihood Based Hierarchical Clustering ［J］. IEEE Transactions on Signal Processing, 2004, 52(8): 2308-2321.
［5］ Shih M, Hero A. Hierarchical Inference of Unicast Network Topologies Based on End-to-End Measurements ［J］. IEEE Transactions on Signal Processing, 2007, 55(5): 1708-1718.
［6］ Fei G, Hu G. Improving Maximum-likelihood-based Topology Inference by Sequentially Inserting Leaf Nodes［J］. IET Communications, 2011, 5(15): 2221-2230.
［7］ Ni J, Xie H, Tatikonda S, et al. Efficient and Dynamic Routing Topology Inference from End-to-End Measurements ［J］. IEEE／ACM Transactions on Networking, 2010, 18(1): 123-135.
［8］ Eriksson B, Dasarathy G, Barford P, et al. Efficient Network Tomography for Internet Topology Discovery［J］. IEEE／ACM Transactions on Networking, 2012, 20(3): 931-943.
［9］于林森, 张田文. 用于图像分割的滤波EM算法［J］. 计算机学报, 2006, 29(6): 928-935.
Yu Linsen, Zhang Tianwen. Filtering EM Algorithm for Image Segmentation［J］. Chinses Journal of Computers, 2006, 29(6): 928-935.
［10］王戈, 于宏毅, 沈智翔, 等. 一种基于EM算法的快速收敛参数估计方法［J］. 吉林大学学报(工学版), 2013, 43(2): 532-537.
Wang Ge, Yu Hongyi, Shen Zhixiang, et al. Fast Convergence Parameter Estimation Method Based on Expectation-maximum Algorithm［J］. Journal of Jilin University(Engineering and Technology Edtion), 2013, 43(2): 532-537.

Efficient topology inference algorithm using the finite mixture model

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 10