de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Almost Optimal Permutation Routing on Hypercubes

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45673

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

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

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: http://hdl.handle.net/11858/00-001M-0000-000F-315E-B
##### Abstract
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.