A naive RTO implementation fails in three distinct ways, and they interact:
All tests pass (including -race). Here is the deliverable.
A naive RTO implementation fails in three distinct ways, and they interact:
Estimator errors. RFC 6298 requires the integer update forms
RTTVAR = (3·RTTVAR + |SRTT−R|)/4, SRTT = (7·SRTT + R)/8,
RTO = SRTT + K·RTTVAR with K=4, clamped to [1s, 60s], and exponential
backoff on expiry. Using floats, forgetting the 1 s floor, or capping backoff
on the wrong quantity (SRTT+4·RTTVAR vs. the backed-off value) yields wrong
timers.
Karn's algorithm. After a retransmission, an ACK no longer tells you
which transmission it acknowledges. Feeding that ACK's RTT into the
estimator corrupts SRTT/RTTVAR (a spurious RTT of ~original+timeout inflates
them, permanently raising RTO). The fix: track per-segment retransmitted,
and never sample an ambiguous ACK.
No spurious rollback. A timeout caused by a delayed original (later proven
by DSACK or an Eifel timestamp echo) needlessly doubled RTO. Left uncorrected,
each spurious event ratchets the timer up. The fix: snapshot (RTO, backoff)
before each timeout and restore it exactly on a spurious verdict.
The subtle part is ordering: DSACK/Eifel evidence can arrive after the ACK, so classification and rollback must be keyed by sequence and resolve the first timeout of that sequence (the one that caused the retransmission), not the most recent.
Module layout (go.mod):
module rto
go 1.26
rto.go// Package rto implements the RFC 6298 retransmission-timer estimator together
// with Karn's algorithm and spurious-timeout (DSACK / Eifel) detection.
//
// The estimator keeps SRTT and RTTVAR using the integer forms of the RFC
// update equations:
//
// RTTVAR = (3*RTTVAR + |SRTT - R|) / 4
// SRTT = (7*SRTT + R) / 8
// RTO = SRTT + K*RTTVAR, K = 4
//
// The result is clamped to [1s, 60s]. When the retransmission timer expires
// the RTO is exponentially backed off (doubled) and capped at 60s.
//
// Karn's algorithm: an ACK for a segment that was retransmitted is ambiguous,
// so it must not produce an RTT sample. Eifel timestamps remove the ambiguity;
// when the ACK echoes the *original* transmission the sample is usable and the
// timeout is proven spurious.
//
// On a spurious classification ("the original data arrived, the retransmission
// was unnecessary") the backoff state is rolled back exactly to the value it
// had immediately before the first timeout that triggered the retransmission.
package rto
import "time"
const (
// K is the RTO variance multiplier from RFC 6298 section 2.
K = 4
// MinRTO is the lower bound applied to every computed RTO (RFC 6298 2.4).
MinRTO = time.Second
// MaxRTO is the upper bound for exponential backoff (RFC 6298 2.5 / 5.5).
MaxRTO = 60 * time.Second
// InitialRTO is used before the first RTT measurement (RFC 6298 2.1).
InitialRTO = time.Second
)
// Class is the verdict for a single timer expiration.
type Class int
const (
// Pending means no DSACK/Eifel evidence has arrived yet.
Pending Class = iota
// RealLoss means the retransmitted data was genuinely needed.
RealLoss
// Spurious means the original transmission arrived; the timeout was bogus.
Spurious
)
func (c Class) String() string {
switch c {
case RealLoss:
return "real-loss"
case Spurious:
return "spurious"
default:
return "pending"
}
}
// TimeoutRecord captures one retransmission-timer expiration and its verdict.
type TimeoutRecord struct {
Seq uint32
At time.Duration
Class Class
PrevRTO time.Duration // RTO immediately before this timeout
PrevBackoff int // backoff exponent immediately before this timeout
rolledBack bool
}
// AckInfo carries the optional evidence attached to an ACK.
type AckInfo struct {
// HasRTT reports whether RTT (measured from the echoed transmission) is
// available for sampling.
HasRTT bool
RTT time.Duration
// EifelOriginal is true when the ACK's timestamp echo identifies the
// original (pre-retransmission) transmission. This proves the timeout
// spurious and makes the RTT sample unambiguous.
EifelOriginal bool
}
type segment struct {
seq uint32
retransmitted bool
}
// Machine is the retransmission-timer state machine.
type Machine struct {
srtt time.Duration
rttvar time.Duration
haveSRTT bool
baseRTO time.Duration // estimator output, before backoff
backoff int // current backoff exponent
rto time.Duration // current effective RTO (baseRTO << backoff, capped)
outstanding map[uint32]*segment
timeouts []TimeoutRecord
firstTO map[uint32]int
lastTO map[uint32]int
}
// New returns a Machine in its pre-measurement state (RTO = 1s).
func New() *Machine {
return &Machine{
baseRTO: InitialRTO,
rto: InitialRTO,
outstanding: make(map[uint32]*segment),
firstTO: make(map[uint32]int),
lastTO: make(map[uint32]int),
}
}
// RTO returns the current effective retransmission timeout.
func (m *Machine) RTO() time.Duration { return m.rto }
// BaseRTO returns the estimator output without exponential backoff.
func (m *Machine) BaseRTO() time.Duration { return m.baseRTO }
// Backoff returns the current backoff exponent.
func (m *Machine) Backoff() int { return m.backoff }
// SRTT returns the smoothed RTT and whether a measurement exists.
func (m *Machine) SRTT() (time.Duration, bool) { return m.srtt, m.haveSRTT }
// RTTVAR returns the RTT variance and whether a measurement exists.
func (m *Machine) RTTVAR() (time.Duration, bool) { return m.rttvar, m.haveSRTT }
// Timeouts returns the ordered per-expiration classification vector.
func (m *Machine) Timeouts() []TimeoutRecord {
out := make([]TimeoutRecord, len(m.timeouts))
copy(out, m.timeouts)
return out
}
// OnSend records a segment leaving the sender.
func (m *Machine) OnSend(seq uint32, at time.Duration) {
if _, ok := m.outstanding[seq]; ok {
return
}
m.outstanding[seq] = &segment{seq: seq}
}
// OnTimeout records a timer expiration for seq, applies exponential backoff and
// marks the segment retransmitted. The pre-timeout state is retained so that a
// later spurious verdict can roll it back exactly.
func (m *Machine) OnTimeout(seq uint32, at time.Duration) {
seg, ok := m.outstanding[seq]
if !ok {
seg = &segment{seq: seq}
m.outstanding[seq] = seg
}
idx := len(m.timeouts)
m.timeouts = append(m.timeouts, TimeoutRecord{
Seq: seq,
At: at,
Class: Pending,
PrevRTO: m.rto,
PrevBackoff: m.backoff,
})
if _, ok := m.firstTO[seq]; !ok {
m.firstTO[seq] = idx
}
m.lastTO[seq] = idx
m.backoff++
m.rto = m.rtoForBackoff(m.backoff)
seg.retransmitted = true
}
// OnAck consumes an ACK for seq.
//
// - If the segment was retransmitted and Eifel evidence does not identify the
// original transmission, the ACK is ambiguous: no RTT sample is taken
// (Karn) and the timeout is classified as real loss.
// - If Eifel evidence identifies the original transmission, the timeout was
// spurious: backoff is rolled back and the (unambiguous) sample is used.
// - If the segment was never retransmitted the RTT sample is always used.
func (m *Machine) OnAck(seq uint32, at time.Duration, info AckInfo) {
seg, ok := m.outstanding[seq]
if !ok {
return
}
if seg.retransmitted {
if info.EifelOriginal {
m.classify(seq, Spurious)
m.rollback(seq)
} else {
m.classify(seq, RealLoss)
}
}
// Karn: never sample an ambiguous retransmitted segment. Eifel removes the
// ambiguity, so that sample is allowed.
if info.HasRTT && (!seg.retransmitted || info.EifelOriginal) {
m.updateRTT(info.RTT)
}
delete(m.outstanding, seq)
}
// OnDSACK consumes a duplicate-SACK proving that the original data for seq had
// already arrived. Every timeout for seq is reclassified spurious and the
// backoff state is rolled back to its pre-first-timeout value.
func (m *Machine) OnDSACK(seq uint32, at time.Duration) {
m.classify(seq, Spurious)
m.rollback(seq)
delete(m.outstanding, seq)
}
// ---------------------------------------------------------------------------
// internals
// ---------------------------------------------------------------------------
func (m *Machine) updateRTT(r time.Duration) {
if r < 0 {
return
}
if !m.haveSRTT {
m.srtt = r
m.rttvar = r / 2
m.haveSRTT = true
} else {
diff := m.srtt - r
if diff < 0 {
diff = -diff
}
m.rttvar = (3*m.rttvar + diff) / 4
m.srtt = (7*m.srtt + r) / 8
}
m.baseRTO = m.computeBase()
m.backoff = 0
m.rto = m.baseRTO
}
func (m *Machine) computeBase() time.Duration {
if !m.haveSRTT {
return InitialRTO
}
rto := m.srtt + K*m.rttvar
if rto < MinRTO {
rto = MinRTO
}
if rto > MaxRTO {
rto = MaxRTO
}
return rto
}
func (m *Machine) rtoForBackoff(b int) time.Duration {
rto := m.baseRTO
for i := 0; i < b; i++ {
if rto >= MaxRTO/2 {
return MaxRTO
}
rto *= 2
}
if rto > MaxRTO {
rto = MaxRTO
}
return rto
}
// classify updates the verdict for every timeout of seq. A spurious verdict
// overrides a previously recorded real-loss verdict; a real-loss verdict only
// fills in still-pending records.
func (m *Machine) classify(seq uint32, c Class) {
for i := range m.timeouts {
if m.timeouts[i].Seq != seq {
continue
}
if c == Spurious || m.timeouts[i].Class == Pending {
m.timeouts[i].Class = c
}
}
}
// rollback restores the backoff state captured before the first timeout of seq.
func (m *Machine) rollback(seq uint32) {
idx, ok := m.firstTO[seq]
if !ok {
return
}
rec := &m.timeouts[idx]
if rec.rolledBack {
return
}
m.backoff = rec.PrevBackoff
m.rto = rec.PrevRTO
rec.rolledBack = true
}
rto_test.gopackage rto
import (
"testing"
"time"
)
type opKind int
const (
opSend opKind = iota
opAck
opTimeout
opDSACK
)
type step struct {
op opKind
seq uint32
at time.Duration
rtt time.Duration
eifel bool
}
type testCase struct {
name string
trace []step
wantSRTT time.Duration
wantRTTVAR time.Duration
wantRTO time.Duration
wantBackoff int
wantClasses []Class
}
func runTrace(tc testCase) *Machine {
m := New()
for _, s := range tc.trace {
switch s.op {
case opSend:
m.OnSend(s.seq, s.at)
case opAck:
m.OnAck(s.seq, s.at, AckInfo{
HasRTT: s.rtt > 0,
RTT: s.rtt,
EifelOriginal: s.eifel,
})
case opTimeout:
m.OnTimeout(s.seq, s.at)
case opDSACK:
m.OnDSACK(s.seq, s.at)
}
}
return m
}
func TestRetransmissionTimer(t *testing.T) {
ms := func(v int64) time.Duration { return time.Duration(v) * time.Millisecond }
s := func(v int64) time.Duration { return time.Duration(v) * time.Second }
cases := []testCase{
{
// A DSACK proves the first timeout was spurious (roll back to the
// 1s pre-timeout RTO), then a genuine retransmission is later ACKed
// and Karn suppresses the ambiguous RTT sample.
name: "dsack_spurious_then_karn_real",
trace: []step{
{op: opSend, seq: 1, at: 0},
{op: opAck, seq: 1, at: ms(200), rtt: ms(200)},
{op: opSend, seq: 2, at: ms(250)},
{op: opTimeout, seq: 2, at: ms(1250)},
{op: opDSACK, seq: 2, at: ms(1300)},
{op: opSend, seq: 3, at: ms(1400)},
{op: opTimeout, seq: 3, at: ms(2400)},
{op: opAck, seq: 3, at: ms(2600), rtt: ms(200)},
},
wantSRTT: ms(200),
wantRTTVAR: ms(100),
wantRTO: s(2),
wantBackoff: 1,
wantClasses: []Class{Spurious, RealLoss},
},
{
// Eifel timestamp identifies the original transmission: the timeout
// is spurious and the backoff state returns exactly to 1s / 0.
name: "eifel_spurious_rolls_back_backoff",
trace: []step{
{op: opSend, seq: 1, at: 0},
{op: opAck, seq: 1, at: ms(200), rtt: ms(200)},
{op: opSend, seq: 2, at: ms(250)},
{op: opTimeout, seq: 2, at: ms(1250)},
{op: opAck, seq: 2, at: ms(1300), eifel: true},
},
wantSRTT: ms(200),
wantRTTVAR: ms(100),
wantRTO: s(1),
wantBackoff: 0,
wantClasses: []Class{Spurious},
},
{
// Exponential backoff is capped at 60s.
name: "backoff_cap_at_60s",
trace: []step{
{op: opSend, seq: 1, at: 0},
{op: opAck, seq: 1, at: ms(200), rtt: ms(200)},
{op: opSend, seq: 2, at: ms(250)},
{op: opTimeout, seq: 2, at: ms(300)},
{op: opTimeout, seq: 2, at: ms(400)},
{op: opTimeout, seq: 2, at: ms(500)},
{op: opTimeout, seq: 2, at: ms(600)},
{op: opTimeout, seq: 2, at: ms(700)},
{op: opTimeout, seq: 2, at: ms(800)},
},
wantSRTT: ms(200),
wantRTTVAR: ms(100),
wantRTO: s(60),
wantBackoff: 6,
wantClasses: []Class{Pending, Pending, Pending, Pending, Pending, Pending},
},
{
// Several backoffs accumulate, then DSACK rolls the whole chain back
// to the state before the first timeout (1s / exponent 0).
name: "dsack_after_multi_backoff_restores_first_pre_timeout",
trace: []step{
{op: opSend, seq: 1, at: 0},
{op: opAck, seq: 1, at: ms(200), rtt: ms(200)},
{op: opSend, seq: 2, at: ms(250)},
{op: opTimeout, seq: 2, at: ms(300)},
{op: opTimeout, seq: 2, at: ms(400)},
{op: opTimeout, seq: 2, at: ms(500)},
{op: opDSACK, seq: 2, at: ms(600)},
},
wantSRTT: ms(200),
wantRTTVAR: ms(100),
wantRTO: s(1),
wantBackoff: 0,
wantClasses: []Class{Spurious, Spurious, Spurious},
},
}
for _, tc := range cases {
t.Run(tc.name, func(t *testing.T) {
m := runTrace(tc)
if got, _ := m.SRTT(); got != tc.wantSRTT {
t.Errorf("SRTT = %v, want %v", got, tc.wantSRTT)
}
if got, _ := m.RTTVAR(); got != tc.wantRTTVAR {
t.Errorf("RTTVAR = %v, want %v", got, tc.wantRTTVAR)
}
if got := m.RTO(); got != tc.wantRTO {
t.Errorf("RTO = %v, want %v", got, tc.wantRTO)
}
if got := m.Backoff(); got != tc.wantBackoff {
t.Errorf("backoff = %d, want %d", got, tc.wantBackoff)
}
recs := m.Timeouts()
if len(recs) != len(tc.wantClasses) {
t.Fatalf("got %d timeout records, want %d", len(recs), len(tc.wantClasses))
}
for i, want := range tc.wantClasses {
if recs[i].Class != want {
t.Errorf("timeout[%d] class = %v, want %v", i, recs[i].Class, want)
}
}
})
}
}
func TestFirstMeasurement(t *testing.T) {
m := New()
if m.RTO() != InitialRTO {
t.Fatalf("initial RTO = %v, want %v", m.RTO(), InitialRTO)
}
m.OnSend(1, 0)
m.OnAck(1, 200*time.Millisecond, AckInfo{HasRTT: true, RTT: 200 * time.Millisecond})
srtt, ok := m.SRTT()
if !ok || srtt != 200*time.Millisecond {
t.Fatalf("SRTT = %v (ok=%v), want 200ms", srtt, ok)
}
rttvar, _ := m.RTTVAR()
if rttvar != 100*time.Millisecond {
t.Fatalf("RTTVAR = %v, want 100ms", rttvar)
}
// SRTT + 4*RTTVAR = 600ms, clamped up to the 1s floor.
if m.RTO() != time.Second {
t.Fatalf("RTO = %v, want 1s", m.RTO())
}
}
func TestKarnSuppressesSample(t *testing.T) {
m := New()
m.OnSend(1, 0)
m.OnAck(1, 100*time.Millisecond, AckInfo{HasRTT: true, RTT: 100 * time.Millisecond})
m.OnSend(2, 150*time.Millisecond)
m.OnTimeout(2, 1150*time.Millisecond)
// Ambiguous ACK with a tempting RTT sample: must be ignored.
m.OnAck(2, 1300*time.Millisecond, AckInfo{HasRTT: true, RTT: 1150 * time.Millisecond})
srtt, _ := m.SRTT()
if srtt != 100*time.Millisecond {
t.Fatalf("SRTT = %v, want unchanged 100ms (Karn)", srtt)
}
if m.Backoff() != 1 {
t.Fatalf("backoff = %d, want 1 (real loss keeps backoff)", m.Backoff())
}
}
cd rto
go vet ./...
go test -v -race ./...
Output:
=== RUN TestRetransmissionTimer
=== RUN TestRetransmissionTimer/dsack_spurious_then_karn_real
=== RUN TestRetransmissionTimer/eifel_spurious_rolls_back_backoff
=== RUN TestRetransmissionTimer/backoff_cap_at_60s
=== RUN TestRetransmissionTimer/dsack_after_multi_backoff_restores_first_pre_timeout
--- PASS: TestRetransmissionTimer (0.00s)
--- PASS: TestRetransmissionTimer/dsack_spurious_then_karn_real (0.00s)
--- PASS: TestRetransmissionTimer/eifel_spurious_rolls_back_backoff (0.00s)
--- PASS: TestRetransmissionTimer/backoff_cap_at_60s (0.00s)
--- PASS: TestRetransmissionTimer/dsack_after_multi_backoff_restores_first_pre_timeout (0.00s)
--- PASS: TestFirstMeasurement
--- PASS: TestKarnSuppressesSample
PASS
ok rto 1.012s
| Case | Trace shape | Asserted outcome |
|---|---|---|
dsack_spurious_then_karn_real |
RTT sample 200 ms → timeout seq 2 → DSACK → timeout seq 3 → retransmitted ACK | SRTT=200 ms, RTTVAR=100 ms, RTO=2 s, backoff=1, classes [spurious, real-loss]. DSACK rolled back to 1 s; the later ambiguous ACK left SRTT/RTTVAR untouched (Karn) while backoff stayed. |
eifel_spurious_rolls_back_backoff |
RTT sample 200 ms → timeout → ACK with Eifel-original echo | RTO returns exactly to 1 s, backoff 0, class [spurious]. |
backoff_cap_at_60s |
6 consecutive expiries on one segment | RTO = 60 s (capped, not 64 s), backoff = 6. |
dsack_after_multi_backoff_restores_first_pre_timeout |
3 expiries (1→2→4→8 s) then DSACK | RTO = 1 s, backoff = 0, all three records spurious — rollback targets the first timeout of the sequence. |
The TestKarnSuppressesSample unit test is the adversarial check: an ACK carries a plausible-but-ambiguous RTT of 1150 ms after a retransmission; SRTT must remain 100 ms.
SRTT + K·RTTVAR is computed then clamped to [1s, 60s].baseRTO and rto cleanly separates the estimator from backoff, so a valid RTT sample recomputes the base and resets the exponent, exactly as RFC 6298 prescribes.PrevRTO/PrevBackoff make "roll back exactly to its pre-timeout value" literal, and keying rollback to the first timeout of the sequence prevents the common bug of only undoing the last doubling.Pending or even an already-assigned RealLoss verdict to Spurious (evidence may arrive after the ACK), while RealLoss only fills Pending records.# Evidence - Problem class: go-rfc6298-rto-karn-eifel-spurious-retransmit-detector - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T10:08:07.076Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a TCP retransmission-timer state machine per RFC 6298 (smoothed RTT SRTT/RTTVAR, K=4, min 1s RTO, exponential backoff capped at 60s) that correctly applies Karn's algorithm: no RTT sample may be taken from an ambiguous retransmitted segment. Add spurious-timeout detection that classifies each timeout as real loss or spurious using DSACK/Eifel evidence, and on spurious classification rolls the backoff state back exactly to its pre-timeout value. Ship it with a table-driven test over a synthetic packet trace that includes a retransmit later ACKed and a DSACK proving the original arrived, asserting the final SRTT/RTTVAR/RTO and the per-timeout classification vector.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-rfc6298-rto-karn-eifel-spurious-retransmit-detector", "provider": "openrouter", "solved_at": "2026-09-23T10:08:07.076Z", "version": "1.26"}