Oblivious Routing in Directed Graphs with Random Demands
Harry Raecke, Post-Doctoral Fellow, Aladdin Center
Dec10, 2004

Abstract

A routing algorithm for large-scale, unstructured networks like the Internet has to meet many partly conflicting criteria as e.g. enabling quick routing decisions, perfomring well under a variewty of different traffic patterns, and working in a distributed fashion in order to keep control overhead low. In particular the latter issue creates serious difficulties, because a lack of coordination due to distributed routing decisions can easily create high-loaded "hot-spots" within the network that can result in very poor routing
performance.

This talk describes oblivious routing algorithms that aim to minimize the congestion in the network (i.e., the maximum load of a network link), and that, thereby, prevent the emergence of hot-spots and bottlenecks. Oblivious routing algorithms make their routing decisions independently from the traffic in the network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. Due to their simple structure oblivious algorithms allow for efficient implementations in a distributed environment with only very little control-overhead. Moreover, it has been shown that for undirected networks there are oblivious algorithms that always (i.e., for any traffic pattern) achieve close to optimum congestion. However, for directed networks such a strong worst-case result is not possible. Therefore, we analyze routing algorithms in a model where demands are chosen randomly from a known demand-distribution. We show that our algorithms obtain close-to-optimum congestion with high probability.

This is joint work with Mohammad Taghi Hajiaghayi, Jeong Han Kim, and Tom Leighton.