User Manual
5,521,591
15
node-disjoint
path
linking
any
unused
input-output
pair.
As
such,
if
Bob
is
talking
to
Alice
and
Ted
is
talking
to
Carol,
then
Pat
can
still
call
Vanna.
To
satisfy
connection
requests
in
a
non-blocking
multi
Benes
network,
an
algorithm
is
employed
that
establishes
a
path
from
an
unused
input
to
an
unused
output
in
0(logN)
bit-steps,
where
N
is
the
number
of
rows
in
the
network.
In
the description
of
the
algorithm
that
follows,
it
is
assumed
that
at
most
one
input
tries
to
access
any
output
at
a
time,
and
that
each
input
accesses
at
most
one
output
at
a
time.
The
central
idea
behind
the
nonblocking
routing
algo
rithm
used
for
an
expansive
switching
network
is
to
treat
the
switches
through
which
paths
have
already
been
established
as
if
they
were
faulty
and
to
apply
the
previously
described
status
propagation
techniques
to
the
network.
In
particular,
a
node
is
de?ned
as
busy
if
there
is
a
path
currently
routing
through
it.
At
the
start, all
busy
nodes
are
said
to
be
unavailable.
A
node
is
de?ned
recursively
to
be
unavailable
if
all
of
its
up
outputs
or
if
all
of
its
down
outputs
are
unavailable.
More
precisely,
switches
are
declared
to
be
unavailable
according
to
the
following
rule.
Working
back
wards
from
level
21
gN-l
gZ
to
level
lgN, a
switch
is
declared
unavailable
if
either
all
d
of
its
up
edges
or
all
d
of
its
down
edges
lead
to
unavailable
switches.
From
level
lgN
—l
to
level
1
gZ, a
switch
is
declared
unavailable
if
all
2d
of
its
outputs
lead
to
unavailable
switches.
A
switch
that
is
not
unavailable
is
said
to
be
available.
After
the
status
propagation
process,
every
available
switch
in
the
?rst
half
of
the
network
has
an
output
that
leads
to
an
available
switch,
and
every
available
switch
in
the
second
half
has
both
an
up
output
and
a
down
output
that
leads
to
available switches.
Furthermore,
since
at
most
a
20c
fraction
of
the
switches
in
each
merger on
level
1
gZ
are
unavailable,
each
of
the
N/Z
inputs
has
an
edge
to
an
available
switch
on
level
Z.
At
the
other
end,
each
of
the
N/Z
outputs
can
be
reached
by
an
available
switch
on
level
21
gN-l
gZ.
As
a
consequence,
a
path
can
be
established
through
available
switches
from
any
unused
input
to
any
unused
output
in
0(logN)
bit-steps
using
a
simple
greedy
algorithm.
Since
the
declaration
of
unavailable
switches
takes
just
0(logN)
bit-steps,
and
since
the
greedy
routing
algorithm
is
easily
accomplished
in
0(logN)
bit-steps,
the
entire
process
takes
just
0(logN)
bit-steps.
It
is
not
di?icult
to
implement
the
circuit-switching
algo
rithm
for
use
with a
multi-Benes
network.
Speci?cally, the
de?nition
of
being
blocked
must
be
modi?ed
so
that
a
node
on
level
L
is
blocked
if
more
than
2B—d—l
of
its
up
(or
down)
neighbors
on
level
L+l
are
unavailable.
(As
before,
it
is
assumed
that
]3>d/2.)
Available
nodes
are
then
guaranteed
to
have
at
least
2d-2
[5+1
available
neighbors.
Hence,
any
set
of
kéotM
available
inputs
in
an
M-input
splitter
has a
(on,
l/d)
dispersion
property,
which
is
su?icient
for the
routing
algorithm
to
work.
Of
course,
it
must
also
check
that
the
modi?ed
de?nition
of
unavailable
does
not
result
in
any
inputs
to
the
multi-Benes
network
becoming
unavailable.
See
Arora,
supra
and
Leighton,
supra
for
details.
The
above
process
can
be
applied
in
a
fault
tolerant
environment
by
initially
declaring
all
faulty
switches
as
unavailable.
Although
preferred
embodiments
have been
speci?cally
described
and
illustrated
herein,
it
will
be
appreciated
that
many
modi?cations
and
variations
of
the
present
invention
are
possible,
in
light
of
the
above
teachings,
within
the
purview
of
the
following
claims,
without
departing
from
the
spirit
and
scope
of
the
invention.
We
claim:
10
15
20
25
35
50
55
60
65
16
1.
A
switching
network
for
routing
messages
comprising
at
least
one
logical cluster
which
comprises:
a)
a
?rst
set
of
switches
having
N
input
switches
for
receiving
messages
and
a
second
set
of
switches
having
approximately
N
output
switches
for
outputting
mes
sages
wherein
the
second
set
of
switches
is
divided
into
at
least
two
unique groups
of
switches;
and
b)
connectors
for
connecting
the
?rst
set
of
switches
to
the
second
set
of
switches
wherein
for
every
subset
of
input
switches
of
size
k
of
the
?rst
set
of
switches,
there
are
at
least
x
output
switches
in
each
group
of
the
second
set
of
switches
that
are
connected
to
precisely
one
of
the
input
switches
of
the
subset
of
size
k
input
switches,
where kéotN,
xéootN,
where
k, x,
and
N
are
positive
integers,
N
is
equal
to
at
least
8,
where
any
particular
subset
includes
any
k
of
the
N
input
switches,
and
where
5
and
or
are
positive
constants
less
than
one,
such
that
the
logical
cluster
exhibits
a
dispersion
property.
2.
A
switching
network
as
recited
in
claim
1
wherein
the
switching
network
is
a
multibutter?y
switching
network
said
multibutter?y
switching
network
comprising
a
superposition
of
plural
butter?y
switching
networks.
3.
A
switching
network
as
recited
in
claim
1
wherein
the
switching
network
is
a
multi-Benes
switching
network,
said
multi-Benes
switching
network
comprising
a
superposition
of
plural
Benes
switching
networks.
4.
A
switching
network
as
claimed
in
claim
1
comprised
of a
plurality
of
said
logical
clusters
of
switches
that
are
interconnected
by
connections,
each
logical
cluster
further
comprising
controller
means
programmed
to
perform
the
following
operations:
declaring
unusable
switches
as
unavailable
and,
proceeding
from
an
output
level
backward,
declaring
each
switch
unavailable
if
the
switch
does
not
have
a
su?icient
quantity
of
connections
to
non-unavailable
switches
in
each
output
group
for
each
logical
cluster,
and
avoiding
switches
declared
unavailable
in
routing
messages
across the
switching
network.
5.
A
network
as
claimed
in
claim
4
wherein
a
busy
switch
or
a
faulty
switch
is
unusable.
6.
A
network
as
claimed
in
claim
4
further
comprising
means
for
deactivating
all
switches
in
one
of
said
logical
clusters
as
well
as
all
descendant
switches
connected
to
the
outputs
of
said
one
of
said
logical
clusters
where
a
number
of
faulty
input
switches
of
that
one
of
said
logical
clusters
exceeds
a
predetermined
threshold.
7.
A
network
as
claimed
in
claim
1
further
comprising
means
for
extending
message
paths
between
switches
of
the
at
least
one
logical
cluster
comprising:
means
for
sending
a
proposal
from
a
current
switch
for
each
message
path
that
is
to
be
extended
to
each
neighbor
switch
in
a
desired
direction
of
extension;
means
for returning
an
acceptance
to
the
proposal
to
the
current
switch
position
from
a
neighbor
switch
if
the
neighbor
receives
exactly
one
proposal;
and
means
for
advancing
each
message
path
to
include
an
accepting
neighbor
switch
for
each
message
path
receiving
exactly
one
acceptance.
8.
A
network
as
claimed
in
claim
7
further
comprising
means
for
sending
placeholders
on
behalf
of
any
message
paths
that
are
not
moved
forward
such
that
the
placeholders
reserve
a
place
at
a
switch
to
which
the
message
path
is
to
extend.
9.
A
switching
network
as
claimed
in
claim
1
wherein
the
second
set
of
switches
is
divided
into
at
least
two
unique
groups of
switches
and
said
at
least
one
logical
cluster
exhibits
an
expansion
property
such
that,
for
small
subsets