Next: 5.3 Path selection and Up: 5 Routing on shuffle-exchange Previous: 5.1 Good and bad

## 5.2 A leveled network

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.

Next: 5.3 Path selection and Up: 5 Routing on shuffle-exchange Previous: 5.1 Good and bad

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996