Congestion Control

Reading: Sections 6.1-6.4

COS 461: Computer Networks
Jennifer Rexford

1
Goals of Today’s Lecture
• Principles of congestion control
– Learning that congestion is occurring
– Adapting to alleviate the congestion

• TCP congestion control

– Additive-increase, multiplicative-decrease
– Slow start and slow-start restart

• Related TCP mechanisms

– Nagle’s algorithm and delayed acknowledgments

• Active Queue Management (AQM)

– Random Early Detection (RED)
– Explicit Congestion Notification (ECN)
2
Resource Allocation vs. Congestion Control

• Resource allocation
– How nodes meet competing demands for resources
– E.g., link bandwidth and buffer space
– When to say no, and to whom

• Congestion control
– How nodes prevent or respond to overload conditions
– E.g., persuade hosts to stop sending, or slow down
– Typically has notions of fairness (i.e., sharing the pain)

3
Flow Control vs. Congestion Control
• Flow control
– Keeping one fast sender from overwhelming a slow
receiver

• Congestion control
– Keep a set of senders from overloading the network

• Different concepts, but similar mechanisms

– TCP flow control: receiver window
– TCP congestion control: congestion window
– TCP window: min{congestion window, receiver window}
4
Three Key Features of Internet
• Packet switching
– A given source may have enough capacity to send data
– … and yet the packets may encounter an overloaded link

• Connectionless flows
– No notions of connections inside the network
– … and no advance reservation of network resources
– Still, you can view related packets as a group (“flow”)
– … e.g., the packets in the same TCP transfer

• Best-effort service
– No guarantees for packet delivery or delay
– No preferential treatment for certain packets
5
Congestion is Unavoidable
• Two packets arrive at the same time
– The node can only transmit one
– … and either buffer or drop the other

• If many packets arrive in a short period of time

– The node cannot keep up with the arriving traffic
– … and the buffer may eventually overflow

6
Congestion Collapse
• Definition: Increase in network load results
in a decrease of useful work done
• Many possible causes
–Spurious retransmissions of packets still in flight
 Classical congestion collapse
 Solution: better timers and TCP congestion control
–Undelivered packets
 Packets consume resources and are dropped
elsewhere in network
 Solution: congestion control for ALL traffic

7
What Do We Want, Really?
• High throughput
– Throughput: measured performance of a system
– E.g., number of bits/second of data that get through

• Low delay
– Delay: time required to deliver a packet or message
– E.g., number of msec to deliver a packet

• These two metrics are sometimes at odds

– E.g., suppose you drive a link as hard as possible
– … then, throughput will be high, but delay will be, too

8
Load, Delay, and Power
Typical behavior of queuing A simple metric of how well the
systems with random arrivals: network is performing:

Load
Power 
Delay

Average Power
Packet delay

Load “optimal Load

load”

Goal: maximize power 9

Fairness
• Effective utilization is not the only goal
– We also want to be fair to the various flows
– … but what the heck does that mean?

• Simple definition: equal shares of the bandwidth

– N flows that each get 1/N of the bandwidth?
– But, what if the flows traverse different paths?

10
Simple Resource Allocation
• Simplest approach: FIFO queue and drop-tail
• Link bandwidth: first-in first-out queue
– Packets transmitted in the order they arrive

• Buffer space: drop-tail queuing

– If the queue is full, drop the incoming packet

11
Simple Congestion Detection
• Packet loss
– Packet gets dropped along the way

• Packet delay
– Packet experiences high delay

• How does TCP sender learn this?

– Loss
 Timeout
 Triple-duplicate acknowledgment
– Delay
 Round-trip time estimate

12
Idea of TCP Congestion Control
• Each source determines the available capacity
– … so it knows how many packets to have in transit

• Congestion window
– Maximum # of unacknowledged bytes to have in transit
– The congestion-control equivalent of receiver window
– MaxWindow = min{congestion window, receiver window}
– Send at the rate of the slowest component

• Adapting the congestion window

– Decrease upon losing a packet: backing off
– Increase upon success: optimistically exploring

13
Additive Increase, Multiplicative Decrease

• How much to increase and decrease?

