Movatterモバイル変換
[0]ホーム
[RFC Home] [TEXT|PDF|HTML] [Tracker] [IPR] [Info page]
UNKNOWN
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. Undercertain circumstances, a datagram originally transmitted as a singleunit will arrive at its final destination broken into several fragments.The IP layer at the receiving host must accumulate these fragments untilenough have arrived to completely reconstitute the original datagram.The specification document for IP gives a complete description of thereassembly mechanism, and contains several examples. It also providesone possible algorithm for reassembly, based on keeping track ofarriving fragments in a vector of bits. This document describes analternate approach which should prove more suitable in some machines. A superficial examination of the reassembly process may suggestthat it is rather complicated. First, it is necessary to keep track ofall the fragments, which suggests a small bookkeeping job. Second, whena new fragment arrives, it may combine with the existing fragments in anumber of different ways. It may precisely fill the space between twofragments, or it may overlap with existing fragments, or completely
2duplicate existing fragments, or partially fill a space between twofragments without abutting either of them. Thus, it might seem that thereassembly process might involve designing a fairly complicatedalgorithm that tests for a number of different options. In fact, the process of reassembly is extremely simple. Thisdocument describes a way of dealing with reassembly which reduces thebookkeeping problem to a minimum, which requires for storage only onebuffer equal in size to the final datagram being reassembled, which canreassemble a datagram from any number of fragments arriving in any orderwith any possible pattern of overlap and duplication, and which isappropriate for almost any sort of operating system. The reader should consult the IP specification document to be surethat he is completely familiar with the general concept of reassembly,and the particular header fields and vocabulary used to describe theprocess. 2. The Algorithm In order to define this reassembly algorithm, it is necessary todefine some terms. A partially reassembled datagram consists of certainsequences of octets that have already arrived, and certain areas stillto come. We will refer to these missing areas as "holes". Each holecan be characterized by two numbers, hole.first, the number of the firstoctet in the hole, and hole.last, the number of the last octet in thehole. This pair of numbers we will call the "hole descriptor", and wewill assume that all of the hole descriptors for a particular datagramare gathered together in the "hole descriptor list".
3 The general form of the algorithm is as follows. When a newfragment of the datagram arrives, it will possibly fill in one or moreof the existing holes. We will examine each of the entries in the holedescriptor list to see whether the hole in question is eliminated bythis incoming fragment. If so, we will delete that entry from the list.Eventually, a fragment will arrive which eliminates every entry from thelist. At this point, the datagram has been completely reassembled andcan 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 newfragment arrives, in order to determine whether or not any of theexisting holes are filled by the new fragment. In the second part ofthis description, we will show a ridiculously simple algorithm formanagement of the hole descriptor list. 3. Fragment Processing Algorithm An arriving fragment can fill any of the existing holes in a numberof ways. Most simply, it can completely fill a hole. Alternatively, itmay leave some remaining space at either the beginning or the end of anexisting hole. Or finally, it can lie in the middle of an existinghole, breaking the hole in half and leaving a smaller hole at each end.Because of these possibilities, it might seem that a number of testsmust be made when a new fragment arrives, leading to a rathercomplicated algorithm. In fact, if properly expressed, the algorithmcan compare each hole to the arriving fragment in only four tests.
4 We start the algorithm when the earliest fragment of the datagramarrives. We begin by creating an empty data buffer area and putting oneentry in its hole descriptor list, the entry which describes thedatagram as being completely missing. In this case, hole.first equalszero, and hole.last equals infinity. (Infinity is presumably implementedby a very large integer, greater than 576, of the implementor's choice.)The following eight steps are then used to insert each of the arrivingfragments into the buffer area where the complete datagram is beingbuilt up. The arriving fragment is described by fragment.first, thefirst octet of the fragment, and fragment.last, the last octet of thefragment. 1. Select the next hole descriptor from the hole descriptor 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 the newly arrived fragment does not overlap with the hole in any way, so we need pay no further attention to this hole. We return to the beginning of the algorithm where 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, the newly arrived fragment does interact with this hole in some way. Therefore, the current descriptor will no longer be valid. We will destroy it, and in the next two steps we will determine whether or not it is necessary to create any new hole descriptors.) 5. If fragment.first is greater than hole.first, then create a new hole descriptor "new_hole" with new_hole.first equal to hole.first, and new_hole.last equal to fragment.first minus one.
5 - (If the test in step five is true, then the first part of the original hole is not filled by this fragment. We create a new descriptor for this smaller hole.) 6. If fragment.last is less than hole.last and fragment.more fragments is true, then create a new hole descriptor "new_hole", with new_hole.first equal to fragment.last plus one and new_hole.last equal to hole.last. - (This test is the mirror of step five with one additional feature. Initially, we did not know how long the reassembled datagram would be, and therefore we created a hole reaching from zero to infinity. Eventually, we will receive the last fragment of the datagram. At this point, that hole descriptor which reaches from the last octet of the buffer to infinity can be discarded. The fragment which contains the last fragment indicates this fact by a flag in the internet header called "more fragments". The test of this bit in this statement prevents us from creating a descriptor for the unneeded hole which describes the space from the end of the datagram to infinity.) 7. Go to step one. 8. If the hole descriptor list is now empty, the datagram is now complete. Pass it on to the higher level protocol processor for further handling. Otherwise, return. 4. Part Two: Managing the Hole Descriptor List The main complexity in the eight step algorithm above is notperforming the arithmetical tests, but in adding and deleting entriesfrom the hole descriptor list. One could imagine an implementation inwhich the storage management package was many times more complicatedthan the rest of the algorithm, since there is no specified upper limiton the number of hole descriptors which will exist for a datagram duringreassembly. There is a very simple way to deal with the holedescriptors, however. Just put each hole descriptor in the first octets
6of the hole itself. Note that by the definition of the reassemblyalgorithm, the minimum size of a hole is eight octets. To storehole.first and hole.last will presumably require two octets each. Anadditional two octets will be required to thread together the entries onthe hole descriptor list. This leaves at least two more octets to dealwith implementation idiosyncrasies. There is only one obvious pitfall to this storage strategy. Onemust execute the eight step algorithm above before copying the data fromthe fragment into the reassembly buffer. If one were to copy the datafirst, it might smash one or more hole descriptors. Once the algorithmabove has been run, any hole descriptors which are about to be smashedhave already been rendered obsolete. 5. Loose Ends Scattering the hole descriptors throughout the reassembly bufferitself requires that they be threaded onto some sort of list so thatthey can be found. This in turn implies that there must be a pointer tothe head of the list. In many cases, this pointer can be stored in somesort of descriptor block which the implementation associates with eachreassembly buffer. If no such storage is available, a dirty buteffective trick is to store the head of the list in a part of theinternet header in the reassembly buffer which is no longer needed. Anobvious location is the checksum field. When the final fragment of the datagram arrives, the packet lengthfield in the internet header should be filled in.
7 6. Options The preceding description made one unacceptable simplification. Itassumed that there were no internet options associated with the datagrambeing reassembled. The difficulty with options is that until onereceives the first fragment of the datagram, one cannot tell how big theinternet header will be. This is because, while certain options arecopied identically into every fragment of a datagram, other options,such as "record route", are put in the first fragment only. (The "firstfragment" is the fragment containing octet zero of the originaldatagram.) Until one knows how big the internet header is, one does not knowwhere 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 possibleinternet header. In fact, the maximum size is not very large, 64octets. Alternatively, one can simply gamble that the first fragmentwill contain no options. If, when the first fragment finally arrives,there are options, one can then shift the data in the buffer asufficient distance for allow for them. The only peril in copying thedata is that one will trash the pointers that thread the holedescriptors together. It is easy to see how to untrash the pointers. The source and record route options have the interesting featurethat, since different fragments can follow different paths, they mayarrive with different return routes recorded in different fragments.
8Normally, this is more information than the receiving Internet moduleneeds. The specified procedure is to take the return route recorded inthe first fragment and ignore the other versions. 7. The Complete Algorithm In addition to the algorithm described above there are two parts tothe reassembly process. First, when a fragment arrives, it is necessaryto find the reassembly buffer associated with that fragment. Thisrequires some mechanism for searching all the existing reassemblybuffers. The correct reassembly buffer is identified by an equality ofthe following fields: the foreign and local internet address, theprotocol ID, and the identification field. The final part of the algorithm is some sort of timer basedmechanism which decrements the time to live field of each partiallyreassembled datagram, so that incomplete datagrams which have outlivedtheir usefulness can be detected and deleted. One can either create ademon which comes alive once a second and decrements the field in eachdatagram by one, or one can read the clock when each first fragmentarrives, and queue some sort of timer call, using whatever systemmechanism is appropriate, to reap the datagram when its time has come. An implementation of the complete algorithm comprising all theseparts was constructed in BCPL as a test. The complete algorithm tookless than one and one-half pages of listing, and generated approximately400 nova machine instructions.That portion of the algorithm actuallyinvolved with management of hole descriptors is about 20 lines of code.
9 The version of the algorithm described here is actually asimplification of the author's original version, thanks to an insightfulobservation by Elizabeth Martin at MIT.
[8]ページ先頭