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:
consecutive 0's (we consider the rightmost and leftmost bits in a
label to be consecutive) (type 1),
consecutive 0's (type 2), or
(type 3).
. For simplicity, we assume
that 
is integral, and that 
.
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 
.
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.
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.
