Minimum failure explanations for path vector routing changes

Mohit Lad (), Dan Massey (), Adam Meyerson (), Akash Nanavati () and Lixia Zhang ()
Additional contact information
Mohit Lad: University of California
Dan Massey: Colorado State University
Adam Meyerson: University of California
Akash Nanavati: Google Inc.
Lixia Zhang: University of California

Journal of Combinatorial Optimization, 2006, vol. 12, issue 1, No 1, 5-16

Abstract: Abstract Path vector protocols in routing networks convey entire path information to each destination. When links fail, affected paths are replaced by new paths, and by observing the entire path information, one might hope to infer the failed links that caused these changes. However, inferring the exact topological changes behind observed routing changes may not be possible due to limited information, and the same changes may be explained by more than one set of candidate failures. In this paper, using a simple path vector routing model, we present the problem of finding the candidate set with minimum number of failures to explain observed route changes. We call this problem the minimum e-set problem and present algorithms for solving it optimally for certain cases. We also show that the minimum e-set problem is NP-complete in the general case.

Keywords: Short Path; Greedy Algorithm; Multicast Tree; Link Failure; Tree Input (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-8901-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:12:y:2006:i:1:d:10.1007_s10878-006-8901-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-8901-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().