Retransmission Timeout Estimation and Karn's Algorithm

A sender that never receives an acknowledgement has to decide when to give up and retransmit. Set the timer too short and every mildly delayed packet is duplicated, which wastes bandwidth and, worse, triggers congestion responses that reduce the sending rate for a loss that never happened. Set it too long and a genuinely lost segment stalls the connection for the full interval.

The interval cannot be a constant, because round-trip times on the public Internet span roughly three orders of magnitude: a same-datacentre path completes a round trip in well under a millisecond, a satellite path in hundreds of milliseconds, and a path through a congested cellular network varies by tens of milliseconds from one second to the next. The timer must adapt, and it must adapt in a way that does not amplify noise.

From a sample to an interval

The input is one measurement per acknowledgement: the time between sending a segment and receiving the acknowledgement that covers it. Call it R. The output is a timeout RTO.

Using a running mean of R alone is not enough. If the mean is 100 ms and the timeout is set to the mean, roughly half of all segments would time out, because half of the samples exceed the mean. The timeout must exceed the mean by enough to cover the spread, and the spread is itself variable: a path with a stable 100 ms delay needs a smaller margin than a path whose delay alternates between 50 ms and 150 ms, even though both have the same mean.

RFC 6298 specifies an exponentially weighted moving average for both the mean and the mean deviation:

/* State per connection, in seconds. */
struct rtt_state {
    double srtt;      /* smoothed round-trip time */
    double rttvar;    /* round-trip time variation */
    int    have_rtt;  /* whether srtt has been initialised */
};

void rtt_sample(struct rtt_state *s, double r) {
    if (!s->have_rtt) {
        s->srtt   = r;
        s->rttvar = r / 2.0;
        s->have_rtt = 1;
        return;
    }
    /* rttvar is updated first, using the old srtt, then srtt is updated. */
    double err = s->srtt - r;
    if (err < 0) err = -err;
    s->rttvar = 0.75 * s->rttvar + 0.25 * err;
    s->srtt   = 0.875 * s->srtt + 0.125 * r;
}

#define G 0.001   /* clock granularity, in the same units as the estimates */

double rto(const struct rtt_state *s) {
    double var = 4.0 * s->rttvar;
    if (var < G) var = G;
    double v = s->srtt + var;
    if (v < 0.200) v = 0.200;   /* sub-second floor; RFC 6298 rounds up to 1 s */
    if (v > 60.0)  v = 60.0;    /* cap; RFC 6298 permits one of at least 60 s */
    return v;
}

Three details in that code carry the design.

The gains are 1/8 for the mean and 1/4 for the deviation, so the deviation tracks changes about twice as fast as the mean. This is deliberate. When a path’s delay suddenly doubles, the mean moves slowly but the deviation jumps immediately, and since the deviation enters the timeout multiplied by four, the timeout widens before the mean has caught up. The system errs toward waiting too long rather than retransmitting too early, which is the correct direction: a spurious retransmission costs a duplicate segment and a rate reduction, while a late retransmission costs only the extra delay.

The update order matters. The deviation is computed against the old smoothed mean, before that mean absorbs the new sample. Computing the deviation against the already-updated mean understates the error, because the new sample has just been partly absorbed into that mean and the gap between them has shrunk. The understatement is modest per sample, but it is systematic: it applies to every sample in the same direction, so the deviation estimate settles below the true spread by a fixed fraction — with alpha at 1/8, roughly an eighth — and the timeout sits closer to the mean than the variance term intends. That is exactly the regime the variance term exists to prevent, so the ordering is not a matter of style.

The lower bound is a floor, not an optimisation. RFC 6298 recommends rounding any computed value below one second up to one second, on the argument that a large minimum keeps the sender conservative and suppresses spurious retransmissions. The computed value itself takes the variance term as at least the clock granularity, because a timer cannot distinguish intervals shorter than its own tick. Implementations that need sub-second timeouts depart from the recommendation, and a floor in the low hundreds of milliseconds is the usual choice on paths where one second would be far longer than the round trip.

Why a retransmitted segment cannot be timed

Suppose a segment is sent at time 0 and lost. The sender retransmits at time 200 ms. The acknowledgement arrives at 300 ms. Was the sample 300 ms, or 100 ms?

