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 [2] 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*.

- 5.1 Good and bad nodes
- 5.2 A leveled network
- 5.3 Path selection and congestion
- 5.4 Packets from bad nodes
- 5.5 Summary

Mon Jul 22 22:57:44 EDT 1996