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.