Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links

Simple item page
dc.creatorBhosle, Amit M.
dc.creatorGonzalez, Teofilo F.
dc.date2008-11-09
dc.date.accessioned2026-07-07T10:17:06Z
dc.date.available2026-07-07T10:17:06Z
dc.descriptionA recent study characterizing failures in computer networks shows that transient single element (node/link) failures are the dominant failures in large communication networks like the Internet. Thus, having the routing paths globally recomputed on a failure does not pay off since the failed element recovers fairly quickly, and the recomputed routing paths need to be discarded. In this paper, we present the first distributed algorithm that computes the alternate paths required by some "proactive recovery schemes" for handling transient failures. Our algorithm computes paths that avoid a failed node, and provides an alternate path to a particular destination from an upstream neighbor of the failed node. With minor modifications, we can have the algorithm compute alternate paths that avoid a failed link as well. To the best of our knowledge all previous algorithms proposed for computing alternate paths are centralized, and need complete information of the network graph as input to the algorithm.
dc.description8 pages, 2 columns, 1 figure
dc.identifierhttps://arxiv.org/abs/0811.1301
dc.identifierhttp://arxiv.org/abs/0811.1301
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/173738
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectData Structures and Algorithms
dc.subjectNetworking and Internet Architecture
dc.titleDistributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links
dc.typetext

Files

Collections

arXiv