Transcript A 50-Gb/s IP Router

A 50-Gb/s IP Router
참고논문: Craig Partridge et al.
[ IEEE/ACM ToN, June 1998 ]
MGR --- multi-gigabit router

Performance



32 MPPS forwarding rates (1000b/packet)
50 Gb/s of full-duplex backplane capacity
rate and bandwidth


2~10 times faster than high-performance
routers available at that time
Why and How?
Outline



Router Architecture
Major Innovations
Architectures






Line Card Design
Forwarding Engines
Switched BUS
Network Processor
Routing/Forwarding Tables
Summary
Why MGR is needed

Several multi-gigabit networking
technologies have emerged:


Thus requires


ATM/SONET, Optical WDM, Fiber Channel…
Multi-gigabit IP routers
Multi-Gigabit Router is especially useful
for integrating ATM into the Internet
Router Architecture
Routing Engines
Packets In
Packet Forwarding
Engines
Packets Out
Router Architecture

Any problems if we design MGR ?
Routing Engines
Bus speed?
Packets In
bottleneck?
Packet Forwarding
Engines
Packets Out
MGR architecture
Innovations
Five major innovations
I.
each forwarding engine has a complete set of
routing tables (100KB for 50K routes)

II.
mis-hit causes 1000 times slow
crossbar switched backplane

parallelism of a switch
III. separate forwarding engines and line cards
instead of one board


not sure one board is enough to fit two functions
flexibility
Innovations
Five major innovations
IV. placing forwarding engines on separate
cards


V.
link-layers/abstract link-layer header format
share forwarding engines/robust
QoS processing in the router



line-speed QoS
classify packets
scheduling in outbound line card
MGR Outline
What’s Following





Line Card Design
Forwarding Engines
Crossbar Switch BUS
Network Processor
Managing Routing and Forwarding
Tables
Line Card Design

One Line Card (total cards: 15)


16 interfaces (total < 2.5Gb/s)
Disjoint inbound/outbound Processing


Inbound Packet Processing
Outbound Packet Processing
Line Card Design --- inbound

Inbound Packet Processing

Simple, 64-Byte pages



1st page (Header) to forwarding engine
Updated page replaces 1st page
Two situations


Multicasts
ATM
Line Card Design --- outbound

Outbound Packet Processing


Assemble pages to packet
Pass to line card’s QoS processor


VLIW programmable state machine
Event-driven




Arrival of packet event
Transmission interface’s ready event
Allocation of bandwidth changes event
Timer event
Forwarding Engines - processor

Alpha 21164 Processor


64-bit 32-Register Super-scalar RISC
First level cache (Instruction & Data) (8kB)



On-chip secondary cache (96kB)


2048 Instructions
Enough to do key routing function
12,000 entry cache (64bit), hit-rate >=95%
Tertiary cache (up to 16M)

Two banks, complete forwarding table
Forwarding Engines - hardware


Read from FIFO
Writes to inbound/outbound line card.
Forwarding Engines - software

Performance



85 instructions in common case
No less than 42 cycles
Peak forwarding speed of 9.8 MPPS per
forwarding engines
Forwarding Engines - software
Three stages for fast path through




Check header/length/option/load route

No checksum here ( Why? )
May lookup the route if not match, may update
TTL/checksum
Write back the TTL/checksum/routing
information


Link-layer information
Flow classifier
21% increasing cycles to pay to check for a rare error
Forwarding Engines - software
Special cases






Header whose destination misses in the route cache
Headers with errors
Header with IP options
Datagrams that must be fragmented
Multicast datagrams
Goal



Frequent and easy-handled packets are done in the Alpha
Otherwise, are pushed of to network processor
Forwarding Engines - software

Instruction Mix
Forwarding Engines – Abstract
link layer header


Summary link-layer information for forwarding engine and line
cards
Advantages: keep forwarding engine and its code simple.
Switched BUS

Switched BUS / Shared BUS




Point-to-Point switch, crossbar
Point-to-Multicast ???
Input-queued switch
Allocation Algorithm

Maximize throughput at the expense of
predictable latency
Switched BUS
Allocator

The heart of the high-speed switch in MGR
Network Processor

Routing Processing/Complicated
processing on packet


Commercial PC motherboard with PCI
interface
1.1 NetBSD release of UNIX



Public source code
Customize IP code
More free software on UNIX
Routing/Forwarding Tables

Routing tables


Forwarding Tables


Network processor
Forwarding engines
Routing Tables  Forwarding Tables



Small forwarding tables for forwarding engine
Two banks of memory in Forwarding Engines
Decouple two operations


Processing routing updates
Actual updating of forwarding tables
Summary

More than fast enough


Keep up with the latest transmission
technologies at that time
Two important contributions

It is feasible for MGR


Examine every datagram header
Eliminate doubts

router technology could not keep up with the
high-speed networks
Questions?
Thank You