   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 steps using constant-size queues. The previous -time algorithms  required queues of size .

Figure 4 shows an 8-node shuffle-exchange graph. Each node is labeled with a unique -bit binary string. A node labeled is linked to a node labeled by a shuffle edge if rotating a one position to the left or right yields b, i.e., if either or . 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., . 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