Title: Oblivious Routing via Random Walks,
Abstract: We present novel oblivious routing algorithms for both splittable and
unsplittable multicommodity flow. Our algorithm for minimizing congestion for
\emph{unsplittable} multicommodity flow is the first oblivious routing
algorithm for this setting. As an intermediate step towards this algorithm, we
present a novel generalization of Valiant's classical load balancing scheme for
packet-switched networks to arbitrary graphs, which is of independent interest.
Our algorithm for minimizing congestion for \emph{splittable} multicommodity
flow improves upon the state-of-the-art, in terms of both running time and
performance, for graphs that exhibit good expansion guarantees. Our algorithms
rely on diffusing traffic via iterative applications of the random walk
operator. Consequently, the performance guarantees of our algorithms are
derived from the convergence of the random walk operator to the stationary
distribution and are expressed in terms of the spectral gap of the graph (which
dominates the mixing time).