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 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 .

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