The transport layer I: UDP and reliable data transfer

The network layer moves datagrams between hosts, with no promises: datagrams can be lost, corrupted, duplicated or delivered out of order. The transport layer turns this into a service between processes. At a minimum it multiplexes and demultiplexes data to the right socket, using port numbers. UDP does that and little else. TCP and QUIC go much further and provide reliable, in-order delivery over the unreliable network. This lesson looks first at UDP and its checksum, then builds up the principles of reliable data transfer step by step: acknowledgements, timeouts, sequence numbers and pipelining with Go-Back-N and Selective Repeat. Lesson 7 shows how TCP puts these principles into practice and adds flow control and congestion control.

Multiplexing and demultiplexing

A host may run dozens of processes using the network at once. When a segment arrives, the transport layer must deliver it to the right socket. For UDP, a socket is identified by the destination IP address and destination port alone: datagrams from different senders to the same port all arrive at the same socket, and the application learns each sender's address from recvfrom. For TCP, a connected socket is identified by all four values: source address, source port, destination address and destination port. That is how a web server's port 443 can have thousands of simultaneous connections, each delivered to its own socket. Lesson 5 showed both behaviours in running code.

UDP: the minimal transport

UDP, defined in RFC 768 in 1980 and only three pages long, adds an 8-byte header to the application's data: source port, destination port, length and checksum. It offers no connection setup, no reliability, no ordering, no flow control and no congestion control. That sounds like a list of defects, but it is often exactly what an application wants. There is no handshake delay, so a DNS query and reply take one round trip. There is no connection state, so a server can handle many more clients. Header overhead is small. And the application controls exactly when data is sent: a voice call would rather skip a late packet than wait for its retransmission.

Applications built on UDP include DNS, the Network Time Protocol, the DHCP protocol that assigns addresses (lesson 8), streaming media and games, SNMP network management and, increasingly, QUIC, which builds its own reliability on top of UDP so that it can evolve in user space. When an application needs reliability over UDP, it must implement it itself, using the principles in the rest of this lesson.

The internet checksum

UDP, TCP and the IPv4 header all use the same error-detection code, the internet checksum (RFC 1071). The sender treats the data as a sequence of 16-bit integers, adds them using one's complement arithmetic (wrapping any carry out of the top bit back into the bottom), and sends the complement of the sum. The receiver adds everything including the checksum; if no bits were corrupted, the result is all ones, so its complement is zero. For UDP and TCP, the sum also covers a pseudo-header containing the source and destination IP addresses, the protocol number and the length, which catches datagrams delivered to the wrong host.

import struct
def internet_checksum(data: bytes) -> int:
    """16-bit one's complement of the one's complement sum (RFC 1071)."""
    if len(data) % 2:
        data += b"\x00"                       # pad odd-length data with a zero byte
    total = 0
    for (word,) in struct.iter_unpack("!H", data):
        total += word
        total = (total & 0xFFFF) + (total >> 16)   # wrap the carry around
    return ~total & 0xFFFF

src, dst = bytes([192, 168, 1, 23]), bytes([10, 0, 0, 53])
payload = b"temp=21.5"
length = 8 + len(payload)
pseudo = src + dst + struct.pack("!BBH", 0, 17, length)        # pseudo-header: addresses, protocol, length
udp = struct.pack("!HHHH", 40000, 9000, length, 0) + payload   # checksum field zero while computing
csum = internet_checksum(pseudo + udp)
print(f"UDP checksum = 0x{csum:04x}")
segment = udp[:6] + struct.pack("!H", csum) + udp[8:]
print("receiver check (should be 0):", hex(internet_checksum(pseudo + segment)))
corrupt = bytearray(segment); corrupt[-1] ^= 0x01               # flip one bit in the payload
print("after a 1-bit error:", hex(internet_checksum(pseudo + bytes(corrupt))))
swapped = segment[:8] + segment[10:12] + segment[8:10] + segment[12:]   # exchange two 16-bit words
print(f"after swapping two words (payload now {swapped[8:].decode()!r}):", hex(internet_checksum(pseudo + swapped)))

