一种高效的单播网络自适应拓扑推测算法

doi:10.3969/j.issn.0372-2112.2013.10.003

电子学报 ›› 2013, Vol. 41 ›› Issue (10): 1888-1894.DOI: 10.3969/j.issn.0372-2112.2013.10.003

一种高效的单播网络自适应拓扑推测算法

杨京礼, 姜守达, 魏长安, 孙超

哈尔滨工业大学自动化测试与控制系, 黑龙江哈尔滨 150001

收稿日期:2012-09-16 修回日期:2012-12-21 出版日期:2013-10-25
- 作者简介:
- 杨京礼 男,1984年出生,哈尔滨工业大学自动化测试与控制系博士研究生.主要研究方向为网络测量与网络层析成像技术. E-mail:icehit0615@163.com 姜守达 男,1964年出生,哈尔滨工业大学自动化测试与控制系教授.主要研究方向为虚拟试验技术、网络测量技术等. 魏长安 男,1981年出生,哈尔滨工业大学自动化测试与控制系讲师.主要研究方向为虚拟试验技术、自动测试技术等.孙超男,1978年出生,哈尔滨工业大学自动化测试与控制系讲师.主要研究方向为虚拟试验技术、图像处理等.
- 基金资助:
- 黑龙江省博士后基金 (No.LBH-Z11171)

Efficient and Adaptive Topology Inference Algorithm for Unicast Network Measurements

YANG Jing-li, JIANG Shou-da, WEI Chang-an, SUN Chao

Automatic Test and Control Institute, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China

Received:2012-09-16 Revised:2012-12-21 Online:2013-10-25 Published:2013-10-25
- Supported by:
- Postdoctoral Foundation of Heilongjiang Province (No.LBH-Z11171)

摘要/Abstract

摘要： 为提高单播网络拓扑推测的效率和准确性,本文提出一种高效的单播网络自适应拓扑推测算法.该算法利用探测包中的TTL信息作为二分深度优先搜索排序中参考节点的选择依据,有效降低测量过程中所需的背靠背包对数量,提高拓扑推测的效率;通过对现有的深度优先搜索下网络拓扑推测算法原理的分析,给出该算法能够正确推测出整个网络拓扑的充分条件,在此基础上提出一种自适应判定阈值选择方法,有效提高网络链路参数未知情况下的拓扑推测准确性.仿真实验结果表明,本文所提出的算法具备更高的拓扑推测效率和准确性.

关键词: 网络测量, 网络层析成像, 拓扑推测, 深度优先搜索

Abstract: In order to improve the accuracy and efficiency of the topology inference algorithm for unicast network,an efficient and adaptive topology inference algorithm is proposed.With the information of TTL hop count,this algorithm reduces the number of the probe pairs needed in the process of bisection Depth-First Search Ordering,and improve the efficiency of the topology inference.On the other hand,through the analysis of the principle of the Depth-First Search topology inference algorithm,a sufficient condition for the algorithm to return the correct network topology is given.Based on this condition,an adapt threshold selection method is proposed,it can improve the accuracy of the topology inference when the network link parameters are unknown.Simulation results show this algorithm can obtain a higher accuracy and efficiency.

Key words: network measurement, network tomography, topology inference, depth-first search

中图分类号:

TP393

杨京礼, 姜守达, 魏长安, 等. 一种高效的单播网络自适应拓扑推测算法[J]. 电子学报, 2013, 41(10): 1888-1894.

YANG Jing-li, JIANG Shou-da, WEI Chang-an, et al. Efficient and Adaptive Topology Inference Algorithm for Unicast Network Measurements[J]. Acta Electronica Sinica, 2013, 41(10): 1888-1894.

参考文献

[1] Coates M,Hero A,Nowak R,et al.Internet tomography[J].IEEE Signal Processing Magazine,2002,19(3):47-65.

[2] Donnet D,Friedman T.Internet topology discovery:A survey[J].IEEE Communications Surveys and Tutorials,2007,9(4):2-15.

[3] 赵洪华,陈鸣.基于网络层析成像技术的拓扑推断[J].软件学报,2010,21(1):133-146. Zhao Hong-hua,Chen Ming.Topology inference based on newtork tomography[J].Journal of Software,2010,21(1):133-146.

[4] Duffield N,Horowitz J,et al.Multicast topology inference from measured end-to-end loss[J].IEEE Transactions on Information Theory,2002,48(1):26-45.

