next up previous
Next: 5.1 Good and bad Up: Randomized Routing and Sorting Previous: 4 Routing on butterflies

5 Routing on shuffle-exchange graphs


In this section, we present a randomized algorithm for routing any permutation of N packets on an N-node shuffle-exchange graph in tex2html_wrap_inline2893 steps using constant-size queues. The previous tex2html_wrap_inline2895 -time algorithms [2] required queues of size tex2html_wrap_inline2897 .

Figure 4 shows an 8-node shuffle-exchange graph. Each node is labeled with a unique tex2html_wrap_inline2901 -bit binary string. A node labeled tex2html_wrap_inline2903 is linked to a node labeled tex2html_wrap_inline2905 by a shuffle edge if rotating a one position to the left or right yields b, i.e., if either tex2html_wrap_inline2911 or tex2html_wrap_inline2913 . Two nodes labeled a and b are linked by an exchange edge if a and b differ in only the least significant (rightmost) bit, i.e., tex2html_wrap_inline2923 . In the figure, the shuffle edges are solid, and the exchange edges are dashed.

Figure 4: An 8-node shuffle-exchange graph. Shuffle edges are solid, exchange edges dashed.

The removal of the exchange edges partitions the graph into a set of connected components called necklaces. Each necklace is a ring of nodes connected by shuffle edges. If two nodes lie on the same necklace, then their labels are rotations of each other. Due to cyclic symmetry, the number of nodes in the necklaces differ. For example, in a 64-node shuffle-exchange graph, the nodes 010101 and 101010 form a 2-node necklace, while 011011, 110110, and 101101 form a 3-node necklace. For each necklace, the node with the lexicographically minimum label is chosen to be the necklace's representative.

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