Efficient and Dynamic Routing Topology Inference From End-to-End Measurements

Inferring the routing topology and link performance from a node to a set of other nodes is an important component in network monitoring and application design. In this paper, we propose a general framework for designing topology inference algorithms based on additive metrics. The framework can flexi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2010-02, Vol.18 (1), p.123-135
Main Authors: Jian Ni, Haiyong Xie, Tatikonda, S., Yang, Y.R.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Computer networks
Dynamics
Fuses
Inference
Inference algorithms
Internet
Maximum likelihood detection
Monitoring
Multicast algorithms
Network measurement
network monitoring
network tomography
Network topology
Networks
Peer to peer computing
Polynomials
Routing
Routing (telecommunications)
routing topology inference
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Inferring the routing topology and link performance from a node to a set of other nodes is an important component in network monitoring and application design. In this paper, we propose a general framework for designing topology inference algorithms based on additive metrics. The framework can flexibly fuse information from multiple measurements to achieve better estimation accuracy. We develop computationally efficient (polynomial-time) topology inference algorithms based on the framework. We prove that the probability of correct topology inference of our algorithms converges to one exponentially fast in the number of probing packets. In particular, for applications where nodes may join or leave frequently such as overlay network construction, application-layer multicast, and peer-to-peer file sharing/streaming, we propose a novel sequential topology inference algorithm that significantly reduces the probing overhead and can efficiently handle node dynamics. We demonstrate the effectiveness of the proposed inference algorithms via Internet experiments.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2009.2022538