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:
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.