Nonblocking and rearrangeable networks have a rich and lengthy
history. See [30] for an excellent survey and
[9, 10] for more comprehensive descriptions of
previous results. In 1950, Shannon [35] 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 [5] and Benes
[6] independently discovered bounded-degree rearrangeable
connectors with depth 
and size 
, and Waksman
[38] gave an elegant algorithm for determining how the
nodes should be set in order to realize any particular permutation.
Ofman
[26] followed with a generalized rearrangeable connector of
size 
. Next, Cantor [7] 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
[3]. Although the Bassalygo and Pinsker proof is
not constructive, subsequent work on the explicit construction of
expanders [23] yielded a construction.
More recent work has focused on the construction of generalized
nonblocking connectors. In 1973, Pippenger [28]
constructed a wide-sense generalized nonblocking connector with 
edges. This result was later improved to 
edges by Feldman, Friedman, and Pippenger [10].
Recently, Turner suggested cascading two of the asymptotically
larger Clos or Cantor networks as a more practical way to construct a
generalized nonblocking connector [36]. 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 [10]. There are a few exceptions. On the
naive nonblocking networks of size 
(e.g. an 
mesh of trees [15]), 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 [22]. 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.