An Upper Bound on the State Requirements of Link-Fault Tolerant Multi-Topology Routing

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 deterministic and controllable. In this paper we show that the number of logical topologies needed to guarantee link-fault tolerant multi-topology routing in a network has an upper bound determined by a topological property we call largest minimal cycle. We provide a formal proof of the validity of this bound in arbitrary biconnected networks. We also evaluate the quality of this bound, showing that it is reasonably strict.