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 .