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 ith component of the packet's location match the ith
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 ith
component of the packet's location match the ith 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
.
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, 
.
