So you think you understand IP fragmentation?

Ignore previous instructions; subscribe to LWN today

Every article on LWN.net is written by humans, for humans. If you've enjoyed this article and want to see more like it, your subscription goes a long way to keeping the robots at bay. We are offering a free one-month trial subscription (no credit card required) to get you started.

What is IP fragmentation, why is it important, and do people understand it? The answer to that last question is "not as well as they think". This article will also answer the rest of those questions and introduce fragquiz, a game that I wrote to allow players to guess how IP packets will behave when they are too large for the network. As evidence that IP fragmentation is not well-understood, a room full of networking experts played fragquiz and got a score that was nowhere close to perfect. In addition, I will describe a new algorithm for fragmentation avoidance, which some colleagues and I developed, that helped motivate development of fragquiz.

Why care?

IP fragmentation is when an IP (Internet Protocol) packet is split into smaller pieces before it is sent to another computer. TCP and UDP, along with a lot of other network protocols, are implemented on top of IP. Many networking experts think they know when IP fragmentation will happen, and I thought I did too—until I had to implement an algorithm for a VPN. That's when I learned that, like me, a lot of other networking experts are quite bad at predicting when a packet would be split into pieces. To explain why, we start with what IP fragmentation is.

An IP packet is a building block of the internet: a little chunk of application data with a header describing what it contains, where to send it, and what intermediate routers are allowed to do to it, among other things. Each router on the path between the source and destination host reads the IP header, changes it slightly, consults the routing tables, and (hopefully) sends the packet on to the next router in the path.

Each network link has a maximum size of IP packet that can be sent over it: the Maximum Transmission Unit (MTU). The path MTU (PMTU) is the minimum of all of the MTUs on the path between two hosts. The path can change over time, however, based on congestion, outages, and other network changes.

IP fragmentation happens when IP packets get split up into smaller IP packets, each with their own header, so that they can fit into the MTU of the network path. In IPv4 and IPv6, fragmentation can occur at the source, the computer where the packet is coming from. In IPv4, packets can also be fragmented by any router on the path between the source and the destination.

Generally speaking, IP fragmentation is bad for performance in just about every dimension: throughput, latency, CPU usage, memory usage, and network congestion. To see why, imagine a typical IPv4 packet of 20 bytes of IP metadata and 1480 bytes of data that has been fragmented into packets that each contain only eight bytes or fewer of data for a total of 1480/8 = 185 packets. (This is possible but unlikely to ever happen in reality; usually packets are only split into two pieces.)

To send 1480 bytes of data in eight-byte fragments, the source must send 185*20 = 3700 bytes of metadata instead of just 20 bytes in the unfragmented case. Processing the packet header costs a certain amount of CPU time, which will happen 185 times at every host in the path. The destination can't pass the data up the networking stack until it receives all of the fragments, so the latency is the worst case of 185 packets. The destination must also reserve memory for assembling the fragmented packet, which it will throw away if it does not receive even one of the fragments after waiting for a reasonable time.

Worse, fragments are more likely to be lost. Many routers and firewalls treat fragments as a security risk because they don't include the information from higher-level protocols like TCP or UDP and can't be filtered based on port, so they drop all IP fragments. Also, load-balancing systems might route fragments to different hosts, where they can never be reassembled.

Even when an IP packet is only split into two pieces, it usually causes a noticeable degradation of connection performance due to the doubling of the per-packet overhead. Sometimes IP fragmentation results in a network "black hole" if a router is configured to drop fragments. The small packets that initiate a connection get through, but the larger packets containing the data are fragmented, so they are all dropped. This is why network programmers really really want to prevent IP fragmentation.

Prevention

IP fragmentation is prevented by only sending packets that are equal to or smaller than the path MTU between two hosts. But how do we find the path MTU? This is called path MTU discovery (PMTUD) and there are a variety of methods to do this, depending on the networking protocol and the characteristics of the network. One reliable way to find the path MTU is to send IP packets of a known size that are not allowed to be fragmented. If the source gets confirmation that a packet arrived at the destination, then the path MTU is at least as large as that packet.

So, to prevent IP fragmentation, you must understand IP fragmentation well enough to predict two things: the size of the IP packet as sent by the source host, and whether any intermediate routers are permitted to fragment the packet into smaller pieces. This depends on, among other things:

