**F. T. Leighton
Bruce M. Maggs
Abhiram G. Ranade
Satish B. Rao **

*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 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 that can simulate any other network of area
with slowdown .
*

- 1 Introduction
- 2 An scheduling algorithm for leveled networks
- 3 Routing on meshes
- 4 Routing on butterflies
- 5 Routing on shuffle-exchange graphs
- 6 Routing on multidimensional arrays
- 7 Construction of area and volume-universal networks
- 8 Sorting on butterflies
- 9 Sorting on shuffle-exchange graphs
- 10 Sorting on multidimensional arrays
- 11 Remarks
- References
- About this document ...

Mon Jul 22 22:57:44 EDT 1996