Exercises — TCP flow control — sliding window, receive buffer

WHAT we compute: occupancy = the two-pointer gap in the buffer. $\text{occupancy}=52000-50000=2000\text{ bytes}$ WHY: those 2000 bytes arrived but the app hasn't read() them yet — they occupy memory. Then the advertised free room: $\text{rwnd}=8000-2000=6000\text{ bytes}$ The receiver puts 6000 into the 16-bit Window field.

It travels in the 16-bit Window field of the TCP header, and it is written by the receiver (the side whose buffer is being protected). The sender only reads it. See TCP segment header format.

Step 1 — advertised room: $\text{rwnd}=4000-(30000-28800)=4000-1200=2800$ Step 2 — bytes already in flight (sent, not yet acked): $\text{in-flight}=30000-29200=800$ Step 3 — remaining budget = free room minus what's already claiming seats: $2800-800=2000\text{ bytes}$ WHY subtract in-flight: those 800 bytes are travelling toward the buffer and will occupy part of the 2800. Ignoring them would overbook the buffer.

New in-flight: $\text{in-flight}=30000-30000=0$ Budget: $2800-0=2800\text{ bytes}$ WHAT just happened geometrically: the ACK slid the window's left edge right up to LastByteSent, freeing the whole advertised window. This is the sliding in sliding window.

The deadlock: with rwnd = 0 the sender is frozen (LastByteSent − LastByteAcked ≤ 0, nothing new allowed). When the app reads 3000 bytes, the receiver's occupancy drops and it would advertise a bigger window — but a receiver emits segments only when it has data or an ACK to send. With no traffic, that fresh window update may never be transmitted, so the sender waits forever. The fix — Zero-Window Probe: the sender periodically sends a 1-byte probe segment. The receiver must reply (it now has something to ACK), and that reply carries the current window. If it read 3000 bytes and, say, RcvBuffer = 4000 with occupancy now 1000, the probe response advertises: $\text{rwnd}=4000-1000=3000$ The sender learns "3000 bytes of room" on the next probe reply, and resumes.

rwnd is set by the receiver to protect its buffer (an endpoint memory limit). cwnd is estimated by the sender from loss and RTT to protect the network path (see TCP congestion control — cwnd, AIMD). They measure two independent bottlenecks, so they need not agree. The sender obeys both by taking the smaller: $\text{allowed}=\min (\text{rwnd},\text{cwnd})=\min (12000,5000)=5000\text{ bytes}$ Here the network is the bottleneck, not the receiver's buffer.

Step 1 — BDP in bits, then bytes. BDP is "how many bits fit in the pipe at once" = bandwidth × RTT: $\text{BDP}=10^9\times 0.040=4\times 10^7\text{ bits}=\frac{4\times 10^7}{8}=5,000,000\text{ bytes}$ WHY BDP: to keep the sender continuously busy, the window must cover a full round trip's worth of unacked data. If the window is smaller, the sender stalls waiting for ACKs. Step 2 — the 16-bit ceiling. A raw Window field maxes at $2^{16}-1=65535$ bytes ≈ 64 KB, which is ~76× too small for 5 MB. So the pipe would sit mostly empty — exactly the failure of a too-short window. Step 3 — window scale. Effective window $=\text{Window}\times 2^s$, and Window $\le 65535$. We need: $65535\times 2^s\ge 5,000,000\Rightarrow 2^s\ge \frac{5,000,000}{65535}\approx 76.3$ Since $2^6=64<76.3\le 128=2^7$, the smallest shift is: $\boxed{s=7}$ With s = 7, one Window unit = 128 bytes, so max advertisable $=65535\times 128=8,388,480$ bytes > 5 MB. ✔

The wire value must be an integer, and effective = value × 128. To not over-promise, round down: $\text{value}=\lfloor \frac{5,000,000}{128}\rfloor =\lfloor 39062.5\rfloor =39062$ Actual advertised room: $39062\times 128=4,999,936\text{ bytes}$ WHY round down: rounding up would advertise more room than exists → risk of buffer overflow. The lost 64 bytes of granularity are harmless.

(a) rwnd. Occupancy = $200000-190000=10000$. $\text{rwnd}=65536-10000=55536\text{ bytes (effective)}$ (b) raw Window value. With s = 4, effective = value × $2^4$ = value × 16. Round down: $\text{value}=\lfloor \frac{55536}{16}\rfloor =3471,\text{re-check: }3471\times 16=55536\text{ (exact)}$ So the wire carries 3471, meaning 55536 bytes exactly. (c) in-flight. $\text{in-flight}=205000-198000=7000\text{ bytes}$ (d) true budget. First the flow-control budget: $\text{rwnd}-\text{in-flight}=55536-7000=48536$ But the sender also obeys congestion control; the allowed window is min(rwnd, cwnd) = min(55536, 6000) = 6000, and its own budget: $\text{allowed extra}=\min (\text{rwnd},\text{cwnd})-\text{in-flight}=6000-7000=-1000$ A negative result means the sender is already 1000 bytes over its congestion limit — it must send 0 more bytes and wait for ACKs to slide the window forward. The network, not the receiver, is the binding constraint here.

1. Occupancy → 65536 = RcvBuffer, so $\text{rwnd}=65536-65536=0$. Receiver advertises Window = 0.
2. Sender now has $\min (\text{rwnd},\text{cwnd})=\min (0,6000)=0$: frozen, may send nothing.
3. To avoid the zero-window deadlock, the sender starts a persist timer and emits 1-byte zero-window probes.
4. When the app finally read()s, occupancy drops, rwnd becomes positive; the next probe reply carries the new non-zero Window (scaled by $2^4$).
5. Sender resumes, bounded again by min(rwnd, cwnd). Every brake in play: rwnd (receiver buffer), cwnd (network), zero-window probe (deadlock breaker), window scale (large-window encoding).

Cover the answers: rwnd formula? budget formula? which window does the sender obey? what breaks a zero-window deadlock? how does scaling encode a big window? rwnd = RcvBuffer − occupancy ::: budget = min(rwnd,cwnd) − in-flight ::: min(rwnd,cwnd) ::: zero-window probe ::: effective = Window × 2^s.