Monitor placement for maximal identifiability in network tomography
Authors:
- 1 April 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1447-1455
Abstract
We investigate the problem of placing a given number of monitors in a communication network to identify the maximum number of link metrics from end-to-end measurements between monitors, assuming that link metrics are additive, and measurement paths cannot contain cycles. Motivated by our previous result that complete identification of all link metrics can require a large number of monitors, we focus on partial identification using a limited number of monitors. The basis to our solution is an efficient algorithm for determining all identifiable links for a given monitor placement. Based on this algorithm, we develop a polynomial-time greedy algorithm to incrementally place monitors such that each newly placed monitor maximizes the number of additional identifiable links. We prove that the proposed algorithm is optimal for 2-vertex-connected networks, and demonstrate that it is near-optimal for several real ISP topologies that are not 2-vertex-connected. Our solution provides a quantifiable tradeoff between level of identifiability and available monitor resources.Keywords
This publication has 15 references indexed in Scilit:
- Link identifiability in communication networks with two monitors2013
- Efficient Identification of Additive Link Metrics via Network Tomography2013
- Practical Beacon Placement for Link Monitoring Using Network TomographyIEEE Journal on Selected Areas in Communications, 2006
- Network Tomography: A Review and Recent Developments2006
- Robust monitoring of link delays and faults in IP networks2004
- On the number of distributed measurement points for network tomography2003
- Multicast-based inference of network-internal delay distributionsIEEE/ACM Transactions on Networking, 2002
- Network Tomography: Estimating Source-Destination Traffic Intensities from Link DataJournal of the American Statistical Association, 1996
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972