Acknowledgements and Retransmission

Reliable delivery over a channel that loses messages is built from three ideas: number every message, have the receiver acknowledge what it got and resend whatever was not acknowledged in time. Lantern's availability feed needs all three, so that a checkout at branch 7 is applied once and in order even when the city network drops it.

The mechanism takes one paragraph to state and is full of prices. A timeout that is too short floods the network with copies; one that is too long leaves a patron looking at a stale shelf count. A sender that waits for each reply idles on a fast link. One lost message holds up everything behind it. TCP is this mechanism, engineered and refined since its specification was published in 1981, and every service you run pays its costs as latency.

Sequence Numbers

Each branch numbers its messages 1, 2, 3 and so on, and the numbering belongs to the branch, not to the network. On the receiving side a gap shows a loss, a repeated number shows a duplicate, and a lower number arriving after a higher one shows reordering. Lantern keeps one number per branch, the highest it has applied, and judges every arriving message against it.

Branch 7's last applied message is 118. Message 119 is the next one, so Lantern applies it and moves the mark to 119. Message 118 arriving again is at or below the mark, so it is a duplicate and Lantern drops it without touching the shelf count. Message 121 skips 120, so Lantern knows 120 is missing and holds 121 until the gap is filled.

last_applied = {}          # branch -> highest sequence number applied

def receive(branch, seq, apply):
    last = last_applied.get(branch, 0)
    if seq <= last:
        return "duplicate: drop"
    if seq > last + 1:
        return f"early: {last + 1} is missing"
    apply()
    last_applied[branch] = seq
    return "new: applied"

# with last_applied[7] = 118:   119 -> new: applied   118 -> duplicate: drop   121 -> early: 120 is missing

The function is the figure in code. It looks up the branch's mark, drops anything at or below it, reports a gap for anything more than one above it, and otherwise applies the change and moves the mark. It needs one integer per sender, however many messages that sender ever sends, which is why a per-sender sequence number is the cheapest duplicate detector there is.

Acknowledgements and the Timeout

The receiver replies with a cumulative acknowledgement: "got everything up to 118". The sender keeps every message until an acknowledgement covers it, and resends a message if no acknowledgement arrives within a timeout. That one rule turns a lossy channel into a reliable one, as long as both ends keep running.

The timeout is the hard part. It must be longer than a normal round trip, or the sender resends messages that were still on their way, and shorter than anyone's patience, or a single loss stalls the feed for seconds. Real round trips vary with load, so implementations measure them continuously and set the timeout from the running average plus a margin for the variation. Van Jacobson introduced that method in 1988, and RFC 6298 standardizes it for TCP with a recommended floor of one second. Linux uses a floor of 200 milliseconds.

Stop-and-Wait and Its Ceiling

The simplest correct protocol sends one message, waits for its acknowledgement and only then sends the next. It is correct, and it is slow in a way no hardware can fix. Across a 50-millisecond round trip the sender gets 20 turns a second. With 1,500-byte packets that is 30 kilobytes a second, or 240 kilobits a second: 0.024 percent of a 1-gigabit link. Upgrade the link to 10 gigabits and the transfer takes exactly as long.

The left half of the figure is stop-and-wait: one packet crosses, its acknowledgement crosses back, and the link sits idle for the rest of the round trip. The right half keeps eight packets in flight, so eight arrive in the time one did. A link's capacity is set by its bandwidth, and the protocol's by how much it lets travel at once divided by the round trip.

The Sliding Window

The fix is to let the sender have up to N unacknowledged messages in flight: a window over the numbered stream. As acknowledgements arrive, the window's left edge moves right and new messages may be sent. To fill a link, the window must cover the bandwidth-delay product, the amount of data that fits in the pipe during one round trip. For 1 gigabit a second and 50 milliseconds, that is 6.25 megabytes, about 4,170 packets of 1,500 bytes.

In the figure, messages up to 118 are acknowledged, 119 to 124 are in flight, and 125 and 126 may be sent now because they still fit in the window of eight. When a message is lost, the sender has two choices. Go-back-N resends everything after the gap, which is simple and wastes the copies that had arrived. Selective repeat resends only the missing message, which needs the receiver to buffer what came early and to acknowledge messages individually.

Head-of-Line Blocking

A receiver that must deliver in order cannot hand over message 122 while 121 is missing. Everything after the gap waits for the retransmission, so one lost packet stalls the whole stream for at least a round trip, or for a full timeout when the loss was the last packet and nothing arrives to reveal the gap.

This is why HTTP/2, which carries many requests over one TCP connection, stalls all of them together when a single packet is lost on a lossy mobile link: TCP has one order for the whole connection. QUIC, the transport under HTTP/3, runs over UDP and keeps a separate order for each stream, so a loss holds up only the stream it belongs to.

The Idea TCP Is Built On, and Its Price

TCP numbers bytes rather than messages, acknowledges cumulatively, estimates its timeout from measured round trips, and slides a window. That sentence is the recognition. The protocol itself, with its handshake and its forty-five years of refinements, is covered in the Transport Layer chapter of Networking Deep Dive, in its topics on acknowledgements and retransmission and on flow control and the sliding window.

The price in systems you run is latency, not loss. A lost packet costs a round trip at best and a full retransmission timeout at worst. On a service whose median response is 2 milliseconds, once more than one request in a hundred meets a lost packet and a 200-millisecond timeout, the 99th percentile sits in the hundreds of milliseconds, with nothing in the service's own code to explain it.