Next: 6 Acknowledgments Up: 5.3 Removing the distinction Previous: 5.3.2 Constructing node-disjoint paths

### 5.3.3 Establishing edge-disjoint paths

It is easier to establish edge-disjoint paths in R than node-disjoint paths. In particular, it is not necessary to apply the technique of [17] for tolerating faults in multibutterflies to the second and third parts of the network as we did in order to establish the node-disjoint paths. The main thing that must be done is to modify the algorithm from Section 4 for locking down node-disjoint paths in a multibutterfly so that it allows a constant number of edge-disjoint paths to pass through each node. Let r be the maximum number of paths that may pass through a node. In order to replace the unshared neighbors protocol with one that allows r paths to pass through a node, we define the following r-neighbors property for splitters. Similar definitions hold for mergers, or for pairs of consecutive levels like those in the first and fourth parts of R.

The following lemma shows that a splitter with a sufficient expansion property also has an r-neighbors property.

The algorithm for routing edge-disjoint paths in a multibutterfly is nearly identical to the algorithm described in Section 4 for routing node-disjoint paths. First, each node that has at least one path to extend in either the up (or down) direction sends a proposal to each of his output neighbors in the up (down) direction. Then, every output node that receives at most r proposals sends back acceptances to all of those proposals. (Notice that this step limits the number of paths passing through a node to at most r.) Finally, each node that receives enough acceptances to extend all of its paths does so. In a network with an r-neighbors property, a constant fraction of the paths on each level are extended at each step. Thus, the time to extend a set of N paths from one level to the next is , and the total time to route a set of N paths from the inputs to the outputs is . As in Section 4, this time can be improved to using place-holders and cancellation signals.

Note that for , only expansion is required in order to have an r-unshared neighbors property, where and . Since an algorithm for finding edge-disjoint paths can be converted to an algorithm for finding node-disjoint paths by replacing each degree-2d node with a complete bipartite graph, the algorithm of this section reduces the expansion required for finding either edge- or node-disjoint paths from to . The difference is important because explicit constructions of expander graphs are known for [13], but not for . The algorithms for tolerating faults in [17] and the algorithms for routing paths in a nonblocking fashion in this paper still seem to require . Recently, however, Pippenger has shown how to perform all of these tasks using only expansion [31].

In order to use this routing algorithm in network R, we must make one modification. The paths from the sources do not necessarily start on level of the first part. In fact as many as four paths may start at any node in the first part. (Recall that sources in the second, third, and fourth parts start their paths in the first part.) Thus, the routing algorithm must be modified so that a node in the first part sends acceptances to the nodes at the previous level only if it receives at most r-4 proposals. The impact on the performance of the algorithm will be negligible if r is large relative to 4.

Next: 6 Acknowledgments Up: 5.3 Removing the distinction Previous: 5.3.2 Constructing node-disjoint paths

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