Browse Prior Art Database

IP datagram reassembly algorithms (RFC0815)

IP.com Disclosure Number: IPCOM000003864D
Original Publication Date: 1982-Jul-01
Included in the Prior Art Database: 2000-Sep-13
Document File: 8 page(s) / 15K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

D.D. Clark: AUTHOR

Abstract

One of the mechanisms of IP is fragmentation and reassembly. Under

This text was extracted from a ASCII document.
This is the abbreviated version, containing approximately 19% of the total text.

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