Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: Active Measurement for Multiple Link Failures Diagnosis in IP Networks
Author: Nguyen, H.
Thiran, P.
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
Publisher: Springer-Verlag
Publisher Place: Berlin
Issue Date: 2004
Series/Report no.: Lecture Notes in Computer Science ; Vol. 3051,
ISBN: 3540214925
ISSN: 0302-9743
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 [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
RMID: 0020093716
DOI: 10.1007/b96961
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.