Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Active Measurement for Multiple Link Failures Diagnosis in IP Networks|
|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|
|Series/Report no.:||Lecture Notes in Computer Science ; Vol. 3051,|
|Conference Name:||International Workshop on Passive and Active Measurements (5th : 2004 : Antibes-Juan les Pins, France)|
|Abstract:||Simultaneous link failures are common in IP networks . 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 . We study in particular the difference between the number of probes and beacons that are required for multiple and single failure(s) diagnosis|
|Appears in Collections:||Mathematical Sciences publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.