next up previous
Next: 1 Introduction

Randomized Routing and Sorting on Fixed-Connection Networks

F. T. Leighton tex2html_wrap_inline1779
Bruce M. Maggs tex2html_wrap_inline1781
Abhiram G. Ranade tex2html_wrap_inline1783
Satish B. Rao tex2html_wrap_inline1785


This paper presents a general paradigm for the design of packet routing algorithms for fixed-connection networks. Its basis is a randomized on-line algorithm for scheduling any set of N packets whose paths have congestion c on any bounded-degree leveled network with depth L in tex2html_wrap_inline1793 steps, using constant-size queues. In this paradigm, the design of a routing algorithm is broken into three parts: (1) showing that the underlying network can emulate a leveled network, (2) designing a path selection strategy for the leveled network, and (3) applying the scheduling algorithm. This strategy yields randomized algorithms for routing and sorting in time proportional to the diameter for meshes, butterflies, shuffle-exchange graphs, multidimensional arrays, and hypercubes. It also leads to the construction of an area-universal network: an N-node network with area tex2html_wrap_inline1797 that can simulate any other network of area tex2html_wrap_inline1799 with slowdown tex2html_wrap_inline1801 .

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996
anonymous logging image