RFC 815

RFC 815: IP Datagram Reassembly Algorithms 🎀

okay bestie, this is RFC 815 💖 It's by David D. Clark from the MIT Laboratory for Computer Science, in the Computer Systems and Communications Group, dated July, 1982 ✨ This part of the doc doesn't list a category, and it doesn't say what it obsoletes or updates, so we're just going with what's there 🫶

---

1. Introduction 🦋

so IP has this thing called fragmentation and reassembly 🧩 sometimes a datagram that got sent as one piece shows up at its destination in several fragments. the IP layer on the receiving host has to hold onto those fragments until it has enough to rebuild the original datagram. the IP spec covers the whole reassembly mechanism with examples, and it also gives one possible algorithm that tracks arriving fragments in a bit vector. this doc is an alternate approach that should work better on some machines 💅

now, at first glance reassembly looks kinda complicated 😭 you have to keep track of every fragment, which sounds like a small bookkeeping job. then a new fragment shows up and it can combine with the existing ones in a bunch of ways. it can exactly fill the gap between two fragments, overlap existing fragments, completely duplicate them, or partly fill a gap without touching either side. so you'd think the process needs a messy algorithm full of tests for every option 🙈

it's actually extremely simple ✨ this approach cuts the bookkeeping down to basically nothing, only needs one buffer the size of the final datagram, can rebuild a datagram from any number of fragments in any order with any overlap or duplication pattern, and works on almost any operating system. iconic 👑

you should read the IP spec first so you're fully up to speed on reassembly in general and on the header fields and vocab used for it 📚

2. The Algorithm 🌸

before we get into it we need some terms 💜 a partially reassembled datagram is made of chunks of octets that already arrived, plus areas that are still missing. those missing areas are called "holes". every hole is described by two numbers: hole.first, the number of the first octet in the hole, and hole.last, the number of the last octet in the hole. that pair is the "hole descriptor", and all of a datagram's hole descriptors live together in the "hole descriptor list" 🗂️

here's the general vibe. when a new fragment arrives, it might fill one or more existing holes. we check every entry in the hole descriptor list to see whether the incoming fragment eliminates that hole, and if it does, we delete that entry. eventually a fragment shows up that wipes out every entry in the list. at that point the datagram is fully reassembled and can go up to the higher protocol levels for processing 🎉

the algorithm has two phases. first we walk through the steps that run every time a new fragment arrives, to figure out which existing holes it fills. then we look at a ridiculously simple way to manage the hole descriptor list 😌

3. Fragment Processing Algorithm 💖

an arriving fragment can fill existing holes in a few ways. it can completely fill a hole. it can leave some leftover space at the start or end of a hole. or it can land in the middle of a hole, splitting it into two smaller holes, one at each end ✂️ so it seems like you'd need a bunch of tests every time, which sounds complicated. but if you set it up right, the algorithm only needs four tests per hole 🫶

