In this section we describe a randomized algorithm for routing *kN*
packets on an *N*-node *k*-dimensional array in steps using
constant-size queues, where *M* is the maximum of the *k* side lengths
of the array. Special cases include the mesh (*k = 2*) and the
hypercube (*M = 2*). For arrays of dimension greater than two, no
asymptotically-optimal constant-queue-size routing algorithms were
previously known.

A *k*-*dimensional array* with side lengths , for , has nodes and *2kN* edges. Each node has a
distinct label , where ,
for . A node has two edges for each dimension; for
, has an edge to
and to . (If , as in the hypercube, then the node
has only one edge in dimension *i*. In this case, the total number of
edges is only *kN*.) We assume that at each step, a
node may simultaneously transmit and receive a packet on each of its
*2k* edges, even if *k* is not constant.

In order to apply the scheduling algorithm from
Section 2, routing is performed on a
bounded-degree leveled *logical network* that the array
emulates. (Note that the degree of the array itself is not
necessarily constant.) The logical network consists of *
plateaus* labeled *0* through *2k*, each consisting of *N* logical
nodes. Each node in the logical network has a label , where for , that is
distinct from the labels of the other nodes on the same plateau. Each
node in the logical network has at most two incoming edges and two
outgoing edges. We begin by describing the edges in plateaus *0*
through *k*. A node on plateau *i* has edges only in dimensions *i*
and *i+1*. If *i > 0* and , then the node labeled
has an edge to the node in the same plateau with
label . Also, if *i<k* and
, then the node has an edge to
on the same plateau. The only
connections to plateau *i+1* come from nodes with . For *i < k*,
is connected to
on plateau *i+1*. Plateau *k*
is connected to plateau *k+1* by dimension *1* edges. Plateaus *k+1*
through *2k* are essentially a copy of plateaus *1* through *k*. The
edges on plateau *i*, are given by the same rules
as the edges on on plateau *i-2k*. The level of node
, , is . For , the level is . The network is
leveled because each edge connects a pair of nodes on adjacent levels.

Each step of the logical network can be emulated by the array in a
constant number of steps. The array node labeled
emulates the *2k+1* logical nodes labeled , one on
each plateau. The array edge from to
emulates at most four
logical edges, one each on plateaus *i-1*, *i*, *k+i-1* and *k+i*.
Note that even though *k* may not be a constant, we are assuming that
each node can process *k* packets in a single step.

Paths for the packets are selected using Valiant's paradigm.
Initially each node on plateau *0* holds *k* packets in an initial
queue. A packet travels from its origin on plateau *0* to a random
destination on plateau *k*, then continues on to its true destination
on plateau *2k*. Suppose that a packet originating at
on plateau *0* is to pass through
on plateau *k* on its way to on
plateau *2k*. In the first half of the path plateau *i* is used to
make the *i*th component of the packet's location match the *i*th
component of its random destination, for . The
packet enters plateau at node
and traverses dimension
*i* edges to . The packet then
traverses dimension *i+1* edges to
and crosses over to
node on plateau *i+1*. In the
second half of the path, plateau *k+i* is used to make the *i*th
component of the packet's location match the *i*th component of the
true destination in a similar fashion. The following lemma shows that
with high probability, the congestion *c* of the paths is at most ,
where *M* is the maximum side length.

**Proof:**
We analyze congestion in the first half of the
network only. The calculation for the second half is identical.

We begin by bounding the probability that a particular edge is
congested. There are two parts to the calculation: counting the
number of packets that can possibly use the edge and bounding the
probability that an individual packet actually does so. First, we
count packets that can use the edge. Consider an edge on plateau
*i-1* or *i* from to . Since a packet does not use any dimension *i+1*
through *k* edges before it uses a dimension *i* edge, any packet that
uses the edge must come from an origin whose last *k-i* components
through match through . There are at
most such origins, each transmitting *k* packets.
Next we bound the probability that each of these packets actually uses
the edge. A packet uses the edge only if components through
of its random destination match through .
The probability that these components match is .

Since the random destinations are chosen independently, the number of
packets *S* that pass through the edge has a binomial distribution.
The probability that more than packets use an edge is at
most

Using the inequalities for , and , we have .

To bound the probability that any edge is congested, we simply sum the probabilities that each particular edge is congested, i.e.,

Since , for any , there is a such that this probability is at most .

to .667emto .667em

**Proof:**
With high probability, the scheduling algorithm from
Section 2 delivers all packets in
steps. The number of levels *L* is , and by
Lemma 6.1 with high probability the congestion
*c* is . Also, .

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996