Skip to main content

2004 | OriginalPaper | Buchkapitel

Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree

verfasst von : Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, Nicola Santoro

Erschienen in: Exploring New Frontiers of Theoretical Informatics

Verlag: Springer US

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

We consider the problem of computing the optimal swap edges of a shortest-path tree. This theoretical problem arises in practice in systems that offer point-of-failure shortest-path rerouting service in presence of a single link failure: if the shortest path is not affected by the failed link, then the message will be delivered through that path; otherwise, the system will guarantee that, when the message reaches the node where the failure has occurred, the message will then be rerouted through the shortest-path to its destination. There exist highly efficient serial solutions for the problem, but unfortunately because of the structures they use, there is no known (nor foreseeable) efficient distributed implementation for them. A distributed protocol exists only for finding swap edges, not necessarily optimal ones.We present two simple and efficient distributed algorithms for computing the optimal swap edges of a shortest-path tree. One algorithm uses messages containing a constant amount of information, while the other is tailored for systems that allow long messages. The amount of data transferred by the protocols is the same and depends on on the structure of the shortest-path spanning-tree; it is no more, and sometimes significantly less, than the cost of constructing the shortest-path tree.

Metadaten
Titel
Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree
verfasst von
Paola Flocchini
Antonio Mesa Enriques
Linda Pagli
Giuseppe Prencipe
Nicola Santoro
Copyright-Jahr
2004
Verlag
Springer US
DOI
https://doi.org/10.1007/1-4020-8141-3_14

Premium Partner