## Bounding Congestion in Networks

Chris Harrelson and Kirsten Hildrum

(Professor Satish Rao)

A recent result by Harald Räcke [1] gives an oblivious algorithm for
routing a flow in a general graph G=(V,E) with polylogarithmic (in V)
congestion over the optimal set of routes. He does this by showing
there exists an embedding of any graph into a tree, T(G), and that
routing any flow on T(G) is no worse than routing the same flow on G.
In addition, he also embeds T(G) on to G and shows that it is possible
to route on G with only polylogarithmically more congestion than on
T(G). Räcke, however, does not give a polynomial-time algorithm for
constructing the embedding.

We have several goals related to this. First, we seek to give a
polynomial-time construction of an embedding that can be used this
way, and hope that such a construction will give lead to a simpler
proof of his result.

Second, we wish to find, in general, the cost of an oblivious
algorithm. While Räcke's result shows that the gap between the best
oblivious algorithm and the best non-oblivious algorithm is polylog(n)
for the general case, this may not be tight, and the gap may even be
constant when all the messages have a single source or single
destination. The gap may be larger if the graph is allowed to have
*directed* edges.

- [1]
- H. Räcke, "Minimizing Congestion in General Networks,"
*Proc. Symp. Foundations of Computer Science,* Vancouver, Canada, November 2002.

Send mail to the author : (hildrum@eecs.berkeley.edu)

Edit this abstract