IP datagram reassembly algorithms (RFC0815)
Original Publication Date: 1982-Jul-01
Included in the Prior Art Database: 2019-Feb-14
Internet Society Requests For Comment (RFCs)
This RFC describes an alternate approach of dealing with reassembly which reduces the bookkeeping problem to a minimum, and requires only one buffer for storage 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.
IP DATAGRAM REASSEMBLY ALGORITHMS
David D. Clark MIT Laboratory for Computer Science Computer Systems and Communications Group July, 1982
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...