In this section, we describe an on-line algorithm for routing an arbitrary number of additional calls in 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 in the multi-Benes network, where L is a power of 2 and . 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.