Next: 3 Routing around faults Up: 2 Butterflies and Multibutterflies Previous: 2.2 Splitter networks

## 2.3 Randomly-wired splitter networks and multibutterflies

In this paper, we are primarily concerned with randomly-wired splitter networks. A randomly-wired splitter network with multiplicity d is a splitter network where the up and down edges within each splitter are chosen at random subject to the constraint that each splitter input has d up and d down edges, and each splitter output has 2d incoming edges.

The crucial property that randomly-wired splitter networks are likely to possess [7, 12] is known as expansion. In particular, an M-input splitter is said to have -expansion if every set of inputs is connected to at least up outputs and down outputs, where and are fixed constants. For example, see Figure 4.

A splitter network is said to have -expansion if all of its splitters have -expansion. More simply, a splitter or a splitter network is said to have expansion if it has -expansion for some constants and . A splitter network with expansion is more commonly known as a multibutterfly [12].

Splitters with expansion are known to exist for any , and they can be constructed deterministically in polynomial time [2, 9, 12], but randomized wirings typically provide better expansion. A discussion of the tradeoffs between and in randomly-wired splitters, can be found in [7] and [12]. For the purposes of this paper, two facts are needed. First, for fixed d and sufficiently small , the expansion, , of a randomly-wired splitter will be close to d-1 with probability close to 1. Second, for fixed and sufficiently large d, will be close (the best possible) with probability close to 1. It is not known if it is possible for to be close to d-1 and for to be close to simultaneously.

A multibutterfly with -expansion is good at routing because one must block splitter outputs in order to block k splitter inputs. In classical networks such as the butterfly, the reverse is true: it is possible to block 2k inputs by blocking only k outputs. When this effect is compounded over several levels, the effect is dramatic. In a butterfly, a single fault can block switches l levels back, whereas in a multibutterfly, it takes faults to block a single switch l levels back.

Figure 4: An M-input splitter with -expansion.

Next: 3 Routing around faults Up: 2 Butterflies and Multibutterflies Previous: 2.2 Splitter networks

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996