TCP congestion control

The congestion-control mechanism is a key component of TCP:

• "classic" TCP (RFC 2581, RFC 5681) uses end-to-end congestion
  • no explicit feedback from the IP layer
  • TCP segment loss is taken as an indication of network congestion
• newer mechanisms provide network-assisted congestion signaling

End-to-end congestion

Congestion control helps TCP figure out how much data the network can handle, so the sender knows how many packets can be sent without overwhelming the network.

The sender adjusts its sending rate based on network congestion:

• if there is no congestion, it sends faster
• if congestion is detected, it slows down

This leads to three main questions.

How does a sender limit the rate at which it sends data?

TCP controls the sending rate using a variable called Congestion Window or cwnd:

The size of cwnd is dynamic, function of perceived network congestion.

The sender limits how much unacknowledged data can be in transit:

• the amount of unACK'd data cannot exceed the smaller of:
  • cwnd (Congestion Window)
  • rwnd (Receive Window)
• LastByteSent – LastByteAcked ≤ min(cwnd, rwnd)

How does a sender detect congestion?

TCP assumes the network is congested when a loss event happens. This can be:

• a timeout
• or receiving three duplicate ACKs

These events suggest that packets were lost because of congestion on the path between sender and receiver.

If no loss events occur, TCP assumes the network is working well:

• ACKs continue arriving normally
• cwnd size is increased
• and hence the transmission rate

Because TCP uses incoming ACKs to control when it increases cwnd, TCP is said to be self-clocking.

How should the sender adjust its sending rate?

TCP senders must collectively balance their sending rate:

• sending too fast can congest the network
• sending too slowly can under utilize the bandwidth

TCP adjusts its sending rate using these rules:

• a lost segment implies congestion → cwd should be decreased
• an acknowledged segment indicates that the network is operating well → cwd can be increased

TCP also continuously probes the available bandwidth to adjust the transmission rate:

• it gradually increases the sending rate to determine when congestion begins
• when congestion begins, TCP backs off from that rate
• it then resumes probing to see whether the congestion threshold has changed

Additive increase/multiplicative decrease (AIMD)

TCP works on many kinds of networks, from slow links to extremely fast ones. So there is no way for a TCP sender to know the network's capacity.

In the late 1980s, Van Jacobson introduced the first TCP congestion-control algorithm in RFC 5681. This happened about eight years after TCP/IP was already in use, when the Internet was experiencing congestion collapse.

The algorithm controls the congestion window (cwnd) using additive increase/multiplicative decrease (AIMD):

• decrease cwnd when congestion increases:
  • when packet loss is detected, TCP halves cwnd
  • thinking in packets instead of bytes:
    • cwnd = 16 packets
    • a loss is detected, cwnd is set to 8
    • another loss is detected, cwnd is set to 4
    • another loss is detected, cwnd is set to 2
    • another loss is detected, cwnd is set to 1
  • cwnd cannot go below one packet (= the MSS maximum segment size)

• increase cwnd when congestion decreases:

  • each time an ACK is received, TCP increments cwnd by a fraction of MSS:

    Increment = MSS × (MSS/cwnd)
    cwnd += Increment
    

  • rather than incrementing cwnd by an entire MSS bytes each RTT

So TCP decreases cwnd aggressively and increases cwnd conservatively throughout the lifetime of the connection.

This creates a sawtooth pattern:

Intuition:

• a large congestion window is more harmful than a small one
• if cwnd is too large, packets are dropped and retransmitted, which worsens congestion
• therefore, TCP reduces the window aggressively when loss occurs

The algorithm has three main parts:

1. slow start
2. congestion avoidance
3. fast recovery

Slow start

Additive increase works well when TCP is already near the network's capacity.

But when a connection starts from scratch, TCP needs a faster way to increase its sending rate. Ironically, this mechanism is called slow start, which increases cwnd exponentially rather than linearly.

During slow start, the cwnd grows like this:

• cwnd starts at 1 MSS
• TCP sends the first segment
• when it is acknowledged, cwnd increases by 1 MSS
• so TCP sends 2 segments giving a cwnd of 4 MSS
• and so on

TCP effectively doubles the number of packets it has in transit every RTT:

Slow start ends in three cases:

1. timeout (loss detected):
   • the TCP sender assumes congestion
   • cwnd is reset to 1 MSS
   • a new threshold, ssthresh, is set to half of the old cwnd
   • a second state variable ssthresh (slow start threshold) is set to half of the value of cwnd when congestion was detected
   • TCP restarts slow start
2. reaching the slow start threshold (cwnd >= ssthresh)
   • TCP becomes more cautious:
     • it might be reckless to keep doubling cwnd when it reaches ssthresh
     • congestion could be just around the corner
   • slow start ends
   • TCP switches to congestion avoidance mode and increases cwnd more cautiously
3. three duplicate ACKs detected before a timeout:
   • TCP assumes a segment was lost but the network is still usable
   • it retransmits the missing segment (fast-retransmit)
   • and enters the fast recovery mode

