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 
will accumulate over the
course of the algorithm.