next up previous
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 tex2html_wrap_inline2945 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 tex2html_wrap_inline2947 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 tex2html_wrap_inline2949 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 tex2html_wrap_inline2951 consecutive 0's (type 2), or

  3. its label is tex2html_wrap_inline2953 (type 3).

Thus, the label of every good node contains a unique longest substring of 0's with length at least tex2html_wrap_inline2955 . For simplicity, we assume that tex2html_wrap_inline2957 is integral, and that tex2html_wrap_inline2959 .

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 tex2html_wrap_inline2961 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 tex2html_wrap_inline2965 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 tex2html_wrap_inline2969 is associated with its neighbor tex2html_wrap_inline2971 .


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 tex2html_wrap_inline2975 bits are associated with it, so at most tex2html_wrap_inline2977 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 tex2html_wrap_inline2979 .

to .667emto .667em


Proof: By Lemma 5.1 at most tex2html_wrap_inline2983 bad nodes are associated with any good necklace. Since every good necklace contains exactly tex2html_wrap_inline2985 nodes, at least tex2html_wrap_inline2987 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 tex2html_wrap_inline2989 in this network, with high probability. Thus, by applying the analysis of Section 2, routing on the logical network takes tex2html_wrap_inline2991 steps with high probability, and uses constant-sized queues. We conclude by describing a deterministic algorithm for routing between good and bad nodes.

next up previous
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