Congestion avoidance

When TCP enters congestion avoidance:

• instead of doubling cwnd every RTT (as in slow start)
• TCP increases cwnd slowly and linearly (additive increase)

When does congestion avoidance stop?

1. timeout occurs:
   • TCP sets ssthresh = cwnd / 2
   • TCP sets cwnd = 1 MSS
   • TCP switches back to slow start
2. three duplicate ACKs detected before a timeout:
   • TCP retransmits the missing segment (fast-retransmit)
   • TCP enters the fast recovery

Fast retransmit and fast recovery

Fast recovery is an optional TCP feature.

Normally, TCP retransmits lost packets only after a timeout. This can led to long periods of time during which the connection is dead while waiting for a timer to expire.

Fast retransmit resends a dropped packet after receiving 3 duplicate ACKs, instead of waiting for a timeout:

• the receiver sends an ACK when it gets data in order
• if a packet arrives out of order, the receiver:
  • cannot acknowledge the missing data yet
  • repeats the last ACK it sent (duplicate ACK)
• when the TCP sender sees a duplicate ACK:
  • it infers that a packet may have been lost
  • after receiving 3 duplicate ACKs, it retransmits the missing packet immediately
• the receiver then sends a cumulative ACK covering all received data

This reduces the number of timeouts and improves throughput (often by around 20%).

After fast retransmit, TCP enters fast recovery:

• TCP sets TCP sets ssthresh = cwnd / 2
• cwnd is then adjusted during fast recovery (implementation-dependent)
• TCP does not return to slow start
• TCP goes directly into congestion avoidance mode

Slow start is used only at the beginning of a connection or after a timeout.

At all other times, cwnd is following a pure additive increase/multiplicative decrease pattern.

TCP CUBIC

Additive-increase/multiplicative-decrease (AIMD) congestion control creates a "sawtooth" pattern.

It illustrates the intuition of TCP "probing" for available bandwidth.

But is cutting the rate in half and then increasing it slowly the best strategy?

• after a packet loss, the network conditions may not have worsened significantly beyond the congestion event
• in that case, reducing the rate so aggressively may be unnecessary
• it may be better to quickly return toward the previous sending rate
• then slow down and probe for available bandwidth more carefully

This idea is the basis of TCP CUBIC (RFC 8312):

• the congestion window is updated only on ACKs using a cubic growth function
• the slow start and fast recovery phases remain the same
• CUBIC only changes the congestion avoidance phase

TCP CUBIC is the default TCP congestion control algorithm in Linux.

Other congestion-avoidance approaches

Loss-based algorithms in TCP Reno/Tahoe interpret packet loss as a signal of congestion.

Other congestion-avoidance approaches try to proactively detect congestion before packet loss occurs.

Network-assisted congestion control

Explicit Congestion Notification (ECN) (RFC 3168) involves both TCP and IP to signal network congestion.

At the IP layer, ECN uses two bits (4 possible values) in the IP header.

These bits are used in two ways:

1. routers mark packets to indicate congestion:
   • congestion indication is carried to the destination host
   • the destination then informs the sending host using TCP feedback
   • the definition of when a router is congested is a configuration choice decided by the network operator
2. hosts uses them to indicate support for ECN:
   • this allows routers to mark packets instead of dropping them when congestion occurs
   • ECN capability is negotiated during TCP connection setup

Delay-based congestion control

Delay- or Avoidance-based algorithms try to detect congestion before packets are dropped, using measurements such as throughput, RTT, and bottleneck bandwidth.

Keep the pipe just full, but no fuller.

TCP Vegas (1994):

• detects congestion by monitoring increases in RTT (queueing delay) instead of waiting for packet loss
• compares the expected and actual throughput to estimate the amount of queued data
• adjusts cwnd based on the estimated queue size

Variants of Vegas:

• FAST TCP
• TCP Westwood
• New Vegas

TCP BBR (Bottleneck Bandwidth and RTT):

• Google's congestion control algorithm
• estimates bottleneck bandwidth and minimum RTT to determine its sending rate

Fairness

A congestion-control mechanism is said to be fair if all connections get an equal share of bandwidth on a link.

AIMD (additive-increase/multiplicative-decrease) tends to promote fairness:

• hosts increase their bandwidth additively
• when congestion occurs, they drop their bandwidth multiplicatively
• so, the host with higher share, loses most
• after that, every host increases its share by the same amount (additivitely)
• as this steps happens again and again, bandwidths converge to fair amounts

UDP traffic does not behave fairly:

• UDP does not reduce its sending rate when there is congestion
• but applications using UDP may implement their own congestion control (e.g., QUIC, WebRTC)

Also, nothing stops a TCP-based application from using multiple parallel connections:

• e.g., web browsers use multiple parallel TCP connections
• parallel TCP connections get a larger fraction of the bandwidth in a congested link