|Title||An Upper Bound on the State Requirements of Link-Fault Tolerant Multi-Topology Routing|
|Publication Type||Proceedings, refereed|
|Year of Publication||2006|
|Conference Name||International Conference on Communications (ICC)|
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.