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.