Nonblocking and rearrangeable networks have a rich and lengthy history. See  for an excellent survey and [9, 10] for more comprehensive descriptions of previous results. In 1950, Shannon  proved that any rearrangeable or nonblocking connector with N-inputs and N-outputs must have edges. Further work on lower bounds can be found in [4, 11, 32, 33]. In 1953, Clos constructed a strict-sense nonblocking connector with edges and depth j, for fixed j. (The degree of the nodes is not bounded). Bounded-depth nonblocking networks have subsequently been studied extensively [8, 10, 24, 25, 29, 33]. In the early 1960's, Beizer  and Benes  independently discovered bounded-degree rearrangeable connectors with depth and size , and Waksman  gave an elegant algorithm for determining how the nodes should be set in order to realize any particular permutation. Ofman  followed with a generalized rearrangeable connector of size . Next, Cantor  discovered a bounded-degree -depth strict-sense nonblocking connector with edges. The existence of a bounded-degree strict-sense nonblocking connector with size and depth was first proved by Bassalygo and Pinsker . Although the Bassalygo and Pinsker proof is not constructive, subsequent work on the explicit construction of expanders  yielded a construction.
More recent work has focused on the construction of generalized nonblocking connectors. In 1973, Pippenger  constructed a wide-sense generalized nonblocking connector with edges. This result was later improved to edges by Feldman, Friedman, and Pippenger . Recently, Turner suggested cascading two of the asymptotically larger Clos or Cantor networks as a more practical way to construct a generalized nonblocking connector . This method requires that all the parties in a multiparty call are known at the time that the call is placed.
Unfortunately, there has not been as much progress on the problem of setting the nodes to realize the connection paths. Indeed, several of the references cited previously show that there exists a way of setting the nodes to realize the desired paths, but are unable to provide any reasonable algorithms for actually finding the right node settings. For example, no polynomial time algorithm is known for finding the paths in the wide-sense generalized nonblocking connector of . There are a few exceptions. On the naive nonblocking networks of size (e.g. an mesh of trees ), a simple greedy algorithm suffices to find the paths on-line in time. (An algorithm that finds the settings for the nodes is called a circuit switching algorithm. An algorithm that is performed by the nodes themselves using only local information is called an on-line algorithm; an off-line algorithm is one that uses more global information.) Also, Lin and Pippenger recently found polylogarithmic time off-line parallel algorithms for path selection in -size strict-sense nonblocking connectors using one processor per request . On any strict-sense nonblocking connector, an on-line version of breadth-first search can be used to find a path from an unused input to an unused output on-line. Unfortunately, this algorithm cannot efficiently cope with simultaneous requests for connections. Nevertheless, no better algorithm, either on-line or off-line, was previously known for any -size nonblocking network.