next up previous
Next: 4.1 Unshared neighbors Up: On-line Algorithms for Path Previous: 3 A proof that

4 Establishing many paths at once


In this section, we describe an on-line algorithm for routing an arbitrary number of additional calls in tex2html_wrap_inline1747 bit steps. As before, we assume for the time being that each input and each output is involved in at most one two-party call. Extensions to the algorithm for handling multiparty calls are described in Section 5. We also assume that paths are established between inputs and outputs on rows congruent to tex2html_wrap_inline1749 in the multi-Benes network, where L is a power of 2 and tex2html_wrap_inline1753 . This will insure that no splitter or merger is ever overloaded.

To simplify the exposition of the algorithm, we start by describing an on-line algorithm for routing any initial set of paths in a multibutterfly (i.e., we don't worry about the nonblocking aspect of the problem for the time being). This comprises the first known circuit-switching algorithm for the multibutterfly. (Previous routing algorithms for the multibutterfly [17, 37] only worked for the store-and-forward model of routing.) The existence of the circuit-switching algorithm provides another proof that the multibutterfly is a rearrangeable connector. We conclude by modifying the definitions of busy and blocked nodes from Section 3 and showing how to implement the circuit-switching algorithm on a multi-Benes network so that it works even in the presence of previously established calls.

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996