Topology Inference and Link Parameter Estimation Based on End-to-End Measurements

Abstract

This paper focuses on the design, implementation, experimental validation, and evaluation of a network tomography approach for performing inferential monitoring based on indirect measurements. In particular, we address the problems of inferring the routing tree topology (both logical and physical) and estimating the links’ loss rate and jitter based on multicast end-to-end measurements from a source node to a set of destination nodes using an agglomerative clustering algorithm. The experimentally-driven evaluation of the proposed algorithm, particularly the impact of the employed reduction update scheme, takes place in real topologies constructed in an open large-scale testbed. Finally, we implement and present a motivating practical application of the proposed algorithm that combines monitoring with change point analysis to realize performance anomaly detection.

Keywords

• network tomography
• agglomerative clustering
• end-to-end measurements
• topology inference
• link parameters
• change point analysis