Transcript Slides: Scalable Network Architectures for Providing Per

Scalable Network Architectures
for Providing
Per-flow Service Guarantees
Jasleen Kaur
Department of Computer Science
University of North Carolina at Chapel Hill
1
The trend: richer network services
Basic Internet service providing is commoditized
 Last decade: network connectivity
 Next decade: value-added services
Value-added services
Quality of Service, Virtual Private Networks,
Intrusion detection, Transcoding services
Focus: providing QoS guarantees in networks
2
The opportunity: QoS
New applications with stringent timeliness requirements
 Live and on-demand video streaming, real-time stock quote
 VPNs for mission-critical enterprise applications
Requirements
 Delay guarantees: upper bound on network delay
 Throughput guarantees: sustained throughput even at short
time-scales
 Fairness guarantees: throughput in proportion to reserved rate
Need to provide per-flow network service guarantees
3
The challenge: growth
Link capacities are increasing rapidly (double every year)
 Less time available to routers for per-packet processing
Capacity
Per-packet Time
100 Mbps Ethernet 38 s
2.45 Gbps (OC48)
1.5 s
9.6 Gbps (OC192)
0.38 s
Internet traffic demands are increasing at similar rate
Requirements
 Minimize # of instructions, memory accesses, amount of memory
 Utilize resources efficiently
Networks need to be scalable and efficient
4
Requirements summary
A network architecture should:
1. Provide per-flow guarantees on delay, throughput, fairness
2. Scale to high capacity links
3. Use efficiently available resources
Design network architectures that meet these requirements
5
Outline
State of the art
Research directions and methodology
Core-stateless Guaranteed Services networks
Scalability evaluation
Summary
Current research directions
6
Network model
Routers
Link
Scheduler
Input
links
Outgoing
link
Packet
Queue
7
State of the art
FIFO networks
+ Are simple and scalable
- Do not provide service guarantees in presence of bursty traffic
Integrated Services (IntServ) networks [Shenker95]
+ Provide per-flow guarantees: use sophisticated scheduling algorithms
- Do not scale: require per-flow state and packet classification
Differentiated Services (DiffServ) networks [Nichols97]
+ Are scalable: only per-aggregate processing in core routers
- Do not provide per-flow guarantees within an aggregate
Architecture Per-flow Guarantees Scalability Efficiency
FIFO
X
X
DiffServ
X
X
IntServ
X
X
8
Two research directions
1.
Can scalable mechanisms be added to enable FIFO networks to
provide per-flow service guarantees?
Performance of FIFO networks with CBR traffic-shaping [NOSSDAV-99]
 Analytical model: heavy-tails at high utilization in large-scale networks
Simulations: heavy-tails even at moderate utilization and small networks
2. Can complexity of IntServ mechanisms be eliminated, while
retaining per-flow guarantees?
Network architectures that provide per-flow service guarantees
without maintaining or using per-flow state in core routers
9
Core-stateless networks
Core routers do not maintain per-flow state
 Scalable: no state maintenance or classification complexity
Edge routers maintain state
 Scalable: small number of flows and low-speed links
Edge Routers
Core Routers
10
Core-stateless schemes
Type of service guarantees
in core-stateless schemes
Statistical
CSFQ [Stoica98], RFQ [Cao00],
CHOKe [Pan00], TUF [Clerget01]
•Approximate fairness over long time-scales
•No guarantees for short-lived flows
Deterministic
CJVC [Stoica99]
•End-to-end delay guarantees
•Non work-conserving
Work-conserving core-stateless networks that provide
deterministic guarantees similar to core-stateful networks
11
Research methodology
Careful blend of theory and practice
Theory
1. Understand end-to-end guarantees in core-stateful networks
First tight lower bound on end-to-end fairness
2. Design core-stateless networks to provide similar guarantees
Exactly same delay guarantees
Throughput guarantees within an additive constant
Fairness guarantees even better
Practice
Design, implement and evaluate
 Scalability of edge and core routers
 Feasibility of deploying the core-stateless network
12
Delay guarantees are fundamental
Theorem 1: (throughput  delay)
A network that provides throughput guarantees also provides
delay guarantees
Theorem 2: (fairness  throughput)
A network that provides fairness guarantees also provides
throughput guarantees
A network that does not provide delay guarantees,
can not provide throughput or fairness guarantees
13
Guaranteed Rate (GR) scheduling algorithms
GR Algorithms
 Class of algorithms that provide delay guarantees to flows
Basic operation
 Reserve a rate for each flow
 Associate with packet k, a Guaranteed Rate Clock GRC(k) value

GRC(k): Transmission deadline for packet based on reserved rate
 Scheduling algorithm belongs to class GR if it guarantees
transmission of packet k by GRC(k) + 
Examples:
 Virtual Clock, Delay-EDD, SCFQ, SFQ, WF2Q+, …
