A Topology Inference Algorithm Using Round Delay Variation

您当前的位置：

首页 >

文章列表页 >

A Topology Inference Algorithm Using Round Delay Variation

更新时间：2025-05-08

- A Topology Inference Algorithm Using Round Delay Variation
- Vol. 43, Issue 6, Pages: 28-32(2009)
- 作者机构：
  
  解放军理工大学指挥自动化学院,南京,210007
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Online First：10 June 2009，
  
  Published：2009
- 稿件说明：
移动端阅览
A Topology Inference Algorithm Using Round Delay Variation[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Hidden Terminals in Dual Busy Tone Multiple Access and an Improved Solution

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Review of the Application of EBSILON Software in Combined Heat and Power System Optimization

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Related Author

张克旺

张德运

潘煜

Related Institution

School of Electronics and Information Engineering, Xi'an Jiaotong University

⁰