next up previous
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 tex2html_wrap_inline2697 scheduling algorithm to route N packets on a tex2html_wrap_inline2701 mesh in tex2html_wrap_inline2703 steps using constant-size queues. Although tex2html_wrap_inline2705 -step routing algorithms for the mesh were known before [13, 14, 39], they all have more complicated path selection strategies.

In an tex2html_wrap_inline2707 mesh, each node has a distinct label tex2html_wrap_inline2709 , where x is its column and y is its row, and tex2html_wrap_inline2715 . Thus, an tex2html_wrap_inline2717 mesh has tex2html_wrap_inline2719 nodes. For x < n-1, node tex2html_wrap_inline2723 is connected to tex2html_wrap_inline2725 , and for y < n-1, node tex2html_wrap_inline2729 is connected to tex2html_wrap_inline2731 . A tex2html_wrap_inline2733 mesh is illustrated in Figure 2. Sometimes wraparound edges are included, so that a node labeled tex2html_wrap_inline2735 is connected to tex2html_wrap_inline2737 and a node labeled tex2html_wrap_inline2739 is connected to tex2html_wrap_inline2741 .

Figure 2: A tex2html_wrap_inline2745 mesh.



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 tex2html_wrap_inline2753 . The packets are scheduled using the tex2html_wrap_inline2755 -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