IP Fragmentation and the TTL Field

An IP datagram is opaque to the routers that forward it, except for its header. When a router must forward a datagram out an interface whose Maximum Transmission Unit (MTU) is smaller than the datagram's total length, it has two choices: drop the datagram (if fragmentation is disallowed) or split it into multiple smaller datagrams called fragments. Each fragment is a fully valid IP datagram in its own right, with its own header, capable of being routed independently and possibly arriving out of order, delayed, or duplicated — exactly like any other datagram. Four IP header fields make fragmentation and reassembly possible. The Identification (ID) field (16 bits) is a number chosen by the original sender for that datagram; every fragment produced from it carries the same ID, so the destination knows which fragments belong together. The Flags field includes the DF (Don't Fragment) bit, which forbids any router from fragmenting the datagram (used for Path MTU Discovery), and the MF (More Fragments) bit, set on every fragment except the last one, telling the receiver when the group is complete. The Fragment Offset field (13 bits) records where, in units of 8 bytes, this fragment's payload belongs within the original datagram's data stream. Because reassembly is stateless and can be interleaved with fragments of other datagrams to the same host, the tuple (source address, destination address, protocol, Identification) uniquely identifies a fragment group. A crucial design decision is that fragmentation can happen at any router along the path, but reassembly happens only at the final destination host (never at an intermediate router). This asymmetry is deliberate: different fragments of the same datagram may take different routes and arrive at different times, so only the endpoint that owns the full picture — the destination — can safely wait for and reorder them. This design keeps routers stateless and fast, at the cost of pushing complexity (timers, buffer management, and vulnerability to incomplete-fragment attacks) to the destination.

Fragmentation at a router. When a router must send a datagram of length `L` (header + data) out a link with MTU `M`, and `L > M`, it fragments as follows. The datagram's header itself is typically 20 bytes (no options, the common case); data must be split into chunks whose length is a multiple of 8 bytes (except possibly the last chunk), because Fragment Offset counts 8-byte units. ``` function FRAGMENT(datagram, MTU): header = datagram.header // 20 bytes, no options (common case) headerLen = length(header) data = datagram.payload maxDataPerFragment = floor((MTU - headerLen) / 8) 8 // must be multiple of 8 if maxDataPerFragment <= 0: error "MTU too small to carry any data" fragments = [] offsetBytes = 0 originalMF = datagram.flags.MF // usually 0 unless already a fragment originalDF = datagram.flags.DF if originalDF == 1: // Not allowed to fragment: drop and report send ICMP "Destination Unreachable: Fragmentation Needed" to source return [] while offsetBytes < length(data): chunk = data[offsetBytes : offsetBytes + maxDataPerFragment] // last chunk may be shorter newHeader = copy(header) newHeader.totalLength = headerLen + length(chunk) newHeader.identification = header.identification // SAME for all fragments newHeader.fragmentOffset = offsetBytes / 8 // in 8-byte units isLast = (offsetBytes + length(chunk) >= length(data)) newHeader.flags.MF = isLast ? originalMF : 1 // set MF unless this is the last piece newHeader.flags.DF = originalDF newHeader.checksum = computeChecksum(newHeader) // recompute! header changed fragments.append(makeDatagram(newHeader, chunk)) offsetBytes += length(chunk) return fragments ``` Two subtleties matter for correctness. First, the header checksum must be <strong>recomputed</strong> for each fragment, since the total length and offset fields changed. Second, if a datagram that is already a fragment (MF = 1, offset > 0) itself needs further fragmentation, the new sub-fragments inherit the original's MF status on the last piece and set MF = 1 on all earlier pieces — the offset field is always relative to the original* unfragmented datagram, so nested fragmentation composes correctly by just adding offsets.

Reassembly at the destination. The destination host buffers arriving fragments, keyed by (source, destination, protocol, ID), until it has enough information to reconstruct the original payload. ``` function REASSEMBLE(fragment, buffers, timers, TIMEOUT): key = (fragment.src, fragment.dst, fragment.protocol, fragment.identification) if key not in buffers: buffers[key] = new FragmentBuffer() start timer for key with duration TIMEOUT buf = buffers[key] buf.insert(fragment.offset 8, fragment.data) // place data at byte offset buf.receivedRanges.add([fragment.offset8, fragment.offset8 + length(fragment.data)]) if fragment.flags.MF == 0: buf.totalLength = fragment.offset8 + length(fragment.data) // now we know final size if buf.totalLength is known AND buf.receivedRanges covers [0, buf.totalLength): cancel timer for key originalDatagram = buf.header + buf.assembledData remove buffers[key] deliver originalDatagram to upper layer // else: keep waiting for more fragments function ON_TIMEOUT(key, buffers): if key in buffers: discard buffers[key] // incomplete: drop silently or ICMP optionally send ICMP "Time Exceeded (fragment reassembly)" ``` The receiver does not need fragments to arrive in order. It tracks which byte ranges of the original payload it has received (`receivedRanges`), and it only learns the total length of the datagram once it sees the fragment with MF = 0 (the last one), because that fragment's offset plus its length gives the true total. Reassembly completes exactly when the union of received ranges covers `[0, totalLength)` with no gaps.

