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.

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

Send mail to the author : (

Edit this abstract