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.

Mon Jul 22 21:19:59 EDT 1996