Congestion Control

Outline

Queuing Discipline Reacting to Congestion Avoiding Congestion

Spring 2003

CS 461

Issues
Two sides of the same coin
pre-allocate resources so at to avoid congestion control congestion if (and when) is occurs Source 1 10Mbp s Et hern et Router Destination 1.5-Mbps T1 link DI
p -Mb 100 s FD

Source 2 Two points of implementation

hosts at the edges of the network (transport protocol) routers inside the network (queuing discipline)

Underlying service model

best-effort (assume for now) multiple qualities of service (later)
Spring 2003 CS 461 2

Framework
Connectionless flows
sequence of packets sent between source/destination pair maintain soft state at the routers Source 1 Router Destination 1 Source Router 2 Router Destination 2 Source 3

Taxonomy
router-centric versus host-centric reservation-based versus feedback-based Spring 2003 window-based versus rate-based CS 461
3

Evaluation
Fairness Power (ratio of throughput to delay)
Throughput/delay

Optimal load

Load

Spring 2003

CS 461

Queuing Discipline
First-In-First-Out (FIFO)
does not discriminate between traffic sources

Fair Queuing (FQ)

explicitly segregates traffic based on flows ensures no flow captures more than its share of capacity variation: weighted fair queuing (WFQ)

Problem?
Flow 1

Flow 2 Round-robin service Flow 3

Flow 4

Spring 2003

CS 461

FQ Algorithm
Suppose clock ticks each time a bit is transmitted Let Pi denote the length of packet i Let Si denote the time when start to transmit packet i Let Fi denote the time when finish transmitting packet i Fi = Si + Pi When does router start transmitting packet i? if before router finished packet i - 1 from this flow, then immediately after last bit of i - 1 (Fi-1 ) if no current packets for this flow, then start transmitting when arrives (call this Ai) Thus: Fi = MAX (Fi - 1 , Ai) + Pi
Spring 2003 CS 461 6

FQ Algorithm (cont)
For multiple flows
calculate Fi for each packet that arrives on each flow treat all Fis as timestamps next packet to transmit is one with lowest timestamp

Not perfect: cant preempt current packet Example Flow 1 Flow 2

Flow 1 Flow 2 Output (arriving) (transmitting) F = 10 F=2 (a) Spring 2003 CS 461 (b) 7 Output F=8 F=5 F = 10

TCP 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)

Challenge
determining the available capacity in the first place adjusting to changes in the available capacity
Spring 2003 CS 461 8

Additive Increase/Multiplicative Decrease

Objective: adjust to changes in the available capacity New state variable per connection: CongestionWindow

limits how much data source has in transit MaxWin = MIN(CongestionWindow, AdvertisedWindow) EffWin = MaxWin - (LastByteSent LastByteAcked) increase CongestionWindow when congestion goes down decrease CongestionWindow when congestion goes up

Idea:

Spring 2003

CS 461

AIMD (cont)
Question: how does the source determine whether or not the network is congested? Answer: a timeout occurs
timeout signals that a packet was lost packets are seldom lost due to transmission error lost packet implies congestion

Spring 2003

CS 461

10

AIMD (cont)
Source Destination

Algorithm
increment CongestionWindow by one packet per RTT (linear increase) divide CongestionWindow by two whenever a timeout occurs (multiplicative decrease)

In practice: increment a little for each ACK

Increment = (MSS * MSS)/CongestionWindow CongestionWindow += Increment

Spring 2003 CS 461 11

AIMD (cont)
Trace: sawtooth behavior
70 60 50 40 30 20 10 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0

KB

Time (seconds)

Spring 2003

CS 461

12

Slow Start
Source Destination

Objective: determine the available capacity in the first Idea:

begin with CongestionWindow = 1 packet double CongestionWindow each RTT (increment by 1 packet for each ACK)

Spring 2003

CS 461

13

Slow Start (cont)

Exponential growth, but slower than all at once Used
when first starting connection when connection goes dead waiting for timeout

Trace 70 60 50 40 30 20 10 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 Problem: lose up to half a CongestionWindows worth of data
Spring 2003
KB

CS 461

14

Fast Retransmit and Fast Recovery

Problem: coarse-grain TCP timeouts lead to idle periods Fast retransmit: use duplicate ACKs to trigger retransmission
Sender Packet 1 Packet 2 Packet 3 Packet 4 Packet 5 Packet 6 ACK 2 ACK 2 Retransmit packet 3 ACK 6 ACK 1 ACK 2 ACK 2 Receiver

Spring 2003

CS 461

