Link identifiability in communication networks with two monitors
Authors:
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1513-1518
Abstract
We investigate the problem of identifying individual link performance metrics in a communication network by measuring end-to-end metrics of selected paths between monitors, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. In a previous work, we developed an algorithm that places the minimum number of monitors to identify all link metrics. However, even the minimum number can be large in some practical networks (e.g., 60% of all the nodes), suggesting high monitor deployment cost. In this paper, we study the dual problem where given a fixed number of monitors, we want to place them to maximize the number of identifiable link metrics, with concrete results for the case of two monitors. The significance of the two-monitor case is that all the tomographic computation can be performed at the destination monitor without shipping measurements to a central node, thus enabling endhost-based network monitoring. We develop an efficient algorithm to determine all identifiable links in an arbitrary network with a given placement of two monitors, based on which we propose an optimal two-monitor placement algorithm to maximize the number of identifiable links. Our evaluation on real ISP topologies shows that although a large number of monitors is needed to identify all link metrics, we can usually identify a substantial portion (up to 97%) of the links using a single pair of optimally placed monitors.Keywords
This publication has 10 references indexed in Scilit:
- Identifiability of link metrics based on end-to-end path measurements2013
- Compressive sensing over graphs2011
- SRLG Failure Localization in All-Optical Networks Using Monitoring Cycles and Paths2008
- Network Tomography: Identifiability and Fourier Domain Estimation2007
- Network Tomography: A Review and Recent Developments2006
- An algebraic approach to practical and scalable overlay network monitoring2004
- 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