CS Atlas GATE 2027
Computer Networks course
0 / 90 complete

Computer Networks/Phase 4 · Transport Layer (TCP)

Lesson 4.3.4 · Item 70 of 90

TCP timeout estimation: EWMA, Jacobson’s algorithm & Karn’s rule

Read at your own pace. Try the questions before opening the answers.

On this page

Recall warm-up

  1. What happens if a retransmission timeout (RTO) is set much shorter than the true round-trip time?
    Stuck? Peek at 4.3.3 TCP flow control (rwnd), sequence wrap-around time & window scaling
    • Flow control: rwnd = RcvBuffer − (LastByteRcvd − LastByteRead); sender keeps BytesInFlight ≤ rwnd.
    • Zero window (`rwnd = 0`): sender runs Persist Timer and sends 1-byte Zero-Window Probes.
    • Wrap-around time: T_wrap = (2³² × 8) / B seconds (34.36 s at 1 Gbps).
    • Window scaling: True rwnd = HeaderWindow × 2ˢ (S ≤ 14, negotiated in SYN).

    Read lesson 4.3.3

  2. What happens if the retransmission timeout (RTO) is set much longer than the true round-trip time?
    Stuck? Peek at 4.2.1 Stop-and-Wait ARQ, 1-bit sequence numbers & link utilisation
    • Stop-and-Wait ARQ: 1 packet in flight; uses 1-bit sequence numbers (0, 1) to discard duplicates when ACKs are lost.
    • Utilisation: η = Tt / (Tt + 2·Tp) = 1 / (1 + 2a), where a = Tp / Tt (with losses of prob p: (1 − p)/(1 + 2a)).
    • Throughput: η × B = L / (Tt + 2·Tp).

    Read lesson 4.2.1

  3. Why does the round-trip time (RTT) between two Internet hosts vary over time?
    Stuck? Peek at 1.3.3 RTT, bandwidth-delay product, utilisation and a = Tp/Tt
    • RTT = 2·Tp for tiny signals (add Tt / queuing if stated).
    • BDP = B × Tp bits in flight; B × RTT before any reply.
    • a = Tp / Tt.
    • Send-and-wait: U = Tt/(Tt + 2Tp) = 1/(1 + 2a); throughput = U·B.
    • To keep the link busy: about 1 + 2a units in flight.

    Read lesson 1.3.3

The Hook

On a single wire in Chapter 4.2, RTT = 2·Tp was a fixed constant. Across the global Internet, a segment might take 80 ms right now and 220 ms five seconds later when a router queue fills up!

How does TCP pick a Retransmission Timeout (RTO) that tracks both the average RTT and how wildly the RTT is jittering, and why must TCP refuse to measure RTT whenever a segment is retransmitted?

Predict First

Suppose TCP sends Segment 1 at t = 0, times out at t = 100 ms, and retransmits Segment 1 at t = 100 ms. At t = 120 ms, an ACK arrives! Was that ACK generated by the original transmission (so true RTT = 120 ms) or by the retransmission (so true RTT = 20 ms)?

,

You cannot tell! Because the cumulative ACK carries only the next expected byte number, both transmissions look identical in the ACK (retransmission ambiguity). Guessing 20 ms makes RTO dangerously small; guessing 120 ms inflates it. Karn's Rule solves this cleanly: never update RTT estimates from an ACK of a retransmitted segment!

Core Concept

Smoothed RTT: Exponentially Weighted Moving Average (EWMA)

A TCP sender measures SampleRTT (time from sending an un-retransmitted segment until its ACK arrives) and maintains a smoothed average EstimatedRTT (also called SRTT) using an Exponentially Weighted Moving Average (EWMA) with weight α = 1/8 = 0.125:

EstimatedRTT (EWMA) Formula:
EstimatedRTT_new = (1 − α) · EstimatedRTT_old + α · SampleRTT   (default α = 1/8 = 0.125).

Why EWMA? Recent samples carry weight α = 1/8, while older samples decay exponentially ((7/8)ᵏ), smoothing out one-off spikes while adapting to real route changes.

Small α (e.g. α = 0.125)
Gives 87.5% weight to history and 12.5% to the new sample → stable, smooth average.
Large α (e.g. α = 0.8)
Reacts jumpy to every single queuing spike.
TCP standard RFC 6298 uses α = 1/8 (0.125).

Jacobson’s Algorithm: Tracking RTT Variation (DevRTT) & RTO

Setting RTO = 2 × EstimatedRTT fails when RTT variance is high! In 1988, Van Jacobson added an EWMA of the mean deviation DevRTT (or RTTVAR) with weight β = 1/4 = 0.25 and set RTO to the mean plus 4 deviations:

