Next: 5.2 Multiple calls to Up: 5 Extensions Previous: 5 Extensions

## 5.1 Multiparty calls

If all of the parties in a multiparty call are known to a caller at the start of the call, then it is possible to extend the algorithms in Sections 3 and 4 to route the call from the caller to all of the parties. As a call advances from level 0 to level of the multi-Benes network, it simply creates branches where necessary to reach the desired output terminals. The bit complexity of the algorithm may increase, however, because more than bits may be needed to specify the set of outputs that the call must reach.

The situation becomes more complicated if parties to a multiparty call are to be added after the call is already underway. One possible solution is to set up paths in the network from the caller to the parties in the call that make multiple passes through the network. To simplify the explanation, let us assume that the input in row i and the output in row i of the multi-Benes network are actually the same node, for . (Thus each input/output can be involved in at most one call.) A multiparty call is established by constructing a binary tree whose root is the caller and whose internal nodes and leaves are the parties in the call. Each node of the binary tree is embedded at an input of the multi-Benes network, and each edge in the tree from a parent to a child is implemented by routing a path through the multi-Benes network from the input at which the parent is embedded to the output (which is also an input) at which the child is embedded. To add a new party to the call, we add a new node to the binary tree wherever its depth will be minimum. This ensures that the depth of a tree with l parties will be . Since each edge of the binary tree corresponds to a path of length in the network, the path from the root to any other node in the tree has length at most in the network. It's easy to see that a new party can be added in bit steps, but with a little work the time can be brought down to bit steps. One problem with this scheme is that the parties corresponding to internal nodes of the binary tree cannot hang up without also disconnecting all of their descendants. Although this solution is not as elegant as those proposed in [10] for wide-sense generalized nonblocking connectors, no polynomial time routing algorithms are known for those constructions.

Next: 5.2 Multiple calls to Up: 5 Extensions Previous: 5 Extensions

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