hide
Free keywords:
-
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.
