AuthorsT. Cicic
EditorsL. Yenel
TitleAn Upper Bound on the State Requirements of Link-Fault Tolerant Multi-Topology Routing
Publication TypeProceedings, refereed
Year of Publication2006
Conference NameInternational Conference on Communications (ICC)
Date PublishedJune
ISBN Number1-4244-0355-3

Multi-topology routing is an increasingly popular concept in computer communications, and can be successfully applied to network fault tolerance. Multi-topology routing implies an increase in routing state requirements proportional to the number of logical topologies used. The network routing state is often subject to stringent system limits and should therefore be deterministically controllable. In this paper we show that the number of logical topologies needed to guarantee link-fault tolerant multi-topology routing has an upper bound determined by the network's largest minimal cycle. We provide a formal proof of validity of this bound in arbitrary biconnected networks. We also evaluate the quality of this bound, showing that it is reasonably strict.

Citation KeyCicic.2006.1