Jacobson's RTO Equations (default α = 1/8, β = 1/4):
• DevRTT = (1 − β) · DevRTT + β · |SampleRTT − EstimatedRTT|
• RTO = EstimatedRTT + 4 · DevRTT.
Convention Note — Which updates first, EstimatedRTT or DevRTT?
• RFC 6298 (Internet standard & our default) updates DevRTT FIRST using the OLD EstimatedRTT, and then updates EstimatedRTT.
• Kurose & Ross textbook updates EstimatedRTT first and plugs the NEW EstimatedRTT into |SampleRTT − EstimatedRTT|.
On GATE, if the question lists the formulas in a specific order, follow that order; otherwise both give nearly identical values (we show both in Example 2 & 3!).
Step (starting from EstRTT = 100 ms, DevRTT = 20 ms, new SampleRTT = 140 ms)RFC 6298 Order (Old EstRTT in Dev)Kurose Order (New EstRTT in Dev)
EstimatedRTT = 0.875(100) + 0.125(140)105 ms105 ms
|SampleRTT − EstimatedRTT||140 − 100| = 40 ms|140 − 105| = 35 ms
DevRTT = 0.75(20) + 0.25 × |diff|15 + 10 = 25 ms15 + 8.75 = 23.75 ms
RTO = EstimatedRTT + 4 × DevRTT105 + 4(25) = 205 ms105 + 4(23.75) = 200 ms
Side-by-side comparison of RFC 6298 vs Kurose update order for SampleRTT = 140 ms.

Karn’s Algorithm & Exponential Timer Back-off

To handle retransmissions and severe congestion, Karn's Algorithm adds two mandatory rules:

  1. No SampleRTT on retransmissions: Never compute SampleRTT (or update EstimatedRTT / DevRTT) for any segment that has been retransmitted.
  2. Timer Back-off (Doubling RTO): Each time the timeout timer expires for an unacknowledged segment, double the current RTO (RTO ← 2 × RTO) until an un-retransmitted segment is finally acknowledged!
Segment sent
start timer = RTO
Timeout fires!
retransmit segment
Karn Rule 1: ignore its ACK for RTT
avoids ambiguity!
Karn Rule 2: double RTO = 2·RTO
exponential backoff
Karn’s two rules: ignore ambiguous samples, and double RTO on consecutive timeouts.

Putting it together

  • TCP smooths RTT measurements using an EWMA: EstimatedRTT = (1 − α)·EstimatedRTT + α·SampleRTT (α = 1/8).
  • Jacobson’s algorithm tracks jitter via DevRTT (β = 1/4) and sets RTO = EstimatedRTT + 4·DevRTT.
  • Karn’s rule prevents retransmission ambiguity by ignoring samples from retransmitted segments and doubling RTO on timeouts.

Visual

061.75123.5185.2524712345100140120160110100105106.9113.5113.1180205196.9219.9193.7Sample NumberTime (ms)
SampleRTT (ms)EstimatedRTT (ms)RTO = Est + 4·Dev (ms)
How EstimatedRTT smooths SampleRTT while RTO = EstimatedRTT + 4·DevRTT maintains a safe margin above spikes.

Worked Examples

Easy

A TCP connection has current EstimatedRTT = 100 ms. A new SampleRTT = 140 ms is measured. Using α = 0.125, what is the new EstimatedRTT?

Show the full solution

EstimatedRTT = (1 − 0.125) × 100 + 0.125 × 140 = 87.5 + 17.5 = 105 ms.

Medium

In Example 1, suppose the initial DevRTT = 20 ms and β = 0.25. Compute the new DevRTT and RTO using the RFC 6298 standard order (updating DevRTT with the old EstimatedRTT = 100 ms).

Show the full solution

• DevRTT = (1 − 0.25) × 20 + 0.25 × |140 − 100| = 15 + 0.25 × 40 = 25 ms.
• RTO = EstimatedRTT_new + 4 × DevRTT_new = 105 + 4 × 25 = 205 ms.

GATE

A TCP sender has current RTO = 200 ms. It sends a segment that is lost three times in a row (three consecutive timeouts occur before the 4th transmission finally succeeds). Under Karn's algorithm, what is the value of RTO after the 3rd timeout, and is EstimatedRTT updated when the ACK for the 4th transmission arrives?

Show the full solution

1) Each timeout doubles RTO: after 1st timeout → 400 ms; after 2nd timeout → 800 ms; after 3rd timeout → 1600 ms.
2) By Karn's Rule, because the segment was retransmitted, its ACK is NOT used to update EstimatedRTT or DevRTT!