The TTL field and loop prevention. Independently of fragmentation, every IP header carries an 8-bit TTL (Time to Live) field, set by the sender (commonly to 64, 128, or 255 depending on the OS). Each router that forwards the datagram decrements TTL by (at least) one before forwarding. ``` function FORWARD(datagram): datagram.TTL = datagram.TTL - 1 if datagram.TTL <= 0: send ICMP "Time Exceeded (TTL expired in transit)" to source drop datagram return recompute IP header checksum // TTL changed, checksum must be updated lookup next hop and send datagram ``` TTL was originally meant to represent seconds a datagram may live (hence its name), with routers that hold a packet for multiple seconds supposed to decrement by more than one. In practice virtually all routers decrement by exactly one per hop, so TTL functions as a hop-count limit. This guarantees that a datagram traversing a routing loop is destroyed after at most `initial TTL` hops, no matter how long the loop persists.

Fragmentation cost. Splitting a datagram of data length `D` for a link with usable payload capacity `C` (a multiple of 8) produces ``` ⌈D / C⌉ ``` fragments, each requiring O(1) header construction and a checksum recomputation over a 20-byte header — O(1) time per fragment, so O(⌈D/C⌉) time and space for the fragmenting router. This is optimal: any correct scheme must emit at least `⌈D/C⌉` fragments to cover `D` bytes and cannot do so in fewer packets, since each packet carries at most `C` data bytes.

Reassembly cost. The destination must buffer up to the full datagram size, `O(D)` space, and track received byte ranges. Using an interval-list or bitmap representation, insertion and gap-checking cost `O(k)` per fragment (where `k` is the number of previously-received fragments, using a sorted interval list) or `O(1)` amortized with a bitmap over 8-byte units, giving O(D/8) total space for the coverage bitmap and O(⌈D/C⌉) total fragments processed, each O(1) with a bitmap — so reassembly is O(D) time and space overall, linear in the datagram size, which is asymptotically necessary since every byte must be written somewhere.

Correctness of reassembly. The key invariant is: A fragment group is complete if and only if the union of `[offset·8, offset·8 + len)` ranges over all received fragments with the same key equals `[0, totalLength)`, where `totalLength` is determined by the unique fragment with MF = 0. This holds because (1) fragmentation partitions `[0, D)` into contiguous, non-overlapping ranges by construction (the `FRAGMENT` procedure advances `offsetBytes` by exactly `length(chunk)` each iteration with no gaps or overlaps), and (2) exactly one fragment — the last one produced — has MF = 0, so `totalLength` is well-defined once that fragment arrives. Since IP fragments can be duplicated (retransmitted by a lower layer or replayed), the buffer must treat overlapping/duplicate ranges idempotently — inserting the same range twice must not create false gaps or double-counted coverage, which the bitmap/interval-union approach naturally guarantees. The reassembly timer bounds how long a receiver waits for a straggling fragment (commonly 30–60 seconds), after which the incomplete datagram is discarded — this is necessary because otherwise a single lost fragment could leak buffer memory forever, a real denial-of-service vector.

Correctness of TTL-based loop termination. Claim: with initial TTL value `T`, no datagram survives more than `T` hops before being dropped. Proof: each hop strictly decreases TTL by at least 1 (an invariant enforced by every conformant router), and a datagram is dropped as soon as TTL would reach 0 or below. TTL is a non-negative integer that strictly decreases at each hop, so by the well-ordering of the naturals it must reach the drop threshold within `T` steps — this is precisely a decreasing-measure / well-founded-descent argument, the same style of reasoning used to prove loop termination in program verification. This holds regardless of the routing table's correctness: even if routing entries form a cycle (a transient inconsistency during convergence, addressed by protocols discussed alongside distance-vector and link-state routing), the datagram cannot loop indefinitely — it is guaranteed to expire.

