Next: 4 Establishing many paths Up: On-line Algorithms for Path Previous: 2 The multi-Benes and

# 3 A proof that the multi-Benes network is nonblocking

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.

Next: 4 Establishing many paths Up: On-line Algorithms for Path Previous: 2 The multi-Benes and

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996