10-9-24 Flow and Congestion Control

(2.1) Flow Control: What is the problem with sending too many packets?

Too many packets may overwhelm the receiver
Size of the receiver's buffers may change over time

(2.1) Flow Control: What is the solution to the problem of sending too many packets?

Sliding window
Receiver tells the sender how big their buffer is
Called the advertised window
For window size n, sender may transmit n bytes without receiving an ACK
After each ACK, the window slides forward
Window may go to zero!

(2.3) Silly Window Syndrome: What is the problem if the window size is very small?

Multiple, small packets, headers dominate data
Header Data Header Data Header Data Header Data

(2.3) Silly Window Syndrome: What causes silly window syndrome?

Poorly implemented TCP flow control
Sending application program creates data slowly
Receiving application program consumes data slowly
Both

(2.4) Nagle’s Algorithm: How does Nagle’s algorithm solve the problem of silly windows?

Sender should send only the first byte on receiving one byte data from the application
Sender should buffer all the rest bytes until the outstanding byte gets acknowledged
Sender should wait for 1 RTT (Round Trip Time)
After receiving the acknowledgment, sender should send the buffered data in one TCP segment
Sender should buffer the data again until the previously sent data gets acknowledged

(2.5) Error Detection: How does checksum detect packet corruption?

Computed over IP header, TCP header, and data

(2.5) Error Detection: How do sequence numbers catch sequence problems?

Duplicates are ignored
Out-of-order packets are reordered or dropped
Missing sequence numbers indicate lost packets

(2.5) Error Detection: How are lost segments detected by the sender?

Use timeout to detect missing ACKs
Need to estimate RTT to calibrate the timeout
Sender must keep copies of all data until ACK

(2.7) Round Trip Time Estimation: How is RTT estimated in the original TCP round-trip estimator?

RTT estimated as a moving average
new_rtt = α (old_rtt) + (1 – α)(new_sample)
Recommended α: 0.8-0.9 (0.875 for most TCPs)
RTO = 2 * new_rtt (i.e. TCP is conservative)

(2.8) RTT Sample Ambiguity: What does Karn’s algorithm suggest for retransmitted segments?

Ignore samples for retransmitted segments

(3.2.1) What is Congestion?: What happens when the load on the network is higher than capacity?

Capacity is not uniform across networks
Modem vs. Cellular vs. Cable vs. Fiber optics
There are multiple flows competing for bandwidth
Residential cable modem vs. corporate data center
Load is not uniform over time
10 PM, Sunday night ⇒ BitTorrent latest Game of Thrones

(3.2.2) Implementing Congestion Control: What variables are maintained in congestion control?

cwnd: congestion window
adv_wnd: receiver advertised window
ssthresh: threshold size (used to update cwnd)

(3.2.2) Implementing Congestion Control: What are the two phases of congestion control?

Slow start (cwnd < ssthresh)
Probe for bottleneck bandwidth
Congestion avoidance (cwnd >= ssthresh)
AIMD (additive-increase/multiplicative-decrease)

(3.2.3) Slow Start: What is the goal of slow start?

Reach knee quickly upon starting (or restarting) a connection
cwnd = 1 MSS
ssthresh = adv_wnd
Each time a segment is ACKed, cwnd++
Continues until ssthresh is reached or a packet is lost
Slow Start is not actually slow
cwnd increases exponentially

(3.2.4) Slow Start Example: What happens when cwnd grows rapidly?

Slows down when cwnd >= ssthresh or a packet drops

(3.3) The Danger of Increasing Load: What happens at the knee and cliff points in an M/M/1 queue?

Knee - point after which throughput increases very slowly and delay increases quickly
Cliff - point after which throughput ⇒ 0 and delay ⇒ ∞

(3.4) Congestion Control vs. Congestion Avoidance: What is the difference between congestion control and congestion avoidance?

Congestion Avoidance: Stay left of the knee
Congestion Control: Stay left of the cliff

(3.5) Advertised Window, Revisited: Does TCP’s advertised window solve congestion?

NO
The advertised window only protects the receiver
A sufficiently fast receiver can max the window
What if the network is slower than the receiver?
What if there are other concurrent flows?
Key points
Window size determines send rate
Window must be adjusted to prevent congestion collapse

(3.6.1) Congestion Window (cwnd): What does the congestion window (cwnd) limit?

Limits how much data is in transit
Denominated in bytes
wnd = min(cwnd, adv_wnd)
effective wnd = wnd − (last_byte_sent − last_byte_acked)

(3.6.2) Congestion Window (cwnd): How does TCP sending behavior work?

Send cwnd bytes, wait RTT for ACKS, then send more bytes
TCP rate ≈ cwnd / RTT bytes/sec
TCP sender limits transmission
cwnd is dynamically adjusted in response to observed network congestion (implementing TCP congestion control)