Hilfe Wegweiser Impressum Kontakt Einloggen





Almost Optimal Permutation Routing on Hypercubes


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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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.

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.