Transport layer II: flow control, congestion control and RTT estimation

Last week we saw how TCP numbers segments. This week we talk about how fast it sends. There are two separate brakes: flow control so as not to overwhelm the receiver, and congestion control so as not to overwhelm the network. The exam almost always has a round-by-round cwnd table and a timeout calculation. Golden rules:

1. Sender window = min(cwnd, rwnd). One comes from the receiver, one from the network.
2. Slow start doubles, congestion avoidance adds 1. The switch point is ssthresh.
3. On loss, ssthresh = cwnd / 2. In both versions, for both kinds of loss.
4. On a timeout, cwnd = 1. Tahoe drops to 1 on a triple duplicate ACK too; Reno drops to ssthresh + 3.
5. Timeout = EstimatedRTT + 4 · DevRTT.

Flow control

The receiver has a buffer (RcvBuffer). Bytes arriving from the network are written here, and the buffer empties as the application reads. If the application reads slowly, the buffer fills and new arrivals are lost. To prevent this, TCP sends the amount of free space, the receive window (rwnd) field, in the header of every segment:

$\text{rwnd} = \text{RcvBuffer} - (\text{LastByteRcvd} - \text{LastByteRead})$

The sender in turn keeps the data in flight below this value:

$\text{LastByteSent} - \text{LastByteAcked} \le \min(\text{cwnd}, \text{rwnd})$

Worked example: RcvBuffer = 20000 bytes, LastByteRcvd = 15000, LastByteRead = 9000.

unread data in the buffer = 15000 − 9000 = 6000 bytes
rwnd = 20000 − 6000 = 14000 bytes

PITFALL · the rwnd = 0 deadlock. If the receiver said rwnd = 0 and has no data to send, it doesn’t announce the new rwnd. The sender could wait forever. That is why the sender sends 1-byte probe segments (zero window probes) while the window is zero.

The window is also a rate limit: at most one window’s worth of data is sent per RTT. Without window scaling, rwnd is at most 65535 bytes, and with RTT 50 ms the rate is at most $65535 \cdot 8 / 0.05 \approx 10.49$ Mbps.

Congestion control: cwnd and ssthresh

When the queues of the routers in the middle of the network fill up, packets are dropped. TCP gets no explicit signal from the network (classic TCP, the end-to-end approach). It treats loss as a sign of congestion and adjusts the congestion window (cwnd) on the sender side. The rate becomes roughly $\text{cwnd} / RTT$.

There are three phases:

Reactions to loss:

When three duplicate ACKs arrive, the sender resends the missing segment immediately without waiting for the timeout. This is called fast retransmit. Why three? One or two duplicate ACKs can also come from mere reordering.

Worked example (fast retransmit): the sender sends segments 1 through 6, and segment 2 is lost. When segment 1 arrives, the receiver indicates that it wants segment 2. As segments 3, 4 and 5 arrive, the same ACK is repeated three times:

arriving seg   ACK (expected)   duplicate count at sender
1              2                -
3              2                1st duplicate
4              2                2nd duplicate
5              2                3rd duplicate → seg 2 is resent immediately

There is no need to wait for segment 6 to arrive or for the timer to expire. The loss is repaired in about one RTT.

AIMD (additive increase, multiplicative decrease): linear increase when there is no loss, halving on loss. Two AIMD connections sharing the same bottleneck approach an equal share over time. This is TCP’s fairness property.

TIP · the table rule. On this page, traces are written per round (RTT). When doubling cwnd in slow start, if you would exceed ssthresh, we stop at ssthresh: cwnd = min(2·cwnd, ssthresh). Some instructors skip the +3 in Reno and write cwnd = ssthresh. On the exam, read the question’s rule.

Worked example: a Tahoe and Reno trace

Start: cwnd = 1 MSS, ssthresh = 8 MSS. At the end of round 12, three duplicate ACKs are seen.

