**William A. Aiello
F. T. Leighton
Bruce M. Maggs
Mark Newman
Bell Communications Research
Morristown, New Jersey 07960
Mathematics Department and
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139
NEC Research Institute
Princeton, NJ 08540
Temple Barker and Sloane Inc.
Lexington, MA 02173**

*In this paper, we describe an -bit-step randomized
algorithm for bit-serial message routing on a hypercube. The result
is asymptotically optimal, and improves upon the best previously known
algorithms by a logarithmic factor. The result also solves the
problem of on-line circuit switching in an -dilated hypercube
(i.e., the problem of establishing edge-disjoint paths between the
nodes of the dilated hypercube for any one-to-one mapping).
*

*
Our algorithm is adaptive and we show that this is necessary to
achieve the logarithmic speedup. We generalize the Borodin-Hopcroft
lower bound on oblivious routing by proving that any randomized
oblivious algorithm on a polylogarithmic degree network requires at
least bit steps with high probability
for almost all permutations.
*

*
*

- 1 Introduction
- 2 Routing on a dilated butterfly
- 3 Emulating the routing algorithm on the hypercube
- 4 Lower bounds on oblivious routing
- 5 Acknowledgments
- References
- About this document ...

Mon Jul 22 17:37:10 EDT 1996