利用往返时延抖动的网络拓扑推断算法

赵洪华; 陈鸣

您当前的位置：

首页 >

文章列表页 >

利用往返时延抖动的网络拓扑推断算法

更新时间：2025-05-08

- 利用往返时延抖动的网络拓扑推断算法
- A Topology Inference Algorithm Using Round Delay Variation
- 西安交通大学学报 2009年43卷第6期页码：28-32
- 作者机构：
  
  解放军理工大学指挥自动化学院,南京,210007
- 作者简介：
- 基金信息：
  
  : 2008-10-07. 作者简介: 赵洪华(1979-),男,讲师. 基金项目: 国家自然科学基金重大研究计划资助项目(90304010);国家高技术研究发展计划资助项目(2007AA01Z418)
- DOI：
  中图分类号： TP393
- 网络首发：2009-06-10，
  
  纸质出版：2009
- 稿件说明：
移动端阅览
赵洪华, 陈鸣. 利用往返时延抖动的网络拓扑推断算法[J]. 西安交通大学学报, 2009,43(6):28-32.

A Topology Inference Algorithm Using Round Delay Variation[J]. 2009, 43(6): 28-32.
赵洪华, 陈鸣. 利用往返时延抖动的网络拓扑推断算法[J]. 西安交通大学学报, 2009,43(6):28-32. DOI：

A Topology Inference Algorithm Using Round Delay Variation[J]. 2009, 43(6): 28-32. DOI：

摘要

为了克服基于端到端单向时延的拓扑推断需要时钟同步及节点间合作的限制

提出了一种利用往返时延抖动的拓扑推断算法.首先定义了四元组列车

其由4个长度相同的ping分组组成

4个ping分组组成2个相邻的紧接分组对

2个紧接分组对的目标地址相同.在空间独立性、时间独立性的条件下

通过四元组列车测量获得的往返时延抖动可以计算节点间的相关性

再根据节点间的相关性便可推断节点间共享链路

从而推断出网络拓扑.理论分析与仿真结果表明

所提算法的收敛速度高于基于端到端单向时延推断拓扑法

并且只需要一个测量节点.

Abstract

In order to reduce the limits of time synchronization and cooperation between nodes in topology inference based on one way delay

a topology inference algorithm based on round delay variation is proposed. A 4-tuple packets train is defined and is composed of 2 packets pairs. Each packets pair is composed of 2 ping packets. The correlations among nodes are then calculated by round delay variation measured with the 4-tuple packets train. Then the links of sharing between nodes and the topology are inferred. The feasibility and correctness of the topology inference based on round delay variation are analyzed theoretically. The algorithm is tested through simulations by NS2. The results show that the convergence of topology inference based on round delay variation is faster than the convergence of topology inference based on one way delay

and the topology inference based on round delay variation needs only one measurement node.

关键词

Keywords

references

CASTRO R, COATES M, LIANG G, et al. Network tomography: recent developments[J]. Statistical Science, 2004, 52(3): 499-517.

LAWRENCE E, MICHAILIDIS G, NAIR V. Network delay tomography using flexi cast experiments[J]. Journal of the Royal Statistical Society Series: B, 2006, 68:785-813.

DUFFIELD N G, LO F, PAXSON V, et al. Network loss tomography using striped unicast probes[J]. IEEE/ACM Transactions on Networking, 2006, 14(4): 697-710.

RATNASAMY S, MCCANNE S. Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements[C]∥Proceedings of IEEE INFOCOM 1999. Piscataway, NJ, USA: IEEE, 1999: 353-360.

DUFFIELD N, HOROWITZ J, PRESTI L F, et al. Multicast topology inference from measured end-to-end loss [J]. IEEE Transactions on Information Theory, 2002, 48(1): 26-45.

DUFFIELD N, HOROWITZ J, PRESTI L F, et al. Multicast topology inference from end-to-end measurements[C]∥The 13th ITC Seminar on IP Traffic Measurement, Modelling and Management. Würzburg, Germany: University of Würzburg, 2000: 654-674.

SHIH M, HERO A O. Hierarchical inference of unicast network topologies based on end-to-end measurements [J]. IEEE Transactions on Signal Processing, 2007, 55(5): 1708-1718.

COATES M, CASTRO R, NOWAK R. Maximum likelihood network topology identification from edge-based unicast measurements[J]. SIGMETRICS Perform Eval Rev, 2002, 30(1): 11-20.

DEMICHELIS C, CHIMENTO P. IP packet delay variation metric for IPPM [EB/OL]. [2008-01-10]. htttp:∥www.ietf.org/internetdrafts/draft-ietf-ippm-ipdv-09.txt.

王立,李增智,宋承谦,等.一种满足多服务质量约束的动态组播路由算法[J].西安交通大学学报,2004,38(4):420-423.

WANG Li, LI Zengzhi, SONG Chengqian, et al. Dynamic multicast routing algorithm satisfying multiple QoS constraints [J]. Journal of Xi'an Jiaotong University, 2004, 38(4): 420-423.

Nsnam Sourceforge Project. The network simulator 2 [EB/OL]. [2008-01-10].http:∥nsnam.isi.edu/nsnam/.

PHILIP B. A survey on tree edit distance and related problems [EB/OL]. [2008-01-10]. http:∥grfia.dlsi.ua.es/ml/algorithms/references/editsurvey-bille.pdf.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

双忙音媒体接入协议中的隐藏节点问题及其改进

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

冷库水平空气幕热湿阻隔性能数值模拟研究

不同板叠材料热声热机能量转换过程数值模拟研究