next up previous
Next: Future Research Up: Fragmentation Made Friendly Previous: Loss of Fragments

Inefficient Reassembly

``Efficient Reassembly is hard: Given the likelihood of lost fragments and the information present in the IP header, there are many situations in which the reassembly process, though straightforward, yields lower than desired performance.'' [KM87]

Reassembling IP fragments correctly (much less efficiently) is clearly difficult. David D. Clark, author of RFC 815 [Cla82a] which provides an efficient algorithm for IP reassembly, writes: ``IP is a simple protocol, especially with respect to the processing of normal packets, so it should be easy to get it to perform efficiently. The only area of any complexity related to actual packet processing has to do with fragmentation and reassembly.'' RFC 817 - [Cla82b] Given reassembly's role in the difficulty of IP implementations, it is clearly worthwhile to examine both the goals and the implementation details of reassembly algorithms with careful skepticism. If fragment reassembly can be significantly improved, the efficiency of IP can be dramatically improved.

Reassembly of IP fragments usually involves the largest number of memory copies and the greatest inefficiency of any IP operation. Fragments must be copied (often more than once) in order to properly reassemble them into a datagram. The problem has two central components: the complete datagram is of unknown size, and the fragments may overlap and arrive out of order, making bounds checking difficult.

The first problem is the most significant with respect to efficiency. The only fragment that indicates the actual size of a datagram is the final fragment, which has the More Fragments (MF) bit set to 0. The size of the completed datagram is equal to the size of the final fragment plus the offset of the final fragment minus its header length. If fragments arrive in order beginning with offset 0 or out of order, the recipient has no way to know how much space to allocate for the datagram. If enough fragments arrive to fill the initially allocated buffer and more fragments arrive, the recipient must allocate a larger buffer and copy the contents of the original into it (or link it into the existing buffer). This has the potential to produce gross inefficiencies in memory utilization and introduce unpredictable latencies during memory allocation. Furthermore, routines dealing with out-of-order fragments are currently among the least robust routines in the IP stack (as has previously been mentioned).

We believe that the efficiency of the reassembly of fragmented packets can be greatly improved if senders sent fragmented packets in reverse order. Reassembly of reverse order fragments has the potential to be the most efficient and simple. Since the last fragment of a fragmented packet contains the length of the entire packet, a reassembly routine can allocate a buffer equal to the size of the entire packet. Additionally, IP headers can simply be written over (within this buffer) instead of being stripped. This reassembly routine requires at most two memory copies, and potentially only requires the one memory copy from kernel space to user space. On the other hand, reassembly of in-order fragments requires stripping off the IP headers of a fragment and requires some guesswork about the final size of the packet. However, in-order transmission of fragments is currently the most widely used according to our data gathered during fragmentation testing.

Others have already recognized the efficiencies inherent in reverse-order fragment sending. It is precisely to attain these receiver efficiencies that the Linux kernel sends NFS traffic as large, fragmented UDP datagrams in reverse order. The reverse order reassembly is currently not treated as a special case by the Linux kernel, but that suggestion has been made.

In-order fragmentation reassembly can be improved in efficiency by implementing RFC 815's [Cla82a] algorithm. RFC 815 suggests a very straightforward algorithm for reassembly that focuses on the holes remaining in the assembled datagram rather than the fragments that are received. A hole-list is maintained and when a fragment is received, the hole-list is traversed to determine whether the fragment corresponds to any existing hole. If a hole is matched, the hole-list entry is deleted, the fragment is copied into place and new hole-list entries are created, if necessary, to represent the space before and after the fragment's data segment. When there are no more entries on the hole-list, the datagram is accepted. If the datagram times out with entries still on the fragment list, the packet is timed out and a NACK is sent to the sender.

Although RFC 815's algorithm is simple both to understand and implement, and the algorithm was published in 1982, it appears that few operating systems have implemented it. It is known that Linux and the various Windows platforms had not implemented the RFC prior to the fall of 1997 because they would not have been susceptible to the Teardrop or Bonk/Boink attacks if they had. Without public source code, it is impossible to be certain, but Cisco claims that IOS version 11.0 (released in December 1995) implements RFC 815 for fragment reassembly.

In short, implementers can dramatically improve the efficiency of fragment reassembly by choosing to send reverse-order fragments and by making the reassembly of these fragments in the IP stack a special case. Furthermore, the correctness and speed of reassembly can be improved by implementing the RFC 815 reassembly algorithm for in-order and out-of-order fragments. Finally, implementers may choose to simply reject all out-of-order fragments since our research (see figure 2) shows that they simply do not occur on the Internet. We appear to have reached a point in the evolution of networks where routes change extremely infrequently and networks always transmit fragments in-order. If implementers are nervous about rejected out-of-order fragments, they can rely on RFC 815 to properly and robustly assemble them.


next up previous
Next: Future Research Up: Fragmentation Made Friendly Previous: Loss of Fragments

2000-07-01