   Next: 2.4 Other improvements Up: 2 Routing without faults Previous: 2.2 The analysis

## 2.3 Improving the constant factors

Although the constant factors derived for the running time bound in Theorem 2.1 are superior to those proved by Upfal  (who achieved a bound of steps for d = 21), they are very far from what can be considered practical. Fortunately, the constant factors can be substantially improved if we allow each switch to process communications along each incident edge at the same time. In particular, we can handle 4d routing problems for the price of one by interleaving and pipelining the 4d problems in the standard way. (I.e., every edge will now be active at every step - edges with the jth color will be working on the ith problem during steps congruent to .) Similarly, we can partition a single problem into 4d batches, each of which can be handled simultaneously but independently. The number of waves in each batch is which means that we can simply reduce PL by a factor of 4d in the overall time bound. As long as PL > 4d, this means that we can route P permutations in steps.

The most interesting application of this procedure is to routing permutations, for which the time bound is steps. For L=16, , , d = 11, , , , and , this gives an absolute bound of steps which is substantially better than the previous bound.

Recently, Leighton and Maggs  developed an alternative method for analyzing greedy routing algorithms on multibutterflies which allows for another order-of-magnitude improvement in the constant factors. In particular, they have shown that a simple greedy algorithm can routing a single permutation in at most steps using d = 10 and queues of size 2 at each edge. By increasing d further, the time bound can be decreased to about . Using a more complicated algorithm, and large d, the time bound can be decreased to nearly .

Even the best bounds for the constant factors are not very good, however. Fortunately, as we will see in Section 4, randomly-wired splitter networks (even those with d = 2) appear to perform much better in practice than would be indicated by the known theoretical upper bounds.   Next: 2.4 Other improvements Up: 2 Routing without faults Previous: 2.2 The analysis

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996