– Increase linearly, decrease multiplicatively
– A necessary condition for stability of TCP
– Consequences of over-sized window are much worse
than having an under-sized window
 Over-sized window: packets dropped and retransmitted
 Under-sized window: somewhat lower throughput

• Multiplicative decrease
– On loss of packet, divide congestion window in half

• Additive increase
– On success for last window of data, increase linearly
14
Leads to the TCP “Sawtooth”

Window

Loss

halved

15
Practical Details
• Congestion window
– Represented in bytes, not in packets (Why?)
– Packets have MSS (Maximum Segment Size) bytes

• Increasing the congestion window

– Increase by MSS on success for last window of data
– In practice, increase a fraction of MSS per received ACK
 # packets per window: CWND / MSS
 Increment per ACK: MSS * (MSS / CWND)

• Decreasing the congestion window

– Never drop congestion window below 1 MSS

16
Getting Started
Need to start with a small CWND to avoid overloading the network.

Window

But, could take a long

time to get started! t
17
“Slow Start” Phase
• Start with a small congestion window
–Initially, CWND is 1 MSS
–So, initial sending rate is MSS/RTT

• That could be pretty wasteful

–Might be much less than the actual bandwidth
–Linear increase takes a long time to accelerate

• Slow-start phase (really “fast start”)

–Sender starts at a slow rate (hence the name)
–… but increases the rate exponentially
–… until the first loss event 18
Slow Start in Action
Double CWND per round-trip time

1 2 4 8
Src

D D D A A D D D D
A
A A A A

Dest

19
Slow Start and the TCP Sawtooth
Window
Loss

Exponential “slow t
start”

Why is it called slow-start? Because TCP originally had

no congestion control mechanism. The source would just
start by sending a whole window’s worth of data.
20
Two Kinds of Loss in TCP
• Triple duplicate ACK
– Packet n is lost, but packets n+1, n+2, etc. arrive
– Receiver sends duplicate acknowledgments
– … and the sender retransmits packet n quickly
– Do a multiplicative decrease and keep going

• Timeout
– Packet n is lost and detected via a timeout
– E.g., because all packets in flight were lost
– After the timeout, blasting away for the entire CWND
– … would trigger a very large burst in traffic
– So, better to start over with a low CWND

21
Repeating Slow Start After Timeout

Window
timeout

Slow start in operation

until it reaches half of
previous
t cwnd.

Slow-start restart: Go back to CWND of 1, but take

advantage of knowing the previous value of CWND.
22
Repeating Slow Start After Idle Period
• Suppose a TCP connection goes idle for a while
– E.g., Telnet session where you don’t type for an hour

• Eventually, the network conditions change

– Maybe many more flows are traversing the link
– E.g., maybe everybody has come back from lunch!

• Dangerous to start transmitting at the old rate

– Previously-idle TCP sender might blast the network
– … causing excessive congestion and packet loss

• So, some TCP implementations repeat slow start

– Slow-start restart after an idle period
23
 Other TCP Mechanisms

Nagle’s Algorithm and Delayed ACK

24
Motivation for Nagle’s Algorithm
• Interactive applications
– Telnet and rlogin
– Generate many small packets (e.g., keystrokes)

• Small packets are wasteful

– Mostly header (e.g., 40 bytes of header, 1 of data)

• Appealing to reduce the number of packets

– Could force every packet to have some minimum size
– … but, what if the person doesn’t type more characters?

• Need to balance competing trade-offs

– Send larger packets
– … but don’t introduce much delay by waiting
25
Nagle’s Algorithm
• Wait if the amount of data is small
– Smaller than Maximum Segment Size (MSS)
• And some other packet is already in flight
– I.e., still awaiting the ACKs for previous packets
• That is, send at most one small packet per RTT
– … by waiting until all outstanding ACKs have arrived
ACK
vs.

• Influence on performance
– Interactive applications: enables batching of bytes
– Bulk transfer: transmits in MSS-sized packets anyway 26
Motivation for Delayed ACK
• TCP traffic is often bidirectional
–Data traveling in both directions
–ACKs traveling in both directions

• ACK packets have high overhead

