next up previous
Next: 2.1 The algorithm Up: Fast Algorithms for Routing Previous: 1.6 Outline

2 Routing without faults


In this section, we describe several algorithms for routing packets in tex2html_wrap_inline1433 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 tex2html_wrap_inline1439 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 tex2html_wrap_inline1443 -expansion, where tex2html_wrap_inline1445 , tex2html_wrap_inline1447 is an integral power of tex2html_wrap_inline1449 , and tex2html_wrap_inline1451 .

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