Tradeoffs. Fragmentation solves the MTU-mismatch problem but at real cost: if even one fragment is lost, the entire original datagram must be retransmitted (since transport-layer retransmission, e.g., TCP, operates on whole segments, not fragments), amplifying the impact of loss. Fragmentation also burdens the destination with reassembly state and exposes it to attacks (see below). This is why modern practice strongly prefers Path MTU Discovery — sending with DF set and shrinking segment size in response to ICMP "Fragmentation Needed" errors — over relying on in-network fragmentation, and why IPv6 removes router fragmentation entirely, pushing the responsibility to the sending host.

A host sends a UDP datagram carrying 3000 bytes of application data. The IP header is 20 bytes (no options), so total datagram length is 3020 bytes, Identification = 512, DF = 0, MF = 0, offset = 0. It travels over Ethernet (MTU 1500) to a router R, which must forward it onto a PPP link with MTU 620. Usable payload per fragment: `⌊(620 − 20)/8⌋ × 8 = ⌊600/8⌋×8 = 75×8 = 600` bytes. Number of fragments: `⌈3000 / 600⌉ = 5`.

All five fragments carry Identification = 512, and each has its header checksum recomputed independently. Suppose fragment 3 is dropped by a congested queue downstream, but fragments 1, 2, 4, 5 arrive at the destination. The receiver's buffer for key `(src, dst, UDP, 512)` accumulates coverage `[0,600) ∪ [600,1200) ∪ [1800,2400) ∪ [2400,3000)`, i.e., `[0,1200) ∪ [1800,3000)` — a gap at `[1200,1800)`. Because fragment 5 (MF=0) arrived, `totalLength = 3000` is known, but coverage never reaches `[0,3000)`. After the reassembly timeout expires, the receiver discards all four buffered fragments and — because this was the first fragment's range that's missing is not the case here, but generally if fragment offset 0 was received — may send an ICMP "Time Exceeded (reassembly)" message back to the original sender. The entire 3000-byte UDP datagram is lost, even though 80% of its bytes arrived intact — illustrating the amplification-of-loss tradeoff discussed above. Now trace TTL on the same path. Suppose the sender set TTL = 4, and the path is Host → R1 → R2 → R3 → Destination (3 router hops). Each router decrements TTL by 1: it arrives at R1 with TTL 4→3, at R2 with TTL 3→2, at R3 with TTL 2→1, and reaches the destination with TTL 1 (still positive, since destinations don't forward, only routers decrement-and-forward). Delivery succeeds. If instead a routing misconfiguration created a loop R2→R3→R2, a datagram entering that loop with TTL = 4 would be decremented at each pass — 4→3 at R2, 3→2 at R3, 2→1 at R2 again, 1→0 at R3 again — and R3 would drop it and emit an ICMP Time Exceeded message rather than looping forever.

The mechanisms described here were codified in the foundational specification of the Internet Protocol, refined through the 1970s and early 1980s as the ARPANET's homogeneous link assumptions gave way to a genuinely heterogeneous internetwork of Ethernet, X.25, packet radio, and satellite links — each with a different MTU.

Fragmentation and TTL are load-bearing mechanisms across the entire internet infrastructure, not historical curiosities. DNS over UDP occasionally produces responses large enough to require fragmentation (especially with DNSSEC), which is one reason large deployments push toward TCP fallback or EDNS0 buffer-size negotiation to avoid fragmentation-related failures. VPN and tunneling protocols (IPsec, GRE, VXLAN) routinely encounter reduced effective MTU because of added encapsulation headers, making correct handling of DF, fragmentation, and ICMP "Fragmentation Needed" messages essential for tunnel reliability — misconfigured firewalls that block that ICMP message are a classic, hard-to-diagnose cause of "traffic hangs only for large packets." TTL underlies the ubiquitous `traceroute`/`tracert` diagnostic tool, which sends probes with increasing TTL values (1, 2, 3, …) specifically to trigger ICMP Time Exceeded responses from each successive router, mapping the path hop by hop. TTL also functions as a coarse anti-amplification and scope-limiting mechanism in multicast routing (TTL scoping) and is checked by security-conscious middleboxes to detect spoofed or malformed traffic. Content-delivery networks and load balancers monitor TTL to infer approximate network distance, and DDoS-mitigation appliances use anomalous TTL patterns as one signal among many for spoofed-source detection. Understanding fragmentation and TTL together explains real, frequently-debugged phenomena — "large packets fail, small ones work," "traceroute stops partway," "one router seems to eat half my traffic" — that recur across enterprise networking, cloud infrastructure, and internet-scale operations.

Ask the tutor: How does Path MTU Discovery actually recover when the ICMP "Fragmentation Needed" message itself gets blocked by a firewall?