Network Congestion

Network Congestion

Gabriel Nell UC Berkeley

Outline  Background:

what is congestion?  Congestion control – End-to-end – Router-based

 Economic

insights  Overview of TCP-friendly congestion control mechanisms

Congestion  The

state of sustained network overload  Congestion collapse – Traffic dominated by overhead such as packet

retransmissions  Current

internet

– Dominated by best-effort traffic – TCP for guaranteed delivery; Congestion-aware – UDP for streaming applications; Congestion-unaware

Controlling Congestion  End-hosts – Advantages: cheap, scalable – Disadvantage: requires cooperation

 Routers – Advantages: can be more aggressive, has a

complete picture of network traffic – Disadvantages: expensive, algorithms difficult to implement in hardware

TCP Congestion Control  Implemented

at end hosts  Relies on feedback – Implicit: packet drops indicate congestion – Explicit: ECN flags in header

 Congestion

controlled by changing window size: additive increase, multiplicative decrease (AIMD)  Problem: delays in adapting to network conditions may cause oscillations

Router-Based Control  Scheduling – Determines service order – Should be easy to implement, provide fairness

and protection, and perform well

 Scheduling

algorithms

– FIFO (first in, first out) – Round-robin / weighted round-robin – Weighted fair queuing

Router-Based Control  Buffer

Management

– Absorbs bursts – Shared/per-flow – Introduce delay

 Queue

Management

– Manage queue length, decide what packets to drop – RED effective, but difficult to parameterize for variable

conditions

Economic Insights  Tragedy

of the Commons

– Network resources a public good – Negative externality

 Solution:

Internalize costs

– Congestion pricing: cover fixed costs, charge

extra under congestion conditions – Charge by willingness to pay

Economic Insights  New

problem - customers prefer:

– Flat rates – Constant performance, even if variable

performance is better on average

TCP-friendly Congestion Control  TCP-friendly:

long-term throughput does not exceed that of TCP under the same conditions  Motivation: want to stream data such as audio and video without degrading overall network performance  For convenience, consider long-lasting streams

Congestion Control Schemes  Window-based

vs. Rate-based  Unicast vs. Multicast  End-to-end vs. Router-supported

Single-rate Vs. Multi-rate  Meaningful

when considering multicast  Single-rate sends data to each client at the same rate  Multirate sends data to each client at whatever rate is best for that client

Single-rate Protocols

Rate-based Approaches  RAP

– Rate Adaptation Protocol

– Simple AIMD behavior

 LDA+

– Loss-Delay Based Adaption Algorithm

– Dynamic AIMD based on RTCP feedback

 TFRC

– TCP-Friendly Rate Control Protocol

– Adjusts sending rate based on complex TCP equation

 TEAR

– TCP Emulation at Receivers

– Uses a congestion window to determine rate, but

averages over larger timescales

Window-based Approaches  RLA

– Random Listening Algorithm

– Tracks number n of congested receivers, window is

decreased if a random number is ≤ 1/n

 MTCP

– Multicast TCP

– Arrange receivers in a tree, children report congestion

to parents. – Root receives aggregate info, sends only as much data as smallest window  NCA

– Nominee-Based Congestion Avoidance

– Selects bottleneck as representative receiver, uses TCP-

style congestion control algorithm

Multi-rate Protocols

Rate-based Approaches  RLC

– Receiver-Driven Layered Congestion Control – Bandwidth consumed by each layer increases

exponentially – Subscription to additional layers comes at particular times, which also increase exponentially; however congestion causes immediate layer drops

Rate-based Approaches  FLID-DL

– Fair Layered Increase/Decrease with Dynamic Layering – Encodes data with digital fountain – Bandwidth consumed by a layer decreases over

time

 LTS/TFRP

– Layered Transmission Scheme/TCP-Friendly Transport Protocol – Use simple TCP rate equation to decide

subscription level

MLDA and Rainbow  MLDA

– Multicast Loss-Delay Based Adaption Algorithm (rate-based) – Same as LDA+, but performs rate calculation at

receiver  Rainbow

(window-based)

– Encode data with digital fountain – Receivers individually request packets based on

individual windows

Conclusion  Congestion

is an important and complex

problem  Many solutions of varying effectiveness and complexity for various applications  Areas of future research: – Methods of comparing protocols – Improve definitions of fairness, friendliness – Improve models of TCP traffic

Questions?