GATE Traps

  • Forgetting the factor of 4 on DevRTT! Jacobson's formula is RTO = EstimatedRTT + 4 × DevRTT (not + DevRTT or + 2·DevRTT).
  • Read the question's α and β carefully! While the RFC defaults are α = 0.125, β = 0.25, some GATE questions specify α = 0.1 or α = 0.2 to make decimal arithmetic easy — always use the given values!

Memory Hook

Est_new = Est + (Sample − Est)/8; RTO = Est + 4·Dev; Karn skips retransmitted samples and doubles RTO on timeout!

Connect the Dots

Now we reach the crown jewel of Phase 4 — and the #1 most-asked numerical topic in Transport Layer on GATE! Next lesson (4.3.5): How does TCP detect and control network congestion using AIMD, Fast Retransmit, and Tahoe vs Reno?

Self-Test

  1. NAT

    A TCP connection has EstimatedRTT = 200 ms. A new SampleRTT of 120 ms is measured (for a segment that was not retransmitted). Using α = 0.125, what is the updated EstimatedRTT in ms?

    Write your answer before opening the key.

  2. NAT

    At a given instant, a TCP connection has EstimatedRTT = 150 ms and DevRTT = 30 ms. According to Jacobson’s formula, what is the Retransmission Timeout (RTO) in ms?

    Write your answer before opening the key.

  3. MCQ

    Why does Karn’s algorithm forbid updating EstimatedRTT from the ACK of a retransmitted TCP segment?

    1. Because retransmitted segments travel over a different physical layer.
    2. Because of retransmission ambiguity: the sender cannot tell whether the arriving ACK corresponds to the original transmission or the retransmission.
    3. Because retransmitted segments do not carry sequence numbers.
    4. Because DevRTT is always zero during retransmissions.
  4. NAT

    A TCP sender has an initial RTO of 300 ms. A segment experiences 2 consecutive timeouts before being acknowledged. What is the RTO (in ms) immediately after the 2nd timeout?

    Write your answer before opening the key.

Rule Card

  • EWMA: Est_new = (1 − α)·Est_old + α·Sample = Est_old + (Sample − Est_old)·α (default α = 1/8).
  • Deviation & RTO: Dev_new = (1 − β)·Dev_old + β·|Sample − Est| (default β = 1/4); RTO = Est + 4·Dev.
  • Karn's rule: ignore RTT samples from retransmitted segments; double RTO on each timeout.

Concept Ledger

  • RTO (Retransmission Timeout)
  • SampleRTT
  • EstimatedRTT (EWMA, α = 1/8)
  • DevRTT (β = 1/4)
  • Jacobson RTO = SRTT + 4·RTTVAR
  • Karn's rule
  • timer exponential back-off

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up answers

  1. The sender times out prematurely and floods the network with unnecessary duplicate retransmissions.
  2. When a segment is actually lost, the sender waits a long time before retransmitting, hurting throughput and adding delay.
  3. Because packets cross multiple routers whose queuing delays fluctuate with competing network traffic.

Self-test answers

  1. 190 — Using the shortcut: Est_new = 200 + (120 − 200)/8 = 200 − 10 = 190 ms.
  2. 270 — RTO = EstimatedRTT + 4 × DevRTT = 150 + 4(30) = 150 + 120 = 270 ms.
  3. B — A cumulative ACK carries the next expected byte number, not which transmission attempt triggered it; using it would corrupt EstimatedRTT.
    • A: Same network stack is used.
    • C: Every TCP segment carries a 32-bit sequence number.
    • D: DevRTT is nonzero and high during losses.
  4. 1200 — Karn’s exponential back-off doubles RTO on each timeout: 300 × 2² = 1200 ms.

Flashcards

  1. Write the shortcut formula for updating EstimatedRTT when α = 1/8.
    Reveal answerEst_new = Est_old + (SampleRTT − Est_old) / 8.
  2. Write Jacobson’s formula for RTO in terms of EstimatedRTT and DevRTT.
    Reveal answerRTO = EstimatedRTT + 4 × DevRTT.
  3. What are the two parts of Karn’s rule?
    Reveal answer1. Do not update RTT estimates from ACKs of retransmitted segments; 2. Double RTO on each consecutive timeout.

Exam shortcuts

  • Fast Mental Math for α = 1/8: Instead of (1 − α)·Est + α·Sample, rewrite it as Est_new = Est_old + (Sample − Est_old) / 8! And for β = 1/4: Dev_new = Dev_old + (|diff| − Dev_old) / 4! — doing EWMA calculations in your head in 5 seconds without decimals!
  • Consecutive Timeouts Formula: After k consecutive timeouts, RTO = RTO₀ × 2ᵏ. — Karn backoff questions.
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.