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, .