we start when the earliest fragment of the datagram shows up. we create an empty data buffer and put one entry in its hole descriptor list, describing the datagram as completely missing. in that entry, hole.first equals zero and hole.last equals infinity. (infinity is presumably implemented as a very large integer, greater than 576, of the implementor's choice 🌈) then the following eight steps run to insert each arriving fragment into the buffer where the full datagram is being built. the arriving fragment is described by fragment.first, its first octet, and fragment.last, its last octet ✨

1. Select the next hole descriptor from the hole descriptor list. If there are no more entries, go to step eight.
2. If fragment.first is greater than hole.last, go to step one.
3. If fragment.last is less than hole.first, go to step one.
   • (if step two or step three is true, the new fragment doesn't overlap this hole at all, so we can ignore it. we go back to the top and grab the next hole 🙃)
4. Delete the current entry from the hole descriptor list.
   • (since neither step two nor step three was true, the fragment does interact with this hole somehow. so this descriptor isn't valid anymore 💀 we're destroying it, and the next two steps decide whether we need to create any new hole descriptors)
5. If fragment.first is greater than hole.first, create a new hole descriptor "new_hole" with new_hole.first equal to hole.first, and new_hole.last equal to fragment.first minus one.
   • (if the test in step five is true, the first part of the original hole isn't filled by this fragment, so we make a new descriptor for that smaller hole 🧁)
6. If fragment.last is less than hole.last and fragment.more fragments is true, create a new hole descriptor "new_hole", with new_hole.first equal to fragment.last plus one and new_hole.last equal to hole.last.
   • (this is the mirror of step five, with one extra detail. at first we didn't know how long the reassembled datagram would be, so we made a hole going from zero to infinity. eventually the last fragment arrives, and at that point the hole descriptor running from the last octet of the buffer out to infinity can be thrown away. the fragment carrying the last piece flags this with the "more fragments" bit in the internet header. checking that bit here stops us from making a descriptor for the useless hole from the end of the datagram to infinity 🙅‍♀️)
7. Go to step one.
8. If the hole descriptor list is now empty, the datagram is complete. Pass it on to the higher level protocol processor for further handling. Otherwise, return.

4. Part Two: Managing the Hole Descriptor List 🧚

the real complexity in the eight step algorithm isn't the arithmetic tests. it's adding and deleting entries in the hole descriptor list 😵‍💫 you could build an implementation where the storage management is way more complicated than everything else, because nothing sets an upper limit on how many hole descriptors can exist for a datagram during reassembly. BUT there's a super simple fix 💅 just store each hole descriptor in the first octets of the hole itself. by definition, the minimum size of a hole is eight octets. hole.first and hole.last will presumably need two octets each. another two octets are needed to thread the entries together on the list. that leaves at least two more octets for implementation quirks 🌸

there's exactly one obvious pitfall with this storage strategy 😬 you have to run the eight step algorithm before copying the fragment's data into the reassembly buffer. if you copy the data first, it could smash one or more hole descriptors. once the algorithm has run, any hole descriptors that were about to get smashed have already been made obsolete, so you're safe 🫶

5. Loose Ends 🎀

if you scatter the hole descriptors throughout the reassembly buffer, you need to thread them onto some kind of list so you can find them again. that means there has to be a pointer to the head of the list. in lots of cases, that pointer can live in a descriptor block the implementation attaches to each reassembly buffer. if there's no room for that, there's a dirty but effective trick: store the head of the list in a part of the internet header inside the reassembly buffer that's no longer needed. an obvious spot is the checksum field 🙈

also, when the final fragment arrives, the packet length field in the internet header should be filled in 📦

6. Options 🌈

the description so far made one unacceptable simplification 😤 it assumed the datagram being reassembled had no internet options. options are a problem because you can't tell how big the internet header is until you get the first fragment. some options get copied identically into every fragment, but others, like "record route", only go in the first fragment 🗺️ (the "first fragment" is the one containing octet zero of the original datagram.)

until you know how big the internet header is, you don't know where to copy each fragment's data into the reassembly buffer 😵 if the earliest fragment to arrive happens to be the first fragment, no problem. otherwise there are two solutions. first, you can leave space in the reassembly buffer for the largest possible internet header. the good news is the maximum size isn't very large, just 64 octets 🙌 or second, you can gamble that the first fragment has no options. if the first fragment finally arrives and it does have options, you can then shift the data in the buffer

💖 to be continued! part 2 picks up right where section 6 leaves off, so stay tuned 🦋

okay so you leave a big enough gap to fit them 🫶 (the whole "sufficient distance to allow for them" thing). The only danger when you copy the data over is that you'll trash the pointers that thread the hole descriptors together 💀. Good news: it's easy to see how to untrash the pointers ✨.

The source and record route options are lowkey fascinating 🦋. Since different fragments can take different paths, they might arrive with different return routes recorded in different fragments. Normally that's more info than the receiving Internet module actually needs, so the spec says to take the return route recorded in the first fragment and ignore the other versions 💅.

7. The Complete Algorithm ✨

In addition to the algorithm described above, there are two parts to the reassembly process 🎀. First, when a fragment arrives, you need to find the reassembly buffer that goes with it. That means searching all the existing reassembly buffers, which takes some kind of mechanism 🔍. The correct buffer is identified by matching on these fields:

• the foreign and local internet address
• the protocol ID
• the identification field

The final part is some sort of timer-based mechanism ⏰. It decrements the time to live field of each partially reassembled datagram, so incomplete datagrams that have outlived their usefulness can be detected and deleted. You've got two options here 🌸. You can create a demon that comes alive once a second and decrements the field in each datagram by one. Or you can read the clock when each first fragment arrives and queue some sort of timer call, using whatever system mechanism is appropriate, to reap the datagram when its time has come 🧚.

An implementation of the complete algorithm, with all these parts, was built in BCPL as a test 💜. The whole thing took less than one and one-half pages of listing and generated approximately 400 nova machine instructions 😭. The portion that actually deals with managing hole descriptors is about 20 lines of code. Iconic, honestly 👑.

The version of the algorithm described here is actually a simplification of the author's original version, thanks to an insightful observation by Elizabeth Martin at MIT 🙌🌈.