In this section, we describe several algorithms for routing packets in
steps on an N-input multibutterfly. We start by
describing and analyzing Upfal's greedy algorithm for routing P
permutations in Sections 2.1 and 2.2.
This duplicates the result of Upfal, except that the proof is simpler
and the constants are better. In
Section 2.3 we describe variations of the
algorithm that allow pipelining and queueing for which the constant
factors in the 
running time bound are substantially
smaller. We conclude in Section 2.4 by
mentioning some improvements to the network itself.
Throughout this section, we will assume that, unless stated otherwise,
the multibutterflies we are working with have multiplicity d and
-expansion, where 
, 
is an integral
power of 
, and 
.