The Network · Chapter 12
How is it reliable?

Chapter 11 found a path across the network, but a path is only a promise to try. Each hop along it can drop a packet when a buffer fills, deliver packets out of order when two take different routes, or even duplicate one. The network is best-effort: it carries what it can and apologises for nothing. Yet a successful file download returns its bytes whole and in order. The transport layer supplies that contract, and reports failure when it cannot complete it. This chapter builds the acknowledgement-and-retry idea at the heart of TCP.

Four ideas do the work. The message is cut into numbered segments. The receiver acknowledges the segments it gets. The sender retransmits whatever goes unacknowledged. And the receiver reassembles the segments in order, throwing away any identical duplicates. Together these mechanisms can deliver an ordered, complete message even when individual attempts lose or reorder its pieces.

Our model has synchronous rounds and intact segment contents. At the end of each round, the sender immediately learns everything the receiver holds: this is a perfect, reliable acknowledgement (ACK) return path, implemented by copying receiver state. The example channel drops and reorders, but never duplicates, and delivers a lost segment on its second attempt. A different channel must recover within the default 100-round limit or delivery raises an error. We model one buffered message, not a persistent TCP byte stream, timers, or ACK loss.

12.1 Segments and sequence numbers

The first step is to cut the message into pieces small enough to send, and to number them. The number is the whole trick: it travels with the segment, so however the pieces arrive, jumbled or repeated, the receiver can put them back in the right order. Figure 12.2 shows a short message cut into four numbered segments.

The interactive version needs the in-browser runtime.

Reassembly is the inverse, and the sequence numbers make it almost trivial. Indexing the received segments by their number does two jobs at once: it discards duplicates, since a repeated segment simply overwrites itself with the same data, and it makes ordering a matter of sorting the numbers.

Example 12-1. Reassembling segments in order

def reassemble(segments) -> bytes:
    """Put received segments back into one message, in sequence order, discarding
    any duplicates."""
    by_seq = {seg.seq: seg.data for seg in segments}1
    return b"".join(by_seq[seq] for seq in sorted(by_seq))2

• indexing by sequence number quietly discards duplicates: a segment that arrives twice just overwrites itself with identical data
• sorting the sequence numbers restores the original order, no matter what order the segments arrived in

12.2 Acknowledge and retransmit

Numbering handles reordering and repeated identical segments. Loss needs more, because a lost segment never arrives to be sorted. The receiver must tell the sender what it has, and the sender must resend what is missing. The receiver acknowledges every segment it holds; the sender, each round, retransmits exactly the segments not yet acknowledged, until none remain or the round limit is reached.

Example 12-2. The reliable-delivery loop

def deliver(message: bytes, channel, size: int = 4, max_rounds: int = 100,
            trace: list = None) -> bytes:
    """Deliver one complete message or fail at the round limit.

    The sender retransmits any segment not yet acknowledged; the receiver buffers
    segments by sequence number and acknowledges every one it holds. The loop ends
    when all segments are acknowledged. The channel may drop, reorder, or repeat
    intact outgoing segments; ACKs are immediate and reliable. If a list is passed
    as `trace`, a per-round record is appended to it. RuntimeError reports failure
    to finish within max_rounds; it does not imply permanent failure of the link.
    """
    outgoing = segment(message, size)
    received = {}   # seq -> Segment, the receiver's buffer
    acked = set()   # seqs the sender has heard acknowledged
    rounds = 0
    while len(acked) < len(outgoing):
        rounds += 1
        if rounds > max_rounds:
            raise RuntimeError(
                "delivery did not finish within the round limit")
        in_flight = [seg for seg in outgoing if seg.seq not in acked]1
        arrived = channel.transmit(in_flight)
        for seg in arrived:
            received[seg.seq] = seg
        acked = set(received)  # Perfect, immediate return path in this model.2
        if trace is not None:
            trace.append({
                "sent": [seg.seq for seg in in_flight],
                "arrived": [seg.seq for seg in arrived],
                "have": sorted(received),
            })
    return reassemble(received.values())

• retransmission: every round sends exactly the segments the sender has not heard acknowledged, so a lost segment is simply sent again
• the perfect ACK return path: copying the receiver’s sequence numbers tells the sender what arrived, so it stops resending them. When the acknowledged set covers every segment, delivery is done.

Figure 12.3 traces the exchange in time, using three segments for clarity. The sender sends its segments; one is lost in the channel; the receiver acknowledges the two that arrived; the sender retransmits only the missing one; a final acknowledgement ends it. With this perfect feedback, an arrived segment is never resent. If a segment stays missing past the round limit, the call fails instead of returning a partial message.

Here the receiver names every segment it holds, a selective acknowledgement. The real protocols do it differently. TCP uses a cumulative acknowledgement, a single number meaning everything up to here has arrived, rather than naming each segment, with optional selective information. Its ACKs can also be lost, so a sender may retransmit data that already arrived. Timers and failure handling are part of real delivery.¹ Our loop’s result has a narrower promise: when it succeeds under the stated channel contract, the returned message is complete and ordered. Retrying cannot guarantee success through a permanent outage.

12.3 The transport, run

Running ftb.transport delivers a message over a channel that drops half the segments on their first try and reorders the rest, then recovers.

message: b'HELLO, NETWORK!'
split into 4 segments:
  seq 0: b'HELL'
  seq 1: b'O, N'
  seq 2: b'ETWO'
  seq 3: b'RK!'

delivering over a lossy, reordering channel:
round  sent          arrived     receiver has
  1    [0, 1, 2, 3]  [3, 1]      [1, 3]
  2    [0, 2]        [2, 0]      [0, 1, 2, 3]

reassembled: b'HELLO, NETWORK!'
matches the original: True

In the first round the channel drops the even-numbered segments and delivers the odd ones, reordered. The sender, hearing only those acknowledged, retransmits the two it is still missing, and the second round delivers them. The receiver reassembles all four into the original message, which the final line confirms. The channel was unreliable at every step; the message arrived intact anyway.

We can now recover a complete message when the channel recovers; the next chapter asks what its bytes actually say.

Exercises

• Make the channel drop every segment. Set max_rounds to 3 when calling deliver, and observe the failure.
• Hand the receiver its segments out of order, and confirm it puts them back in place.