Transcript PI Meeting Presentation

Extreme Networking
Achieving Nonstop Network Operation
Under Extreme Operating Conditions
FredTurner
Kuhns
Jon
[email protected]
[email protected]
http://www.arl.wustl.edu/arl
Motivation

Internet subject to extreme traffic conditions.
» correlated user behavior; selfish and/or malicious users

Growing reliance on data networks.
» higher expectations for reliability and performance

Design networks for worst-case traffic conditions.
» practice constructive paranoia
» provide carefully regulated reserved bandwidth services
» better queueing mechanisms for traffic isolation
» network mechanisms to protect web sites from DDOS
» plan for continuous upgrading of network infrastructure


extensible routers that can adapt to new threats, as they appear
Technology progress making extreme defenses
practical, without sacrificing performance.
‹#› - Jonathan Turner - July 31, 2001
Extreme Network Services

Lightweight Flow Setup (LFS)
» one-way unicast flow with reserved bandwidth, soft-state
» no complex signaling, wire-speed setup, easy to deploy

Network Access Service (NAS)
» provides controlled access to LFS
» registration/authentication of hosts, users
» resource usage data collection for monitoring, accounting

Reserved Tree Service (RTS)
» configured, semi-private network infrastructure for
information service providers
» reserved bandwidth, separate queues for traffic isolation
» paced upstream forwarding with source-based queues for
isolation and DOS protection
‹#› - Jonathan Turner - July 31, 2001
Can We Afford Per Flow Processing?
If it adds value, absolutely.
 Per Flow State

» at $50/MB (fast SRAM), 200B of flow state = 1 cent
» at $1/MB (DRAM), 10KB of flow state = 1 cent
» if used for 2000 hours (avg. of <5% over 5 years),
costs 1 mcent per hour to cover cost of both

Per Flow Processing
» to enable average of 10 instructions/byte on OC-192,
need 12.5 GIPS
10 i/b enough for header processing
 100 i/b enough for DES encryption

» at $200/GIPS, a 10 Mb/s flow will cost 125 mcents/hour
» by 2010, expect to do 100 inst./byte for 12.5 mc/h
‹#› - Jonathan Turner - July 31, 2001
Resource Reservation in Internet?
Bandwidth reservation can provide dramatically
better performance for some applications.
 Obstacles to resource reservation in Internet.

» distaste for signaling protocols
» perceived complexity of IntServ+RSVP
» requires end-to-end deployment
» little motivation for service providers

How to get resource reservation in Internet?
» keep it simple
focus on top priorities - one-way unicast flows
 avoid complex signaling - leverage hardware routing mechanisms

» make it useful when only partially deployed
» provide motivation for ISPs to deploy it
‹#› - Jonathan Turner - July 31, 2001
Lightweight Flow Setup

Implicit, one-way, unicast flow reservation.
» to setup flow, just send packets - no advance signaling
» specify flow rate(s) in packet header (using IP option)
» flow detected and route selection triggered as needed
» route for flow pinned until flow is released or times out
» prefer routes with ample unreserved bandwidth

Stable rate reservation.
» allocated independently by routers along path
» congested links forward packets as datagrams


reservation request honored as bandwidth released by other flows
Transient rate reservation.
» routers allocate bandwidth fairly among competing flows
» direct feedback of bottleneck bandwidth to senders
‹#› - Jonathan Turner - July 31, 2001
IP Option for LFS
op identifies flow setup
operation
- release state
- reserve stable rate
- reserve transient rate
- status report
code
8

- status request
- ignore
allocated
rate
requested
rate
length
8
op. flags
4
4
rate1
8
rate2
4
Stable rate fraction updated by routers on path.
» may trigger usage-based accounting
Status request flags trigger status report.
 Alloc. rate stored at last hop router for status gen.
 F.P. rates with 4 bit mantissa, 4 bit exponent.

» specify rates from 64 Kb/s to 4 Gb/s , 6% “granularity”
‹#› - Jonathan Turner - July 31, 2001
Implementing LFS - Input Side
Flow
Table
Route
Table
Flow
Proc.
. . .
Flow
Processor
Flow
Table
Access
Table
If flow table entry present, use stored next hop
 If no flow table entry, lookup route & create entry

» store selected next hop in flow table entry

At access router
» check privileges and record usage in access table
» if flow setup not enabled, forward packet as datagram
‹#› - Jonathan Turner - July 31, 2001
Implementing LFS - Output Side
Flow
Table
Route
Table
Flow
Proc.
. . .
Flow
Processor
Flow
Table
Access
Table
If flow table entry present, use it to find queue,
otherwise create an entry & allocate queue.
 If stable rate specified, update entry.

» keep list of unsatisfied reservation requests to process as
bandwidth becomes available
If transient rate, update fair share and pacing
‹#› - rate.
Jonathan Turner - July 31, 2001

Example Application
Edge Router
Web
Site
ISP
Network
Private
LAN
Web site specifies stable rate in outgoing
streaming media packets
 Use feedback to adjust sending rate if necessary.
 Note: no action required by receivers.

