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.