In this paper, we are primarily concerned with randomly-wired splitter
networks. A *randomly-wired splitter network* 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 is incident
to *d* up and *d* down edges, and each splitter output is incident to
*2d* incoming edges.

The crucial property that randomly-wired splitter networks are likely
to possess 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* [29], and a *multibutterfly
with -expansion and multiplicity d* consists of
splitters in which each splitter input is incident to

Splitters with expansion are known to exist for any , and
they can be constructed deterministically in polynomial time
[11, 23, 29], but randomized wirings typically
provide the best possible expansion. In fact, the expansion of a
randomly-wired splitter will be close to *d-1* with probability close
to *1*, provided that is a sufficiently small constant. (For
a discussion of the tradeoffs between and in
randomly-wired splitters, see [20, 29].)

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.

In 1989, Upfal showed that any *N*-input multibutterfly can route any
one-to-one problem in steps using a simple greedy
algorithm [29], and that, by using pipelining, any *N*-input
multibutterfly can route one-to-one problems in steps. Although the proof is complicated and the constants hidden
by the Big Oh notation are large, the result is important because the
only previously known deterministic on-line linear-hardware -step packet routing algorithm [18] requires the use
of the AKS sorting circuit [1] (which is even more
complicated and has even larger constant factors).

Mon Jul 22 18:45:42 EDT 1996