15

Results
70 60 50 40 30 20 10 1.0 2.0 3.0 4.0 5.0 6.0 7.0

KB

Fast recovery
skip the slow start phase go directly to half the last successful
CongestionWindow (ssthresh)

Spring 2003

CS 461

16

Congestion Avoidance
TCPs strategy
control congestion once it happens repeatedly increase load in an effort to find the point at which congestion occurs, and then back off

Alternative strategy
predict when congestion is about to happen reduce rate before packets start being discarded call this congestion avoidance, instead of congestion control

Two possibilities
router-centric: DECbit and RED Gateways host-centric: TCP Vegas

Spring 2003

CS 461

17

DECbit
Add binary congestion bit to each packet header Router
monitors average queue length over last busy+idle cycle Queue length Current time Time Previous Current cycle cycle Averaging interval set congestion bit if average queue length > 1 attempts to balance CS 461 throughout against delay Spring 2003

18

End Hosts
Destination echoes bit back to source Source records how many packets resulted in set bit If less than 50% of last windows worth had bit set
increase CongestionWindow by 1 packet

If 50% or more of last windows worth had bit set

decrease CongestionWindow by 0.875 times

Spring 2003

CS 461

19

Random Early Detection (RED)

Notification is implicit
just drop the packet (TCP will timeout) could make explicit by marking the packet

Early random drop

rather than wait for queue to become full, drop each arriving packet with some drop probability whenever the queue length exceeds some drop level

Spring 2003

CS 461

20

RED Details
Compute average queue length

AvgLen = (1 - Weight) * AvgLen + Weight * SampleLen 0 < Weight < 1 (usually 0.002) SampleLen is queue length each time a packet arrives MaxThreshold MinThreshold

AvgLen
Spring 2003 CS 461 21

RED Details (cont)

Two queue length thresholds

if AvgLen <= MinThreshold then enqueue the packet if MinThreshold < AvgLen < MaxThreshold then calculate probability P drop arriving packet with probability P if MaxThreshold <= AvgLen then drop arriving packet

Spring 2003

CS 461

22

RED Details (cont)

Computing probability P

TempP = MaxP * (AvgLen - MinThreshold)/ (MaxThreshold - MinThreshold) P = TempP/(1 - count * TempP)

P(drop)

Drop Probability Curve

1.0

MaxP MinThresh MaxThresh

AvgLen

Spring 2003

CS 461

23

Tuning RED
Probability of dropping a particular flows packet(s) is roughly proportional to the share of the bandwidth that flow is currently getting MaxP is typically set to 0.02, meaning that when the average queue size is halfway between the two thresholds, the gateway drops roughly one out of 50 packets. If traffic id bursty, then MinThreshold should be sufficiently large to allow link utilization to be maintained at an acceptably high level Difference between two thresholds should be larger than the typical increase in the calculated average queue length in one RTT; setting MaxThreshold to twice MinThreshold is reasonable for traffic on todays Internet Penalty Box for Offenders
Spring 2003 CS 461 24

TCP Vegas
Idea: source watches for some sign that routers queue is building up and congestion will happen too; e.g.,
KB

RTT grows 70 60 50 sending rate flattens 40

30 20 10 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 Time (seconds) 5.0 5.5 6.0 6.5 7.0 7.5 8.0 8.5

1100 900 700 500 300 100 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 Time (seconds) 5.0 5.5 6.0 6.5 7.0 7.5 8.0 8.5

Queue size in router

Sending KBps

10 5

0.5 1.0 1.5

2.0 2.5 3.0 3.5 4.0 4.5 Time (seconds)

5.0 5.5 6.0

6.5

7.0 7.5 8.0 8.5

Spring 2003

CS 461

25

Algorithm
Let BaseRTT be the minimum of all measured RTTs (commonly the RTT of the first packet) If not overflowing the connection, then

ExpectRate = CongestionWindow/BaseRTT

Source calculates sending rate (ActualRate) once per RTT Source compares ActualRate with ExpectRate

Diff = ExpectedRate - ActualRate if Diff < increase CongestionWindow linearly else if Diff > decrease CongestionWindow linearly else leave CongestionWindow unchanged
CS 461 26

Spring 2003

Algorithm (cont)
Parameters
- = 1 packet - = 3 packets
KB
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 Time (seconds) 70 60 50 40 30 20 10

240 200 160 120 80 40 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 Time (seconds) 5.0 5.5 6.0 6.5 7.0 7.5 8.0

Even faster retransmit

Spring 2003

CAM KBps

CS 461

27