The networks that we use to obtain these results are constructed by combining expanders and Benes networks in much the same way that expanders and butterflies are combined to form the multibutterfly networks described by Upfal [37]. We refer to these networks as multi-Benes networks. The nonblocking networks of Bassalygo and Pinsker [3] are similar. The details of the construction are provided in Section 2 of the paper.
The techniques in this paper can also be applied to bandwidth-limited switching networks such as fat-trees [21]. These networks may be more useful in the context of real telephone systems, where there are limitations on the number of calls based on the proximity of the calls (e.g., it is unlikely that everyone on the East Coast will call everyone on the West Coast at the same time).
The description and analysis of the path selection algorithm is
divided into three sections. In Section 3, we prove that
the multi-Benes network is a strict-sense nonblocking connector. A
similar approach was used in [17] to show that the
multibutterfly is capable of routing in the presence of many faulty
nodes. Indeed, we can think of currently-used nodes as being
faulty since they cannot be used to form new connections. Similarly,
the algorithms we describe for routing in nonblocking networks can
easily be extended to be highly tolerant to faults in the network.
In Section 4, we describe an 
-bit-step
algorithm for bit-serial routing in a multibutterfly. This algorithm
relies on an unshared-neighbor property possessed by all highly-expanding
graphs. By implementing this algorithm on the multi-Benes network
and combining it with the methods of Section 3, we produce
an algorithm that can handle many calls at the same time, independent
of what calls have been made previously and what calls are currently
connected.
In Section 5, we describe algorithms for handling multiparty calls, and situations where many inputs try to reach the same output simultaneously. Some of these algorithms rely on sorting circuits and are not as practical as those described in Section 4. We also show how to remove the distinction between terminals and non-terminals.