next up previous
Next: 4.5 Processing incoming calls Up: 4.4 Routing many paths Previous: 4.4.1 The subnetwork of

4.4.2 Routing new paths

Once the working nodes have been identified, new paths from the inputs to the outputs of the multi-Benes network can be established using an algorithm that is essentially the same as the circuit-switching algorithm for multibutterflies described in Section 4.3. There are two main differences. First, in the multi-Benes network, only working nodes are used. However, by Lemmas 4.9 and 4.10 the working switches have an tex2html_wrap_inline2349 unshared neighbors property. Hence, we can run the algorithm of Section 4.3 with tex2html_wrap_inline2351 . Second, routing in the first half of the multi-Benes network is actually easier than in the second half, which is a multibutterfly, since there is no notion of up or down edges. The goal is simply to get each new path from an input on level tex2html_wrap_inline2353 to any working node on level 0. The algorithm uses placeholders and cancellation signals in the first half in the same way that they are used in the second half.

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