next up previous
Next: 6 Routing on multidimensional Up: 5 Routing on shuffle-exchange Previous: 5.4 Packets from bad

5.5 Summary

The main result of this section is summarized in the following theorem.

theorem641

Proof: There are three phases to the algorithm. First, packets originating at bad nodes are deterministically routed to the good nodes with which they are associated. By Lemma 5.4 this phase requires tex2html_wrap_inline3219 steps. Next, packets are routed between the good nodes on the logical network. Since at most tex2html_wrap_inline3221 bad nodes are associated with each good necklace, with high probability the congestion of the paths on the logical network is tex2html_wrap_inline3223 , by Lemma 5.3. Thus, this phase requires tex2html_wrap_inline3225 steps, with high probability. The packets are routed in tex2html_wrap_inline3227 steps using the scheduling algorithm from Section 2. Finally, packets destined for bad nodes are deterministically routed from the good nodes to bad. By an analysis similar to that of Lemma 5.4, this phase also requires tex2html_wrap_inline3229 steps.


to .667emto .667em



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