The Boolean Solution to the Congested IP Link Location Problem: Theory and Practice
Authors:
- H. X. NguyenHNH. X. Nguyen
- P. ThiranPTP. Thiran
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 2117-2125
Abstract
Like other problems in network tomography or traffic matrix estimation, the location of congested IP links from end-to-end measurements requires solving a system of equations that relate the measurement outcomes with the variables representing the status of the IP links. In most networks, this system of equations does not have a unique solution. To overcome this critical problem, current methods use the unrealistic assumption that all IP links have the same prior probability of being congested. We find that this assumption is not needed, because these probabilities can be uniquely identified from a small set of measurements by using properties of Boolean algebra. We can then use the learnt probabilities as priors to find rapidly the congested links at any time, with an order of magnitude gain in accuracy over existing algorithms. We validate our results both by simulation and real implementation in the PlanetLab network.Keywords
This publication has 15 references indexed in Scilit:
- Towards deterministic network diagnosisACM SIGMETRICS Performance Evaluation Review, 2006
- An algebraic approach to practical and scalable overlay network monitoring2004
- Computing the Unmeasured: An Algebraic Approach to Internet MappingIEEE Journal on Selected Areas in Communications, 2004
- User-level internet path diagnosis2003
- Model-based identification of dominant congested links2003
- Internet tomographyIEEE Signal Processing Magazine, 2002
- The use of end-to-end multicast measurements for characterizing internal network behaviorIEEE Communications Magazine, 2000
- On the origin of power laws in Internet topologiesACM SIGCOMM Computer Communication Review, 2000
- Network Tomography: Estimating Source-Destination Traffic Intensities from Link DataJournal of the American Statistical Association, 1996
- An algorithm for set covering problemEuropean Journal of Operational Research, 1987