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.

Mon Jul 22 21:19:59 EDT 1996