next up previous
Next: 2.2 Routing in the Up: 2 Routing on a Previous: 2 Routing on a

2.1 Routing in the strong switch model

A simple calculation, performed below, reveals that, with high probability, at most tex2html_wrap_inline983 packets pass through any bundle. If the butterfly is dilated by this tex2html_wrap_inline985 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 tex2html_wrap_inline991 inputs, and from this bundle tex2html_wrap_inline993 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 tex2html_wrap_inline995 inputs passes through the switch is simply the probability that it chooses one of these tex2html_wrap_inline997 outputs as its random intermediate destination, tex2html_wrap_inline999 . Since n packets originate at each input, and each of these packets chooses its intermediate destination independently, the probability that more than tex2html_wrap_inline1003 packets pass through the bundle is at most tex2html_wrap_inline1005 . Using the fact that tex2html_wrap_inline1007 for tex2html_wrap_inline1009 , we see that for any constant k, there is a constant c such that this probability is at most tex2html_wrap_inline1015 . Summing the probabilities for all 2N bundles, we see that the probability that more than tex2html_wrap_inline1019 packets pass through any switch is at most tex2html_wrap_inline1021 .

Bruce Maggs
Mon Jul 22 17:37:10 EDT 1996