Active Measurement for Multiple Link Failures Diagnosis in IP Networks
Date
2004
Authors
Nguyen, H.
Thiran, P.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 5th International Workshop on Passive and Active Network Measurement (PAM) 19-20 April, 2004 / C. Barakat and I. Pratt (eds.), pp.185-194
Statement of Responsibility
Conference Name
International Workshop on Passive and Active Measurements (5th : 2004 : Antibes-Juan les Pins, France)
DOI
Abstract
Simultaneous link failures are common in IP networks [1]. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that minimizes both the additional traffic due to probe messages and the measurement infrastructure costs. In the first phase, using elements from max-plus algebra theory, we show that the optimal set of probes can be determined in polynomial time, and we provide an algorithm to find this optimal set of probes. In the second phase, given the optimal set of probes, we compute the location of a minimal set of measurement points (beacons) that can generate these probes. We show that the beacon placement problem is NP-hard and propose a constant factor approximation algorithm for this problem. We then apply our algorithms to existing ISP networks using topologies inferred by the Rocketfuel tool [2]. We study in particular the difference between the number of probes and beacons that are required for multiple and single failure(s) diagnosis