28. Retransmission timeout (RTO), RTT estimation, and Karn's algorithm

28.1 Why RTT estimation is hard

The RTO must be long enough that a normal ACK isn't mistaken for loss, but short enough to recover quickly. RTT varies constantly (queueing, route changes, Wi-Fi). TCP measures it and adapts.

28.2 The Jacobson/Karels algorithm (RFC 6298)

Maintain a smoothed RTT (SRTT) and a smoothed mean deviation (RTTVAR):

On first RTT sample R:
    SRTT   = R
    RTTVAR = R / 2

On each subsequent sample R:
    RTTVAR = (1 - 1/4) * RTTVAR + 1/4 * |SRTT - R|
    SRTT   = (1 - 1/8) * SRTT   + 1/8 * R

    RTO    = SRTT + max(G, 4 * RTTVAR)      # G = clock granularity
    RTO    = clamp(RTO, 1s (RFC min) .. 60s)

• Weighting new samples at 1/8 makes SRTT a low-pass filter — stable but slow to react.
• Including 4 * RTTVAR means a jittery path gets a generously padded RTO (fewer spurious retransmits) while a stable path gets a tight RTO (fast recovery). This variance term is the key insight that fixed 1980s TCP.
• Linux uses a practical minimum RTO of 200 ms (TCP_RTO_MIN), not the RFC's 1 s, and can be tuned per-route (ip route ... rto_min 20ms inside a data center).

28.3 Karn's algorithm — the retransmission ambiguity

If you send segment X, it times out, you resend X, then an ACK arrives — was that ACK for the original or the retransmission? You can't tell, so you can't compute a valid RTT sample. Karn's algorithm:

1. Do not take an RTT sample from any segment that was retransmitted.
2. Do apply exponential backoff to the RTO on each retransmit (RTO = RTO * 2, capped), and keep the backed-off RTO until a segment is ACKed without retransmission (then resume normal calculation).

Backoff is what makes TCP retreat politely from a badly congested or broken path instead of hammering it: retries at roughly 1s, 2s, 4s, 8s, 16s… (Linux caps around tcp_retries2 ≈ 15 attempts ≈ 13–30 minutes before giving up on an established connection; tcp_syn_retries ≈ 6 for the initial SYN ≈ ~127 s).

28.4 Timestamps make RTT measurement continuous

With the TCP Timestamps option, every segment carries TSval; the ACK echoes it in TSecr. The sender computes RTT = now - TSecr on every ACK, not just once per window, and Karn's ambiguity disappears (the echoed timestamp disambiguates original vs retransmit). This gives a much better SRTT, and also powers PAWS (rejecting old segments whose sequence numbers wrapped on a fast link).

28.5 Tail loss and the RTO's worst case

If the last segments of a transfer are lost, there are no later segments to generate dup-ACKs, so fast retransmit can't trigger — you eat a full RTO (often 200 ms+). This is deadly for small request/response RPCs. Fixes:

• TLP (Tail Loss Probe): ~2×SRTT after the last segment, send one probe (retransmit the last segment or a new one) to elicit ACKs and trigger fast recovery instead of an RTO. Part of RACK-TLP, on by default in Linux.
• Early Retransmit and lowering the dup-ACK threshold when the window is small.

28.6 War story

An RPC service's p99.9 latency had a hard cliff at +200 ms. Traces showed the final segment of small responses occasionally lost; with no trailing data, the client waited a full TCP_RTO_MIN (200 ms) before the server's RTO fired. Enabling tcp_early_retrans/RACK-TLP on the servers (newer kernel) and, on the low-RTT data-center path, setting ip route ... rto_min 20ms collapsed the p99.9 spike. Lesson: a latency histogram with a spike exactly at 200 ms / 1 s = an RTO firing; look at tail-loss recovery (TLP) and rto_min.

Try it yourself

ss -tie dst <peer>     # shows rtt:<srtt>/<rttvar>  rto:<ms>  ato:<delayed-ack timeout>
nstat -az | grep -Ei 'TCPLossProbe|TCPTimeouts|TCPSpuriousRTOs|TCPRenoRecovery'
sysctl net.ipv4.tcp_timestamps net.ipv4.tcp_early_retrans net.ipv4.tcp_retries2
ip route show cache