Transcript presentation source

Agenda (Rev 2)
Week 1: Background (Basic Concepts; Internet History)
Week 2: Routing vs. Switching
Week 3: Architecture and Topology Trends
Week 4: Performance of LANs and Routers -Ladner
Week 5: Congestion vs. Quality of Service
Week 6: Routing part 1 (Intro, RIP, OSPF) -Corbato
Week 7: Routing part 2 (BGP, state of Internet) -Corbato
Week 8: ATM; IP QoS -Minshall
Week 9: Failure Modes and Fault Diagnosis
Week 10: Product evaluation criteria; Wrap-up
1
Week 5: Congestion vs. QoS
Coping with Rush Hour on the Info Highway
• Part 1: The Performing Arts
• Part 2: Congestion Obsession
• Part 3: Better than “Best Effort”
2
But first… it’s time for more
Gray’s Networking Nuggets
• The key to high-performance (and world
peace) is reducing contention for shared
resources.
• Failing that, you need a fair method of
divvying up the spoils.
• Speed, Quality, Efficiency: Pick two
3
Part 1: The Performing Arts
•
•
•
•
Performance implies speed and quality
Achieving the promise of fast hardware...
Need finesse as well as brute force
Balancing speed, quality, and efficiency
4
Performance Metrics
•
•
•
•
Lost or corrupted packets
Effective Throughput
Delay (Latency)
Jitter (Delay variation)
• Power = Throughput/Delay
5
Delay vs. Bandwidth
•
•
•
•
Total delay = prop’n delay + buffering delay
Independent of link speed (bandwidth)
Can trade bandwidth to reduce latency (cache)
As bandwidth increases, RTTs dominate
performance equation...
6
Measuring Throughput
• Packets vs. Bytes per second
• Raw vs. Effective rate (Gross vs. Net)
– with/without factoring retransmissions
• Steady state vs. per transmission or RTT
– Effective Throughput = XferSize/XferTime
– Transfer Time = Delay + (TransferSize/BW)
• If BW >> TSize, ET = TransferSize/Delay
7
Burstiness
• How to characterize? Max rate over what interval?
• Strong law of large numbers… doesn’t hold
– flows may be correlated
– but even uncorrelated flows appear to be fractal!
• MAC Fairness… doesn’t hold
– capture effect and super-tokening
• Longer paths mean less randomness
– “Bunching”
– Higher probability of buffer overrun
– Special case: ACK compression
8
Performance Elements
• Client Machine/Software
End-End
System
–
–
–
–
Computer-to-Closet
Closet-to-BDF
BDF-to-Router
Router-to-Router
Network Core
• Server Machine/Software
9
Policies vs. Performance (Jain)
• Transport
–
–
–
–
–
Retransmission
Out-of-order caching
Acknowledgement
Flow control
Timeout determination
–
–
–
–
–
Use of Virtual circuits vs. Datagrams
Packet queuing and service
Packet discard
routing algorithm
Packet lifetime
–
–
–
–
Retransmission
Out-of-order caching
Acknowledgement
Flow control
• Network
• Data Link
10
Other Performance Factors…
•
•
•
•
•
•
Use of unicast vs. multicast
Policy routing overhead
Topology (esp. speed mismatches)
VLANs
Application efficiency
Desktop O.S. (esp. regarding Jitter)
11
Part 2: Congestion Obsession
• Goal:
– Avoid dropping packets on the floor
• Alternatives:
– Increase capacity
– Decrease load
– Congestion collapse
12
Decreasing Offered Load
• Congestion avoidance (before it happens)
– Admission Control
– Traffic Shaping (Open or Closed Loop)
• Congestion control (after it happens)
– Tell sender to shut-up (or slow down)
– Drop packets
• Different methods for datagrams vs. VCs
13
Not a new problem…
“In the course of designing this current
protocol, we have come to understand that
flow control is more complex than we
imagined. We now believe that flow control
techniques will be one of the active areas of
concern as the network traffic increases.”
– RFC 54 (June 18, 1970), S. Crocker et al.
14
Flow vs. Congestion Control
• Flow control concerns one conversation
– (unless we’re talking with switch vendors)
– Tries to prevent buffer overrun in receiver
• Congestion control deals with network
– Effect of multiple conversations
– Tries to prevent buffer overrun in intermediate
systems
• Contention vs. Congestion
15
Load Shedding
aka Discard Policy
• If you can’t get sender(s) to stop in time…
need to throw some packets on the floor
• Which ones?
– Random
– Oldest first (video)
– Newest first (files)
• Why not just have bigger queues??
– Bigger buffers means more Latency
– Nagle’s discovery: congestion w/infinite queues
16
Queuing Disciplines
(packet scheduling)
• First-In-First-Out (FIFO)
– does not discriminate between traffic sources
• Fair Queuing (FQ)
– explicitly segregates traffic based on flows
– ensures no flow gets more than its share variation:
weighted fair queuing (WFQ)
• Problem: packets not all the same length
– really want bit-by-bit round robin
– not feasible to interleave bits (schedule on pkt basis)
– simulate by determining when packet would finish
17
Taxonomy #1 (Zhang)
• Router-centric vs. Host-centric
• Reservation-based vs. Feedback-based
• Window-based vs. Rate-based
18
Taxonomy #2 (Yang & Reddy)
• Open Loop
– Source action
– Intermediate/Destination action
• Closed Loop
– Implicit feedback
– Explicit feedback
19
Evaluation
• Fairness
• Applicability
– Datagram & VC?
– Cooperating & Non-cooperating end-systems?
• Power (ratio of throughput to delay)
20
Implicit Feedback
• Source notices congestion…
by time out waiting for ACK
• Packets are rarely dropped,
except in congestion
• Lost packet implies congestion
– in a link, or switch, or both
21
Explicit Feedback
• Source quench; choke packets, C-bit
• Per link or per flow?
• End-to-end or hop-by-hop?
22
Congestion Avoidance
• Goal: slow sender(s) before buffer overrun
• Irony: some CA schemes involve dropping
packets intentionally
23
Two Examples
• DECbit or C-bit
–
–
–
–
Switch/router monitors average queue length...
Above threshold, sets bit in header of each pkt
Source resets window based on % of pkts with C-bit
Requires cooperating transport layer
• RED = Random Early Detection
– Switch/router monitors average queue length...
– Above threshold, drop or mark random packets with
probability proportional to connection’s share of
bandwidth
24
TCP Flow/Congestion Control
• Idea
–
–
–
–
assumes best-effort network (FIFO or FQ routers)
each source determines network capacity for itself
uses implicit feedback
ACKs pace transmission (self-clocking)
• Problem: knowing when to time-out, retransmit
– determining the available capacity in the first place
– adjusting to changes in the available capacity
25
TCP Performance vs. Loss
Curtis Villamizar
• Very high performance requires very low loss
• Performance drops off above 1% loss
• TCP can move bits under high loss, but
response may get very slow
• TCP-dominated nets are *NOT* prone to
congestion collapse, but are more efficient
with a smaller number of flows w/large
windows than w/lots of smaller flows
26
Layer Interactions
• Size of discard unit vs. retransmission unit
• TCP end-to-end congestion feedback
vs. ATM hop-by-hop control
• MAC retransmission and LLC flow control
vs. upper-layer congestion control
27
Part 3: Better than “Best Effort”
Integrated Services & Bandwidth-on-Demand
• Hopes: Making little pipes from big pipes
• Promises: Class of Service (CoS)
• Guarantees: Quality of Service (QoS)
– But at what cost?
28
Making little pipes from big ones
-Bandwidth sharing, but how dynamic?
•
•
•
•
•
•
Per contract (e.g. two DS3s)
Per device configuration (e.g. Frac. DS3)
Per s/w configuration (e.g. PVC)
Per VC setup (e.g. SVC)
Per flow, changeable (e.g. ABR)
Per packet, no guarantees (e.g. UBR)
29
Switching Techniques redux
• Circuit (SDM or TDM or FDM)
• Message (Store-and-forward)
• Packet (Frame, FPS, Cell)
– Datagram: connectionless (no state)
– Flow Switching (soft state)
– Virtual Circuit: connection-oriented (hard state)
• Does TCP provide a virtual circuit??
30
Real-Time Applications
• Cases where delayed packets are worthless
• Examples: audio, video
• S. Crocker: “All apps are real-time... There
always exists some interval after which no
one cares about the result.”
31
QoS Application Examples
•
•
•
•
•
Live/scheduled “Broadcast”/Multicast
On Demand: Audio and/or Video
Two people wanting ad hoc desktop conf
N-person collaboration
Real-time/High-bandwidth applications
– Medical imaging
– Virtual Reality
32
QoS Goals
• Keep net-hostile apps from killing baseline
services (e.g. telnet).
• Allow net-hostile apps to reserve what they need.
• Manage resource scarcity.
• Easy for end-users to live with.
• Easy for network managers to live with.
33
QoS: How much is enough?
• No one really knows…
• Clearly it depends…
• So far, limited market for high QoS.
– Guaranteed services are expensive
– Administration issues are non-trivial
– Many will opt for less expensive compromises
34
QoS: There is no Free Lunch
• Deterministic/Guaranteed Behavior
– Reserve BW for worst-case burstiness
– Inefficient
• Probabilistic/Statistical
– Reserve BW for typical burstiness
– Be prepared for some packet loss
• Traffic Shaping and Admission Control
– Essential for either case
• Do we need QoS if BW is adequate?
35
QoS Elements/Strategies
•
•
•
•
•
•
•
Flow Specification
Traffic Shaping
Routing
Resource Reservation
Admission Control
Packet Scheduling/Discard
Feedback
36
Flow Specifications
• Characterize sender’s traffic pattern (Tspec)
– e.g. average and peak rates, packet size
• Characterize requested network behavior (Rspec)
– Delay
– Delay variance
– Packet loss
37
Example Flow Spec (RFC1363)
•
•
•
•
•
•
•
•
•
•
•
Version
Max Transmission Unit
Token Bucket Rate
Token Bucket Size
Max Transmission Rate
Min Delay Noticed
Max Delay Variation
Loss Sensitivity
Burst loss sensitivity
Loss Interval
Quality of Guarantee
38
Traffic Shaping
• Goal: sender moderates burstiness
• Deterministic vs. Statistical
• Common Methods
– Leaky Bucket (Turner)
– Token Bucket --allow some burstiness
• Enforcement (Policing)
– Intermediate systems monitor
– Excessive packets may be discarded
39
ATM Service Classes
• Constant Bit Rate (CBR)
– Reserve BW for Peak Cell Rate (PCR)
• Variable Bit Rate (VBR)
– Reserve for Sustainable Cell Rate (SCR)
• Available Bit Rate (ABR)
– Reserve for Min Cell Rate (MCR)
– Get more if RM cells say OK
• Unspecified Bit Rate (UBR)
– aka “Best Effort” (no reservation)
40
RSVP Service Classes
• Guaranteed
• Predictive Delay
– Net reports typical delay to application
– Application adapts to reported delay
• Controlled Delay
– Application requests bounds on delay
• Best Effort
– “Ask me no questions & I’ll tell you no lies”
41
RSVP Design Goals
•
•
•
•
•
•
•
Allow heterogeneous receivers
Adapt to changing mcast membership
Net efficiency: exploit diffs in apps needs
Allow receivers to switch channels
Adapt to routing changes
Keep overhead growth sublinear
Modular design
42
RSVP Design Principles
•
•
•
•
•
•
Receiver-initiated reservations
Separating reservation from pkt filtering
Provide for different reservation styles
Use soft-state in the network
Protocol overhead control
Modularity
43
Alternative Transport: RTP
• UDP + new header
• RTP header:
– Sequence number
– timestamp
– Synchronization Src packet ID
• Followed by add’l header, e.g. H.261
• Companion control protocol (RTCP)
44
ATM “Flow” Control
• Huge debate in ATM Forum!
• Two choices:
– Rate based
– Credit based
• Rate-based won
– Periodic Resource Manager (RM) cells
allow sender to increase rate if no congestion
– Used for Available Bit Rate (ABR) service
45
Peterson&Davie Comparison of
RSVP & ATM
•
•
•
•
•
Receiver initiates reservations
Soft state (refresh/timeout)
Separate from route setup
QoS can change dynamically
Receiver heterogeneity
•
•
•
•
•
Sender initiates reservations
Hard state (explicit delete)
Concurrent w/route setup
QoS static for life of connection
Uniform QoS to all receivers
46
Open QoS Issues
•
•
•
•
•
•
•
•
•
•
On-campus vs. off-campus: costs, mechanisms, capacity
Will RSVP scale?
Security: Authorization, Private conferences
What about net-hostile apps that don’t request high QoS?
Migration/interaction: tunnels, DVMRP, PIM, 802.1p
Privileges or quotas or recharge?
By user or by device?
Relationship to campus authorization & billing DBMS
How will NOC know when QoS is working?
Is there ANY hope for administering QoS?
47
QoS Alternatives
• Over-provision best-effort infrastructure
– Locally, may be cheaper than managing QoS!
• CoS: multiple queues, no guarantees
• Multiple best-effort services
– Varying over-capacity
– Varying price
• Combinations
48
Questions?
• Next two weeks: routing
• 5/22 More on QoS, ATM
49