next up previous
Next: 7 Construction of area Up: Randomized Routing and Sorting Previous: 5.5 Summary

6 Routing on multidimensional arrays


In this section we describe a randomized algorithm for routing kN packets on an N-node k-dimensional array in tex2html_wrap_inline3237 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 tex2html_wrap_inline3249 , for tex2html_wrap_inline3251 , has tex2html_wrap_inline3253 nodes and 2kN edges. Each node has a distinct label tex2html_wrap_inline3257 , where tex2html_wrap_inline3259 , for tex2html_wrap_inline3261 . A node has two edges for each dimension; for tex2html_wrap_inline3263 , tex2html_wrap_inline3265 has an edge to tex2html_wrap_inline3267 and to tex2html_wrap_inline3269 . (If tex2html_wrap_inline3271 , 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 tex2html_wrap_inline3281 plateaus labeled 0 through 2k, each consisting of N logical nodes. Each node in the logical network has a label tex2html_wrap_inline3289 , where tex2html_wrap_inline3291 for tex2html_wrap_inline3293 , 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 tex2html_wrap_inline3307 , then the node labeled tex2html_wrap_inline3309 has an edge to the node in the same plateau with label tex2html_wrap_inline3311 . Also, if i<k and tex2html_wrap_inline3315 , then the node has an edge to tex2html_wrap_inline3317 on the same plateau. The only connections to plateau i+1 come from nodes with tex2html_wrap_inline3321 . For i < k, tex2html_wrap_inline3325 is connected to tex2html_wrap_inline3327 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, tex2html_wrap_inline3347 are given by the same rules as the edges on on plateau i-2k. The level of node tex2html_wrap_inline3351 , tex2html_wrap_inline3353 , is tex2html_wrap_inline3355 . For tex2html_wrap_inline3357 , the level is tex2html_wrap_inline3359 . 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 tex2html_wrap_inline3361 emulates the 2k+1 logical nodes labeled tex2html_wrap_inline3365 , one on each plateau. The array edge from tex2html_wrap_inline3367 to tex2html_wrap_inline3369 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 tex2html_wrap_inline3393 on plateau 0 is to pass through tex2html_wrap_inline3397 on plateau k on its way to tex2html_wrap_inline3401 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 tex2html_wrap_inline3411 . The packet enters plateau tex2html_wrap_inline3413 at node tex2html_wrap_inline3415 and traverses dimension i edges to tex2html_wrap_inline3419 . The packet then traverses dimension i+1 edges to tex2html_wrap_inline3423 and crosses over to node tex2html_wrap_inline3425 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 tex2html_wrap_inline3437 , 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 tex2html_wrap_inline3453 to tex2html_wrap_inline3455 . 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 tex2html_wrap_inline3465 through tex2html_wrap_inline3467 match tex2html_wrap_inline3469 through tex2html_wrap_inline3471 . There are at most tex2html_wrap_inline3473 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 tex2html_wrap_inline3477 through tex2html_wrap_inline3479 of its random destination match tex2html_wrap_inline3481 through tex2html_wrap_inline3483 . The probability that these components match is tex2html_wrap_inline3485 .

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 tex2html_wrap_inline3489 packets use an edge is at most


Using the inequalities tex2html_wrap_inline3493 for tex2html_wrap_inline3495 , and tex2html_wrap_inline3497 , we have tex2html_wrap_inline3499 .

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


Since tex2html_wrap_inline3503 , for any tex2html_wrap_inline3505 , there is a tex2html_wrap_inline3507 such that this probability is at most tex2html_wrap_inline3509 .

to .667emto .667em


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

to .667emto .667em

next up previous
Next: 7 Construction of area Up: Randomized Routing and Sorting Previous: 5.5 Summary

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996