Exercises — TCP reliability — seq - ack numbers, retransmission, cumulative ACK

Using the interval rule $[\text{SEQ},\text{SEQ}+L)$: $[5000,5000+200)=[5000,5200).$ That means bytes $5000,5001,\dots ,5199$ — the last byte is $5199$, not $5200$ (the right end is excluded). The next in-order segment starts right after, at ${\text{SEQ}}_{\text{next}}=5000+200=5200.$

ACK is the next byte expected = highest contiguous byte $+1$: $\text{ACK}=8399+1=8400.$ Read it as: "I have everything below $8400$; send byte $8400$ next."

The SYN flag consumes one sequence number (it is treated as one phantom byte at position $x$). So the highest thing "received" is $x$, and the next expected is $\text{ACK}=x+1.$ This $+1$ is exactly why a fresh connection's data starts at $x+1$, not $x$.

After each in-order arrival, the highest contiguous byte jumps by 100, and ACK $=$ that $+1$:

A fills the prefix → ACK $1100$. Then C and D arrive but there is a hole at bytes $[1100,1200)$, so the highest contiguous byte is still $1099$. The receiver buffers C and D but cannot advance the boundary:

• A → ACK $1100$
• C → still ACK $1100$ (duplicate #1)
• D → still ACK $1100$ (duplicate #2)

ACK sequence: $1100,1100,1100$. Two of these are duplicate ACKs.

B fills the last hole. Now A, B, C, D are all contiguous, up to byte $1399$: $\text{ACK}=1399+1=1400.$ It leaps from $1100$ to $1400$ in one message because cumulative ACK reports the whole contiguous prefix at once — filling the single hole at B instantly connects the buffered C and D.

Each update uses:

$\text{SRTT}=\frac{7}{8}(100)+\frac{1}{8}(300)=87.5+37.5=125\text{ ms}.$ For RTTVAR, use the old SRTT deviation $|100-300|=200$ (standard TCP updates RTTVAR using the SRTT before this sample's SRTT update): $\text{RTTVAR}=\frac{3}{4}(0)+\frac{1}{4}(200)=50\text{ ms}.$ $\text{RTO}=125+4\cdot 50=325\text{ ms}.$ Insight: one spike more than tripled the RTO. The $4\cdot \text{RTTVAR}$ term deliberately over- reacts to jitter so the sender waits longer and avoids declaring a false loss. (See RTT estimation / Jacobson's algorithm.)

The first $1100$ (after A) is the original ACK. The next two are duplicates → 2 duplicate ACKs. Fast retransmit needs 3 duplicate ACKs (4 identical ACKs total). With only 2 duplicates the threshold is not reached, so fast retransmit does not fire — the sender would have to wait for the RTO timer instead. If one more out-of-order segment arrived to produce a 3rd duplicate $1100$, fast retransmit would trigger.

• A arrives → contiguous to $1099$ → ACK $1100$ (original).
• C arrives → hole at B → ACK $1100$ (dup #1).
• D arrives → still hole → ACK $1100$ (dup #2).
• E arrives → still hole → ACK $1100$ (dup #3).

That is 3 duplicate ACKs for $1100$ → fast retransmit fires: the sender resends the segment at SEQ $1100$ (that is B) immediately, without waiting for RTO.

• B arrives → now A,B,C,D,E all contiguous, up to byte $1899$ → ACK $=1899+1=1900$.

Full ACK trace: $1100,1100,1100,1100,1900$. One retransmission repaired the whole gap.

• A → ACK $1100$.
• C → hole at B → ACK $1100$ (dup #1). Only one duplicate so far.
• B → hole filled, and C is already buffered → contiguous to $1299$ → ACK $1300$.
• D → contiguous to $1399$ → ACK $1400$.

ACK trace: $1100,1100,1300,1400$. Only 1 duplicate ACK appeared — below the threshold of 3 — so fast retransmit never fires and nothing is resent. This is exactly why the rule waits for 3 duplicates: a single reorder should not be mistaken for loss.

Byte layout: $S_i$ covers $[(i-1)100,i\cdot 100)$. So $S_3=[200,300)$ and $S_7=[600,700)$.

• $S_1,S_2$ arrive → ACK advances to $200$.
• $S_3$ lost. $S_4,S_5,S_6$ arrive → all produce duplicate ACK $200$ (contiguous stuck at $199$).
• Sender resends $S_3$ (at SEQ $200$). It fills the first hole → contiguous now jumps to byte $599$ (because $S_4,S_5,S_6$ were buffered) → ACK $600$. That is retransmission #1.
• $S_7$ lost. $S_8,S_9,S_{10}$ arrive → duplicate ACK $600$.
• Sender resends $S_7$ (SEQ $600$) → fills the second hole → contiguous to $999$ → ACK $1000$. That is retransmission #2.

Total retransmissions = 2 (one per hole). Cumulative ACK's inefficiency: while the sender waited for the ACK to unstick, it could not tell which higher segments were already safely buffered — the single number $200$ (then $600$) hid the fact that $S_4,S_5,S_6$ (and later $S_8,S_9,S_{10}$) were fine. A naïve Go-Back-N sender that reacts to a duplicate ACK by resending everything from the hole onward would resend $S_3\dots S_{10}$ needlessly. This ambiguity is the precise motivation for Selective ACK (SACK).

Failure scenario (lost ACK): With cumulative ACKs, if an ACK is lost it is self-healing — the next ACK carries a larger number that supersedes it, so no information is permanently lost. "ACK the exact last byte received" loses this: if the receiver ACKs byte $1099$ and that ACK is lost, the sender never learns $1099$ arrived; and because there is no "everything-below" semantics, a later ACK of, say, byte $1199$ does not confirm that $1100\dots 1198$ arrived. The sender cannot deduce the prefix. Property lost: cumulativeness — a single number can no longer summarize an entire contiguous prefix, so one ACK can no longer cover many segments, and a lost ACK is no longer automatically repaired by the next. (Also they'd reintroduce the off-by-one bug the $+1$ was designed to prevent: the sender must still figure out the next byte to send, i.e. last $+1$, so the $+1$ never actually goes away.)

Cumulative ACK $N$ means what, exactly? ::: The receiver has every byte below $N$ contiguously and wants byte $N$ next. How many duplicate ACKs trigger fast retransmit? ::: Three (i.e. 4 identical ACKs total). Why does the ACK "leap" when a hole is filled? ::: Cumulative ACK reports the whole contiguous prefix, so filling one hole connects all the buffered segments after it. In Jacobson's algorithm, RTTVAR uses the deviation from which SRTT? ::: The old SRTT, before this sample updates it.