MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Vöcking, Bertholddblp
Editor(s):
BibTeX cite key*:
Voecking2001b
Title, Booktitle
Title*:
Almost Optimal Permutation Routing on Hypercubes
Booktitle*:
Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-01)
Event, URLs
Conference URL::
Downloading URL:
http://portal.acm.org/citation.cfm?id=380752.380848&coll=portal&dl=ACM&type=series&idx=SERIES396&part=series&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=2148683&CFTOKEN=8528073#FullText
Event Address*:
Hersonissos, Crete, Greece
Language:
English
Event Date*
(no longer used):
July, 6-8, 2001
Organization:
ACM
Event Start Date:
6 July 2001
Event End Date:
8 July 2001
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
July
Pages:
530-539
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
1-58113-349-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Voecking2001b,
AUTHOR = {V{\"o}cking, Berthold},
TITLE = {Almost Optimal Permutation Routing on Hypercubes},
BOOKTITLE = {Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-01)},
PUBLISHER = {ACM},
YEAR = {2001},
ORGANIZATION = {ACM},
PAGES = {530--539},
ADDRESS = {Hersonissos, Crete, Greece},
MONTH = {July},
ISBN = {1-58113-349-9},
}


Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Berthold Voecking
Created
03/17/2002 05:16:11 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02/14/2005 09:44:07 PM
08.04.2002 13:43:10
08.04.2002 13:35:36
22.03.2002 13:26:14
17/03/2002 17:28:46