Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs

Author

Medard, Muriel ; Finn, Steven G. ; Barry, Richard A. ; Gallager, Robert G.

Author_Institution

Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA

Volume

7

Issue

5

fYear

1999

fDate

10/1/1999 12:00:00 AM

Firstpage

641

Lastpage

652

Abstract

We present a new algorithm which creates redundant trees on arbitrary node-redundant or link-redundant networks. These trees are such that any node is connected to the common root of the trees by at least one of the trees in case of node or link failure. Our scheme provides rapid preplanned recovery of communications with great flexibility in the topology design. Unlike previous algorithms, our algorithm can establish two redundant trees in the case of a node failing in the network. In the case of failure of a communications link, our algorithm provides a superset of the previously known trees

Keywords

network topology; telecommunication links; telecommunication network reliability; telecommunication network routing; trees (mathematics); algorithm; arbitrary vertex-redundant graphs; communications link failure; edge-redundant graphs; link-redundant networks; network survivability; node failure; node-redundant networks; path rerouting; preplanned recovery; redundant trees; self-healing networks; topology design; Asynchronous transfer mode; Distributed computing; Laboratories; Multicast algorithms; Network topology; Quality of service; Robustness; SONET; Tree graphs; Wavelength division multiplexing;

fLanguage

English

Journal_Title

Networking, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1063-6692

Type

jour

DOI

10.1109/90.803380

Filename

803380