next up previous
Next: 5.3 Removing the distinction Up: 5 Extensions Previous: 5.1 Multiparty calls

5.2 Multiple calls to the same output

If many parties want to call the same output terminal, then we have two options: merging the callers into a single multiparty call, or giving busy signals to all but one of the callers.

In either case, the first thing to do is to sort the calls according to their destinations. Unfortunately, no deterministic tex2html_wrap_inline2387 -bit-step sorting algorithm is known for the multibutterfly network at present, although tex2html_wrap_inline2389 word- and bit-step randomized algorithms are known for the butterfly [20, 34]. If a deterministic tex2html_wrap_inline2391 -bit-step algorithm is required, the multibutterfly could be augmented with a sorting circuit such as the AKS sorting circuit [2]. The AKS sorting circuit will provide us with a set of edge-disjoint paths from its inputs to its outputs. If node-disjoint paths are desired, then each tex2html_wrap_inline2393 comparator in the circuit can be replaced by a tex2html_wrap_inline2395 complete bipartite graph. Note that in neither case is the sorting circuit a nonblocking network, since adding new calls at the inputs may alter the sorted order, thus disrupting existing paths. In the remainder of this section, we will use a sorting circuit either in conjunction with a butterfly network to route calls in a rearrangeable fashion, or in conjunction with a multibutterfly to route calls in a nonblocking fashion. In the latter case, the sorting circuit is used only to help compute the routes that the calls take, and not to route the calls themselves.

Once the calls have been sorted, a parallel prefix computation is applied to the sorted list of calls. For each destination, one of the calls is marked as a winner, and the others as losers. For a description of prefix operations, and how they can be implemented in tex2html_wrap_inline2397 bit steps on a complete binary tree (which is a subgraph of the butterfly), see [16, Section 1.2,].

If it suffices to send a busy signal to all of the callers except one, then these signals can be sent back to the losers along their paths through the sorting circuit, and the winning path can be established (in a nonblocking fashion) in a multibutterfly network.

If the calls are to be merged into a single call, then the next step is to label the winners according to their positions in the sorted order, and to give each loser the label of the winner for its destination. This is also prefix computation.

To route calls in a rearrangeable fashion, we identify the outputs of the sorting circuit with the inputs of a butterfly network. Each call is routed greedily in the butterfly network to the output in the row with the same number as the winner's index. This type of routing problem is called a packing problem. Surprisingly, only calls with the same destination will collide during the routing of any packing problem [16, Section 3.4.3,]. After this step, all of the calls to the same destination have been merged into a single call. Since the calls remain sorted by destination, the problem of routing them to their destinations is called a monotone routing problem. Any monotone routing problem can be solved with a single pass through two back-to-back butterfly networks without collisions [16, Section 3.4.3,].

To route calls in a nonblocking fashion, we can either assume that all callers are known at the time that a call is established or not. If all of the callers are known, we can route the calls backwards through a multibutterfly from the shared output to each of the inputs of the callers using the first scheme described in Section 5.1. Otherwise, we can use the second scheme of Section 5.1 in reverse to route the calls using paths of length tex2html_wrap_inline2399 .

next up previous
Next: 5.3 Removing the distinction Up: 5 Extensions Previous: 5.1 Multiparty calls

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