|
A
comparative analysis between
 The Knockout Switch
The Barcher-Banyan
Switch
The
Knockout Switch
The knockout switch is a fully
connected architecture which
attempts to combine the implementation
simplicity of input queuing
(buffer complexity is linear
in the number of ports) with
the throughput performance of
output queuing (permitted input
load and saturation throughput
both approaching 100%).
The knockout switch architecture
achieves this goal by intentionally
introducing a new source of
packet loss, known as buffer
blocking, in addition to packet
loss mechanisms present in any
switch architecture, namely
buffer overflow and noise-induced
random channel errors. The rate
of loss from buffer blocking
can be readily controlled and
kept low, to reduce significantly
the complexity of a switch based
in principle on the output queuing
idea.
The knockout switch architecture
is explained in the following
set of diagrams.
As in the output queuing model,
each fixed-length cell arriving
at one of the input ports is
placed on a broadcast bus from
which each of the output modules
taps the cells intended for
itself. It is obvious that multicast
and broadcast cells are readily
supported. The output module
acts as a statistical multiplexer,
deferring cells that cannot
be immediately placed onto the
output link because of contention.
Each input to an output module
receives the fixed-length cells
broadcasted on the corresponding
input bus. The job of each packet
filter is simply to pass the
cell to the concentrator if
the cell is destined for that
output, and to mark the cell
as inactive otherwise. Such
a filter can be easily implemented
by a ß-element, only one
input and one output of which
is used. The role of the concentrator
is to identify among its inputs
those cells that are active
and route them to its leftmost
outputs, one cell per output
line. Note that the concentrator
has only L<N outputs. Should
L+1 or more cells arrive simultaneously,
only L of them will be processed
via the concentrator; all others
will be lost. This is the extra
packet loss source in the knockout
switch. By properly choosing
L, the loss rate induced by
the concentrator can be controlled
and maintained at a reasonably
low level. Furthermore, the
value of L required to maintain
a given loss rate is relatively
small, independent of the number
of inputs when the latter is
large, and grows only logarithmically
in the loss rate. For example,
L = 8 is sufficient to maintain
the packet loss rate in the
concentrator at one packet per
million, for large N and full
input load, and it only grows
by one per every order of magnitude
reduced in the loss rate (i.e.
L = 11 is enough for a loss
rate of one packet per billion).
This effect is the key to maintaining
linear complexity of the knockout
switch, as the number of buffers
is proportional to L×N
rather than N².
The concentrator inputs receive
cells, which have already been
passed by the packet filters
and are known to be intended
for the switch output port served
by the concentrator. There are
four (generally, L) stages in
the concentrator shown in the
diagram. Each stage is designed
to operate like an elimination
tournament. Specifically, each
ß-element is programmed
to set itself to the "bar"
state if there is an active
cell on its left input, and
to "cross" otherwise.
Whenever there is only one active
cell at the inputs of a ß-element,
it is allowed to pass downward.
If both cells are active, the
right-hand one is "knocked
out" to the next stage
and contends there. Each stage
produces one "winner"
among the active cells that
enter it, and each subsequent
stage receives one less active
cell than the previous one.
Therefore, when there are k
active cells, they are guaranteed
to come out on the outputs of
the first k stages.
If the packet buffers in the
output module diagram were to
be loaded directly from the
concentrator outputs, then the
leftmost buffers would tend
to fill up faster, and might
even overflow despite the presence
of empty buffer entries on the
right. The shifter prevents
that from happening by spreading
each bulk of cells arriving
at its input continuously to
the right; in other words, if
the last buffer to receive a
packet happened to be m, then
the next k cells arriving at
the shifter's input will be
directed to buffers m+1, ...,
m+k (modulo L). Physically,
the shifter can be implemented
with an L×L Banyan network.
Because of the round-robin
nature of the shifter and the
fact that the buffers are filled
cyclically, they can also be
emptied cyclically. At each
time slot, the output line fetches
a cell from a buffer just right
(cyclically) of the buffer last
fetched from, beginning with
buffer 1. Moreover, if the output
circuitry encounters an empty
buffer, the round-robin policy
of buffer filling guarantees
that all buffers are empty at
that point, and the one just
reached is precisely the next
one to be filled again. The
output pointer can then just
stop there and wait for that
buffer to receive a cell, after
which the circular emptying
of buffers can restart from
that point.
The Knockout Switch full crossbar
requires each output port to
handle up to n input packets
in simultaneous inputs for same
output is unlikely, especially
in large switch instead implement
port to accept (l < n) packets
at the same time hard issue:
what value of l to use!?
Knockout Switch Topology
Knockout switch.
The Knockout switch topology
uses a series of cross point
switches to select "winners"
(cells that transmit immediately)
and "losers" (cells
that have to go wait in the
buffer) from input contenders.
In the Knockout/Concentrator
example shown above, there is
a shared buffer system to hold
the cells in the queue. This
system works very well until
the system is stressed with
too much input, because overflow
from the buffers is simply lost. |
