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(\Delta \alpha^-1 \log n), where \Delta is the maximum degree and \alpha is the edge expansion of G. We show that a simple, greedy online algorithm achieves a competitive ratio of O(k^3 \cdot 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 \Omega(k \cdot F) is given.In addition, we study the k disjoint flows problem (k-DFP), which is a generalization of the well-known unsplittable 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 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.
Introduction
This paper was motivated by a talk given by Rakesh Sinha from Ciena Inc. at
the DIMACS Workshop on Resource Management and Scheduling in Next Generation
Networks, March 26-27, 2001. The speaker pointed out in his talk that
standard problems such as the edge-disjoint paths problem and the unsplittable
ow problem are insu-cient for practical purposes: they do not allow a rapid
adaptation to edge faults or heavy load conditions. Instead of having just one
path for each request, it would be much more desirable to determine a collection
of alternative independent paths for each accepted request that can
exibly be
used to ensure rapid adaptability. The paths, however, should be chosen so
that not too much bandwidth is wasted under normal conditions. Keeping this
in mind, we introduce two new (to the best of our knowledge) optimization
problems: the k edge-disjoint paths problem (k-EDP) and the k disjoint
ows
problem (k-DFP).
In the k-EDP we are given an undirected graph E) and a set of
terminal pairs (or requests) T . The problem is to nd a maximum subset of the
pairs in T such that each chosen pair can be connected by k disjoint paths and,
moreover, the paths for dierent pairs are mutually disjoint.
Similarly, in the k-DFP we are given an undirected network E) with
edge capacities and a set of terminal pairs T with demands d i , 1  i  jT j. The
problem is to nd a subset of the pairs of maximum total demand such that
each chosen pair can be connected by k disjoint paths, each path is carrying
units of
ow and no capacity constraint is violated.
In order to demonstrate that the k-DFP can be used to achieve fault tolerance
together with a high utilization of the network resources and also a rapid
adaptability, consider a network G in which new edge faults may occur continuously
but the total number of faulty edges at the same time is at most f .
In this case, given a request with demand d, the strategy is to reserve k
disjoint
ow paths for it, for some k  1, with total demand (1 As
long as at most f edge faults appear at the same time, it will still be possible
to ship a demand of d along the remaining paths. Furthermore, under fault-free
conditions, only a fraction f=k of the reserved bandwidth is wasted, which can
be made su-ciently small by setting k su-ciently large (which will, of course,
be limited by the properties of the network).
1.1 Previous results
Since we are not aware of previous results for the k-EDP and the k-DFP for
k > 1, we will just survey results for the heavily studied case of
the edge-disjoint paths problem (EDP) and the more general unsplittable
ow
problem (UFP).
Several results are known about the approximation ratio and competitive
ratio achievable for the UFP under the assumption that the maximum demand
of a commodity, dmax , does not exceed the minimum edge capacity, c min , called
here the no-bottleneck assumption [1, 12, 4, 7, 10, 13, 14]. If only the number
of edges, m, is known, Baveja and Srinivasan [4] present a polynomial time
algorithm with approximation ratio O(
m). On the lower bound side, it was
shown by Guruswami et al. [10] that on directed networks the UFP is NP-hard
to approximate within a factor of m 1=2  for any  > 0. The best result
for the EDP and the UFP known so far was given by Kolman and Scheideler
[14]. Using a new parameter called the
ow number F of a network, they show
that a simple online algorithm has a competitive ratio of O(F ) and prove that
n), where for the EDP  is the maximal degree of the network,
is the edge expansion, and n is the number of nodes. For the UFP,  has to
be dened as the maximal node capacity of the network for the bound above to
hold, where the capacity of a node is dened as the sum of the capacities of its
edges. Combining the approach of Kolman and Scheideler [14] with the AAP
algorithm [1], Chakrabarti et al. [7] recently proved an approximation ratio of
O( 2  1 log 2 n) for the more general UFP with prots where  is just the
maximal degree of the network.
We also consider two related problems, the integral splittable
ow problem
(ISF) [10] and the k-splittable
ow problem (k-SFP). In both cases, the input
and the objective (i.e., to maximize the sum of accepted demands) are the
same as in the UFP. The dierence is that in the ISF all demands are integral
and a
ow satisfying a demand can be split into several paths, each carrying
an integral amount of
ow. In the k-SFP 1 a demand may be split into up
to k
ow paths (of not necessarily integral values). Under the no-bottleneck
assumption Guruswami et al. [10] give an O(
m) approximation for
the ISF. Recent results of Kolman and Scheideler [14] allow to achieve an O(F )
randomized competitive ratio and an O(F ) deterministic approximation ratio
for both of these problems on uniform capacity networks. Although the ISF and
the k-SFP on one side and the k-DFP on the other seem very similar at rst
glance, there is a serious dierence between the two. Whereas the ISF and the
k-SFP are relaxations of the UFP (they allow the use of more than one path
for a single request and the paths are not required to be disjoint), the k-DFP
is actually a more complex version of the UFP since it requires several disjoint
paths for a single request.
1.2 New results
The main results or this paper are
a deterministic online algorithm for the k-EDP with competitive ratio
a deterministic oine algorithm for the k-DFP on unit-capacity networks
with an approximation ratio of O(k 3 F log(kF )),
a lower
bound
for the competitive ratio of any deterministic online
algorithm for the k-EDP (and thus, obviously, for the k-DFP).
1 The k-splittable
ow problem was recently independently introduced by Baier et al. [3].
Thus, for constant k, we have matching upper and lower bounds for the k-EDP.
Furthermore, we demonstrate that the disjointness condition of the k paths
for every single request seems to be the crucial condition that makes the problems
above harder than other problems such as the integral splittable
ow problem
[10] or the k-splittable
ow problem.
Using known techniques, we also show how the online algorithm for the k-
EDP can be transformed into an oine algorithm with approximation ratio
O(k 3 F ) for the k-EDP with prots, and we describe how the oine algorithm
for the k-DFP can be converted into a randomized online algorithm for the
k-DFP with an expected competitive ratio of O(k 3 F log(kF )).
Our algorithms for the k-EDP and k-DFP are based on a simple concept,
which is a natural extension of the bounded greedy algorithm (BGA) that has
already been studied in several papers [12, 13, 14]: for every request for which
there are still k disjoint
ow paths of total length at most L available without
violating the capacity constraints, select any such system of k paths for it. The
core of the paper is in the analysis of this simple algorithm. The problem is
to show that this strategy works even if the optimal oine algorithm connects
many requests via k disjoint paths of total length more than L. In order to
solve this problem we use a new technique, based on Menger's theorem and the
Lovasz Local Lemma, that converts large systems of k disjoint paths into small
systems of k disjoint paths. Previously, shortening strategies were only known
1.3 Basic notation and techniques
Many of the previous techniques for the EDP and related problems do not allow
us to prove strong upper bounds on approximation or competitive ratios due
to the use of inappropriate parameters. If m is the only parameter used, an
upper bound of O(
m) is essentially the best possible for the case of directed
networks [10]. Much better ratios can be shown if the expansion or the routing
number [16] of a network are used. These measures give very good bounds for
low-degree networks with uniform edge capacities, but are usually very poor
when applied to networks of high degree or highly nonuniform degree or edge
capacities. To get more precise bounds for the approximation and competitive
ratios of algorithms, Kolman and Scheideler [14] introduced a new network
measure, the
ow number F . Not only does the
ow number lead to more precise
results, it also has the major advantage that, in contrast to the expansion or
the routing number, it can be computed exactly in polynomial time. Hence we
will use the
ow number in this paper as well.
Before we can introduce the
ow number, we need some notation. In a
concurrent multicommodity
ow problem there are k commodities, each with
two terminal nodes s i and t i and a demand d i . A feasible solution is a set
of
ow paths for the commodities that obey capacity constraints but need not
meet the specied demands. An important dierence between this problem and
the unsplittable
ow problem is that the commodity between s i and t i can be
routed along multiple paths. The (relative)
ow value of a feasible solution is
the maximum f such that at least f  d i units of commodity i are simultaneously
routed for each i. The max-
ow for a concurrent multicommodity
ow problem
is dened as the maximum
ow value over all feasible solutions. For a path p in a
solution, the
ow value of p is the amount of
ow routed along it. A special class
of concurrent multicommodity
ow problems is the product multicommodity
ow
problem (PMFP). In a PMFP, a nonnegative weight (u) is associated with each
node u 2 V . There is a commodity for every pair of nodes and the demand for
the pair (u; v) is equal to (u)  (v).
Suppose we have a network E) with arbitrary non-negative edge
capacities. For every node v, let the capacity of v be dened as
w:fv;wg2E c(v; w) and the capacity of G be dened as
c(v). Given
a concurrent multicommodity
ow problem with feasible solution S, let the dilation
D(S) of S be dened as the length of the longest
ow path in S and the
congestion C(S) of S be dened as the inverse of its
ow value (i.e., the congestion
tells us how many times the edge capacities would have to be increased in
order to fully satisfy all the original demands, along the paths of S). Let I 0 be
the PMFP in which
for every node v, that is, each pair of nodes
(v; w) has a commodity with demand c(v)  c(w)=. The
ow number F (G) of a
network G is the minimum of maxfC(S); D(S)g over all feasible solutions S of
I 0 . When there is no risk of confusion, we will simply write F instead of F (G).
Note that the
ow number of a network is invariant to scaling of capacities.
The smaller the
ow number, the better are the communication properties of
the network. For example, F
n), F
(log n), F (butter
n). In the analysis
of the presented algorithms, a useful tool will be the Shortening lemma [14].
Lemma 1.1 (Shortening Lemma) For any network with
ow number F it
holds: for any  2 (0; 1] and any feasible solution S to an instance of the concurrent
multicommodity
ow problem with a
ow value of f , there exists a feasible
solution with
ow value f=(1+) that uses paths of length at most 2  F (1+1=).
Moreover, the
ow through any edge e not used by S is at most   c(e)=(1
Another useful class of concurrent multicommodity
ow problems is the
balanced multicommodity
ow problem (or short BMFP). A BMFP is a multi-
commodity
ow problem in which the sum of the demands of the commodities
originating and the commodities terminating in a node v is at most c(v) for
every We will make use of the following property of the problem [14]:
Lemma 1.2 For any network G with
ow number F and any instance I of a
for G, there is a feasible solution for I with congestion and dilation at
most 2F .
Apart from the
ow number we will also need Cherno bounds [11], the
(symmetric form of the) Lovasz Local Lemma [9] and Menger's theorem [6,
p. 75].
Lemma 1.3 (Cherno Bound) Consider any set of n independent binary
random variables
and  be chosen so that
E[X ]. Then it holds for all -  0 that
Lemma 1.4 (Lovasz Local Lemma) Let A An be \bad" events in an
arbitrary probability space. Suppose that each event is mutually independent of
all other events but at most b, and that Pr[A i
with probability greater than 0, no bad event occurs.
Lemma 1.5 (Menger's theorem) Let s and t be distinct vertices of G. Then
the minimal number of edges separating s from t is equal to the maximal number
of edge-disjoint s-t paths.
1.4 Organization of the paper
In Section 2 we present our upper and lower bounds for the k-EDP and some
related problems, and in Section 3 we present our upper bounds for the k-DFP.
The paper ends with a conclusion and open problems.
Algorithms for the k-EDP
Consider the following extension of the bounded greedy algorithm: Let L be
a suitably chosen parameter. Given a request, if it is possible to nd k edge-disjoint
paths, between the terminal nodes of the request that are
mutually disjoint with the previously selected paths and that fulll
L, where jpj is the length (i.e., the number of edges) of a path p, then accept
the request and select any such collection of paths for it. Otherwise, reject the
request. Let us call this algorithm k-BGA.
Note that the problem of nding k edge-disjoint paths of total
length at most L can be reduced to the classical min-cost (integral)
ow problem,
which can be solved by standard methods in polynomial time [8, Chapter 4]. It
is worth mentioning that if there were a bound of L=k on the length of every
path, the problem would not be tractable any more (cf. [5]).
2.1 The upper bound
Theorem 2.1 Given a network G of
ow number F , the competitive ratio of
the k-BGA with parameter
Proof. In the following, we call the k edge-disjoint paths that were selected
for a request a k-system. A k-system is small if it has at most L edges.
Let B be the solution obtained by the k-BGA and O be the optimal solution.
For notational simplicity we allow a certain ambiguity. Sometimes B and O
refer to the subsets of T of the satised requests, and sometimes to the actual
k-systems that realize the satised requests. We say that a k-system q 2 B is
a witness for a k-system p if p and q share an edge. Obviously, a request with
a small k-system in the optimal solution that was rejected by the k-BGA must
have a witness in B.
Let O 0  O denote the set of all k-systems in O that are larger than L
and that correspond to requests not accepted by the k-BGA and that do not
have a witness in B. Then each k-system in O O 0 either has a witness or
was accepted by the k-BGA. Since the k-systems in O O 0 are edge-disjoint,
each request accepted by the k-BGA can be a witness to at most L requests in
O O 0 . Hence, jO O
It remains to prove an upper bound on jO 0 j. To achieve this, we transform
the k-systems in O 0 into a set P of possibly overlapping but small k-systems.
these small k-systems would have been candidates for the k-BGA but were
not picked, each of them has at least one witness in B. Then we show that the
small k-systems in P do not overlap much and thus many k-systems from B are
needed in order to provide a witness for every k-system in P .
Note that the set O 0 of k-systems can be viewed as a feasible solution of
relative
ow value 1 to the set of requests O 0 of the concurrent multicommodity
ow problem where each request has demand k. The Shortening lemma with
parameter immediately implies the following fact.
Fact 2.2 The k-systems in O 0 can be transformed into a set R of
ow systems
transporting the same amount of
ow such that every
ow path has a length of
at most 5k  F . Furthermore, the congestion at every edge used by a k-system
in O 0 is at most 1 1=(2k), and the congestion at every other edge is at most
1=(2k).
This does not immediately provide us with short k-systems for the requests
in O 0 . However, it is possible to extract short k-systems out of the
ow system
R.
Lemma 2.3 For every request in O 0 , a set of small k-systems can be extracted
out of its
ow system in R with a total
ow value of at least 1=4.
Proof. Let xed request from O 0 and let E i be the set of all edges
that are traversed by the
ow system for Consider any set of k 1
edges in E i . Since the edge congestion caused by R is at most 1 + 1=(2k), the
total amount of
ow in the
ow system for that traverses the k 1
edges is at most (k 1)(1 1=2. Thus, the minimal s
in the graph consists of at least k edges. Hence, Menger's theorem [6]
implies that there are k edge-disjoint paths between s i and t i in E i . We take
any such k paths and denote them as the k-system  1 . We associate a weight
(i.e., total
ow) of k   1 with  1 , where  1 is the minimum
ow from s i to t i
through an edge in E i belonging to the k-system  1 .
Assume now that we have already found ' k-systems
'  1. If
stop the process of dening  j . Otherwise, the
must still be at least k, because the total
ow
along any k 1 edges in E i is still less than the total remaining
ow from s i to
Thus, we can apply Menger's theorem again. This allows us to nd another
k-system  '+1 between s i and t i and in the same way as above we associate with
it a weight  '+1 . Let ^
' be the number of k-systems at the end of the process.
So far there is no guarantee that any of the k-systems dened above will be
small, neither that they will transport enough
ow between the terminal pair
s i and t i . However, after a simple procedure they will satisfy our needs.
According to Fact 2.2, all
ow paths in R have a length of at most 5kF .
Hence, the total amount of edge capacity consumed by a
ow system in R representing
a request in O 0 is at most 5k 2 F . If there were k-systems in
of total weight at least 1=4 that use more than 20k 3 F edges each, then they
would not t into the available edge capacity, because 20k 3 F
Thus, there exists a subset of the k-systems  total weight at least
1=4 such that each of them is small, that is, each of them uses at most 20k 3 F
edges. ut
denote the set of small k-systems for request (s
Lemma 2.3, and let S be the set of all S i . A random experiment will nally
help us to bound jO 0 j in terms of jBj. Independently for each (s
choose exactly one of its k-systems in S, where a k-system  j is picked with a
probability proportional to its
ow value. After the selection, each of the chosen
k-systems is used to carry k units of
ow, one unit along each of its paths. Let
P denote the chosen k-systems with the k units of
ow.
Since each k-system in P is small, it must have been a candidate for the
k-BGA. But it was rejected by the k-BGA and hence it must have a witness in
B. By the denition of O 0 this witnessing must be at an edge that is not used
by any k-system in O 0 . Hence, only edges outside of the edges used by O 0 can
be potential witness edges. From Fact 2.2 we know that each of these edges
can have a congestion of at most 1=(2k). Hence, after selecting a k-system for
each request at random and shipping a demand of 1 along each of its paths,
the expected congestion at every potential witness edge is at most 2. Thus,
in expectation, every k-system from B can serve as a witness to at most 2  L
k-systems from P . We conclude that there exists a random choice for which the
k-systems from B serve as witnesses to at most 2  L  jBj k-systems from P (cf.
[13]). Since jP the proof is completed. ut ut
The above upper bound on the competitive ratio for the k-BGA with parameter
is the best possible, since a k-system of size (k 3 F ) may prevent
other k-systems from being selected. An open question is whether it is
possible to achieve a better competitive ratio with a stronger restriction on the
size of the k-systems that are used by the k-BGA.
2.2 General online lower bound
Next we show there is a lower bound that holds for the competitive ratio of any
deterministic online algorithm for the k-EDP problem which is not far away
from the performance of the k-BGA.
Theorem 2.4 For any n, k, and F  log k n with n  k 2  F there is a graph
G of size (n) with maximum degree O(k) and
ow number such that the
competitive ratio of any deterministic online algorithm on G is
Proof. A basic building block of our construction is the following simple graph.
Let D k (diamond) denote the graph consisting of two bipartite graphs K 1;k and
K k;1 glued naturally together at the larger sides. The two k-degree nodes in D k
are its endpoints. Let C (chaplet) denote the graph consisting of F diamond
graphs attached one to the other at the endpoints, like in an open chaplet.
The core of the graph G consists of disjoint copies
of the chaplet graph C attached to the inputs of a k-ary multibutter
y
ure 1). In addition, a node s is connected to the rst k chaplet graphs and a
node t is connected to the rst k output nodes of the multibutter
y. Let s i;j
denote the rst endpoint of a diamond j in a chaplet i, and let t i;j (= s i;j+1 )
denote the other endpoint. We will use the fact that a k-ary multibutter
y
with inputs and outputs (which is a network of degree O(k)) can route any
r-relation from the inputs to the outputs with edge congestion and dilation at
most O(max[r=k; log k n 0 ]) [16].
multi-
butterfly
log k n
F
inputs outputs

Figure

1: The graph for the lower bound.
First, we show that our graph G has a
ow number of the
diameter of G is
F ) it is su-cient to prove that a PMFP with
for the given graph can be solved with congestion and dilation O(F ). Consider
each node v of degree - v to consist of - v copies of nodes and let V 0 be the set
of all of these copies. Then the PMFP reduces to the problem of sending a
packet of size 1=N for any pair of nodes in V 0 , where Such a routing
problem can be split into N permutations  i with  i
Each such permutation represents a routing
problem  in the original network where each node is the starting point and
endpoint of a number of packets that is equal to its degree. We want to bound
the congestion and dilation for routing such a problem.
In order to route , we rst move all packets to the inputs of the k-ary
multibutter
y in such a way that every input node of the multibutter
y will
have O(kF ) packets. This can clearly be done with edge congestion O(F ) and
dilation O(F ). Next, we use the multibutter
y to send the packets to the rows
of their destinations. Since every input has O(k  F ) packets, this can also be
done with congestion and dilation O(F ). Finally, all packets are sent to their
correct destinations. This also causes a congestion and dilation of at most O(F ).
Hence, routing  only requires a total congestion and dilation of O(F ).
Combining the fact that all packets are of size 1=N with the fact that we
have N permutations  i , it follows that the congestion and dilation of routing
the PMFP in the given graph is O(F ). Hence, its
ow number is
Now consider the following two sequences of requests:
(1) (s; t), and
Obviously, every deterministic online algorithm has to accept (s; t) to ensure
a nite competitive ratio for the sequence (1). However, in this case none of
the other requests in (2) can be satised. But the optimal solution for (2) is
to reject (s; t) and to accept all other requests. Hence, the competitive ratio is
2.3 Managing requests with prots
In the k edge-disjoint paths with prots problem (k-EDPP) we are given an
undirected graph E) and a set of requests T . Each request r
has a positive prot b(r i ). The problem is to nd a subset S of the pairs in T of
maximum prot for which it is possible to select disjoint paths such that each
pair is connected by k disjoint paths.
It turns out that a simple oine variant of the k-BGA gives the same approximation
ratio for the k-EDPP as we have for the k-EDP. The algorithm
involves sorting the requests in decreasing order of their prots and running the
k-BGA on this sorted sequence. We call this algorithm the sorted k-BGA.
Theorem 2.5 Given a network G of
ow number F , the approximation ratio
of the sorted k-BGA with parameter for the k-EDPP.
Proof. The proof is almost identical to the proof of Theorem 2.1. The only
additional observation is that, since the sorted k-BGA proceeds through the
requests from the most protable, every small k-system in O O 0 and in the
modied set P has a witness in B with larger or equal prot. ut
2.4 The multi-EDP
Another variant of the k-EDP our techniques can be applied to is the multiple
edge-disjoint paths problem (multi-EDP) which is dened as follows: given a
graph G and a set of terminal pairs with integral demands d i , 1  d i  , nd
a maximum subset of the pairs for which it is possible to select disjoint paths
so that every selected pair i has d i disjoint paths. Let dmax denote the maximal
demand over all requests.
A variant of the k-BGA, the multi-BGA, can be used here as well: Given
a request with demand d i , reject it if it is not possible to nd d i edge-disjoint
paths between the terminal pairs of total length at most 20d i d 2
select any such d i paths for it.
Theorem 2.6 Given a network G of
ow number F , the competitive ratio of
the multi-BGA is O(d 3
Proof. The proof goes along the same lines as the proof of Theorem 2.1: rst,
the Shortening lemma with parameter applied and, afterwards,
the extraction procedure is used. The dierence is that now we extract only
-systems for a request with demand d i , not dmax -systems. ut
3 Algorithms for the k-DFP
Throughout this section we will assume that the maximal demand is at most k
times larger than the minimal edge capacity, which is analogous to assumptions
made in almost all papers about the UFP. We call this the weak bottleneck
assumption. Moreover, we assume that all edge capacities are the same. Since
F is invariant to scaling, we simply set all edge capacities to one. The minimal
demand of a request will be denoted by d min . We rst show how to solve the
oine k-DFP, and then mention how to extend this solution to the online case.
To solve the oine k-DFP, we rst sort the requests in decreasing order of
their demands. On this sorted sequence of requests we use an algorithm that
is very similar to the k-BGA: Let L be a suitably chosen parameter. Given a
request with a demand of d, accept it if it is possible to nd k edge-disjoint
ow value d=k between the terminal nodes of the request
that t into the network without violating the capacity constraints and whose
total length
is at most L. Otherwise, reject it. This extension of the
k-BGA will be called k-
ow BGA.
The next theorem demonstrates that the performance of the k-
ow BGA for
the k-DFP is comparable to the performance of the k-BGA for the k-EDP. It is
slightly worse due to a technical reason: it is much harder to use our technique
for extracting short k-systems for the k-DFP than for the k-EDP.
Theorem 3.1 Given a unit-capacity network G with
ow number F , the approximation
ratio of the k-
ow BGA for the k-DFP with parameter
O(k 3 F log(kF )), when run on requests sorted in non-increasing order, is
O(k 3 F log(kF )).
Proof. As usual, let B denote the set of k-systems for the requests accepted by
the BGA and O be the set of k-systems in the optimal solution. Each k-system
consists of k disjoint
ow paths which we also call streams. For notational
simplicity we will sometimes think about B and O also as a set of streams
(instead of k-systems).
For each stream q 2 B or q 2 O, let f(q) denote the
ow along that stream.
If q belongs to the request (s =k. For a set
Q of streams let
f(q). Also, for an edge e 2 E and a stream q,
let F (e; q) denote the sum of
ow values of all streams in B passing through e
whose
ow is at least as large as the
ow of q, i.e., F (e;
a witness for a stream q if f(p)  f(q)
and p and q intersect in an edge e with F 1. For each edge e let
W(e; B) denote the set of streams in B that serve as witnesses on e. Similarly,
for each edge e let V(e; Q) denote the set of streams in Q that have witnesses
on e. We also say that a k-system has a witness on an edge e if any of its k
streams has a witness on e. We start with a simple observation.
3.2 For any stream q and edge e, if q has a witness on e then
Proof. Let p be a witness of q on e. Assume, by contradiction, that F (e; q) <
1=2. It easily follows that f(p) < 1=2. Since f(q)  f(p) and F
by the denition of a witness, we have a contradiction. ut
Let O 0  O be the set of k-systems that are larger than L and that correspond
to requests not accepted by the k-
ow BGA and that do not have a
witness in B. The next two bounds on jjO n O 0 jj and jjO 0 jj complete the proof.
Lemma 3.3 jjO n O 0 jj  (1
Proof. We partition O n O 0 into two sets. Let O 1  O n O 0 consist of all
the k-systems corresponding to requests accepted by the BGA and let O
Obviously, jjO 1 jj  jjBjj. Note that each k-system in O 2 must
have a witness in B. Let E 0  E denote the set of all edges on which some
k-system from O 2 has a witness. We then have
For the rst inequality note that a k-system of demand d i in O 2 may only have
a witness at a single edge, and this edge can only be traversed by a
ow of
belonging to that k-system. The second inequality holds due to the unit
capacities and the last one follows from Claim 3.2.
Since all k-systems in B are of length at most L, we have
streams p2B
systems s2B
This completes the proof of Lemma 3.3. ut
In the next lemma we bound kO 0 k by rst transforming the large k-systems
in O 0 into a set S of small k-systems and then bounding kSk in terms of kBk.
Lemma 3.4 kO
Proof. In order to prove the lemma, we will transform the k-systems in O 0
into a set of k-systems S in which each k-system has a length at most L and
therefore must have a witness in B. To achieve this, we perform a sequence of
transformations:
1. First, we scale the demands and edge capacities so that each edge in G
has a capacity of requests have demands that
are integral multiples of k. More precisely, the demand of each request
of original demand d is set to d
1=3)d], this slightly increases the demands and therefore also the
ows
along the streams so that the total
ow along an edge is now at most
(1+1=3)C. Note that slightly increasing the demands only increases kO 0 k
and therefore only makes the bound on the relationship between kO 0 k and
kBk more pessimistic.
2. Next, we replace each request (s
of demand k each, shipped along the same k-system as for (s
every k-system of such a request, we only keep the rst 8c  kF and the
last 8c  kF nodes along each of its k streams, for some
The resulting set of (possibly disconnected) streams of a k-system will be
called a k-core. As shown in Claim 3.5, we can distribute the elementary
requests into C=c sets S so that the congestion caused by the
k-cores within each set is at most 2c at each edge.
3. Afterwards, we consider each S i separately. We will reconnect disconnected
streams in each k-core in S i with
ow systems derived from the
ow number. The reconnected k-cores will not yet consists of k disjoint
streams. We will show in Claim 3.6 how to extract k-systems of length at
most L from each reconnected k-core.
4. Once we have found the short k-systems, we will be able to compare kO 0 k
with kBk with the help of witnesses.
Next we present two vital claims. The proof of the rst claim requires the use
of the Lovasz Local Lemma, and the proof of the second claim is similar to the
proof of Theorem 2.1.
3.5 The elementary requests can be distributed into C=c sets S
for some so that for each set S i the edge congestion caused by
its k-cores is at most 2c.
Proof. We rst prove the claim for afterwards demonstrate
how to get to
Consider the random experiment of assigning to each elementary request a
number uniformly and independently at random, and let S i be
the set of all requests that choose number i. For every edge e let the random
variable X e;i denote the number of streams assigned to S i that traverse e. Since
the maximal edge congestion is at most 4C=3, we have E[X e;i ]  4c=3 for every
edge e. Every edge e can be used by at most one stream of any k-core. Hence,
a k-core can contribute a value of at most 1 to X e;i and the contributions of
dierent k-cores are independent. We can use the Cherno bound to derive
For every edge e and every i e;i be the event that X e;i > 2c.
2, the above probability estimate bounds the probability that
the event A v;i appears. Our aim is to show, with the help of the LLL, that it
is possible in the random experiment to assign numbers to the requests so that
none of these events appears, which would yield our claim. To apply the LLL
we have to bound the dependencies among the events A e;i .
Each edge e can be used by at most 2C k-cores and these are the only k-cores
that aect the values X e;i , C=cg. Realizing that each of the k-cores
contains at most 2k(8c  kF ) edges and that the k-cores choose their sets S i
independently at random, we conclude that the event A e;i depends on at most
events A f;j .
To be able to use the LLL, we now olny have to choose the value c so that
e  e 4c=3 4
(32ck
This can certainly be achieved by setting
The above procedure is su-cient if
42 a more
involved technique will be used. The k-cores will be distributed into the sets S i
not in a single step but in a sequence of renements (a similar approach was
used, e.g., by Leighton et al. [15] and Scheideler [16]). In the rst renement,
our aim is to show that for c the k-cores can be distributed into
the sets S so that the edge congestion in each S i is at most (1
O(1= =3. For this we use the same random experiment as for c above.
It follows that E[X e;i and that
Hence, to be able to use the LLL, we have to choose the value c 1 so that
e  e 4 3
This can certainly be achieved by setting c large enough, which
completes the rst renement step.
In the second renement step, each S i is rened separately. Consider some
xed S i . Our aim is to show that for c the k-cores in S i can be
distributed into the sets S so that the edge congestion in each
S i;j is at most (1
=3. The proof for this follows exactly
the same lines as for c 1 . Thus, overall C=c 2 sets S i;j are produced in the second
step, with the corresponding congestion bound.
In general, in the (' 1)st renement step, each set S established in rene-
ment ' is rened separately, using c
the rst time. Note that in this case, c
this point we use the method presented at the beginning of the proof for the
parameter c to obtain C=c 0 sets
for some c
congestion of at most@ '
Y
where l is the total number of renement steps. Using the facts that 1 +x  e x
for all x  0 and that e x holds for the product
that
Y
1= 3
for a constant 0 <   1=2 that can be made arbitrarily small by making sure
that c ' is above a certain constant value depending on . Hence, it is possible
to select the values c so that the congestion in each S i at the end is
at most 2c 0 . ut
3.6 For every set S i , every elementary request in S i can be given k-
systems of total
ow value at least 1=4 such that each of them consists of at
most L edges. Furthermore, the congestion of every edge used by an original
k-system in S i is at most 2c + 1=(2k), and the congestion of every other edge is
at most 1=(2k).
Proof. For an elementary request r let p r
'r be all the disconnected
streams in its k-core, 1  ' r  k. Let the rst 8c  kF nodes in p r
i be denoted by
a r
i;8ckF and the last8c  kF nodes in p r
i be denoted by b r
.
Consider the set of pairs
'r
f(a r
Due to the congestion bound in Claim 3.5, a node v of degree - can be a starting
point or endpoint of at most 2c- pairs in L. From Lemma 1.2 we know that for
any network G with
ow number F and any instance I of the BMFP on G there
is a feasible solution for I with congestion and dilation at most 2F . Hence, it
is possible to connect all of the pairs in L by
ow systems of length at most
2F and
ow value f(p r
so that the edge congestion is at most 2c  2F . Let
the
ow system between a r
i;j and b r
i;j be denoted by f r
i;j . For each elementary
request and each 1  i  ' r and each 1  j  8c  kF , we dene a
ow system g r
it moves from s to a r
i;j along p r
, then from a r
i;j to b r
along f r
i;j , and nally from b r
i;j to t along p r
, and we assign to it a
ow value of
This ensures that a total
ow of f(p r
being shipped for
each p r
. Furthermore, this allows us to reduce the
ow along f r
i;j by a factor of
1=(8c  Hence, the edge congestion caused by the f r
i;j for all reduces
to at most 4c  F=(8c  Therefore, the additional congestion at
any edge is at most 1=(2k), which proves the congestion bounds in the claim.
Now consider any given elementary request t). For any set of k 1
edges, the congestion caused by the
ow systems for r is at most (k 1)(1
Hence, according to Menger's theorem there are k edge-
disjoint
ows in the system from s to t. Continuing with the same arguments
as in Theorem 2.1, we obtain a set of k-systems for r with as properties stated
in the claim. ut
Now that we have short k-systems for every elementary request, we combine
them back into the original requests. For a request with demand d this results
in a set of k-systems of size at most L each and total
ow value at least d=(4k).
Let the set of all these k-systems for all requests be denoted by S. Since every
k-system has a size at most L, it could have been a candidate for the BGA.
Thus, each of these k-systems must have a witness. Crucially, every edge that
has witnesses for these k-systems must be an edge that is not used by any of
the original k-systems in O 0 . (This follows directly from the denition of O 0 .)
According to the proof of Claim 3.6, the amount of
ow from S traversing any
of these edges is at most 1=(2k). Let E 0 be the set of all witness edges.
For each request we now choose independently at random one of its k-
systems, with probability proportional to the
ow values of the k-systems. This
will result in a set of k-systems P in which each request has exactly one k-system
and in which the expected amount of
ow traversing any edge in E 0 is at most
1=(2k). Next, we assign the original demand of the request to each of these
k-systems. This causes the expected amount of
ow that traverses any edge in
to increase from at most 1=(2k) to at most 4k  2.
We are now ready to bound kPk in terms of kBk. For every k-system h 2 S,
let the indicator variable X h take the value 1 if and only if h is chosen to be
in P . We shall look upon kPk as a random variable (though it always has the
same value) and bound its value by bounding its expected value E[kPk]. In the
following we assume that f(h) is the
ow along a stream of the k-system h and
d(h) is the demand of the request corresponding to h. Also, recall that the total
ow value of k-systems in S belonging to a request with demand d is at least
d=(4k).
4k
where the last calculations are done in the same way as in the proof of
Lemma 3.3. ut
Combining the two lemmas proves the theorem. ut
We note that if the minimum demand of a request, d min , fullls d min
k= log(kF ), then one would not need Claim 3.5. In particular, if d min were
known in advance, then the k-
ow BGA could choose to
achieve an approximation ratio of O(k 3 F=(d min =k)). This would allow a smooth
transition from the bounds for the k-EDP (where d to the k-DFP.
3.1 Online algorithms for the k-DFP
In this section we present a randomized online algorithm for the k-DFP. This
algorithm, which we shall call the randomized k-
ow BGA, is an extension of
the k-
ow BGA algorithm for the oine k-DFP. The technique we present for
making oine algorithms online has been used before [2, 14].
Consider, rst, the set O of k-systems for requests accepted by the optimal
algorithm. Let O 1  O consist of k-systems each with demand at least k=2, and
let O Exactly one of the following events is true: (1) jjO 1 jj  1=2jjOjj
or (2) jjO 2 jj > 1=2  jjOjj.
The randomized k-
ow BGA begins by guessing which of the two events
above will happen. If it guesses the former, it ignores all requests with demand
less than k=2 and runs the regular k-
ow BGA on the rest of the requests. If it
guesses the latter, it ignores all requests with demand at least k=2 and runs the
ow BGA on the rest.
Theorem 3.7 Given a unit-capacity network G with
ow number F , the expected
competitive ratio of the randomized k-
ow BGA for the online k-DFP is
Proof. The proof runs along exactly the same lines as the proof for Theorem
3.1, but we have to prove Lemma 3.2 for the changed situation. Note that
the original proof for Lemma 3.2 relies on the fact that requests are sorted in
a non-decreasing order before being considered. That need not be true here.
as usual, the k-systems for requests accepted by the randomized
ow BGA.
Consider the case when the algorithm guesses that jjO 1 jj  1=2  jjOjj. We
claim that for any stream q 2 O 1 and edge e, if q has a witness on e then
kW(e; B)k  1=2. Let q be witnessed by p, a stream in B. Now, since the algorithm
only considers requests with demand at least k=2, f(p)  1=2. The claim
follows since kW(e; B)k  f(p). Following the rest of the proof for Theorem 3.1,
substituting O 1 for O, shows that in this case the randomized k-
ow BGA will
have a competitive ratio of O(k 3 F log(kF )).
Now consider the case when the algorithm guesses jjO 2 jj  1=2  jjOjj. We
claim that even in this case for any stream q 2 O 2 and edge e, if q has a
witness on e then kW(e; B)k  1=2. From the denition of witnessing, we have
F 1. Next, from the denition of O 2 , f(q) < 1=2. The claim
follows as kW(e; B)k  F (e; q). As in the previous case, the rest of the proof
for Theorem 3.1 applies here too; substitute O 2 for O.
The competitive ratio in both cases is O(k 3 F log(kF )). Note that the algorithm
may guess incorrectly which event shall be true. But that just reduces
the expected competitive ratio by a factor of 2. ut
3.2 Comparison with other
ow problems
In this section we demonstrate that the k-DFP may be harder to approximate
than other related
ow problems because of the requirement that the k paths
for every request must be disjoint.
The k-splittable
ow problem and the integral splittable
ow problem have
been dened in the introduction. As already mentioned there, previous proof
techniques [14] imply the following result under the no-bottleneck assumption
(i.e., the maximal demand is at most equal to the minimal edge capacity).
Theorem 3.8 For a uniform-capacity network G with
ow number F , the approximation
ratio of the 1-BGA with parameter for the k-SFP and for
the ISF, when run on requests ordered according to their demands starting from
the largest, is O(F ).
Proof. The crucial point is that in the analysis of the BGA algorithm for the
UFP problem in the previous work [14] the solution of the BGA is compared
with an optimal solution of a relaxed problem, namely the fractional maximum
multicommodity
ow problem, and this problem is also a relaxation for both
the ISF and the k-SFP. It follows that the approximation guarantee O(F ) of the
BGA proved for the UFP problem holds for the k-SFP and the ISF problems
as well. ut
Using the standard techniques mentioned earlier, the algorithm can be converted
into a randomized online algorithm with the same expected competitive
ratio. If there is a guarantee that the ratio between the maximal and the minimal
demand is at most 2 (or some other constant) or that the maximal demand
is at most 1=2 (or some other constant smaller than 1, the edge capacity), the
online algorithm can be made even deterministic with the same competitive
ratio (cf. [13]). Taking into account the online lower bound of Theorem 2.4,
this indicates that the k-SFP and the ISF are indeed simpler problems than the
k-DFP.
The techniques of the current paper imply results for the ISF even when the
no-bottleneck assumption does not hold and only the weak bottleneck assumption
is guaranteed (i.e., the maximal demand is at most k times larger than
the minimal edge capacity). In this case we use a variant of the k-
ow BGA,
vary-BGA, that looks for d i disjoint paths of total length O(d i d 2
for a request with demand d i . A consequence of the Theorem 3.1 is the following
corollary:
Corollary 3.9 Given a uniform-capacity network G with
ow number F , the
approximation ratio of the vary-BGA for the ISF under the weak bottleneck
assumption, when run on requests ordered according to their demands starting
from the largest, is O(d 3
In this case the algorithm can also be converted into a randomized online
algorithm.
Conclusions
In this paper we presented upper and lower bounds for the k-EDP and the k-
DFP and related problems. Many problems remain open. For example, what is
the best competitive ratio a deterministic algorithm can achieve for the k-EDP?
We suspect that it is O(k  F ), but it seems very hard to prove. Concerning the
k-DFP, is it possible to simplify the proof and improve the upper bound? We
suspect that it should be possible to prove an O(k  F ) upper bound as well.
Even an improvement of the O(k 3 F log(kF )) bound k-DFP to O(k 3 F ) would
be interesting.
A bunch of other problems arises for networks with nonuniform edge capac-
ities: the k-
ow BGA algorithm can be used on them as well but is it possible
to prove the same performance bounds?

Acknowledgements

We would like to thank Rakesh Sinha for bringing these problems to our attention
and Alan Frieze for helpful insights.



--R


Strongly polynomial algorithms for the unsplittable ow problem.
On the k-splittable ow problem
Approximation algorithms for disjoint paths and related routing and packing problems.
On the complexity of vertex-disjoint length-restricted path prob- lems

Approximation algorithms for the unsplittable ow problem.
Combinatorial Optimization.



Approximation Algorithms for Disjoint Paths Problems.

Improved bounds for the unsplittable ow problem.
Packet routing and job-shop scheduling in O(congestion
Universal Routing Strategies for Interconnection Networks.
--TR
Combinatorial optimization
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
Simple on-line algorithms for the maximum disjoint paths problem
Improved bounds for the unsplittable flow problem
Universal Routing Strategies for Interconnection Networks
Strongly Polynomial Algorithms for the Unsplittable Flow Problem
On the k-Splittable Flow Problem
Approximation algorithms for disjoint paths problems

--CTR
Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length menger's theorem and reliable optical routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Ronald Koch , Ines Spenke, Complexity and approximability of k-splittable flows, Theoretical Computer Science, v.369 n.1, p.338-347, 15 December 2006
Ronald Koch , Ines Spenke, Complexity and approximability of k-splittable flows, Theoretical Computer Science, v.369 n.1-3, p.338-347, December, 2006
Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length Menger's theorem and reliable optical routing, Theoretical Computer Science, v.339 n.2, p.315-332, 12 June 2005
multicommodity flow;fault-tolerant routing;greedy algorithms;flow number;edge-disjoint paths