14
Virtual Clock: need for per-flow state
Assign a transmission deadline (VC) to packet k:
EAT(k) = max{ VC(k-1), AT(k) }
VC(k) = EAT(k) + lk/r
Transmit packets in increasing order of their VC values
If flow r  C, packet gets transmitted by VC(k) + lmax/C
End-to-end delay bound = f(upper bound on VC(k) at last node)
Delay bound = f(upper bound on transmission deadline)
Transmission deadline of packet k = f(state of packet k-1)
 Need to maintain state of previous packet!
How to compute deadlines without maintaining state?
15
Key insight
Upper bounds on deadline at any node
= f (deadline of same packet at previous node)
.
..
= f (deadline of same packet at first node)
Ingress router does maintain per-flow state
 can compute upper bounds on deadlines for all nodes
Using upper bounds on deadlines results in same network delay guarantee
1
Ingress
router
2
Core routers
16
Core-stateless Guaranteed Rate networks
Ingress router maintains per-flow state
 Computes and encodes deadlines for all nodes
Core routers do not maintain per-flow state
 Use deadline encoded by ingress router
Computes deadlines
Sorts and transmits packets
Sorts and transmits packet
1
Ingress
router
2
Core routers
17
CSGR: properties
Theorem:
End-to-end delay guarantee of a CSGR network is same as
corresponding GR network
Salient features:
 Methodology for deriving core-stateless version of any GR network
 Leads to design of work-conserving core-stateless networks
 Core-stateless Delay-EDD: decouples delay and rate guarantees
 Same bound on end-to-end delay as core-stateful version
 Simple computations
Caveat:
 Do not preserve short time-scale throughput or fairness guarantees
Flows that use idle capacity to send at more than their reserved
rate accumulate “debit” and may be penalized in the future !
18
CSGS networks: properties
CSGR [Infocom-01]: Delay
 Provide exactly same delay guarantees as core-stateful networks
CSGT [Infocom-03]: Throughput
 Provide throughput guarantees within an additive constant of corestateful networks
 First work-conserving core-stateless network that provides
deterministic throughput guarantees
CSGF [IWQoS-03]: Fairness
 Provide better fairness guarantees than core-stateful networks
 First work-conserving core-stateless network that provides
deterministic fairness guarantees
19
Research methodology
Careful blend of theory and practice
Theory
1. Understand end-to-end guarantees in core-stateful networks
First tight lower bound on end-to-end fairness
2. Design core-stateless networks to provide similar guarantees
Exactly same delay guarantees
Throughput guarantees within an additive constant
Fairness guarantees even better
Practice
Design, implement and evaluate
 Scalability of edge and core routers
 Feasibility of deploying the core-stateless network
20
Scalability evaluation of network architectures
Constraints in high-speed routers
 Time: Per-packet processing time budget is limited
 Space: Total fast-path memory is limited
Key question:
What are the performance limits of routers in different network
architectures?
Specific values depend on router platform !
Our Approach:
Implement a CSGS, FIFO, and IntServ router on common
platform and measure relative performance
21
Router throughput in different architectures
1.2
1
0.8
Worst
Best
0.6
0.4
0.2
0
FIFO/IP
CSGS/src
CSGS/IP
IntServ/src
Source routing + core-stateless architecture  A network architecture
that provides end-to-end per-flow service guarantees
with scalability close to conventional IP routers
22
Summary
Goal: design network architectures that provide per-flow
guarantees, are scalable, and efficient
FIFO inadequate if premium traffic occupies a large fraction
of capacity [NOSSDAV-99]
Core-stateless networks: theory
 First end-to-end fairness analysis of fair queuing networks
[RTSS-02]
 Design of core-stateless networks
Exactly same delay guarantees [Infocom-01]
Throughput guarantees within a constant [Infocom-03]
Fairness guarantees even better [IWQoS-03]
Core-stateless networks: practice
 Routers in core-stateless networks, with source routing,
have performance similar to conventional IP routers
23
Some challenges and open questions
CSGS networks still require modifications to all routers
Is it possible to provide end-to-end service guarantees
using mechanisms instantiated only at the edges of a
network?
[Zhang-Sigcomm02]: Throughput of many TCP flows is limited
due to default parameter settings !
How suitable for today’s Internet are traditional end-host
mechanisms for flow control?
Does congestion occur at all? If so, where does it occur?
At end-hosts? At the edge? At the core?
24
Variability in TCP round-trip times
Max, median, and min RTTs may differ by several orders of
magnitude within individual TCP connections !!
25
Current research directions
Detecting congestion
 Where does congestion occur?
 What mechanisms help detect it quickly and non-intrusively?
 How to design a large-scale, distributed congestionmonitoring infrastructure?
Designing edge-based services
 Efficacy of overlay-based alternate path routing
 Availability of ‘‘parallel’’ bandwidth
Designing end-host flow control mechanisms
 Does the ‘‘single-bottleneck’’ assumption hold?
 Does traditional flow control work well in high bandwidth
networks?
26
More details being made available at…
URL: http://www.cs.unc.edu/~jasleen/
Email: [email protected]
27