next up previous
Next: 8.3 Bounding the load Up: 8 Sorting on butterflies Previous: 8.1 The algorithm

8.2 Analysis

The analysis of the algorithm is broken into three parts, each corresponding to a different use of randomization in the algorithm. We first examine the use of randomization in selecting the splitters. We show that, with high probability, the number of splitters chosen by each butterfly is within a constant factor of the expectation and the number of packets in each interval is smaller than the number of inputs of the subbutterfly to which it is assigned. Next, we bound the probability that the congestion is large at any particular switch in Steps 6 and 7. Finally, we show that if the packets are scheduled using the randomized algorithm for leveled networks, then it is unlikely that a delay of more than tex2html_wrap_inline3939 will accumulate over the course of the algorithm.

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