loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
10th Pacific Rim International Symposium on Dependable Computing (PRDC'04)
An Algorithmic Approach to Identifying Link Failures
Papeete, Tahiti, French Polynesia
March 03-March 05
ISBN: 0-7695-2076-6
ASCII Text
x 
 
Mohit Lad, Akash Nanavati, Dan Massey, Lixia Zhang, "An Algorithmic Approach to Identifying Link Failures," Pacific Rim International Symposium on Dependable Computing, IEEE, pp. 25-34, 10th Pacific Rim International Symposium on Dependable Computing (PRDC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/PRDC.2004.1276549,
author = {Mohit Lad and Akash Nanavati and Dan Massey and Lixia Zhang},
title = {An Algorithmic Approach to Identifying Link Failures},
journal ={Pacific Rim International Symposium on Dependable Computing, IEEE},
volume = {0},
year = {2004},
isbn = {0-7695-2076-6},
pages = {25-34},
doi = {http://doi.ieeecomputersociety.org/10.1109/PRDC.2004.1276549},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Pacific Rim International Symposium on Dependable Computing, IEEE
TI - An Algorithmic Approach to Identifying Link Failures
SN - 0-7695-2076-6
SP25
EP34
A1 - Mohit Lad,
A1 - Akash Nanavati,
A1 - Dan Massey,
A1 - Lixia Zhang,
PY - 2004
KW - Fault Tolerant Algorithms
KW - Fault Diagnosis
KW - Routing and Graph Theory
VL - 0
JA - Pacific Rim International Symposium on Dependable Computing, IEEE
ER -
 
Mohit Lad, University of California at Los Angeles
Akash Nanavati, University of California at Los Angeles
Dan Massey, University of Southern California
Lixia Zhang, University of California at Los Angeles
Due to the Internet?s sheer size, complexity, and various routing policies, it is difficult if not impossible to locate the causes of large volumes of BGP update messages that occur from time to time. To provide dependable global data delivery we need diagnostic tools that can pinpoint the exact connectivity changes. In this paper we describe an algorithm, called MVSChange, that can pin down the origin of routing changes due to any single link failure or link restoration. Using a simplified model of BGP, called Simple Path Vector Protocol (SPVP), and a graph model of the Internet, MVSChange takes as input the SPVP update messages collected from multiple vantage points and accurately locates the link that initiated the routing changes. We provide theoretical proof for the the correctness of the design.
Index Terms:
Fault Tolerant Algorithms, Fault Diagnosis, Routing and Graph Theory
Citation:
Mohit Lad, Akash Nanavati, Dan Massey, Lixia Zhang, "An Algorithmic Approach to Identifying Link Failures," prdc, pp.25-34, 10th Pacific Rim International Symposium on Dependable Computing (PRDC'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.