There is no way to tell from the acknowledgement alone, because the acknowledgement field says only “all bytes below this number have arrived” and carries no indication of which transmission produced them. If the original arrived and its acknowledgement was merely delayed, the true sample is 300 ms. If the original was lost and the retransmission produced the acknowledgement, the true sample is 100 ms. The two possibilities are indistinguishable, and they differ by a factor of three.

Karn’s algorithm resolves this by refusing to decide: never take an RTT sample from a segment that has been retransmitted. This discards information, but the discarded information is not merely noisy, it is biased. A sender that timed every retransmitted segment would have to choose which transmission to measure from, while the acknowledgement may have been produced by either. Measured from the original transmission, a sample for a segment whose first copy was lost includes the whole timeout interval, so the estimate drifts upward; and because the estimate produces the timeout, an overestimate lengthens the next interval, which inflates the next such sample. The protocol avoids that loop by taking no sample at all for those segments.

The cost is that on a path that is losing segments constantly, almost no samples are usable and the estimate freezes at whatever it was before the loss began. Karn’s algorithm is paired with an exponential backoff that doubles the timeout on each successive retransmission of the same segment, so the frozen estimate is at least scaled by the observed failure. RFC 6298 permits a cap on that doubling of at least 60 seconds, and requires the timer to be restarted when an acknowledgement advances SND.UNA: the interval runs from the most recent transmission attempt, not the first.

Two extensions soften the information loss. The timestamp option, covered in Timestamps, RTTM, and Protection Against Wrapped Sequences, lets the sender compute a round trip for a specific transmission even when the segment was retransmitted, because the echoed timestamp identifies which transmission the acknowledgement refers to. And the Eifel detection logic uses exactly that timestamp to distinguish a spurious retransmission from a real one after the fact, which allows the sender to undo the congestion response it applied to a loss that never happened.

The timer that is really a queue

A connection does not have one timer. It has one timer for the oldest unacknowledged segment, and restarting that timer is the whole of the mechanism: when an acknowledgement advances SND.UNA, the timer is rearmed with a fresh RTO and now covers the new oldest segment. When the timer fires, the sender retransmits that segment and doubles the interval.

This is why the timer is often described as being attached to the left edge of the window rather than to any particular segment. It is a consequence of the cumulative acknowledgement: the receiver’s acknowledgement of byte n implies receipt of every byte below n, so the sender’s outstanding range has a single well-defined left edge, and the oldest unacknowledged byte is the only one whose fate is unknown at the granularity the timer cares about.

The arrangement has one weakness. If the oldest segment is lost and the segments after it arrive, the receiver keeps acknowledging the same value, the timer keeps covering the same segment, and the sender learns nothing until the timer fires. Recovery takes one full timeout. The mechanisms that avoid this wait are treated in SACK Blocks and the Retransmission Queue: duplicate acknowledgements provide an early signal, and selective acknowledgement tells the sender which later segments did arrive, so the lost one can be resent without waiting for the timer at all.

Measurement error and the limits of the estimate

Every RTT sample is itself a coarse measurement. The timestamp used is taken when the segment is handed to the network stack, not when it leaves the wire, so it includes any queueing delay in the sender’s own device driver. On the receiving side, the acknowledgement is generated either by the kernel immediately or after a delayed-acknowledgement timer of up to about 500 ms, and the sender cannot distinguish the two cases. A single sample can therefore be inflated by nearly half a second by a receiver that happened to batch its acknowledgement.

The smoothing is what makes this tolerable. A single 500 ms outlier moves a 100 ms estimate by 0.125 × 400 = 50 ms, and the next clean sample moves it back by a similar amount. The variance term absorbs the rest. But the filter has a settling time measured in several samples, and a path whose delay changes abruptly will be mis-estimated for that interval. The delayed-acknowledgement interaction, and the way it distorts both the timer and the sender’s segmentation decisions, is examined in Nagle’s Algorithm and the Delayed Acknowledgement Deadlock.

The upper bound is a permission rather than a requirement. RFC 6298 allows a cap on the computed value provided it is at least 60 seconds, and the same cap may be applied to the exponential backoff: each expiry doubles the interval, and the doubling stops once the cap is reached. The specification also allows an implementation to discard its smoothed average and variance entirely after several backoffs, on the argument that the samples behind them describe a path that is no longer delivering.