Inferring Link Metrics From End-To-End Path Measurements: Identifiability and Monitor Placement
Authors:
- 18 June 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (4) , 1351-1368
Abstract
We investigate the problem of identifying individual link metrics in a communication network from end-to-end path measurements, under the assumption that link metrics are additive and constant. To uniquely identify the link metrics, the number of linearly independent measurement paths must equal the number of links. Our contribution is to characterize this condition in terms of the network topology and the number/placement of monitors, under the constraint that measurement paths must be cycle-free. Our main results are: 1) it is generally impossible to identify all the link metrics by using two monitors; 2) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; 3) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only facilitate efficient identifiability tests, but also enable an efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed algorithm achieves identifiability using a much smaller number of monitors than a baseline solution.Keywords
Funding Information
- U.S. Army Research Laboratory
- U.K. Ministry of Defence
This publication has 30 references indexed in Scilit:
- Network Tomography: A Review and Recent Developments2006
- Network Tomography: Recent DevelopmentsStatistical Science, 2004
- Multicast-based inference of network-internal delay distributionsIEEE/ACM Transactions on Networking, 2002
- Internet tomographyIEEE Signal Processing Magazine, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- The use of end-to-end multicast measurements for characterizing internal network behaviorIEEE Communications Magazine, 2000
- Critical Power for Asymptotic Connectivity in Wireless Networks1999
- A note on finding the bridges of a graphInformation Processing Letters, 1974
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972