next up previous
Next: 8.5 Bounding the cumulative Up: 8 Sorting on butterflies Previous: 8.3 Bounding the load

8.4 Bounding the congestion at each switch

The second step in the analysis is to bound the probability that too many packets pass through any switch in Steps 6 and 7. The following lemma provides a bound on the probability that the congestion, c, in an M-input butterfly exceeds tex2html_wrap_inline4133 in either of of these steps.


Proof: For the sake of brevity, we examine Step 7 only. A similar (and simpler) analysis holds for Step 6.

We begin by counting the number of packets that can possibly use a switch. Let L denote the depth of an M-input butterfly, i.e., tex2html_wrap_inline4145 . From a switch at level l, tex2html_wrap_inline4149 , tex2html_wrap_inline4151 rows can be reached. The splitters partition these rows into subbutterflies. By Lemma 8.4, the number of packets that enter each of these subbutterflies is at most the number of inputs, with high probability. Thus, at most tex2html_wrap_inline4153 packets can pass through the switch.

Next we determine the probability that a packet that can pass through the switch actually does so. A switch at level l can be reached from tex2html_wrap_inline4157 different inputs. Since each packet begins in a random input, the probability that it can reach the switch is tex2html_wrap_inline4159 .

The number of packets, S, that pass through a particular switch at level l has a binomial distribution. The number of trials is tex2html_wrap_inline4165 and the probability of success is tex2html_wrap_inline4167 . Thus, tex2html_wrap_inline4169 and tex2html_wrap_inline4171 . Using the inequality tex2html_wrap_inline4173 , we have tex2html_wrap_inline4175 .

We bound the congestion in the entire butterfly by summing the individual probabilities over all tex2html_wrap_inline4177 switches in the butterfly. We have


For tex2html_wrap_inline4181 , we have tex2html_wrap_inline4183 for some constant tex2html_wrap_inline4185 .

to .667emto .667em

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