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

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.

Mon Jul 22 19:56:03 EDT 1996