next up previous
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 tex2html_wrap_inline1639 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 tex2html_wrap_inline1649 inputs and outputs in rows that are multiples of L. Since the other inputs and outputs are not used, the first and last tex2html_wrap_inline1653 levels of the network can be removed, and the tex2html_wrap_inline1655 inputs and outputs can each be connected directly to their L descendants and ancestors on levels tex2html_wrap_inline1659 and tex2html_wrap_inline1661 , 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 tex2html_wrap_inline1663 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 tex2html_wrap_inline1673 , 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.

  lemma252

proof255

  lemma259

proof262

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 tex2html_wrap_inline1717 fraction of the nodes in each merger on level tex2html_wrap_inline1719 are blocked, and tex2html_wrap_inline1721 for tex2html_wrap_inline1723 and tex2html_wrap_inline1725 , each of the tex2html_wrap_inline1727 inputs has an edge to a working node on level tex2html_wrap_inline1729 . As a consequence, we can establish a path through working nodes from any unused input to any unused output in tex2html_wrap_inline1731 bit steps using a simple greedy algorithm. Since the declaration of blocked nodes takes just tex2html_wrap_inline1733 bit steps, and since the greedy routing algorithm is easily accomplished in tex2html_wrap_inline1735 bit steps, the entire process takes just tex2html_wrap_inline1737 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 tex2html_wrap_inline1739 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 tex2html_wrap_inline1745 , 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 up previous
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