next up previous
Next: 5.4 Packets from bad Up: 5 Routing on shuffle-exchange Previous: 5.2 A leveled network

5.3 Path selection and congestion

For each packet we choose its path by uniformly choosing a random good necklace for it to route through before it goes to its final destination. So the path for a packet consists of a path through L to the node on level 0 of its necklace, a path through tex2html_wrap_inline3053 to its random intermediate necklace, a path through the second tex2html_wrap_inline3055 to its destination necklace, and a path through the second L to the proper node of its destination necklace.

The following lemma shows that if at most tex2html_wrap_inline3059 packets originate and terminate in each good necklace, then this method yields paths with congestion tex2html_wrap_inline3061 with high probability.


Proof: We observe that for the paths in the copies of L, we have congestion at most tex2html_wrap_inline3077 , since at most tex2html_wrap_inline3079 packets start or end in any good necklace. By symmetry we claim that the analysis of the path portions in both copies of tex2html_wrap_inline3081 is the same. Finally we recall that in tex2html_wrap_inline3083 , we route packets going to intermediate destination necklaces with fewer 0's straight across (i.e, without using any flip edges) in network A. Thus, the congestion of the straight across paths in A is at most tex2html_wrap_inline3089 . Also, we route packets going to intermediate necklaces with the same or more 0's straight across in network tex2html_wrap_inline3091 . We will show that any intermediate necklace gets tex2html_wrap_inline3093 packets with high probability, so the straight across portion of the paths in tex2html_wrap_inline3095 will have tex2html_wrap_inline3097 congestion. To finish, we analyze the congestion in network A due to packets routing to intermediate necklaces with the same or more 0's, and claim that the arguments will hold by symmetry for tex2html_wrap_inline3101 .

Consider a shuffle or flip edge e in the first copy of network A. Suppose that e traverses levels m and m+1. Let x be the length of the longest string of 0's in the necklace to which e goes. If m < x, then e must be a shuffle edge and no packet from any other necklace can use e, since we only map to a necklace via flip edges after its longest string of 0's. Otherwise ( tex2html_wrap_inline3123 ) we consider the number of packets from other necklaces that can use e. We know that only packets from at most tex2html_wrap_inline3127 other necklaces with tex2html_wrap_inline3129 can use e since at most l bits can change by level m+1 (there are no flip edges in the first tex2html_wrap_inline3137 levels of any necklace). Thus the number of packets that can use e is at most tex2html_wrap_inline3141 since each necklace starts with at most tex2html_wrap_inline3143 packets. The probability that a specific packet uses e is the number of necklaces that can be reached using e, at most tex2html_wrap_inline3149 (i.e., necklaces that match e's necklace in the first tex2html_wrap_inline3153 bits), divided by the total number of good necklaces, at least tex2html_wrap_inline3155 , which is just tex2html_wrap_inline3157 .

The probability that more than tex2html_wrap_inline3159 packets use e is at most


since there are tex2html_wrap_inline3165 Bernoulli trials, each succeeding with probability tex2html_wrap_inline3167 . The probability that any of the tex2html_wrap_inline3169 edges of this stage has congestion more than tex2html_wrap_inline3171 is tex2html_wrap_inline3173 times this probability. Using the inequality tex2html_wrap_inline3175 , for any tex2html_wrap_inline3177 we can bound the product by tex2html_wrap_inline3179 by choosing tex2html_wrap_inline3181 large enough.

to .667emto .667em

Because the congestion and number of levels are tex2html_wrap_inline3183 , with high probability, the time to route the packets between the good nodes is also tex2html_wrap_inline3185 , with high probability, and the queue size is constant.

next up previous
Next: 5.4 Packets from bad Up: 5 Routing on shuffle-exchange Previous: 5.2 A leveled network

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