‹#› - Jonathan Turner - July 31, 2001
Regulating LFS Usage

Regulate LFS use to ensure availability to users.
» user-specific privileges (limit rates, # reserved flows,...)

Record usage for monitoring, accounting.
» record reservation periods, rates, # bytes delivered
User privilege and usage information stored in
host/user database.
 Regulation & monitoring at network access points.

» for fixed access, just use physical interface
» for roaming access to ISP or corporate network
registration protocol executed when host connects to network
 IP tunnel for data transfers between host and access point
 all data to/from host passes through that point

‹#› - Jonathan Turner - July 31, 2001
Reserved Tree Service
70 Mb/s
downstream
Datagram
Forwarding
Web
Site
100 Mb/s
70 Mb/s
Entry-Exit
Point
upstream
Reserved Tree
10 Mb/s
15 Mb/s
10 Mb/s
 Reserved
tree branches out to locations where users are.
 Downstream packets forwarded on-tree, share reserved bandwidth pipes.
» last hops use datagram forwarding
 Upstream
packets paced and kept in source-based queues.
‹#› - Jonathan Turner - July 31, 2001
Extreme Router Architecture
Scalable
switch fabric
• system mgmt.
• route table cfg.
• setup for non-LFS
flows
Control
Processor
Switch Fabric
Dist. Q. Ctl.
Dist. Q. Ctl. Output
Port
Proc.
Flow
Lookup
. . .
Input Dist. Q. Ctl.
Port
Proc.
Flow/Route
Lookup
Lookup route
or state for
reserved flows
‹#› - Jonathan Turner - July 31, 2001
Flow/Route
Lookup
Distrib. queueing
• traffic isolation
• protect res. flows
Dist. Q. Ctl.
Flow
Lookup
Improving Datagram Service
Per Source
Aggregate
Queues
 Bandwidth
hogging.
»single user can take more than
fair share of link bandwidth
»other users’ packets delayed
 Synchronization
of TCP flows.
»large queues and large delays
sending rate
>6.5 sec.
>500 MB
queue length
1000 flows at avg. rate of 10 Mb/s
10 Kbits per packet, 100 ms RTT
‹#› - Jonathan Turner - July 31, 2001
...
Shared
Output
Queue
 Deficit
round-robin service.
 Discard policy
»longest queue with hysteresis
»discard front
 Provides
traffic isolation.
»each queue gets fair share
»small delays for “nice” flows
 Aggregate
queues based on
source prefix.
»avoid using up queues
»limits bandwidth use from
single subnet
Super-Scalable Packet Scheduling
wheel 1
fast forward bits 00110100
wheel 2
10000010
wheel 3
00101010
output list


Scalability of QoS packet schedulers constrained by need
to maintain sorted list of queues.
Use approximate radix sorting, with compensation - O(1).
» timing wheels with increasing granularity and range
» approximate sorting produces inter-packet timing errors
» observe errors & compensate when next packet scheduled


Fast-forward bits used to skip to empty buckets.
Scheduler puts no limit on number of queues.
‹#› - Jonathan Turner - July 31, 2001

...
...
» ensures reserved flows
...
receive assigned bandwidth
» allocates unreserved
bandwidth fairly to datagram traffic

Periodic broadcast of bandwidth assignments.
...
Distributed queueing
regulates flow of traffic
through fabric.
Switch Fabric
Distributed Queueing
...
» per flow guarantees, without per flow info. broadcast
» switch fabric “repackages” data so each port receives
only relevant information
» update period limited to use <5% of switch bandwidth

adds <100 KB to each input’s buffer space in 1K port router
‹#› - Jonathan Turner - July 31, 2001
Prototype Extreme Router
Control
Processor
Field Programmable Port Ext.
Smart Port Card
Sys.
FPGA
ATM
Switch Core
FPX
FPX
FPX
VCI
Transmisson Interfaces
‹#› - Jonathan Turner - July 31, 2001
TI
TI
Reprogrammable
SPC
Application
Device
VCI OUT
TI
SRAM
4 MB
OPP
IPP
OPP
SDRAM
FPX
FPX
128
MB
Input Port Processor
Field
Programmable
SPC
SPC
SPC
SPC Port Extenders
Embedded
TI Processors
TI
IPP
OPP
IPP
IPP
OPP
Cache
OPP
Pentium
APIC
IPP
IPP
North
Bridge
Switch Fabric
OPP
64
MB
FPX
Network
SPC
Interface
Device
TI
Summary
Growing reliance on data networks creates higher
expectations - reliability, consistent performance.
 Design for worst-case - constructive paranoia.
 Technology progress making extreme defenses
practical, without sacrificing performance.
 Extensible, rapidly reconfigurable routers essential.

» reconfigurable hardware, embedded processors
Project will develop & evaluate technologies for
extreme networking .
 Things that haven’t worked.

» PI’s lumbar region
» otherwise, too early to say
‹#› - Jonathan Turner - July 31, 2001