Fast Algorithms for Bit-Serial Routing on a Hypercube

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

Abstract:

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
  • 2.1 Routing in the strong switch model
  • 2.2 Routing in the weak switch model
• 3 Emulating the routing algorithm on the hypercube
• 4 Lower bounds on oblivious routing
• 5 Acknowledgments
• References
• About this document ...