In this section we prove that the multi-Benes network is a
strict-sense nonblocking connector. As a consequence, a simple
algorithm like breadth-first search can be used to establish a single
path from any unused input to any unused output in 
bit
steps, where N is the number of rows. Algorithms that handle
simultaneous requests for connections and multiparty calls are
deferred to Sections 4 and 5.
In order for the algorithm to succeed, the multi-Benes network
must be ``lightly loaded'' by some fixed constant factor L, where we
will choose L to be a power of 2. Thus, in an N-row
multi-Benes network, we only make connections between the 
inputs and outputs in rows that are multiples of L. Since the other
inputs and outputs are not used, the first and last 
levels of
the network can be removed, and the 
inputs and outputs can each
be connected directly to their L descendants and ancestors on levels
and 
, respectively.
The basic idea is to treat the nodes through which paths have already
been established as if they were faulty and to apply the fault
propagation techniques from [17] to the network. In
particular, we define a node to be busy if there is a path
currently routing through it. We recursively define a node in the
second half of the network to be blocked if all of its up
outputs or all of its down outputs are busy or blocked. More
precisely, nodes are declared to be blocked according to the following
rule. Working backwards from level 
to level 0, a
node is declared blocked if either all d of its up edges or all d
of its down edges lead to busy or blocked nodes. From level -1 to
level 
, a node is declared blocked if all 2d of
its outgoing edges lead to busy or blocked nodes. A node that is
neither busy nor blocked is said to be working.
The following pair of lemmas bound the fraction of input nodes that are blocked in every splitter and merger.
After the fault propagation process, every working node in the first
half of the network has an output that leads to a working node, and
every working node in the second half has both an up output and a
down output that lead to working nodes. Furthermore, since at most
a 
fraction of the nodes in each merger on level 
are blocked, and 
for 
and 
, each of the 
inputs
has an edge to a working node on level 
. As a
consequence, we can establish a path through working nodes from any
unused input to any unused output in 
bit steps using a
simple greedy algorithm. Since the declaration of blocked nodes
takes just 
bit steps, and since the greedy routing
algorithm is easily accomplished in 
bit steps, the entire
process takes just 
bit steps.
The preceding algorithm for establishing paths one after another in
the multi-Benes network implies that it is a wide-sense
nonblocking connector. The proofs of Lemmas 3.1
and Lemmas 3.2, however, do not make any assumptions
about the strategy used to make previous connections between inputs
and outputs. Indeed, the only requirement is that there are at most
paths through each M-input splitter or M-output merger,
which holds for any path selection strategy. Therefore, no matter how
the paths for the previous connections were found, there is still at
least one working node in each block at level 
, and as
a consequence, at least one path between any unused input and unused
output. Thus the multi-Benes network is also a strict-sense
nonblocking connector. As such, it is not really necessary to label
the nodes as blocked or working; a simple on-line algorithm like
breadth-first search is guaranteed to find a path. When simultaneous
requests are dealt with in Section 4.4, however,
a proper labeling will be important.