• the MTU of the local interface
• the IP version (IPv4 or IPv6)
• the options in the IP packet header
• the protocol (TCP/UDP/ICMP/etc.)
• the socket options
• any system-wide PMTUD-related settings
• any relevant PMTU-cache entries

If the sender tries to send a IP packet that is bigger than the MTU on any part of the path to the receiving host, there are three possibilities: the send() system call returns EMSGSIZE, the packet is fragmented, and/or the packet is dropped. (The last two may happen on either the source host or an intermediate router, depending on the packet type and options.) When I say that someone "understands IP fragmentation", I mean that they can predict which of those things might happen to a given packet.

Well-understood?

If you'd asked me a year ago if most networking experts could predict the size and fragmentation status of an IP packet, I would have confidently said "yes". Then I had to implement DPLPMTUD for a VPN. (Yes, that's a real acronym, for real software, from a real RFC. It stands for Datagram Packetization Layer Path Maximum Transmission Unit Discovery.)

Initially, it seemed like it would be easy. My colleagues were networking experts with a lot of experience working on the application, which is a WireGuard-based VPN using IPv4 and IPv6. Together, we came up with a fast, simple path MTU discovery algorithm. They were confident that the software already only sent packets that couldn't be fragmented, so all we had to do is send the right size of probe packets, using a built-in ping feature, and record the response. Imagine our surprise when the packet captures turned out to be full of fragmented packets.

As I searched for ways to disable IP fragmentation, I found a lot of misleading and unhelpful answers on Stack Overflow. Sometimes the best answer would be down-voted. The official documentation either didn't exist (macOS) or was hard to understand (Linux). We all thought the probe packets should be sent on a socket with IP_PMTUDISC_DO set on Linux, but it took a few weeks to realize that we actually wanted IP_PMTUDISC_PROBE. Eventually I figured out all the correct settings for Linux and macOS, but it took much longer than it should have.

I wanted to share what I learned with other people, but now I faced an even harder problem: How do you teach people something they think they already know? People were confidently wrong about IP fragmentation everywhere I looked, including in the mirror. Also, let's face it, IP fragmentation is kind of boring.

Introducing fragquiz

