IP datagram reassembly algorithms
RFC - Unknown
(July 1982; No errata)
||RFC Editor Note
RFC 815 (Unknown)
||Send notices to
IP DATAGRAM REASSEMBLY ALGORITHMS
David D. Clark
MIT Laboratory for Computer Science
Computer Systems and Communications Group
One of the mechanisms of IP is fragmentation and reassembly. Under
certain circumstances, a datagram originally transmitted as a single
unit will arrive at its final destination broken into several fragments.
The IP layer at the receiving host must accumulate these fragments until
enough have arrived to completely reconstitute the original datagram.
The specification document for IP gives a complete description of the
reassembly mechanism, and contains several examples. It also provides
one possible algorithm for reassembly, based on keeping track of
arriving fragments in a vector of bits. This document describes an
alternate approach which should prove more suitable in some machines.
A superficial examination of the reassembly process may suggest
that it is rather complicated. First, it is necessary to keep track of
all the fragments, which suggests a small bookkeeping job. Second, when
a new fragment arrives, it may combine with the existing fragments in a
number of different ways. It may precisely fill the space between two
fragments, or it may overlap with existing fragments, or completely
duplicate existing fragments, or partially fill a space between two
fragments without abutting either of them. Thus, it might seem that the
reassembly process might involve designing a fairly complicated
algorithm that tests for a number of different options.
In fact, the process of reassembly is extremely simple. This
document describes a way of dealing with reassembly which reduces the
bookkeeping problem to a minimum, which requires for storage only one
buffer equal in size to the final datagram being reassembled, which can
reassemble a datagram from any number of fragments arriving in any order
with any possible pattern of overlap and duplication, and which is
appropriate for almost any sort of operating system.
The reader should consult the IP specification document to be sure
that he is completely familiar with the general concept of reassembly,
and the particular header fields and vocabulary used to describe the
2. The Algorithm
In order to define this reassembly algorithm, it is necessary to
define some terms. A partially reassembled datagram consists of certain
sequences of octets that have already arrived, and certain areas still
to come. We will refer to these missing areas as "holes". Each hole
can be characterized 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. This pair of numbers we will call the "hole descriptor", and we
will assume that all of the hole descriptors for a particular datagram
are gathered together in the "hole descriptor list".
The general form of the algorithm is as follows. When a new
fragment of the datagram arrives, it will possibly fill in one or more
of the existing holes. We will examine each of the entries in the hole
descriptor list to see whether the hole in question is eliminated by
this incoming fragment. If so, we will delete that entry from the list.
Eventually, a fragment will arrive which eliminates every entry from the
list. At this point, the datagram has been completely reassembled and
can be passed to higher protocol levels for further processing.
The algorithm will be described in two phases. In the first part,
we will show the sequence of steps which are executed when a new
fragment arrives, in order to determine whether or not any of the
existing holes are filled by the new fragment. In the second part of
this description, we will show a ridiculously simple algorithm for
management of the hole descriptor list.
3. Fragment Processing Algorithm
An arriving fragment can fill any of the existing holes in a number
of ways. Most simply, it can completely fill a hole. Alternatively, it
may leave some remaining space at either the beginning or the end of an
existing hole. Or finally, it can lie in the middle of an existing
hole, breaking the hole in half and leaving a smaller hole at each end.
Because of these possibilities, it might seem that a number of tests
must be made when a new fragment arrives, leading to a rather
complicated algorithm. In fact, if properly expressed, the algorithm
can compare each hole to the arriving fragment in only four tests.
We start the algorithm when the earliest fragment of the datagram
Show full document text