Next: 5.2 A leveled network Up: 5 Routing on shuffle-exchange Previous: 5 Routing on shuffle-exchange

## 5.1 Good and bad nodes

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:

1. its label does not contain a substring of consecutive 0's (we consider the rightmost and leftmost bits in a label to be consecutive) (type 1),

2. its label contains at least two disjoint longest substrings of at least consecutive 0's (type 2), or

3. its label is (type 3).

Thus, the label of every good node contains a unique longest substring of 0's with length at least . 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 .

to .667emto .667em

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.

to .667emto .667em

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.

Next: 5.2 A leveled network Up: 5 Routing on shuffle-exchange Previous: 5 Routing on shuffle-exchange

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