IP datagram reassembly algorithms
RFC 815

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions

RFC:  815

                   IP DATAGRAM REASSEMBLY ALGORITHMS

                             David D. Clark
                  MIT Laboratory for Computer Science
               Computer Systems and Communications Group
                               July, 1982

     1.  Introduction

     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


                                   2

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

process.

     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".


                                   3

     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.


                                   4

     We  start  the algorithm when the earliest fragment of the datagram