Algorithms for fault-tolerant routing in circuit-switched networks

In this paper we consider the k edge-disjoint paths problem (k-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph G = ( V, E) and a set of terminal pairs ( or requests) T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edge-disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for k > 1. To measure the performance of our algorithms we use the recently introduced flow number F of a graph. This parameter is known to fulfill F = O(Delta alpha(-1) log n), where Delta is the maximum degree, a is the edge expansion of G, and n is the number of vertices in G. We show that a simple greedy online algorithm achieves a competitive ratio of O(k(3)F) which naturally extends the best known bound of O( F) for k = 1 to higher k. To achieve this competitive ratio, we introduce a new method of converting a system of k disjoint paths into a system of k length-bounded disjoint paths. We also show that any deterministic online algorithm has a competitive ratio of Omega(kF). In addition, we study the k disjoint flows problem (k-DFP), which is a generalization of the previously studied unsplittable flow problem. The difference between the k-DFP and the k-EDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands d(i). The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand d(i) is connected by k disjoint paths, each of flow value d(i)/k. The k-EDP and k-DFP problems have important applications in fault-tolerant (virtual) circuit switching, which plays a key role in optical networks.