Congestion Control

Question 1

Principles of Congestion Control

Answer 1

• Packet retransmission (last lecture) treats a symptom (packet loss) but does not treat the cause
• This cause is congestion: “too many sources sending too much data too fast for network to handle”
• Manifestations:
  
  • Lost packets (buffer overflow at routers)
  • Long delays (queueing in router buffers)

Question 2

Causes/costs of congestion: scenario 1

Answer 2

Simplest scenario:
- one router, infinite buffers
- input, output link capacity: R
- Two flows
- no retransmissions needed

Question 3

Causes/costs of congestion: scenario 2

Answer 3

• one router, finite buffers

Idealization: perfect knowledge
- Sender sends only when router buffer is available

• sender retransmits only lost, timed-out packet
  
  • application-layer input = application-layer output: lin = lout
• transport-layer input includes retransmissions: l’in => lin

Question 4

Causes/costs of congestion: scenario 2
Idealization: some perfect knowledge

Answer 4

• packets can be lost (dropped at router) due to full buffers
• sender knows when packet has been dropped: only resends if packet known to be lost

Question 5

Causes/costs of congestion: scenario 2
Realistic scenario: un-needed duplicates

Answer 5

• packets can be lost, dropped at router due to
  full buffers – requiring retransmissions
• but sender times can time out prematurely,
  sending two copies, both of which are delivered

“costs” of congestion:
- more work (retransmission) for given receiver throughput
- unneeded retransmissions: link carries multiple copies of a packet
* decreasing maximum achievable throughput

Question 6

Causes/costs of congestion: scenario 3

Answer 6

• four senders
• multi-hop paths
• timeout/retransmit

Q: what happens as (lambda)in and (lambda)in’ increase ?
A: as red (lambda)in’ increases, all arriving blue pkts at upper queue are dropped, blue throughput g 0

Question 7

Causes/costs of congestion: scenario 3
another “cost” of congestion:

Answer 7

§ when packet dropped, any upstream transmission capacity and buffering used for that packet was wasted!

Question 8

Causes/costs of congestion: insights

Answer 8

Question 9

TCP Congestion control
(High-level idea)

Answer 9

• High-level idea: each sender limits the rate at which it sends traffic into its connection as a function of perceived network congestion
• If a sender perceives that there is little congestion on the path between itself and the destination, then the TCP sender increases its send rate;
• If a sender perceives that there is congestion along the path, then the sender reduces its send rate.

Question 10

How to perceive congestion? (End-end congestion control)

Answer 10

• no explicit feedback from network
• congestion inferred from observed loss, delay
• approach taken by most TCP implementations

Question 11

How to perceive congestion? (Network-assisted congestion control)

Answer 11

• routers provide direct feedback to sending/receiving hosts with flows passing through congested router
• may indicate congestion level or explicitly set sending rate
  *TCP ECN, ATM, DECbit protocols

Question 12

How does a sender limit its sending rate?

Answer 12

• TCP sender limits transmission:
  LastByteSent- LastByteAcked < cwnd
• cwnd is dynamically adjusted in response to observed network congestion (implementing TCP congestion control)

Question 13

Types of loss detection

Answer 13

Question 14

Why 3 duplicates? Why not 1 or 10?

Answer 14

“Since TCP does not know whether a duplicate ACK is caused by a lost segment or just a reordering of segments, it waits for a small number of duplicate ACKs to be received (in this case, 3).

It is assumed that if there is just a reordering of the segments, there will be only one or two duplicate ACKs before the reordered segment is processed, which will then generate a new ACK. If three or more duplicate ACKs are received in a row, it is a strong indication that a segment has been lost (and Fast Retransmit is being requested by receiver).”

Question 15

How to adjust sending rate with perceived congestion?

Answer 15

• Basic approach: senders can increase sending rate until packet loss* (congestion) occurs, then decrease sending rate on loss event

Question 16

TCP AIMD: more

Answer 16

Multiplicative decrease detail: sending rate is
- Cut in half on loss detected by triple duplicate ACK (TCP Reno)
- Cut to 1 MSS (maximum segment size) when loss detected by timeout (TCP Tahoe)

