A simple calculation, performed below, reveals that, with high probability, at most packets pass through any bundle. If the butterfly is dilated by this factor, then there will be an unused outgoing edge for each packet that enters a switch. Thus, with high probability, no packet is ever delayed in the strong switch model. At each step, a switch simply examines all of its incoming edges, and shunts those with new packets to outgoing edges.

For simplicity, we will examine the first routing phase only. The
analysis of the second phase is similar. Consider a bundle connecting
a switch on level *l* to a switch on level *l+1*. This bundle can be
reached from inputs, and from this bundle outputs
can be reached. Since there is a unique path from any input to any
output, the probability that a packet originating at one of these
inputs passes through the switch is simply the probability that
it chooses one of these outputs as its random
intermediate destination, . Since *n*
packets originate at each input, and each of these packets chooses its
intermediate destination independently, the probability that more than
packets pass through the bundle is at most . Using the fact that for , we see that for any constant *k*,
there is a constant *c* such that this probability is at most .
Summing the probabilities for all *2N* bundles, we see that the
probability that more than packets pass through any switch
is at most .

Mon Jul 22 17:37:10 EDT 1996