@misc{13006,
  author = {Tarik Cicic},
  title = {On Upper Bounds on the State Requirements of Fault-Tolerant Multi-Topology Routing},
  abstract = {Multi-topology routing is an increasingly popular concept in computer communications, and can be successfully applied to the 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 minimal number of logical topologies needed to guarantee fault-tolerant multi-topology routing is related to the size of the largest minimal cycle (LMC) in the network. Link-fault tolerance and node-fault tolerance are discussed separately. For link-fault tolerant routing, the LMC size is the upper bound. For node-fault tolerant routing, the upper bound is the greatest of 6 and the LMC size of an arbitrary planar sub-topology. We provide formal proofs of validity of these bounds in arbitrary biconnected networks. We also evaluate the quality of these bounds, showing that they are reasonably strict.},
  year = {2005},
  number = {2005-17},
  month = {12/2005},
  publisher = {Simula Research Laboratory},
  note = {Please note that after this report was published a counter-example has been found for a claim stated in Sec. 4.2. Please contact the author for details.},
}