User Manual
5,521,591
1
SWITCHING
NETWORKS
WITH
EXPANSIV
E
AND/OR
DISPERSIVE
LOGICAL
CLUSTERS
FOR
MESSAGE
ROUTING
RELATED
PATENT
APPLICATIONS
This
application
is
a
continuation
of
application
U.S.
Ser.
No.
07/732,031
?led
Jul.
18,
1991,
abandoned,
which
is
a
continuation
of
Ser.
No.
07/488,693
?led
Mar.
5,
1990,
abandoned,
and
PCT
application
No.
PCT/U39
1/015
13
?led
Mar.
5,
1991.
BACKGROUND
OF
THE
INVENTION
A
switching
network
typically
is
made
of
input
ports
and
output
ports
that
are
interconnected
by
switches
and
wires.
The
switching
network
serves
primarily
to
correctly
route
messages
from
the
input
ports
to
the
output
ports.
Each
wire
in
the
network
serves
as
a
conduit
for
transmitting
a
message
from
one
of
its
ends
to
the
other
of
its
ends.
The
term
wire,
in
this
context,
or the
terms
connection
or
connector,
includes
any
means
for
communicating
data
between
switches,
such
as
electrical
wires,
parallel
groups
of
wires,
optical
?bers,
multiplexed
channels
over
single
wires,
or
free
space
radio
or
optical
communication
paths.
The
switch
is
an
atomic
unit
that
resembles
a
switching
network
in
function
(i.e.,
a
switch
has
inputs
and
outputs
and
connects
the inputs
to
the
outputs
in
any
desired
pattern).
The
degree
of
a
switch
is
the
number
of
inputs
and
outputs
in
the
switch.
For
example,
as
shown
in
FIG.
1
a
2X2
switch
2
has
a
degree
of
four.
A
switching
network
may
route
any
kind of
digital
or
analog
data
including
voice
or
video
signals.
It
can
also
route
address
information
that
speci?es
the
correct
output
for
the
message,
and
routing
information
that
helps
direct
the
message
to
the
correct
output
or
that
establishes
communi
cations
links
such
as in
a
telephone
network.
In
some
networks,
the
routing
is
accomplished
by
setting
switches
so
that
input
ports
become
directly
connected
to
output
ports
(e.g.,
in
a
telephone network).
In
other
networks,
the inputs
ports
do
not
become
directly
connected
to
the
output
ports.
Instead,
the
messages
are
routed
as
packets
through
the
network
in
steps.
Switching
networks
are
widely
used
to
route
messages
and
to
establish
communications
among
multiple
parties.
Typical
examples
of
networks
in
which
switching
networks
are
used
include
telephone
networks,
data
networks,
com
puter
networks,
and
interconnection
networks
in
parallel
data
processing
systems.
There
are
several
varieties
of
switching
networks
that
are
classi?ed
by
the
manner
in
which
messages
are
handled
by
the
network.
Common
types
of
switching
networks
include
packet-switching,
circuit-switching,
cut-through,
and
worm
hole
networks.
In
a
packet-switching
network,
packets
are
treated
as
atomic
objects.
At
each
time
step,
each
wire
in
the
packet
switching
network
can
transmit
an
entire
packet
from
one
switch
to
another
switch.
If
necessary,
packets
may
be
queued
in
buffers
located
at
the
switches
or
at
the
wires
of
the
network.
These
networks
are
also
often
referred
to
as
store-and-forward
networks.
The
name
“store
and
forwar
”
is
derived
from
the
characteristic
of
the
networks
that
packets
are
temporarily
stored
in
the
queues
and
then
forwarded
to
the
next
destination
in
the
network.
A
circuit
switching
network
is
appropriate
when
messages
are
too
large
to
be
treated
as
atomic
objects
(such
as
packets).
In
this
type
of
network,
a
dedicated
path
is
estab
20
25
35
50
55
65
2
lished
in
the
switching
network
between
the
sender
and
receiver
of
each
message.
The
paths
corresponding
to
dif
ferent
messages
are
disjoint
(i.e.,
they
do
not
share
any
wires).
Once
a
path
is
established,
the
sender
can
transmit
an
arbitrarily
long
message
to
the
receiver
without
interference
from
the
other
messages.
This
model
is
also
called the
lock-down
model,
and
most
closely
resembles
the
approach
adopted
by
current
telephone
networks.
The
wonnhole
and
cut-through
networks
are
best
classi
?ed
as
lying
in
a
class
situated
between
the
packet
and
circuit-switching
networks.
In
a
Wormhole
network,
a
packet
is
assumed
to
consist
of
a
sequence
of
Hits
(a
?it
is
typically
a
bit
or a
byte).
At
the
end
of
each
wire
is
a
buifer
that
can
hold
a
small
number
of
?its
(typically
two
?its).
A
packet
is
not
stored
entirely
in
one
buffer,
but
instead
is
spread
out
over
a
quantity
of
wires
indicated
by
the
packet
length
(number
of
Hits)
and
by
the
buffer
size.
A
packet
can
be
thought
of
as
a
worm
proceeding
head-?rst
through
the
network.
Behind
the
head,
each
?it
of
the
worm
advances
only
if
there
is
adequate
space
in
the
bu?er
at
the
end
of
the
next
wire
to
hold
the
?it.
When
the
head
moves,
the
buffer
space
it
frees
up
trickles
back
to
the
tail,
allowing
the
entire
worm
to
move.
If
blocked,
a
packet
compresses
(like
an
accordion)
to
a
length acceptable
for the
buffer
size
at
the
appropriate
node.
The
integrity
of
the
packet
is
also
pre
served
(i.e.,
it
cannot
be
cut
in
half
by
another
packet).
In
a
cut—through
network,
the
butfer
size
is
large
enough
that
the
entire
packet
can
accumulate
at
a
single
node.
SUMMARY
OF
THE
INVENTION
The
present
invention
is
comprised
of
a
novel
class
of
switching
networks
comprised
of low-degree,
expansive
logical
clusters
and/or
low-degree,
dispersive
logical
clus
ters,
and
of
methods
described
below
for
routing
messages
on
these
networks
in
an
e?icient
on-line
fashion.
The
meth
ods
for
routing
messages
are
superior
to
previously
known
methods
in
that
they
are
fast,
fault-tolerant,
on-line,
and
non-blocking.
These
attractive
features
are
attained
by
virtue
of
the
expansion
and/or
dispersion
properties
of
the
logical
clusters
of
the
switching
network.
In
accordance
with
the
present
invention,
a
logical
cluster
comprises
a
?rst
set
and
a
second
set
of switches
having
inputs
for
receiving
messages
and
outputs
for
outputting
messages.
The
second
set
of
switches
is
divided
into
one
or
more
disjoint
groups of
switches.
The
?rst
set
of
switches
and
possibly
the
second
set
of
switches
make
local
routing
decisions.
Connectors
are
provided
for
connecting
the
?rst
set
of
switches
to
the
second
set
of
switches.
The
connectors
interconnect
the
switches
such
that
an
output
of
each
of
the
?rst
set
of
switches
is
connected
to
an
input
of
a
switch
in
each
of
the
groups of
the
second
set
of
switches.
The
connectors
interconnect
the
?rst
set
of
switches
and
the
second
set
of
switches
so
that
the
logical
cluster
exhibits
an
expansion
property.
In
particular,
there
exists,
for
every
set
of
k
switches
in
the
?rst
set
of
switches,
at
least
Bk
switches
in
each group
of
the
second
set
of
switches
are
connected
to
the
outputs
of
the
?rst
set
of
k
switches.
[3>l
and
ké
otN,
where
N
equals
the
number
of
input
switches
in
the
?rst
set
of
switches.
Further,
2otB<l.
The
switches
of
the
logical
cluster
may
each
have
two
input
wires
and
two
output
wires.
Preferably,
0t
is
at
least
0.1
and
approximately
equal
to
0.1,
N
is
greater
than
or
equal
to
32
and
otN
is
greater
than
or
equal
to
2.
The
present
invention
also
envisions
a
logical
cluster
that
is
dispersive.
Speci?cally,
for
every
set
of
k
switches
in
the
?rst
set
of
switches,
there
are
at
least
5k
switches
in
each