next up previous
Next: 4.4.1 The subnetwork of Up: 4 Establishing many paths Previous: 4.3 A faster algorithm

4.4 Routing many paths in a nonblocking fashion on a multi-Benes network


It is not difficult to implement the circuit-switching algorithm just described on a multi-Benes network. The main difference between routing through a multi-Benes network and a multibutterfly network is that in the first half of the multi-Benes network, a path at a merger input is free to extend to any of the 2d neighboring outputs. As the following definition and lemma show, the mergers have an unshared-neighbor property analogous to that of the splitters.




In order to route around existing paths in a multi-Benes network, we combine the circuit-switching algorithm with the kind of analysis used in Section 3. To do so, we need to modify the definition of being blocked. A splitter input on level l, tex2html_wrap_inline2263 , is blocked if more than tex2html_wrap_inline2265 of its d up (or down) neighbors on level l+1 are busy or blocked. A merger input on level l, tex2html_wrap_inline2273 , is blocked if more than tex2html_wrap_inline2275 of its 2d neighbors on level l+1 are either busy of blocked. Any node that is not blocked is considered to be working.

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