next up previous
Next: 5.5 Summary Up: 5 Routing on shuffle-exchange Previous: 5.3 Path selection and

5.4 Packets from bad nodes

In this section we show how to deterministically route the packets from the bad nodes to their associated good necklaces.

  lemma635

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 tex2html_wrap_inline3189 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 tex2html_wrap_inline3191 bits to the right to 0's. Thus we map a bad node to a good necklace at its level tex2html_wrap_inline3193 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 tex2html_wrap_inline3195 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 tex2html_wrap_inline3197 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 tex2html_wrap_inline3199 only the necklaces represented by tex2html_wrap_inline3201 and tex2html_wrap_inline3203 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 tex2html_wrap_inline3205 , tex2html_wrap_inline3207 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 tex2html_wrap_inline3209 , which is adjacent to node tex2html_wrap_inline3211 .


to .667emto .667em



next up previous
Next: 5.5 Summary Up: 5 Routing on shuffle-exchange Previous: 5.3 Path selection and



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