Build it: only the lost page (selective repeat, loss and reordering)

The postcard and the phone call again. The last lesson built a call that survives lost postcards. This one builds the version that does not waste the road when it happens, and measures the difference.

Before you start. You need Build it: the page that gets through (stop-and-wait, then a window): the same test road, the same five-byte packets, and the stop-and-wait and go-back-N senders that this lesson races against. Its idea is The page that never arrived (TCP reliable delivery): when one page in a window is lost, go-back-N resends it and everything after it, and selective repeat resends only the lost one. Python 3 is all the machine needs.

The idea in 30 seconds

A cumulative ack (“I have everything below N”) cannot say which later pages arrived, so after a loss a go-back-N sender must resend the whole window.
Selective repeat has the receiver hold pages that arrive early, ack each page by its own number, and file them in order when the gap closes; the sender gives each page its own timer and resends only pages whose clock ran out.
On the test road at 20% loss go-back-N sent 271 postcards for 100 pages and selective repeat sent 153, almost exactly the 100 plus the pages actually lost.
A page that arrives late looks lost to a receiver that discards out-of-order pages: with no loss at all but 20% of pages delayed, go-back-N sent 242 postcards for 100 pages, selective repeat 108.
Real TCP gets selective repeat by keeping its cumulative ack and adding SACK blocks (RFC 2018, October 1996), at most 4 per segment, after the 1988 proposal in RFC 1072 was never deployed.

Read the story · Skip to the numbers