UDP checksum = 0xef38
receiver check (should be 0): 0x0
after a 1-bit error: 0x100
after swapping two words (payload now 'mpte=21.5'): 0x0

The checksum catches the single-bit error but not the swapped words, because addition is commutative: exchanging two 16-bit words leaves the sum unchanged, so the corrupted reading passes the check. The internet checksum is cheap to compute in software but weak; link layers use stronger cyclic redundancy checks (lesson 10), and TLS and QUIC add cryptographic integrity checks that catch deliberate tampering as well as accidents. Why check at the transport layer at all, if links already check? Because not every link checks, errors can occur inside routers' memory, and the end-to-end principle says that only the endpoints can verify end-to-end correctness.

Building a reliable protocol step by step

Imagine designing a protocol to deliver data reliably over a channel that can corrupt and lose packets. Following the classic presentation by Kurose and Ross, we can build it in stages, each adding one mechanism to handle one new problem.

The result of the first four stages is the alternating-bit protocol, a stop-and-wait protocol: the sender transmits a packet with sequence number 0 or 1, starts a timer and waits. If the ACK arrives intact with the right number, it sends the next packet with the other number. If the timer expires, it retransmits. The receiver delivers each new packet to the application, discards duplicates (but still acknowledges them, since the earlier ACK may have been lost) and always acknowledges the last correctly received packet. Choosing the timeout is a balancing act: too short causes needless retransmissions, too long makes recovery from loss slow. Lesson 7 shows how TCP estimates it from measured round-trip times.

The problem with stop-and-wait

Stop-and-wait is correct but slow. The sender transmits one packet, taking \(L/R\) seconds, and then sits idle for a whole round trip waiting for the acknowledgement. Its utilization, the fraction of time the sender is actually sending, is

For a 1,500-byte packet on a 1 Gbit/s link with a 30 ms round trip, that is 12 microseconds of sending per 30 milliseconds: a utilization of 0.04%, or 400 kbit/s of a 1 Gbit/s link. The solution is pipelining: let the sender have many packets in flight at once. With a window of \(N\) unacknowledged packets, utilization rises by a factor of \(N\) until the pipe is full. The window needed to fill it is the bandwidth–delay product from lesson 1 divided by the packet size.

# Sender utilization of stop-and-wait versus pipelining with window N
L, R, RTT = 1500 * 8, 1e9, 0.030          # 1,500-byte packets, 1 Gbit/s, 30 ms RTT
t = L / R
for N in (1, 10, 100, 1000, 2500, 5000):
    U = min(1.0, N * t / (RTT + t))
    print(f"window {N:5d} packets: utilization {U:8.4%}, throughput {U * R / 1e6:8.1f} Mbit/s")
print("window needed to fill the pipe:", round((RTT + t) / t), "packets")

window     1 packets: utilization  0.0400%, throughput      0.4 Mbit/s
window    10 packets: utilization  0.3998%, throughput      4.0 Mbit/s
window   100 packets: utilization  3.9984%, throughput     40.0 Mbit/s
window  1000 packets: utilization 39.9840%, throughput    399.8 Mbit/s
window  2500 packets: utilization 99.9600%, throughput    999.6 Mbit/s
window  5000 packets: utilization 100.0000%, throughput   1000.0 Mbit/s
window needed to fill the pipe: 2501 packets

Pipelining has consequences. The range of sequence numbers must grow, since many packets are outstanding. Both sides may need to buffer packets. And when a packet is lost, the protocol must decide what to retransmit. Two classic answers are Go-Back-N and Selective Repeat.

Go-Back-N

