In this section we show how to deterministically route the packets from the bad nodes to their associated good necklaces.
Proof:
Recall that we associate a bad node of type 1 with the necklace
represented by a 1 in the least significant or current bit plus
0's in the most significant bits. We route these packets
in the shuffle exchange graph by changing the current bit to a 1 (if
it is 0) and changing 
bits to the right to 0's. Thus we
map a bad node to a good necklace at its level 
node.
For any necklace, the shuffle-exchange graph emulates binary
tree whose leaves are mapped to the necklace. Each edge of the tree
is emulated by either a shuffle edge or an exchange edge followed by
a shuffle edge. Each level of the tree corresponds to one of the
bits that were changed. Therefore, we can route
packets from the binary tree leaves to the necklace, and distribute
them along the necklace deterministically. This is easily done in
time with constant queues. The routing from the necklace
to the tree is equally trivial. But, we need to ensure that traffic
from the separate binary trees does not interfere too much. This is
easy since any bad node is in at most two binary trees; in at most one
as a leaf since any node is mapped to exactly one good node, and in at
most one as an internal node since the number of 0's between the
current bit and the closest 1 to the left determines a unique level
and the rest of the bits determine a unique tree.
To finish, we consider bad nodes of type 2. These are nodes without a
unique longest string of 0's. Here we extend one of the groups of 0's
by one 0, making sure not to join two groups of 0's by inserting a 1, thus
mimicking the flip operation. For any good necklace whose
representative is 
only the necklaces represented by
and 
can be mapped to it. Again, at most
two bad necklaces are associated with any good necklace.
For each packet in such a bad necklace we route it through the node
connecting it to the appropriate good necklace. We perform this
movement by pipelining the packets through the flip edge that connects
the two necklaces. We see that this mapping maps at most one packet
from the bad necklace to a node in the good necklace. Since we are
basically routing on linear arrays of length 
, 
steps are sufficient to route the packets from the two bad necklaces.
This finishes the description of the maps to and from all the bad
nodes except for node 
, which is adjacent to node 
.
