Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Almost Optimal Permutation Routing on Hypercubes


Vöcking,  Berthold
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Vöcking, B. (2001). Almost Optimal Permutation Routing on Hypercubes. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-01) (pp. 530-539). New York, USA: ACM.

Cite as:
This paper deals with permutation routing on hypercube networks in the store-and-forward model. We introduce the first (on-line and off-line) algorithms routing any permutation on the $d$-dimensional hypercube in $d+o(d)$ steps. The best previously known results were $2d+o(d)$ (oblivious on-line) and $2d-3$ (off-line). In particular, we present \begin{itemize} \item a randomized, oblivious on-line algorithm with routing time $d + O(d / \log d)$, \item a matching lower bound of $d + \Omega(d / \log d)$ for (randomized) oblivious on-line routing, and \item a deterministic, off-line algorithm with routing time $d+O(\sqrt{d \log d})$. \end{itemize} Previous algorithms lose a factor of two mainly because packets are first sent to intermediate destinations in order to resolve congestion. As a consequence, the maximum path length becomes $2d - o(d)$. Our algorithms use intermediate destinations as well, but we introduce a simple, elegant trick ensuring that the routing paths are not stretched too much. In fact, we achieve small congestion using paths of length at most $d$. The main focus of our work, however, lies on the scheduling aspect. On one hand, we investigate well-known and practical scheduling policies for on-line routing, namely {\em Farthest-to-Go\/} and {\em Nearest-to-Origin}. On the other hand, we present a new off-line scheduling scheme that is based on frugal colorings of multigraphs. This scheme might be of interest for other sparse scheduling problems, too.