   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 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., . From a switch at level l, , 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 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 different inputs. Since each packet begins in a random input, the probability that it can reach the switch is .

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

We bound the congestion in the entire butterfly by summing the individual probabilities over all switches in the butterfly. We have For , we have for some constant .

to .667emto .667em

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