User Manual
5,521,591
9
through
21
gN.
Levels
lgN
through
21
gN
form
a
multibut
ter?y,
while
levels
0
through
lgN
form
the
mirror
image
of
a
multibutter?y.
Thus,
informally
the
2
multi-Benes
network
can
be
viewed
as
a
network
made
of
two
butter?y
networks
placed
back
to
back.
As
in
the
multibutter?y,
the
edges
in
levels
lgN
through
21
gN
of
the
multi-Benes
are
partitioned
into
splitters.
Between
levels
0
and
lgN,
however,
the
edges
are
parti
tioned
into
mergers.
More
precisely,
the
edges
from
level
L
to
level
L+l
in
rows
j
2"+1
to
(j+l)2l‘—1
form
a
merger
for
all
OéL+lgN
and
0§j§N/2L+1—l.
Each
of
the
NI2L+1
L
<1gN
and
O§j§N/2L+1=1.
Each
of
the
N/2"+1
mergers
starting
at
level
L
has
2'’1
inputs
and
outputs.
The
inputs
on
level
L
are
naturally
divided
into
2L
up
inputs
and
2L
down
inputs.
All
mergers
on
the
same
level
L
are
isomorphic,
and
each
input
is
connected
to
2d
outputs.
There
is
a
single
(trivial)
logical
path
from
any
input
of
a
multi-Benes
network
through
the
mergers
on
the
?rst
lgN
levels
to
the
single
splitter
on
level
lgN.
From
level
lgN,
there
is
a
single
logical
path
through
the
splitters
to
any
output.
In
both
cases,
the
logical
path
can
be
realized
by
many
physical
paths.
An
M-output
merger
has
expansion
property
(m5)
if
every
set
of
kéotM
inputs
(up
or
down)
is
connected
to
at
least
25k
outputs
where
[5>l.
With
nonzero
probability,
a
random
set
of
permutations
yields
a
merger
with
expansion
property
(ot,B)
for
any
d,
or,
and
B
for
which
otB<l
and
A
multi-Benes
network
has
expansion
property
(11,13)
if
each
of
its
component
mergers
and
splitters
has
expansion
property
(call).
The
multibutter?ies
and
multi-Benes
net
works
considered
herein
are
assumed
to
have
expansion
property
(ot,[3)
unless
otherwise
stated.
Dispersive
Logical
Clusters
The
present
invention
is
also
concerned
with
dispersive
logical
clusters.
An
N-input
logical cluster
is
said
to
be
dispersive
if
for
prespeci?ed
threshold
parameters
or,
5,
for
every
k§t1N
and
for
every
set
of
k
inputs,
there
are
at
least
5k
outputs
ports
(switches)
in
each
group of
the
logical
cluster
that
are
connected
to
precisely
one
of
the
k
input
ports
(switches).
This
de?nition
of a
dispersive
logical
cluster
may
be
restated
as:
a
logical cluster
wherein
every
subset
x
of
kéotN
inputs
in
the
cluster,
there
are
8k
switches
in
x
which
have
a
neighbor
in
each
output
group
that
is
not
connected
to
any
other
switch
in
x.
In
other
words,
6k
nodes
in
x have
a
unique
neighbor
for
each
output
group.
This
property
is
called
the
unique~neighbors
property
in
S.
Arora,
T.
Leighton
and
B.
Maggs,
On-line
algorithms
for
path
selection
in
a
non-blocking
network,
Proceedings
of
the
22nd
Annual
ACM
Symposium
on
the
Theory
of
Computing,
1990
incorporated
herein
by
reference.
A
switching
network
comprised
of
dispersive
logical
clusters
is
called
a
dispersive
switching
network.
A
switching
network
with
dispersive
logical
clusters
offers
substantial
advantages
over
ordinary
switching
net
works.
Ordinary
networks
are
typically
unable
to
concur
rently
move
all
messages
forward. In
most
instances,
some
messages
are
moved
forward
while
others
are
terminated
or
queued
for
long
periods
of
time.
In
a
network
with
disper
sive
logical
clusters,
on
the
other
hand,
a
message
at
an
input
can
advance
without
fear
of
blocking
other
messages
if
the
input
is
connected
to
an
output
which
is
coupled
to
no
other
inputs
with
a
message.
Given
that
in
a
dispersive
logical
cluster
at
least
5k
outputs
in
each
output
group
of
a
cluster
15
25
35
40
45
55
60
65
10
are
connected
to
precisely
one
input
switch,
at
least
a
5
fraction
of
all
messages
can
advance
at
every
step
in
a
dispersive
logical
cluster
without
ever
blocking
other
mes
sages.
Any
splitter
with
the
(ot,[3)
expansion
property
has
the
(ot,5)
dispersion
property
where
8:2B/d-l,
provided
that
B>d/2.
See
Arora
et
al.,
supra.
By
Equation
1,
it
is
evident
that
randomly
generated
splitters
have
the
(ot,5)
dispersion
property
where
6
approaches
1,
as
d
gets
large
and
as
e
gets
small.
Explicit
constructions
of
such
splitters
are
not
known,
however.
Only
multibutter?ies
with
the
(ot,8)
dispersion
property
for
5>0
will
be
discussed
below.
It
should
be
noted
that
the
(oc,B)
expansion
property
(where
B>d/2)
is
a
su?i
cient
condition
for
the
dispersion
property,
but
by
no
means
necessary.
In
fact,
the
existence
of
random
splitters
which
have
a
fairly
strong
((1,5)
dispersion
property
for
small
degree
is
proven
in
Arora
et
a1.
Amongst
the
many
methods
for
constructing
expansive
and/or
dispersive
logical
clusters
with
low-degree
is
a
method
consisting
of
connecting
the
input
ports
to
the
output
ports
randomly
so
that
every
switch
has
the
same
degree.
With
high
probability,
the
resulting
logical
cluster
is
expan
sive
and
dispersive
if
the
number
of
connections
from
each
input
port
to
each
output
port
is
3
or
higher.
Even
if
the
there
are
only
2
connections
from
each
input
port
to
each
output
port,
the
concatenation
of
two
logical
clusters
still
has
the
expansive
and
dispersive
properties
with
high
probability.
Logical
clusters
such
as
splitters
and
mergers
have been
described
thus
far
as
only
having
a
depth
of
1
(i.e.,
input
ports
are
switches
that
are
directly
connected
to
output
ports).
Nevertheless,
the
logical
clusters
can
have
more
than
one
level.
For
example,
if
two
depth
1
splitters
are
cascaded,
a
depth
2N
splitter
30
is
generated
(See
FIG.
11).
Logical
clusters
with
depth
1,
2,
or
3 are
of
primary
interest
in
the
present
invention.
For
logical
clusters
with
depth
2
or
more,
an
input
port
is
connected
to
an
output
port
if
it
can be
connected
to
the
output
port
by
an
appropriate
setting
of
the
switches
in
the
logical
cluster.
The
de?nitions of
expansion
and
dispersion
given
above
apply
equally
to
such
logical
clusters.
Using
these
de?nitions,
it
is
possible
to
construct
depth
2
logical
clusters
comprised
of
2X2
switches
that
have
the
expansion
and
the
dispersion
property
(see
Arora,
supra;
and
T.
Leighton
and
B.
Maggs,
Expanders
might
be
practi
cal:
fast
algorithms
for
routing
around
faults
in
multi
butter?ies,
Proceedings
of
the
30th
Annual
Symposium
on
Foundations of
Computer
Science,
October
1989,
pps.
384—389
which
is
incorporated
herein
by
reference.
Routing
Methods
In
addition
to
the
new
types
of
switching
networks,
the
present
invention
is
concerned
with
methods
for
routing
messages
on
such
networks.
These
routing
methods
allow
many
messages
to
be
routed
to
their
correct
destination
quickly
using
only
destination
addresses
and
on-line
control.
On-line
control
refers to
all
decisions
regarding
switching
being
made
locally
by
each
switch
without
global
inforrna~
tion
about
the
location
and
destinations
of
other
packets
as
for
example,
shown
routing
controller
57
connected
to
switch
59
in
FIG.
18.
The
routing
methods
also
allow
the
messages
to
be
routed
around
faulty
switches
and/or
busy
switches.
A
switch
is
said
to
be
faulty
if
it
is
not
functioning
correctly,
and
it
is
said
to
be busy
if
it
cannot be
used
to
route
any
additional
messages
(i.e.,
all
of
its
capacity
is
currently
being
used).
These
features
of
the
routing
methods
can
be
integrated
into
the
notion of
switch
availability.
In
particular,
the
status