In Go-Back-N (GBN), the sender may have up to \(N\) unacknowledged packets in flight. The window begins at base, the oldest unacknowledged sequence number. The receiver is simple: it accepts only the next packet in order, discards anything that arrives out of order, and sends a cumulative acknowledgement for the highest in-order sequence number received, meaning all packets up to and including it have arrived. The sender keeps a single timer for the oldest unacknowledged packet. If it expires, the sender retransmits every packet in the window, going back to base. GBN is simple and needs no receiver buffering, but a single loss on a path with a large window causes many needless retransmissions of packets that had arrived intact.

Selective Repeat

Selective Repeat (SR) avoids those needless retransmissions. The receiver acknowledges each correctly received packet individually, buffering packets that arrive out of order and delivering them to the application once the gap is filled. The sender keeps a timer for each outstanding packet and retransmits only the ones whose timers expire. The cost is more state at both ends, and a subtle constraint on the window size: the window must be no more than half the size of the sequence number space. Otherwise the receiver cannot tell whether a packet carrying a given number is a retransmission of an old packet whose acknowledgement was lost or a new packet from the next window.

# Why Selective Repeat needs window <= half the sequence number space
k = 2                                  # 2-bit sequence numbers: 0..3
space = 2 ** k
for window in (3, 2):
    first = list(range(window))                        # packets the sender sends first
    receiver_expects = [(s + window) % space for s in range(window)]   # after acking all of them
    retransmit = first                                 # if every ACK is lost, sender resends these
    ambiguous = sorted(set(retransmit) & set(receiver_expects))
    print(f"window {window}: receiver now accepts {receiver_expects}, "
          f"old retransmissions carry {retransmit} -> confused on {ambiguous or 'nothing'}")

window 3: receiver now accepts [3, 0, 1], old retransmissions carry [0, 1, 2] -> confused on [0, 1]
window 2: receiver now accepts [2, 3], old retransmissions carry [0, 1] -> confused on nothing

The simulation below compares the three protocols delivering 2,000 packets over a channel that loses 5% of packets, with a window of 8 and a round trip of 10 ms. Each simulated round sends a window of packets and receives their acknowledgements. Go-Back-N retransmits more than Selective Repeat because it resends everything after a loss; stop-and-wait sends the fewest packets but takes far longer, because it never has more than one in flight.

# Simulate stop-and-wait, Go-Back-N and Selective Repeat over a lossy channel
import random
def simulate(protocol, n_packets=2000, window=8, loss=0.05, rtt=10, seed=1):
    rnd = random.Random(seed)
    t, sent, base, delivered = 0, 0, 0, set()
    acked = set()
    while base < n_packets:
        w = 1 if protocol == "stop-and-wait" else window
        batch = range(base, min(base + w, n_packets))
        lost = [s for s in batch if s not in acked and rnd.random() < loss]
        for s in batch:
            if protocol == "selective-repeat" and s in acked:
                continue                       # SR resends only what is missing
            sent += 1
        t += rtt                              # one round of sends and acknowledgements
        if protocol == "go-back-n":
            first_lost = min(lost) if lost else None
            good = [s for s in batch if first_lost is None or s < first_lost]
            acked.update(good)                # receiver discards everything after a gap
        else:
            acked.update(s for s in batch if s not in lost)
        while base in acked:
            base += 1
    return t, sent
for proto in ("stop-and-wait", "go-back-n", "selective-repeat"):
    t, sent = simulate(proto)
    print(f"{proto:17s} time {t:6d} ms  transmissions {sent:5d}  ({sent/2000:.2f} per packet)")

stop-and-wait     time  21130 ms  transmissions  2113  (1.06 per packet)
go-back-n         time   3250 ms  transmissions  2593  (1.30 per packet)
selective-repeat  time   3020 ms  transmissions  2113  (1.06 per packet)

Real protocols mix these ideas. TCP uses cumulative acknowledgements like GBN, but buffers out-of-order segments and, with the selective acknowledgement (SACK) option, tells the sender exactly which blocks arrived, so it retransmits only what is missing, much like SR. QUIC never reuses packet numbers, which removes the ambiguity about which transmission an acknowledgement refers to, and acknowledges ranges of packets. Both add congestion control, the subject of lesson 7.