next up previous
Next: 1 Introduction

Fast Algorithms for Bit-Serial Routing on a Hypercube

William A. Aiello tex2html_wrap_inline773
F. T. Leighton tex2html_wrap_inline775
Bruce M. Maggs tex2html_wrap_inline777
Mark Newman tex2html_wrap_inline779

tex2html_wrap_inline781 Bell Communications Research
Morristown, New Jersey 07960

tex2html_wrap_inline783 Mathematics Department and
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139

tex2html_wrap_inline785 NEC Research Institute
Princeton, NJ 08540

tex2html_wrap_inline787 Temple Barker and Sloane Inc.
Lexington, MA 02173


In this paper, we describe an tex2html_wrap_inline789 -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 tex2html_wrap_inline791 -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 tex2html_wrap_inline793 bit steps with high probability for almost all permutations.

Bruce Maggs
Mon Jul 22 17:37:10 EDT 1996
anonymous logging image