As per Relevance of the word reassembly, we have this rfc below:
RFC: 815
IP DATAGRAM REASSEMBLY
David D.
MIT Laboratory for Computer
Computer Systems and Communications
July, 1982
1.
One of the mechanisms of IP is fragmentation and reassembly.
certain circumstances, a datagram originally transmitted as a
unit will arrive at its final destination broken into several fragments
The IP layer at the receiving host must accumulate these fragments
enough have arrived to completely reconstitute the original datagram
The specification document for IP gives a complete description of
reassembly mechanism, and contains several examples. It also
one possible algorithm for reassembly, based on keeping track
arriving fragments in a vector of bits. This document describes
alternate approach which should prove more suitable in some machines
A superficial examination of the reassembly process may
that it is rather complicated. First, it is necessary to keep track
all the fragments, which suggests a small bookkeeping job. Second,
a new fragment arrives, it may combine with the existing fragments in
number of different ways. It may precisely fill the space between
fragments, or it may overlap with existing fragments, or
2
duplicate existing fragments, or partially fill a space between
fragments without abutting either of them. Thus, it might seem that
reassembly process might involve designing a fairly
algorithm that tests for a number of different options
In fact, the process of reassembly is extremely simple.
document describes a way of dealing with reassembly which reduces
bookkeeping problem to a minimum, which requires for storage only
buffer equal in size to the final datagram being reassembled, which
reassemble a datagram from any number of fragments arriving in any
with any possible pattern of overlap and duplication, and which
appropriate for almost any sort of operating system
The reader should consult the IP specification document to be
that he is completely familiar with the general concept of reassembly
and the particular header fields and vocabulary used to describe
process
2. The
In order to define this reassembly algorithm, it is necessary
define some terms. A partially reassembled datagram consists of
sequences of octets that have already arrived, and certain areas
to come. We will refer to these missing areas as "holes". Each
can be characterized by two numbers, hole.first, the number of the
octet in the hole, and hole.last, the number of the last octet in
hole. This pair of numbers we will call the "hole descriptor", and
will assume that all of the hole descriptors for a particular
are gathered together in the "hole descriptor list".
3
The general form of the algorithm is as follows. When a
fragment of the datagram arrives, it will possibly fill in one or
of the existing holes. We will examine each of the entries in the
descriptor list to see whether the hole in question is eliminated
this incoming fragment. If so, we will delete that entry from the list
Eventually, a fragment will arrive which eliminates every entry from
list. At this point, the datagram has been completely reassembled
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
fragment arrives, in order to determine whether or not any of
existing holes are filled by the new fragment. In the second part
this description, we will show a ridiculously simple algorithm
management of the hole descriptor list
3. Fragment Processing
An arriving fragment can fill any of the existing holes in a
of ways. Most simply, it can completely fill a hole. Alternatively,
may leave some remaining space at either the beginning or the end of
existing hole. Or finally, it can lie in the middle of an
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
must be made when a new fragment arrives, leading to a
complicated algorithm. In fact, if properly expressed, the
can compare each hole to the arriving fragment in only four tests
4
We start the algorithm when the earliest fragment of the
arrives. We begin by creating an empty data buffer area and putting
entry in its hole descriptor list, the entry which describes
datagram as being completely missing. In this case, hole.first
zero, and hole.last equals infinity. (Infinity is presumably
by a very large integer, greater than 576, of the implementor's choice.)
The following eight steps are then used to insert each of the
fragments into the buffer area where the complete datagram is
built up. The arriving fragment is described by fragment.first,
first octet of the fragment, and fragment.last, the last octet of
fragment
1. Select the next hole descriptor from the hole
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 either step two or step three is true, then
newly arrived fragment does not overlap with the hole
any way, so we need pay no further attention to
hole. We return to the beginning of the algorithm
we select the next hole for examination.)
4. Delete the current entry from the hole descriptor list
- (Since neither step two nor step three was true,
newly arrived fragment does interact with this hole
some way. Therefore, the current descriptor will
longer be valid. We will destroy it, and in the
two steps we will determine whether or not it
necessary to create any new hole descriptors.)
5. If fragment.first is greater than hole.first, then create
new hole descriptor "new_hole" with new_hole.first equal
hole.first, and new_hole.last equal to fragment.first
one
5
- (If the test in step five is true, then the first
of the original hole is not filled by this fragment.
create a new descriptor for this smaller hole.)
6. If fragment.last is less than hole.last and fragment.
fragments is true, then create a new hole
"new_hole", with new_hole.first equal to fragment.last
one and new_hole.last equal to hole.last
- (This test is the mirror of step five with
additional feature. Initially, we did not know how
the reassembled datagram would be, and therefore
created a hole reaching from zero to infinity
Eventually, we will receive the last fragment of
datagram. At this point, that hole descriptor
reaches from the last octet of the buffer to
can be discarded. The fragment which contains the
fragment indicates this fact by a flag in the
header called "more fragments". The test of this bit
this statement prevents us from creating a
for the unneeded hole which describes the space from
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
for further handling. Otherwise, return
4. Part Two: Managing the Hole Descriptor
The main complexity in the eight step algorithm above is
performing the arithmetical tests, but in adding and deleting
from the hole descriptor list. One could imagine an implementation
which the storage management package was many times more
than the rest of the algorithm, since there is no specified upper
on the number of hole descriptors which will exist for a datagram
reassembly. There is a very simple way to deal with the
descriptors, however. Just put each hole descriptor in the first
6
of the hole itself. Note that by the definition of the
algorithm, the minimum size of a hole is eight octets. To
hole.first and hole.last will presumably require two octets each.
additional two octets will be required to thread together the entries
the hole descriptor list. This leaves at least two more octets to
with implementation idiosyncrasies
There is only one obvious pitfall to this storage strategy.
must execute the eight step algorithm above before copying the data
the fragment into the reassembly buffer. If one were to copy the
first, it might smash one or more hole descriptors. Once the
above has been run, any hole descriptors which are about to be
have already been rendered obsolete
5. Loose
Scattering the hole descriptors throughout the reassembly
itself requires that they be threaded onto some sort of list so
they can be found. This in turn implies that there must be a pointer
the head of the list. In many cases, this pointer can be stored in
sort of descriptor block which the implementation associates with
reassembly buffer. If no such storage is available, a dirty
effective trick is to store the head of the list in a part of
internet header in the reassembly buffer which is no longer needed.
obvious location is the checksum field
When the final fragment of the datagram arrives, the packet
field in the internet header should be filled in
7
6.
The preceding description made one unacceptable simplification.
assumed that there were no internet options associated with the
being reassembled. The difficulty with options is that until
receives the first fragment of the datagram, one cannot tell how big
internet header will be. This is because, while certain options
copied identically into every fragment of a datagram, other options
such as "record route", are put in the first fragment only. (The "
fragment" is the fragment containing octet zero of the
datagram.)
Until one knows how big the internet header is, one does not
where to copy the data from each fragment into the reassembly buffer
If the earliest fragment to arrive happens to be the first fragment
then this is no problem. Otherwise, there are two solutions. First
one can leave space in the reassembly buffer for the maximum
internet header. In fact, the maximum size is not very large, 64
octets. Alternatively, one can simply gamble that the first
will contain no options. If, when the first fragment finally arrives
there are options, one can then shift the data in the buffer
sufficient distance for allow for them. The only peril in copying
data is that one will trash the pointers that thread the
descriptors together. It is easy to see how to untrash the pointers
The source and record route options have the interesting
that, since different fragments can follow different paths, they
arrive with different return routes recorded in different fragments
8
Normally, this is more information than the receiving Internet
needs. The specified procedure is to take the return route recorded
the first fragment and ignore the other versions
7. The Complete
In addition to the algorithm described above there are two parts
the reassembly process. First, when a fragment arrives, it is
to find the reassembly buffer associated with that fragment.
requires some mechanism for searching all the existing
buffers. The correct reassembly buffer is identified by an equality
the following fields: the foreign and local internet address,
protocol ID, and the identification field
The final part of the algorithm is some sort of timer
mechanism which decrements the time to live field of each
reassembled datagram, so that incomplete datagrams which have
their usefulness can be detected and deleted. One can either create
demon which comes alive once a second and decrements the field in
datagram by one, or one can read the clock when each first
arrives, and queue some sort of timer call, using whatever
mechanism is appropriate, to reap the datagram when its time has come
An implementation of the complete algorithm comprising all
parts was constructed in BCPL as a test. The complete algorithm
less than one and one-half pages of listing, and generated
400 nova machine instructions. That portion of the algorithm
involved with management of hole descriptors is about 20 lines of code
9
The version of the algorithm described here is actually
simplification of the author's original version, thanks to an
observation by Elizabeth Martin at MIT
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
