The basis of most of the results in this paper is a proof that a
variant of Ranade's algorithm can be used to schedule any set
of N packets whose paths have congestion c on a bounded-degree
leveled network with depth L in 
steps using
constant-size queues. The algorithm is randomized, but requires only
bits of randomness to succeed with high
probability. The proof of this result is included in
Section 2. Curiously, the proof is simpler
than the previous proof of the same result applied specifically to
routing random paths in butterflies [29], and allows for
improved constant factors.
In Sections 3 through 10 we examine
the many applications of the 
-step scheduling algorithm
for leveled networks. These applications include routing algorithms
for meshes, butterflies, shuffle-exchange networks, multidimensional
arrays and hypercubes, and fat-trees. Section 3
presents the simplest application: routing N packets in
steps on a 
mesh. Another
simple application, described in Section 4, is
an algorithm for routing N packets in 
steps on an
N-node butterfly. It is not obvious that the scheduling algorithm
can be applied to the shuffle-exchange network because it is not
leveled. Nevertheless, in Section 5 we show how to
route N-packets in 
steps on an N-node shuffle-exchange
network by identifying a leveled structure in a large portion of the
network. In Section 6 we present an algorithm for
routing kN packets on an N-node k-dimensional array with maximum
side length M in 
steps. In Section 7, we
show how to adapt the scheduling algorithm to route a set of messages
with load factor 
in 
steps on a fat-tree
[21] with root capacity M.
The fat-tree routing algorithm 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
. An analogous result is shown for a class of
volume-universal networks.
Our sorting results are included in Sections 8
through 10. In particular, we describe an 
-step algorithm for sorting on an N-node butterfly or hypercube
in Section 8, an 
-step algorithm for
sorting on a shuffle-exchange network in Section 9, and
an 
-step algorithm for sorting 
items on a
k-dimensional array with side length M in
Section 10.