–40 bytes for the IP header and TCP header
–… and zero data traffic

• Piggybacking is appealing
–Host B can send an ACK to host A
–… as part of a data packet from B to A
27
TCP Header Allows Piggybacking

Source port Destination port

Sequence number
Flags: SYN
Acknowledgment
FIN
RST HdrLen 0 Flags Advertised window
PSH
URG Checksum Urgent pointer
ACK Options (variable)

Data

28
Example of Piggybacking

A B

B has data to send

B doesn’t have data to send

A has data to send

29
Increasing Likelihood of Piggybacking
• Increase piggybacking
– TCP allows the receiver to wait A B
to send the ACK
– … in the hope that the host will
have data to send

• Example: rlogin or telnet

– Host A types characters at a
UNIX prompt
– Host B receives the character
and executes a command
– … and then data are generated
– Would be nice if B could send
the ACK with the new data 30
Delayed ACK
• Delay sending an ACK
– Upon receiving a packet, the host B sets a timer
 Typically, 200 msec or 500 msec
– If B’s application generates data, go ahead and send
 And piggyback the ACK bit
– If the timer expires, send a (non-piggybacked) ACK

• Limiting the wait

– Timer of 200 msec or 500 msec
– ACK every other full-sized packet

31
 Queuing Mechanisms

Random Early Detection (RED)

Explicit Congestion Notification (ECN)

32
Bursty Loss From Drop-Tail Queuing
• TCP depends on packet loss
– Packet loss is the indication of congestion
– In fact, TCP drives the network into packet loss
– … by continuing to increase the sending rate

• Drop-tail queuing leads to bursty loss

– When a link becomes congested…
– … many arriving packets encounter a full queue
– And, as a result, many flows divide sending rate in half
– … and, many individual flows lose multiple packets

33
Slow Feedback from Drop Tail
• Feedback comes when buffer is completely full
– … even though the buffer has been filling for a while

• Plus, the filling buffer is increasing RTT

– … and the variance in the RTT

• Might be better to give early feedback

– Get one or two flows to slow down, not all of them
– Get these flows to slow down before it is too late

34
Random Early Detection (RED)
• Basic idea of RED
– Router notices that the queue is getting backlogged
– … and randomly drops packets to signal congestion

• Packet drop probability

– Drop probability increases as queue length increases
– If buffer is below some level, don’t drop anything
– … otherwise, set drop probability as function of queue
Probability

Average Queue Length 35

Properties of RED
• Drops packets before queue is full
– In the hope of reducing the rates of some flows

• Drops packet in proportion to each flow’s rate

– High-rate flows have more packets
– … and, hence, a higher chance of being selected

• Drops are spaced out in time

– Which should help desynchronize the TCP senders

• Tolerant of burstiness in the traffic

– By basing the decisions on average queue length

36
Problems With RED
• Hard to get the tunable parameters just right
– How early to start dropping packets?
– What slope for the increase in drop probability?
– What time scale for averaging the queue length?

• Sometimes RED helps but sometimes not

– If the parameters aren’t set right, RED doesn’t help
– And it is hard to know how to set the parameters

• RED is implemented in practice

– But, often not used due to the challenges of tuning right

• Many variations
– With cute names like “Blue” and “FRED”… 
37
Explicit Congestion Notification
• Early dropping of packets
– Good: gives early feedback
– Bad: has to drop the packet to give the feedback

• Explicit Congestion Notification

– Router marks the packet with an ECN bit
– … and sending host interprets as a sign of congestion

• Surmounting the challenges

– Must be supported by the end hosts and the routers
– Requires two bits in the IP header (one for the ECN
mark, and one to indicate the ECN capability)
– Solution: borrow two of the Type-Of-Service bits in the
IPv4 packet header 38
Conclusions
• Congestion is inevitable
– Internet does not reserve resources in advance
– TCP actively tries to push the envelope
• Congestion can be handled
– Additive increase, multiplicative decrease
– Slow start, and slow-start restart
• Active Queue Management can help
– Random Early Detection (RED)
– Explicit Congestion Notification (ECN)
• Next class
– Domain Name System (50 minutes)
– Q&A for the first assignment (30 minutes)
39