ALCOMFT-TR-01-174 |
![]() |
Berthold Vöcking
Almost optimal permutation routing on hypercubes
MPI. Work packages 2 and 4. August 2001.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 presentPostscript file: ALCOMFT-TR-01-174.ps.gz (100 kb).Previous algorithms lose a factor 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.
- a randomized, oblivious, on-line algorithm with routing time d + O(d / log d),
- a matching lower bound of d + Omega(d / log d) for (randomized) oblivious, on-line routing, and
- a deterministic, off-line algorithm with routing time d+O(\sqrt{d log 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 Farthest-to-Go and 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.