PAPERBACK
\$52.75

• #### 12 Missing Pieces, Derandomization, and Concluding Remarks 175-178

FIGURE 11.1: An 8-input butterfly network. Reprinted, with permission, from Arora et al. (1990). Copyright © 1990 by ACM Press.

to its destination output. One problem with this algorithm (and hence the network) is that if some switch or edge along the unique path from input i to output j (say) becomes congested or fails, then communication between input i and output j will be disrupted.

#### 11.1.1Dilated Butterflies

Because message congestion is a common occurrence in real networks, the wires in butterfly networks are typically dilated, so that each wire is replaced by a channel consisting of two or more wires. In a d-dilated butterfly, each channel consists of d wires. Because it is harder to congest a channel than it is to congest a single wire in a butterfly, dilated butterflies are better routing networks than simple butterflies (e.g., Koch, 1988; Kruskal and Snir, 1983; Rettberg et al., 1990).

#### 11.1.2Delta Networks

Butterfly and dilated butterfly networks belong to a larger class of networks called delta networks (see, e.g., Kruskal and Snir, 1986). The switches on each level of a delta network can be partitioned into blocks. All of the switches on level 0 belong to the same block. On level 1, there axe two blocks, one consisting of the switches that are in the upper N/2 rows and the other consisting of the switches that are in the lower N/2 rows. In general, the switches in a block B of size M on level l have neighbors in two blocks, Bu, and Bl, on level l + 1. The upper block, Bu, contains the switches on level l + 1 that are in the same rows as the upper M/2 switches

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement