Transcript document

Case Study: The Abacus Switch
CS 4594
Goals and Considerations
•
•
•
•
•
•
•
Handles cell relay (fixed-size packets)
Can be modified to handle variable-sized packets.
Implements multicasting.
Scalable from few tens to few thousands of input ports.
Built from integrated circuits (chips).
Uses channel grouping to reduce hardware complexity.
Analyzed for throughput, average cell delay, and cell loss
ratio.
History
• Development lead by H J Chao
• Described by a series of papers, starting in
1991.
• See copy of 1997 paper.
• Called Abacus because of appearance of the
integrated circuit (chip) that is used the
construct it.
Components
• Input port controller (IPC) for each input
• Multicast Grouping Network (MGN) is first
stage of switch fabric.
• Multicast Translation Tables (MMT)
• Small Switch Modules (SSM) at second
stage of switch fabric.
• Output port controller (OPC) for each
output.
Overall Architecture (see fig 1)
IPC
IPC
.
.
.
.
.
.
IPC
Multicast
Group
Network
MTT
MTT
MTT
MTT
SSM
MTT
MTT
MTT
MTT
SSM
OPC
OPC
OPC
OPC
MTT
MTT
MTT
MTT
SSM
OPC
OPC
K groups of LxM
N
Feedback loop
N
Overall Architecture
•
•
•
•
Input port controller (IPC) for each input
Output port controller (OPC) for each output.
Output ports are divided into K groups of M.
Multicast Grouping Network (MGN) reads cells
from IPCs and send cells to the correct output
groups.
• Separate small switch modules (SSM) for each
group of outputs to send cells to correct OPC.
Input Port Controller
•
The IPC
– Reads cells from SONET/ATM line into its input
buffer.
– Takes cells from the head of its input buffer and sends
these cells to the switching fabric, tagging, grouping,
and replicating the cells.
Location of IPCs
IPC
IPC
.
.
.
.
.
.
IPC
N
Multicast
Group
Network
MTT
MTT
MTT
MTT
SSM
MTT
MTT
MTT
MTT
SSM
OPC
OPC
OPC
OPC
MTT
MTT
MTT
MTT
SSM
OPC
OPC
K groups of LxM
N
Input Controller
From SONET
Cell
Extraction
Input Buffer(FIFO)
Routing
Table
One
Cell
buffer
K lines
Feedback from fabric
Multicast
Contention
Resolution
Unit
Bus
P/S
to MGN
Input Port Controller Process
1. If a new cell is to be sent, it examines the cell at the head of the
line (HOL) of input buffer and matches VPI/VCI against routing
table to determine the set of output port groups (via MP) and the
multicast call (via BCN). The cell is tagged with this information
and removed from the input buffer.
2. The cell is temporarily stored in a one-cell holding buffer. It is held
here in case it needs to be transmitted again.
3. The cell is sent to the distribution network (MGN).
4. The IPC then reads feedback information from MGN to see if cell
needs to be sent again. If so, it loops back to step 3. If not, it goes
back to step 1 for a new cell.
Multicasting Group Network
• The MGN distributes the cells from the
IPCs to the output groups.
• It consists of K routing modules (RM), one
for each of the K output groups.
Location in Overall Architecture
IPC
IPC
.
.
.
.
.
.
IPC
Multicast
Group
Network
MTT
MTT
MTT
MTT
SSM
MTT
MTT
MTT
MTT
SSM
OPC
OPC
OPC
OPC
MTT
MTT
MTT
MTT
SSM
OPC
OPC
K groups of LxM
N
Feedback loop
N
Multicasting Group Network
N
Routing
Module
Routing
Module
LxM
LxM
...
Routing
Module
LxM
Routing Module
• Each routing module (RM) listens to all inputs and
sends cells to one group of outputs.
• Each RM has inputs from all IPCs.
• Each RM has LxM outputs to a particular group of
M outputs. L is called the group expansion ratio.
Multicasting Group Network
N
Routing
Module
Routing
Module
LxM
LxM
...
Routing
Module
LxM
Routing Module
N
Lines
from
N inputs
AB
AB
AB
SWE
SWE
SWE
SWE
SWE
SWE
SWE
SWE
SWE
LxM lines to output group
Routing Module
• A routing module (RM) consists of a N by LxM crossbar
2D array of switch elements (SWE)
• At the top, a set of address broadcasters (AB) generates
empty cells with the correct destination address, but low
priority.
• The flow through the RM starts at the top at the set of AB
and goes down or to the right. At the bottom cells go to
the output groups.
• Each switch element has two states “across” (straight
through) or “toggle” (turn). It normally sends old cells
down toward their destination and new cells down the line.
Switch Elements
• “Across” is the default state, it lets a downward cell
continue toward its destination and sends an entering cell
over to the right. It happens when the destination of the
cell to the north (old cell) does not match the destination of
the cell from the west (left) or the priority of the cell on the
west (new cell) is less than the priority of the cell from the
north.
• “Toggled” happens when the destinations match and the
cell on the left has higher priority. It bumps the downward
(old) cell over to the right and lets the western (new) cell
start heading down to its destination.
Switch Element
across state
toggle state
Switch Elements
• Switch elements are small integrated
circuits
• Implemented in CMOS as the ARC chip
– 32 x 32 per IC
– 81,000 transistors
– 240 MHz
Tables
• Tables contain routing information (see
figure 6.18)
• They are located in the
– IPC to map the VPI/VCI to the destination and
to an ID (BCN) that can be used to uniquely
identify the virtual circuit in the switch
– MMT to map the BCN to the new VPI/VCI and
set up last cell replications
Performance
• Throughput
• Average Delay
• Cell loss
Performance depends on
• The type of buffering (input vs. output)
• The number of inputs contending for
outputs
• The load
• The burstiness of the traffic
• The amount of grouping (M)
• The amount of parallelism (group expansion
ratio L)
Maximum Throughput
• Maximum throughput = utilization at the output
port
• For fixed expansion ratio, as the group size
increases, throughput starts at .583 and gradually
increases to one and burstiness gradually becomes
less important (figure 7.7)
• For fixed group size, as the expansion ratio
increases, throughput starts at .583 and gradually
increases to one and burstiness gradually becomes
less important (figures 7.8, 7.9)
Average Delay
• There are two types of delay
– Input-buffered delay
– Output-buffered delay
• Input-buffered delay is small under a light load and can go
to infinity as a switch saturates (figure 7.10).
• Output-buffered delay is larger than input-buffered delay
for small loads (figure 7.10).
• Unicast traffic does not do as well as multicast traffic
(figure 7.11).
Cell Loss
• Cell loss occurs at the input buffers and output buffers, but not in the
fabric (MGN)
• See figure 7.12 for input buffer cell loss probability as a function of
burstiness and input buffer size (load .9, N =256, M =16)
• See figure 7.13 for output buffer cell loss probability as a function of
burstiness and output buffer size (load .9, N =256, M =16)
• For 10-6 cell loss probability, for burst length of 15 input buffer should
be close to 50 cells and the output buffer size should be over 300.
• For 10-10 cell loss probability, for burst length of 15, input buffer
should be 100 cells (extrapolating).
Extensions to Abacus
• Variable packet
• Scaling up by multistaging the MGN
• Resequencing cells at the output