round :   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
Tahoe :   1  2  4  8  9 10 11 12 13 14 15 16  1  2  4  8  9 10 11 12
Reno  :   1  2  4  8  9 10 11 12 13 14 15 16 11 12 13 14 15 16 17 18
ssth  :   8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8  8

Step by step:

• Rounds 1-4: slow start, 1 → 8. In round 4, cwnd = ssthresh = 8, and we are now in congestion avoidance.
• Rounds 5-12: +1 per round, 9 → 16.
• Three duplicate ACKs at the end of round 12: ssthresh = 16 / 2 = 8 (it stays the same).
• Tahoe: cwnd = 1, slow start again: 1, 2, 4, 8 (rounds 13-16), then 9, 10, 11, 12.
• Reno: cwnd = 8 + 3 = 11 (round 13), then linear: 12, 13, … 18.

Eight rounds later Reno is at 18 and Tahoe at 12. That is the gain of fast recovery.

Typical things the questions ask: “In which rounds is it slow start?” (the rounds where cwnd < ssthresh), “Is the loss detection a triple duplicate ACK or a timeout?” (if cwnd drops to 1 and it is Reno, it is a timeout; if it is halved, it is a triple duplicate ACK), “What is ssthresh in round n?” (half of the cwnd at the last loss).

Average TCP throughput

In congestion avoidance the window rises to the value W at the moment of loss, halves, and rises again. The average of the sawtooth is $\frac{3}{4}W$:

$\text{average rate} \approx \frac{0.75 \cdot W}{RTT}$

Worked example: W = 40 segments, MSS = 1500 bytes, RTT = 100 ms.

W = 40 × 1500 × 8 = 480000 bit
0.75 × 480000 / 0.1 s = 3600000 bit/s = 3.6 Mbps

RTT estimation and timeout

If the timeout is too short, there are unnecessary retransmissions; if it is too long, the reaction to loss is late. TCP smooths the measured round-trip times (SampleRTT) with an exponentially weighted moving average (EWMA):

$\text{EstimatedRTT} = (1-\alpha)\,\text{EstimatedRTT} + \alpha\,\text{SampleRTT}, \quad \alpha = 0.125$

$\text{DevRTT} = (1-\beta)\,\text{DevRTT} + \beta\,\lvert \text{SampleRTT} - \text{EstimatedRTT} \rvert, \quad \beta = 0.25$

$\text{TimeoutInterval} = \text{EstimatedRTT} + 4\cdot\text{DevRTT}$

Worked example: EstimatedRTT = 100 ms, DevRTT = 10 ms, new SampleRTT = 140 ms.

Est     = 0.875 × 100 + 0.125 × 140 = 87.5 + 17.5 = 105 ms
Dev     = 0.75 × 10 + 0.25 × |140 − 105| = 7.5 + 8.75 = 16.25 ms
Timeout = 105 + 4 × 16.25 = 170 ms

PITFALL · the update order. The order in the textbook: first EstimatedRTT, then DevRTT with the new Est. RFC 6298, on the other hand, updates DevRTT first with the old Est: Dev = 0.75·10 + 0.25·|140 − 100| = 17.5, Timeout = 175 ms. If the question doesn’t specify the order, use the textbook order and state the order you used.

If several samples arrive, chain the same step. Starting with Est = 80, Dev = 8 and samples 120, 60, 96 ms:

sample  EstimatedRTT   DevRTT       Timeout
120     85             14.75        144
60      81.875         16.53125     148
96      83.640625      15.48828125  145.59375

A single large sample (120) moves Est by only 5 ms but increases Dev immediately. What really protects the timeout is the Dev term.

Two additional rules:

• Karn’s algorithm: no SampleRTT is taken from the ACK of a retransmitted segment, because it is unclear which copy the ACK belongs to.
• Exponential backoff: on a timeout, the next timeout doubles (1.25 s → 2.5 s → 5 s). When a new ACK arrives, return to the formula.

Common mistakes