Name
Title | ||
|---|---|---|
Minimizing Probing Cost for Detecting Interface Failures: Algorithms and Scalability Analysis |
Abstract | ||
|---|---|---|
The automatic detection of failures in IP paths is an essential step for operators to perform diagnosis or for overlays to adapt. We study a scenario where a set of monitors send probes toward a set of target end-hosts to detect failures in a given set of IP interfaces. Unfortunately, there is a large probing cost to monitor paths between all monitors and targets at a very high frequency. We make two major contributions to reduce this probing cost. First, we propose a formulation of the probe optimization problem which, in contrast to the established formulation, is not NP complete. Second, we propose two linear programming algorithms to minimize probing cost. Our algorithms combine low frequency per-path probing to detect per-interface failures at a higher frequency. We analyze our solutions both analytically and experimentally. Our theoretical results show that the probing cost increases linearly with the number of interfaces in a random power-law graph. We confirm this linear increase in Internet graphs measured from PlanetLab and RON. Hence, Internet graphs belong to the most costly class of graph to probe. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/INFCOM.2009.5062054 | INFOCOM |
Keywords | Field | DocType |
IP networks,Internet,fault diagnosis,graph theory,linear programming,system recovery,IP interfaces,IP paths,Internet graphs,NP complete,PlanetLab,RON,automatic failure detection,fault diagnosis,interface failure detection,linear programming algorithms,low frequency per-path probing,per-interface failures,probe optimization,probing cost,random power-law graph,scalability analysis | PlanetLab,Computer science,Computer network,Real-time computing,Linear programming,Condition monitoring,Overlay,Optimization problem,Distributed computing,Graph theory,Algorithm design,Algorithm,Scalability | Conference |
ISSN | Citations | PageRank |
0743-166X | 7 | 0.53 |
References | Authors | |
19 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hung Xuan Nguyen | 1 | 83 | 5.03 |
| Renata Teixeira | 2 | 1636 | 100.35 |
| Patrick Thiran | 3 | 2712 | 217.24 |
| Christophe Diot | 4 | 7831 | 590.69 |