The network *R* consists of four parts, each of which contains levels of *N* nodes. Each of the first three parts shares
its last level with the first level of the next part, so the total
number of levels is , and the total number of nodes in
the network is .

The first part is a set of levels labeled
through . For , the edges
connecting level *i* to *i+1*, form an *N*-input merger. Hence, every
set of nodes on one level has at least
neighbors on the next level, where , , and *d* are
related as in Equation 2.2.

The second part consists of a multibutterfly whose levels are labeled
through *0*. The multibutterfly has expansion property
, where , , and *d* are related as in
Equation 2.1.

The third and fourth parts are the mirror images of the first and
second parts. The levels of these parts are labeled *0* through
.

Although any node in *R* can be chosen to be a source or a sink, it
would be more convenient if all of the sources were to reside in the
first part, and all the sinks in the fourth. Thus, the node on level
*-i* of the second part, *i* of the third part, and of the
fourth part each have an edge called a *cross* edge to the
corresponding node on level of the first part.
Similarly, each node in the fourth part has cross edges to the
corresponding nodes in first, second, and third parts. If a node in
any part other than the first is chosen to be a source, then its path
begins with its cross edge to the first part. If a node in any part
other than the fourth is chosen to be a sink, then the path to it ends
with a cross edge from the fourth part. At this point, each node in
the first part may represent up to four sources, and each node in the
fourth part may represent up to four sinks.

Mon Jul 22 21:19:59 EDT 1996