One deficiency with the state-of-the-art in packet routing is that aside from Valiant's paradigm of first routing to random destinations, all of the algorithms and their analyses are very specifically tied to the network on which the routing is to take place. For example, the way that the queue size is kept constant in the butterfly routing algorithms is quite different from the way that it is kept constant in the mesh routing algorithms. Moreover, the butterfly and hypercube algorithms are so specific to those networks that no -step constant-queue-size algorithm was previously known for the closely related shuffle-exchange network. The lack of a good routing algorithm for the shuffle-exchange network is one of the reasons that the butterfly is preferred to the shuffle-exchange network in practice.

Our approach to the problem differs from previous approaches in that we separate the process of selecting paths for the packets from the process of timing the movements of the packets along their paths. More precisely, we break a routing problem into two stages. In Stage 1, we select a path for each packet from its origin to its destination. In Stage 2, we schedule the movements of the packets along their paths. The focus of this paper is on Stage 2. The goal of Stage 2 is to find a schedule that minimizes both the time for the packets to reach their destinations and the number of packets that are queued at any node. The schedule must satsify the constraint that at each time step each edge in the network can transmit at most one packet.

Of course, there must be some correlation between the performance of
the scheduling algorithm and the selection of the paths. In
particular, the maximum distance *d* traveled by any packet is always
a lower bound on the time required to route all packets. We call this
distance the *dilation* of the set of paths. Similarly, the largest
number of packets that must traverse a single edge during the entire
course of the routing is a lower bound. We call this number the *
congestion* *c* of the paths. In terms of these parameters, the
goal of Stage 1 is to select paths for the packets that minimize *c*
and *d*.

For many networks, Stage 1 is easy. We simply use Valiant's paradigm
of first routing each message to a random destination. It is easily
shown for meshes, butterflies, shuffle-exchange networks, etc., that
this approach yields values of *c* and *d* that are within a small
constant factor of the diameter of the network. Moreover, this
technique also usually works for many-one problems provided that the
address space is randomly hashed.

Stage 2 has traditionally been the hard part of routing. Curiously,
however, we have found that by ignoring the underlying network and the
method of path selection, Stage 2 actually becomes easier to solve!
In [20] for example, Leighton, Maggs, and Rao show that
for any set of packets whose paths have congestion *c* and dilation
*d*, in any network, there is a schedule of length in which
at most one packet traverses each edge at each time step, and in which
the maximum queue size required is . In this paper, we show that
there is an efficient randomized parallel scheduling algorithm for the
entire class of bounded-degree *leveled* networks. In a leveled
network, each edge is directed and connects a level *i* node to a
level *i+1* node, where the level numbers range from *0* to *L*. We
call *L* the *depth* of the network. The algorithm produces a
schedule of length with high probability, and uses
constant-size queues.

By applying the approach just described, we can design fast routing
algorithms for the most common fixed-connection networks. The
first step is to convert the network at hand into a leveled network.
In particular, we create a virtual leveled network that can be
efficiently simulated by the existing network, and we figure out how
to move packets between the two networks (i.e., we reduce the problem
of routing on the given network to the problem of routing on a very
similar leveled network). Next, we select paths for the packets so as
to minimize the congestion *c* in the leveled network. Because the
network is leveled, the dilation is automatically at most *L*, which
in all of our algorithms is at most a constant factor larger than the
diameter of the underlying network. The path selection strategy
typically uses some combination of greedy paths and random
intermediate destinations. We then conclude by applying the
-step scheduling algorithm.

Mon Jul 22 22:57:44 EDT 1996