[5] Zhang X,Phillips C.Asurvey on selective routing topology inference through active probing[J].IEEE Communications Surveys and Tutorials,2011,9(23):1-13.

[6] Coates M,Castro R,Nowak R.Maximum likelihood network topology identification from edge-based unicast measurements [A].International Conference on Measurement and Modeling of Computer Systems [C].Marina Del Rey:ACM,2002.11-20.

[7] Fei G,Hu G.Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes[J].IET Communications,2011,5(15):2221-2230.

[8] Shih Meng-Fu,Hero Ⅲ,et al.Hierarchical inference of unicast network topologies based on end-to-end measurements[J].IEEE Transactions on Signal Processing,2007,55(51):1708-1718.

[9] Ni Jian,Tatikonda S.A markov random field approach to multicast-based network inference problems [A].International Symposium on Information Theory [C].Seattle:IEEE,2006.2769-2773.

[10] Ni Jian,Xie H 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.

[11] Eriksson B,Dasarathy G,Barford P,et al.Toward the practical use of network tomography for internet topology discovery [A].Proceedings of IEEE INFO-COM 2010 [C].San Diego:IEEE,2010.1-9.

[12] Eriksson B,Dasarathy G,Barford P,Nowak R.Efficient network tomography for internet topology discovery[J].IEEE/ACM Transactions on Networking,2012,20(3):931-943.

[13] Clegg R G,Cairano-Gilfedder C D,Zhou S.A critical look at power lawmodeling of the Internet[J].Computer Communications,2010,33(3):259-268.

[14] Alerto M,Ibrahim M,John B.On the origin of power laws in internet topologies.ACM Computer Communication Review,2000,30(2):18-28.

[15] Knight K,Nguyen H X,et al.The internet topology zoo [OL].http://www.topology-zoo.org.

一种高效的单播网络自适应拓扑推测算法

Efficient and Adaptive Topology Inference Algorithm for Unicast Network Measurements

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

[1]	欧阳与点, 谢鲲, 谢高岗, 文吉刚. 面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[J]. 电子学报, 2022, 50(7): 1653-1663.
[2]	姜守达, 尹文涛, 杨京礼, 魏长安. 基于最大公共路径匹配的拓扑推断算法[J]. 电子学报, 2016, 44(9): 2189-2196.
[3]	尹文涛, 杨京礼, 姜守达, 魏长安. 基于子树丢包模式的链路丢包率快速推断算法[J]. 电子学报, 2016, 44(3): 565-571.
[4]	陈松;王珊;周明天. 基于实时分析的网络测量抽样统计模型[J]. 电子学报, 2010, 38(5): 1177-1180.
[5]	曾彬;张大方;黎文伟;谢高岗. 基于Gilbert丢包机制的TCP吞吐量模型[J]. 电子学报, 2009, 37(8): 1728-1732.
[6]	钱峰;胡光岷;姚兴苗;李乐民. 一种非平稳网络延迟层析成像的方法[J]. 电子学报, 2008, 36(7): 1338-1343.
[7]	程京, 沈永坚, 张大方, 黎文伟. TCP-Shape:一种改进的网络拥塞控制算法研究[J]. 电子学报, 2006, 34(9): 1621-1625.
[8]	胡汉平, 梁兴, 张宝良. 一种主动防御的网络传输系统[J]. 电子学报, 2005, 33(4): 701-705.
[9]	王洪波, 林宇, 金跃辉, 程时端. 一个消除单向时延测量中时钟频差和时钟重置的新方法[J]. 电子学报, 2005, 33(4): 584-589.
[10]	王娜, 纪震, 贾传荧, 李霞. 基于内存优化和启发式深度优先搜索的小波零树图像编码算法[J]. 电子学报, 2005, 33(3): 440-443.
[11]	杨家海;吴建平;C Liu. 基于非平稳型流量队列模型的Internet流量测量研究[J]. 电子学报, 2004, 32(5): 727-730.
[12]	林宇;邬海涛;程时端;王重钢;金跃辉;王文东. 网络瓶颈带宽测量的噪声分析[J]. 电子学报, 2004, 32(4): 552-556.
[13]	林宇;程时端;邬海涛;金跃辉;王文东. IP网端到端性能测量技术研究的进展[J]. 电子学报, 2003, 31(8): 1227-1233.
[14]	赵永祥;陈常嘉. 网络多流控制器[J]. 电子学报, 2003, 31(2): 259-263.