Question 17

Why AIMD?

Answer 17

• AIMD – a distributed, asynchronous algorithm – has been shown to:
  
  • optimize congested flow rates network wide!
  • have desirable stability properties

Question 18

TCP slow start

Answer 18

• when connection begins, increase rate exponentially until first loss event:
  
  • initially cwnd = 1 MSS
  • double cwnd every RTT
  • done by incrementing cwnd for every ACK received
• summary: initial rate is slow, but ramps up exponentially fast

Question 19

TCP: from slow start to congestion avoidance

Answer 19

Q: when should the exponential increase switch to linear (i.e., AIMD)?
A: when cwnd gets to 1/2 of its value before timeout

Implementation:
- variable ssthresh
- on loss event, ssthresh is set to 1/2 of cwnd just before loss event

Question 20

Detecting and Reacting to Loss
Loss indicated by timeout (TCP Reno and Tahoe)

Answer 20

• cwnd set to 1 MSS;
• Window then grows exponentially (as in Slow Start) to threshold, then grows linearly (as in Congestion Avoidance)

Question 21

Detecting and Reacting to Loss (Loss indicated by 3 duplicate ACKs)

Answer 21

• Indicates network capable of delivering some segments
• TCP Reno and Tahoe do Fast Retransmit (see Lec. 10)
• TCP Reno: cwnd is cut in half (equal to ssthresh), window then grows linearly
  
  • Starts Fast Recovery phase
• TCP Tahoe: always sets cwnd to 1 MSS;

Question 22

TCP Congestion Control
Versions

Answer 22

TCP Tahoe
* This is the original version of TCP congestion control
* Slow Start
* Fast Retransmit (see Lecture 10)

TCP Reno
* Same as Tahoe, but with Fast Recovery TCP Vegas
* This is a completely new implementation based on delay variation (instead of packet loss)

Question 23

TCP Tahoe vs TCP Reno

Answer 23

Question 24

Summary: TCP congestion control (Reno)

Answer 24

Question 25

TCP and the congested “bottleneck link”

Answer 25

- TCP increases the sending rate until packet loss occurs at some router’s output: the bottleneck link - understanding congestion: useful to focus on congested bottleneck link

Question 26

Delay-based TCP congestion control

Answer 26

Keeping sender-to-receiver pipe “just full enough, but no fuller”: keep bottleneck link busy transmitting, but avoid high delays/buffering Delay-based approach: - RTTmin - minimum observed RTT (uncongested path) - uncongested throughput with congestion window cwnd is cwnd/RTTmin if measured throughput “very close” to uncongested throughput increase cwnd linearly /* since path not congested */ else if measured throughput “far below” uncongested throughout decrease cwnd linearly /* since path is congested */

Question 27

Delay-based TCP congestion control

Answer 27

- congestion control without inducing/forcing loss - maximizing throughout (“keeping the just pipe full… ”) while keeping delay low (“…but not fuller”) - a number of deployed TCPs take a delay-based approach - BBR deployed on Google’s (internal) backbone network

Question 28

Explicit congestion notification (ECN)

Answer 28

TCP deployments often implement network-assisted congestion control: - two bits in IP header (ToS field) marked by network router to indicate congestion * policy to determine marking chosen by network operator - congestion indication carried to destination - destination sets ECE bit on ACK segment to notify sender of congestion - involves both IP (IP header ECN bit marking) and TCP (TCP header C,E bit marking)

Question 29

TCP fairness

Answer 29

Fairness goal: if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/K

Question 30

Q: is TCP Fair?

Answer 30

Example: two competing TCP sessions: - additive increase gives slope of 1, as throughout increases - multiplicative decrease decreases throughput proportionally

Question 31

TCP flow control

Answer 31

- TCP receiver “advertises” free buffer space in rwnd field in TCP header * RcvBuffer size set via socket options (typical default is 4096 bytes) * many operating systems autoadjust RcvBuffer - sender limits amount of unACKed (“in-flight”) data to received rwnd * LastByteSent – LastByteAcked ≤ min{cwnd, rwnd} - guarantees receive buffer will not overflow

Question 32

TCP flow control 2