A
comparative analysis between
two types of ATM Switches:
The Knockout Switch
The Barcher-Banyan
Switch
The
Banyan Switch
The Banyan switch is a multistage
self-routing architecture which
uses fewer β-elements
than the minimum number required
for a rearrangeably nonblocking
design. More specifically, an
N×N Banyan switch uses
(N/2) log N elements. Consequently,
the switch cannot be nonblocking;
input-to-output permutations
can be constructed that cannot
be concurrently routed with
the switch. Therefore, smoothing
buffers must lie inside the
switch to achieve a reasonably
low packet loss rate.
The structure of an 8×8
Banyan switch is depicted in
the diagram.
We see that the β-elements
are arranged in three columns
of four elements each, in a
pattern that resembles a grid
of butterflies. The inputs to
the switch are the inputs to
the elements in the first column,
and the outputs of the last
column are the outputs from
the switch. In each β-element,
one output is connected to the
input of the element just horizontally
on its right, and the other
goes to an element whose line
number, represented in binary,
differs in precisely the j's
bit, where j is the column number
of the element (counting from
0). For example, the outputs
of element (2,1) (bold in the
diagram) are connected to the
inputs of elements (2,2) (horizontal
connection) and (0,2) (diagonal
connection), as the numbers
2 and 0 differ in bit #1 of
their binary representation.
This simple rule also tells
how to construct a path from
any input to any output: in
each column j, an appropriate
β-element should be
set in the "bar" state
if the j's bits of the input
and the output numbers equal,
and in the "cross"
state if those bits differ.
The path shown in bold in the
diagram illustrates how to connect
input 7 to output 0. Since all
the bits in the binary representations
of the input and the output
differ, all elements along the
path are set to "cross".
Note that every such path is
unique. Obviously, several paths
cannot be routed concurrently
unless they happen to require
the same states of the β-elements.
Thus, in our case, once input
7 is connected to output 0,
input 6 cannot be connected
to outputs 2, 4, and 6, because
any of these connections would
require the element in the first
column to be set to "bar".
Several remedies can be employed
to attempt resolving this type
of routing conflict: (1) Provide
buffers within the β-elements,
so that cells that cannot be
immediately delivered are stored
and their routing deferred according
to some contention resolution
policy; (2) Run the internal
links at a rate that is a multiple
of the cell arrival rate, sequentially
establishing several paths within
the duration of one cell. To
provide an insight to how good
these techniques can be in reducing
packet loss rate, it suffices
to quote the results of a computer
simulation for a large (1024×1024)
Banyan switch run at full input
load. With the internal links
running at twice the cell rate
(hence capable of establishing
two subsequent paths within
one time slot) and a buffer
size of 5 cells in each β-element,
as many as 92% of
the input cells were delivered,
compared to about 25%
for a simple unbuffered switch,
and about 75% for
a double-rate unbuffered switch.
Still, to achieve reasonable
packet loss rates (such as one
packet per million), the input
load would have to be reduced
considerably.
Banyan Switch Topology
Banyan 3 stage switch.
Banyan 3 stage switch.
Banyan switches are based
on cross bar switches that have
been built into a binary tree
topology. There are many different
configurations for Banyan switches.
Two possible configurations
for 3 stage Banyan switches
are shown above. Banyan switches
are extremely efficient, but
have the unfortunate problem
of BLOCKING. This occurs when
two inputs at a switching node
are in contention for the same
output and one of the inputs
is forced to wait. This situation
can be avoided if the inputs
are PRESORTED before entering
the Banyan Tree Structure. This
topology is called the Batcher
Banyan switching topology and
is the next topology on our
list.
Batcher Banyan Switch
Topology
Batcher Banyan Switch
The Batcher sorting procedure
involves 3 levels of sorting
to produce NONBLOCKING input
for a 3 stage Banyan network.
The price for removing the wait
states in the Banyan network
is more nodes (more cost) and
a longer travel time through
the greater number of nodes.
These switches are however much
faster than simple Banyan switches,
and of course, much more expensive.
The Knockout Switch
