Router Architecture Overview
two key router functions:
run routing algorithms/protocol (e.g. RIP, OSPF, BGP)
forwarding datagrams from incoming to outgoing link
forwarding tables computed, routing
pushed to input ports routing, management
processor
control plane (software)
forwarding data
plane (hardware)
high-seed
switching
fabric
router input ports router output ports
Router Architecture Overview
Input Port Functions
lookup,
link forwarding
line layer switch
termination protocol fabric
(receive)
queueing
physical layer:
bit-level reception
data link layer: decentralized switching:
e.g., Ethernet • given datagram dest., lookup output port
using forwarding table in input port
memory (“match plus action”)
• goal: complete input port processing at
‘line speed’
• queuing: if datagrams arrive faster than
forwarding rate into switch fabric
Router Architecture Overview
Switching Fabrics
transfer packet from input buffer to
appropriate output buffer
switching rate: rate at which packets can be
transfered from inputs to outputs
often measured as multiple of input/output line rate
N inputs: switching rate N times line rate desirable
three types of switching fabrics
memory
memory bus crossbar
Router Architecture Overview
Switching via Memory: First Generation Routers
• traditional computers with switching under direct control of CPU
• packet copied to system’s memory
• speed limited by memory bandwidth (2 bus crossings per
datagram)
input output
port memory port
(e.g., (e.g.,
Ethernet) Ethernet)
system bus
Router Architecture Overview
Switching via a bus
datagram from input port memory
to output port memory via a
shared bus
bus contention: switching speed
limited by bus bandwidth
bus
32 Gbps bus: sufficient speed for
access and enterprise routers
Router Architecture Overview
Switching via interconnection network
overcome bus bandwidth limitations
banyan networks, crossbar, other
interconnection nets initially
developed to connect processors in
multiprocessor
advanced design: fragmenting
datagram into fixed length cells, switch crossbar
cells through the fabric.
Cisco 12000: switches 60 Gbps
through the interconnection network
Router Architecture Overview
Output Ports
datagram
switch buffer link
fabric layer line
protocol termination
(send)
queueing
buffering required when datagrams arrive from fabric
faster than the transmission rate
scheduling discipline chooses among queued datagrams
for transmission
Router Architecture Overview
Output Port Queuing
switch
switch
fabric
fabric
at t, packets more one packet time later
from input to output
buffering when arrival rate via switch exceeds output line speed
queueing (delay) and loss due to output port buffer overflow!
Router Architecture Overview
How much buffering?
• RFC 3439 rule of thumb: average buffering equal
to “typical” RTT (say 250 msec) times link capacity
C
– e.g., C = 10 Gpbs link: 2.5 Gbit buffer
• recent recommendation: with N flows, buffering
equal to
RTT . C
N
Router Architecture Overview
Input Port Queuing
fabric slower than input ports combined -> queueing may
occur at input queues
queueing delay and loss due to input buffer
overflow!
Head-of-the-Line (HOL) blocking: queued datagram at front
of queue prevents others in queue from moving forward
switch switch
fabric fabric
output port contention: one packet time
only one red datagram can later: green
be transferred. packet
lower red packet is blocked experiences HOL