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 
.