Although the constant factors derived for the running time bound in Theorem 2.1 are superior to those proved by Upfal [29]
(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 *j*th color will be working on the *i*th 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 [19] 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 [2].

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.

Mon Jul 22 18:45:42 EDT 1996