On basic properties of fault-tolerant multi-topology routing

Multi-topology routing has recently gained popularity as a simple yet efficient traffic engineering concept. Its basic purpose is to separate different classes of network traffic, which are then transported over disjoint logical topologies. Multi-topology routing is used as a basis for implementation of an IP fast reroute scheme called Multiple Routing Configurations (MRC).MRC has a range of attractive properties, but they do come at a cost. In order to guarantee recovery from any single link or node failure in the network, MRC has to maintain several logical topologies and thus an increased amount of routing information. The number of the logical topologies in MRC need not be large; even simple heuristic algorithms often yield good results in practice. However, why this is the case is not fully understood yet.In this paper, we introduce a theoretical framework for fault-tolerant multi-topology routing (FT-MTR). MRC is a practical implementation of FT-MTR in connectionless IP networks. We use FT-MTR to study how the internal topological structure of the communication network relates to two important problems. The first problem is minimizing the number of logical topologies and thus the routing state in FT-MTR. We show how to use the sets of nodes that separate the topology graph to devise an advanced heuristic for “intelligent” construction of the logical topologies. Finding the separating sets in a topology graph is computationally demanding; we present an algorithm that performs well in tested real network topologies. We evaluate the separation-set based heuristic for the logical topology construction and show that it outperforms the known MRC heuristics.The second problem is the FT-MTR load distribution after a failure. We use the separating sets to devise a novel algorithm for failure load distribution. This algorithm does not require knowledge of the traffic demand matrix, still, our tests indicate that it performs as good as, or better than, known MRC load-distribution algorithms that do require the demand matrix as input.