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 will use the recently introduced flow number F' of a graph. This parameter is known to satisfy F = O(Δα~(-1) log n), where Δ is the maximum degree and a is the edge expansion of 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 get this bound, we introduce a new method of converting a system of k disjoint paths into a system of k length-bounded disjoint paths. Also, an almost matching deterministic online lower bound Ω(k · F) is given. In addition, we study the k disjoint flows problem (k-DFP), which is a generalization of the well-known unsplit-table flow problem (UFP). The k-DFP is similar to the k-EDP with the difference that we now consider a graph with edge capacities and the requests can have arbitrary demands di. 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 di 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.