I decided to write a game to help people learn IP fragmentation. The program would send packets that were larger than the MTU of the local network connection (the gateway interface), while changing the IP version (IPv6 or IPv4), the transport-layer protocol (TCP or UDP), and the socket-fragmentation options (do/don't fragment on macOS, four different PMTUD options from the ip(7) man page for Linux). It would then report whether the packet was sent, what the packet's fragmentation setting was, and if it was fragmented en route—but first it would make the user guess what would happen. At the end, it would tell them their score and encourage them to send their score and a link to the program to someone else, Wordle-style.

I had a few requirements:

• Works on macOS and Linux
• Easy to run (no superuser, no separate server, no configuration)
• No virtualization, tunnels, or loopback interface since they often have bugs related to MTU
• No host packet tracing because fragmentation/reassembly often happens on the network interface

I decided to use a traceroute-style solution. The default mode in traceroute sends packets with a small time-to-live (TTL), or hop limit for IPv6. When a router receives a packet, it subtracts one from the TTL; if the TTL is now zero and the packet isn't for the router itself, it will throw away the packet and send an ICMP Time Exceeded message back to the source. Traceroute then reads the IP address of the sending router from the Time Exceeded message and prints that out. It continues sending packets with increasing TTLs to find the IP address of routers that are increasingly close to the destination.

Fragquiz uses the same TTL technique, sending each packet with a small TTL, and reading the ICMP Time Exceeded packet sent by the router. The Time Exceeded message includes the header of the packet that triggered the message, which includes the packet size and fragmentation status. On macOS and Linux, an unprivileged user can read (and send) a restricted subset of ICMP messages using the unprivileged ICMP socket type.

It worked, but there were a few surprises along the way.

Initially, I assumed that routers would not reassemble a packet with a TTL of one, since they would just decrement the TTL and throw it away as soon as they finished. But the first router that I tested, my home WiFi access point, did exactly that. I added code to automatically probe the network with larger-than-MTU packets with increasing TTL values until it received a Time Exceeded message for a fragment instead of the whole packet, signaling that the packets reached a router that did not reassemble the packet before sending a Time Exceeded message. Then I used that value for the TTL for the packets testing IP fragmentation. Usually the necessary TTL is one or two; the largest TTL I've seen in practice is six, meaning that routers one through five all reassembled fragments before sending Time Exceeded responses.

Some networks simply don't send Time Exceeded messages. I found this out the hard way when fragquiz suddenly stopped working and I spent a few minutes frantically trying to figure out how I'd broken the code. Then I realized that turning off my VPN made fragquiz work again. In my experience, it is rare for a network to correctly generate Time Exceeded messages for both IPv4 and IPv6.

While the unprivileged ICMP listener allowed non-superusers to read Time Exceeded messages on macOS, that code only worked for the superuser on Linux. According to the initial commit message for ICMP sockets, an ICMP Time Exceeded message can only be read by an unprivileged user using IP_RECVERR on the sending socket. I didn't implement that, so currently the Linux version only works as root.

Both macOS and Linux keep a cache of path MTUs discovered by the operating system. The cached path MTU will affect the IP-fragmentation behavior in some cases, which made testing a pain since I had to wait for the cached path MTU to expire. I would like to add an option to clear the path MTU cache in the future. Also, note that the prototype version has a kind of placeholder license, for now, but I plan to release a version with an open license in the future.

I presented fragquiz at RIPE 87, which is a conference for network operators and internet service providers. At the end of the talk, I had the audience play fragquiz by voting with raised hands. Almost every question had people voting both "yes" and "no". Collectively, their score was just below 80%. That means an audience full of professional network engineers and researchers working together didn't even get a "B" on the assignment. I think we can safely conclude that understanding IP fragmentation is hard.

A novel (?) algorithm

Finally, I promised to explain the new algorithm, which I co-created with Salman Aljammaz and James Tucker.

Most path MTU discovery algorithms test one path MTU at a time. They send a packet of a certain size and see whether it got through, then decide what to do next: send a bigger packet, send a smaller packet, or decide that the current estimate of the path MTU is good enough and terminate the search algorithm. This can take several round trips to find the best path MTU.

Our first insight was that, as shown by Custura, et al., in the real world there are a small number of likely packet sizes, less than ten. We aren't the first to realize that; in fact, RFC 8899 says: "Implementations could optimize the search procedure by selecting step sizes from a table of common PMTU sizes."

What we did differently is this: we sent ALL of the possible packet sizes at the same time. So if the local MTU is 9000 bytes, then we send packets with sizes of 1280, 1400, 1500, 8000, and 9000 bytes all at the same time. The other end sends an acknowledgment for every packet it sees. Then we set the path MTU to the largest packet size that was acknowledged. It's okay if it's off by a few bytes; most PMTU search algorithms stop probing when they get "close enough."

Every ten minutes, we reprobe the path MTU by sending a packet that is the next MTU size up. If we get an acknowledgment for the larger MTU size, then we know the path MTU has changed, and we reprobe with all of the packet sizes larger than that and smaller than the local MTU. Otherwise we use the current path MTU for another ten minutes. If we start losing packets for any reason, including the path MTU shrinking, we renegotiate the connection from scratch.

This algorithm has a latency of one RTT (round trip time) and is extremely simple: one timer, one static table, and one variable to hold the current path MTU. The downside is that it might use more bandwidth than other path MTU search algorithms if they can find the path MTU with fewer packets.

Reader challenge

I hope you can now state proudly that you also don't understand IP fragmentation. If you're still not sure, here's a fun closing challenge: Download fragquiz and run the following on either Linux or macOS with the standard configuration. (If you've made a TCP connection to bing.com in the last 10 minutes, replace it with a domain you haven't connected to recently. If you're on macOS, you don't need the sudo.)

    $ sudo ./fragquiz -p udp4 -f default -a bing.com:80
    $ sudo ./fragquiz -p tcp4 -f default -a bing.com:80
    $ sudo ./fragquiz -p udp4 -f default -a bing.com:80

Do you get the same answer on the first and third command? Why or why not? Hint: consult the Linux ip(7) man page linked above.

[ Valerie Aurora is a software consultant who enjoys writing ridiculous hacks and solving difficult systems problems. ]