Next: 4 Routing on butterflies Up: Randomized Routing and Sorting Previous: 2.3.2 Variable-length messages

# 3 Routing on meshes

In this section we apply the scheduling algorithm to route N packets on a mesh in steps using constant-size queues. Although -step routing algorithms for the mesh were known before [13, 14, 39], they all have more complicated path selection strategies.

In an mesh, each node has a distinct label , where x is its column and y is its row, and . Thus, an mesh has nodes. For x < n-1, node is connected to , and for y < n-1, node is connected to . A mesh is illustrated in Figure 2. Sometimes wraparound edges are included, so that a node labeled is connected to and a node labeled is connected to .

Figure 2: A mesh.

Proof:

The algorithm consists of four phases. In the first phase only those packets that need to route up and to the right are sent. The paths of the packets are selected greedily with each packet first traveling to the correct row, and then to the correct column. The level of a node is the sum of its row and column numbers. This simple strategy guarantees that both the congestion and the number of levels of the phase are . The packets are scheduled using the -step algorithm from Section 2. The up-right phase is followed by up-left, down-right, and down-left phases.

to .667emto .667em

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