User Manual

5,521,591
7
of the number of inputs or outputs in the logical cluster. A
switching network is said to be low-degree if the degree of
the switches in the network is a small ?xed constant inde
pendent of the number of inputs or outputs in the network.
For practical implementation of these networks, the low
degree property is a requirement due to ?xed component
pinout.
Expansion
The present invention is concerned with low degree
logical clusters exhibiting expansion and/or dispersion. An
N-input logical cluster is said to be (ot,B)—expansive if for
every small subset of k switches, i.e., l(<(X.N, every subset of
k input ports (switches) collectively is connected to at least
Bk output ports in each group of outputs, where B>l and B
and 0t are ?xed threshold parameters independent of N.
Typical values of 0t and B are ot=1/3 and B=4/3. More simply,
a logical cluster is said to be expansive if it is (ot,B)
expansive for some threshold values of B>l and 2otB<l.
Intuitively, the expansion property for a logical cluster
implies that for all subsets of size k of the input switches to
the cluster, there are more than k output switches in each
output group which are connected to the subsets of size k.
The possible paths that a message may assume, thus, expand
between input and output. The extent to which there are
more than k switches in the output group is determined by
the parameter B. Hence, if B is 2, there are twice as many
output switches in each output group that are connected to
the k input switches. k has a value less than the total number
of input switches into the cluster N. The extent to which k
is less than N is determined by or.
A switching network comprised of expansive logical
clusters is said to be expansive. Two examples of expansive
switching networks are the multibutter?y network and the
multi-Benes network, both of which will be discussed
below.
Multibutter?y
A multibutter?y network is formed by merging butter?y
networks in a somewhat unusual manner. In particular, given
2 N-input butter?ies G1 and G2 and a collection of permu
tations (I'I=1t0, n1, . . . , nlgN) where nL:[0,(N/2L—l)] [0,(N/
2L—l)]a 2-butter?y is formed by merging the switch in row
(jN/2L)+i of level L of G1 with the switch in row Q'N/2L)+
1tL(i) of level L of G2 for all Oéié (N/2L)—l, all O§j<(2l‘
—l), and all OéLélgN. The result is a 2-butter?y comprising
an N-input lgN+l —level graph.
In other words, a twin multibutter?y 55 is formed from
merging two butter?ies such as 51 and 53 in FIG. 8, each
having N input switches. How the butter?ies 51 and 53 are
merged is determined by the permutation H. In particular,
given a ?rst switch in the ?rst butter?y located on level L at
a given row (i,e, row=jN/2L+i), the ?rst switch is merged
with a second switch in the second butter?y also on level L,
but at a row determined by the permutation (i.e. jN/ZL
+11:L(l)). The permutation maps an integer in the range of 0
to N/2L—l to a permuted integer also in the range of 0 to
N/2L—l.
For an example of such a butter?y, see the multibutter?y
55 shown in an enlarged view in FIG. 9. Of the 4 output
wires at a switch in the multibutter?y 55, two are up outputs
and two are down outputs (with one up wire and one down
wire being contributed from each butter?y). Thus, switch 31
has two up wires 33 and two down wires 35. Multibutter?ies
(i.e. d-butter?ies) are composed from d butter?ies in a
10
20
25
30
35
45
50
55
60
65
8
similar fashion using d—l sets of permutations 11(1), . . . ,
1101-1) to produce a lgN level networks with 2d><2d switches.
The notion of up and down edges (or wires) discussed
above relative to a Z-butter?y can be formalized in terms of
splitters. More precisely, the edges from level L to level L+1
in rows (iN/2L) to ((i+l)N/2L)—1 in a multibutter?y form a
splitter for all 0§L<lgN and 0§j§2L—l. Each of the 2'“
splitters starting at level L has N/2L inputs and outputs. The
outputs on level L+l are naturally divided into NIZLJ"1 up
outputs and N/2L+1 down outputs. All splitters on the same
level L are isomorphic (i.e. they have the same number of
inputs, the same number of outputs and the same wire
connection patterns), and each input is connected to d up
outputs and (1 down outputs according to the butter?y and
the permutations 11L“), . . . , ELM-1). Hence, any input and
output of the multibutter?y are connected by a single logical
(up-down) path through the multibutter?y, but each step of
the logical path can be taken on any one of d edges.
An important characteristic of a multibutter?y is the set of
permutations II“), . . . , TIM-1) that prescribe the way in
which the component butter?ies are merged. For example, if
all of the permutations are the identity map, then the result
is the dilated butter?y (i.e., a butter?y with (1 copies of each
edge).
Of particular interest to the present invention are multi
butter?ies that have expansion properties. A multibutter?y
has expansion property (ot,B) if each of its component
splitters has expansion property (ot,B). In turn, an M-input
splitter has expansion property (ot,B) if every set of kéotM
inputs is connected to at least Bk up outputs and Bk down
outputs for B>l.
If the permutations 11(1), . . . , I'IVH) are chosen randomly,
then there is a good probability that the resulting d-butter?y
has expansion property (ot,B) for any d, or, and B for which
2otB<l and
It is not difficult to see that a multibutter?y network offers
many advantages over a butter?y network. For example,
whereas a butter?y contains just one path from each input
port to each output port, a multibutter?y contains many
paths from each input to each output port. Indeed, there is
still just one logical (up-down) path from any input to any
output, but this logical path can be realized as any one of
several physical paths.
Another advantage of a multibutter?y (or any switching
network comprised of expansive logical clusters) is that it is
very hard for a large number of switches to become blocked
by congestion or by faults. The reason is that for k inputs of
an expansive logical cluster to become blocked, at least Bk
of the outputs would have to be blocked or faulty them
selves. In a typical network like the butter?y, the reverse is
true. One can block k inputs by congesting only k/2 outputs.
When this property is cascaded over several levels of the
network, the difference in performance between the butter?y
versus the multibutter?y can be dramatic. For example, one
fault can block 1000 switches 10 levels back in the butter?y,
but 1000 faults would be necessary to block just 1 switch 10
levels back in the multibutter?y (if B:2).
Multi-Benes
Like a multibutter?y, a multi-Benes network is formed
from merging networks together, speci?cally Benes net
works. A 2-multi-Benes network 26 is shown in FIG. 10. An
N-input multi-Benes network has 21 gN+l levels labeled 0