Unlike the mesh and butterfly networks, the shuffle-exchange graph
cannot emulate a leveled network in a transparent fashion.
Nevertheless, it is still possible to apply the
scheduling algorithm for leveled networks to the problem of routing on
the shuffle-exchange graph. The key idea is that a large subset of
the shuffle-exchange graph (at least nodes) can emulate a
leveled network. We call these nodes *good* nodes. The rest of
the nodes are *bad*.

A node can be classified as bad for one of three reasons:

- its label does not contain a substring of
consecutive 0's (we consider the rightmost and leftmost bits in a
label to be consecutive) (
*type 1*), - its label contains at least two disjoint longest
substrings of at least consecutive 0's (
*type 2*), or - its label is (
*type 3*).

Since the length of a substring of consecutive 0's in a label is not changed by rotation, a necklace consists either entirely of good nodes or entirely of bad nodes. Furthermore, each good necklace consists of good nodes since a unique longest substring of consecutive 0's precludes cyclic symmetry.

In order to route packets among all *N* nodes of the shuffle-exchange
graph, we associate the bad nodes with good nodes. A type-1 bad node
is associated with a good node by changing the least significant bit
of its label to a 1 and the most significant bits to 0's.
Each bad necklace of type 2 is associated with a good necklace by
changing the two bits following the leftmost group of 0's in its
representative's label to *01*. Finally, the node is
associated with its neighbor .

**Proof:**
Each type-1 bad node is associated with the representative of a good
necklace since, after the transformation, the longest string of
consecutive 0's begins with the most significant bit. Only type-1 bad
nodes whose labels differ from the representative's label in at most
bits are associated with it, so at most type-1 bad nodes are associated with any good
necklace.

To assess the number of type-2 bad nodes associated with a good necklace, we consider the label of the representative of the good necklace and notice that only a bad necklace whose representative's label differs in the last bit of its leading block of 0's and possibly the bit after that can be mapped to the good necklace. Thus, at most two type-2 bad necklaces are associated with any good necklace.

Finally, no bad nodes of either type 1 or 2 are associated with the necklace of node .

to .667emto .667em

**Proof:**
By Lemma 5.1 at most bad nodes
are associated with any good necklace. Since
every good necklace contains exactly nodes, at least of
the nodes are good.

to .667emto .667em

The remainder of this section provides the details of the routing algorithm. We begin by describing a logical leveled network that the good nodes can easily emulate with constant overhead. Next, we show that for any routing problem, choosing random intermediate destinations yields paths with congestion and dilation in this network, with high probability. Thus, by applying the analysis of Section 2, routing on the logical network takes steps with high probability, and uses constant-sized queues. We conclude by describing a deterministic algorithm for routing between good and bad nodes.

Mon Jul 22 22:57:44 EDT 1996