Efficient and Dynamic Routing Topology Inference From End-to-End Measurements
Authors:
- 22 September 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 18 (1) , 123-135
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- An active measurement system for shared environments2007
- Neighbor-Joining RevealedMolecular Biology and Evolution, 2006
- Network Tomography: Recent DevelopmentsStatistical Science, 2004
- Likelihood Based Hierarchical ClusteringIEEE Transactions on Signal Processing, 2004
- Network delay tomographyIEEE Transactions on Signal Processing, 2003
- Multicast-based inference of network-internal delay distributionsIEEE/ACM Transactions on Networking, 2002
- Internet tomographyIEEE Signal Processing Magazine, 2002
- Multicast topology inference from measured end-to-end lossIEEE Transactions on Information Theory, 2002
- Maximum likelihood network topology identification from edge-based unicast measurementsACM SIGMETRICS Performance Evaluation Review, 2002
- Full reconstruction of Markov models on evolutionary trees: Identifiability and consistencyMathematical Biosciences, 1996