The level of a node is determined by the distance to the
representative node in its necklace. An alternate way to write a
node's label is to place a line under its least significant bit (which
we call the current bit), and then rotate the label until it
matches its representative's label. For example, 110001 can also be
written 
. The level of a node is the
position of the current bit, starting with zero and counting from the
left. For example, 
lies on level 2. (Note that
the representative node lies on level 
.)
The problem with this leveling scheme is that although it induces a leveling of the shift edges, it does not necessarily induce a leveling of the exchange edges. An exchange edge may create a new longest substring of 0's by appending two substrings separated by a single 1, and thus connect two levels that are very far apart.
To overcome this difficulty, we replace the exchange edges with
flip edges. A flip edge links nodes labeled a and b if both
are good, 
, 
, j > 0,
and 
is not in the longest block of 0's of a. Note that a flip
edge extends a group of 0's by at most one. Thus no flip edge can
create a new leading group of 0's, because if it grew a shorter group
to be as long as the leading group, then it would lead to a bad node of
type 2, a contradiction since flip edges occur only between good nodes
by definition. Thus flip edges are leveled. The operation of the
flip edges can be emulated by the shuffle-exchange graph with only a
constant factor of slowdown; each flip edge is composed of an exchange
edge, a shuffle edge, and possibly another exchange edge.
We denote by A the network composed of the good nodes, the shuffle
edges (excluding the shuffle edges from level 
to 0),
and the flip edges. Note that in network A, from the level 0 node
of any necklace it is possible to reach any other necklace whose
longest string of 0's has the same or greater length by correcting
bits starting from the end of the leading block of 0's.
In fact, we wish to be able to get from the level 0 node of a
necklace to any other necklace. Thus we append a mirror image
of A to itself so that from any level 0 node it is possible to
reach necklaces with fewer 0's in the longest string. The leveling is
extended in the natural manner. We call this network 
, and note
that network A can emulate it with constant slowdown.
We denote by L the network consisting of the shuffle edges on the good
nodes, again excluding shuffle edges from level 
to level
0. Our method of path selection consists of routing from a good
node to the level 0 node in its necklace, then routing to a random
intermediate necklace, then routing to the destination necklace, and
finally routing to the appropriate good node. Thus, we route in a
leveled network composed of network L, network 
, another network
, and another network L. We extend the leveling in the
natural manner and note that network A can emulate the whole
thing with constant slowdown.