Abstract:
A method for processing a datagram, including receiving an initial fragment of the datagram over a communication link and classifying in an initial classification the initial fragment as a first fragment, a middle fragment, or a last fragment of the datagram. The method further includes receiving one or more subsequent fragments over the communication link, following the initial fragment, and classifying each of the one or more subsequent fragments in respective subsequent classifications so as to find among the subsequent fragments at least one of the first fragment, the middle fragment, and the last fragment of the datagram.  
     Responsive to the initial and the one or more subsequent classifications, a determination is made whether the datagram is completely constituted by the initial fragment and no more than two of the subsequent fragments. The datagram is reassembled responsive to the determination.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application claims the benefit of U.S. Provisional Patent Application No. 60/317,670, filed Sep. 6, 2001, which is incorporated herein by reference. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The present invention relates generally to transmission of datagrams, and specifically to reassembling fragments of Internet Protocol (IP) datagrams.  
         BACKGROUND OF THE INVENTION  
         [0003]    The Transmission Control Protocol/Internet Protocol suite is a widely-used transport protocol in digital packet networks. The Internet Protocol is described by Postel in Request For Comments (RFC) 791 of the U.S. Defense Advanced Research Projects Agency (DARPA), published in 1981, which is incorporated herein by reference. The Internet Protocol (IP) enables an IP datagram to be split into two or more IP fragments when an interface is unable to transmit the original datagram due to the latter being too large. The oversized datagram is split into separate IP fragments, each fragment being small enough to be transmitted by the interface. The process of fragmentation may occur more than once, depending on the maximum transmission unit (MTU) of each network component. For example, a datagram which is originally 1518 bytes—the maximum datagram size for networks operating according to an Ethernet protocol—may be sent to a first router having an MTU of 1000. The router divides the datagram into two IP fragments, 1000 bytes and 518 bytes, and forwards the two fragments to a second router having an MTU of 576 bytes, The second router divides the 1000 byte fragment into a 576 byte fragment and a 423 byte fragment, and thus transmits three fragments representing the original 1518 byte datagram.  
           [0004]    The IP layer at the receiving host accumulates the fragments until enough have arrived to reconstitute the original datagram. RFC 791 describes a reassembly mechanism, and an algorithm for reassembly based on tracking arriving fragments in a vector of bits. The algorithm operates in substantially the same manner regardless of the number of fragments.  
           [0005]    [0005]FIG. 1 is a diagram of IP header  10 , as described in RFC 791. Header  10  is prefixed to a message from a transport protocol, so forming a datagram or a fragment of a datagram. Header  10  is formed of 20 or more bytes. Fields  12 ,  14 , and  16  respectively represent a version number, a length of header  10 , and a type of service supported. A field  18  gives a total length of the datagram or fragment, in bytes, including header  10  and data. An identification field  20  is assigned by the sender as an aid to assembling datagrams.  
           [0006]    A field  22  comprises 1-bit flags  24 ,  26 , and  28 , and a 13-bit fragment offset  30 . Flag  24  must be set to zero. Flag  26  is set to 0 if the datagram may be fragmented, and is set to 1 if the datagram may not be fragmented. Flag  28  is set to 0 to indicate that this fragment is the last fragment, and is set to 1 to indicate that there are more fragments. Fragment offset  30  indicates where in the datagram the fragment belongs. It is calculated in units of 8 bytes, and is set to 0 for the first fragment. Field  22  is used by the datagram receiver to know in which order fragments are placed, and in order to correctly reassemble the fragments to the original datagram.  
           [0007]    RFC 815, “IP Datagram Reassembly Algorithms,” by David D. Clark, published in 1982, which is incorporated herein by reference, describes an alternative fragment reassembly system to that described in RFC 791. RFC 815 refers to a partially reassembled datagram which is assumed to have missing areas, termed holes. Each hole is characterized by the first byte number and a last byte number of the hole, the pair of numbers being termed a hole descriptor. A processor stores each hole descriptor, together with a pointer to the next hole, in its respective hole. The partially reassembled datagram is stored with its hole decriptors, by the processor, in a reassembly buffer. (The buffer size must be sufficient to accommodate the largest datagram transmitted by IP.) The buffer also maintains a global pointer to the first hole in the datagram.  
           [0008]    As long as network speed was the main factor limiting receiver rates, software implementations of IP receiver logic provided adequate performance levels. However, with the advent of network speeds in the 1 Gbps and 10 Gbps range, this is no longer the case. Faster IP receiver processing is required. requiring a new approach to the original specifications in RFC 791 and/or RFC 815. Among the issues to be addressed are maximization of parallel processing, efficient information passing, and rapid classification and handling of fragments.  
         SUMMARY OF THE INVENTION  
         [0009]    It is an object of some aspects of the present invention to provide apparatus and a method for efficient reassembly of datagram fragments.  
           [0010]    In preferred embodiments of the present invention, a processor classifies an incoming fragment, which has been generated from a complete datagram, as a first, a middle, or a last fragment. The processor performs similar classifications on up to two subsequent fragments. If the first two classifications result in first and last fragment classifications, and if the two fragments form the complete datagram, the complete datagram is reassembled from the two fragments. If the first two classifications do not result in fragments forming the complete diagram, but do imply that the complete datagram may be split into three fragments, the process classifies a third fragment. If the three classifications result in the first, the middle, and the last fragment which together form the complete datagram, the complete datagram is reassembled from the three fragments. By classifying incoming fragments as first, middle, or last fragments, re-assembling the complete datagram (where it is initially divided into two or three fragments) is made significantly faster than prior art systems for reassembling datagrams from fragments.  
           [0011]    If the classifications indicate that the datagram has been split into more than three fragments, for example, if the first two classifications yield different middle fragments, the fragments are processed using any suitable prior art reassembly method. Thus, the prior art method is only implemented for cases of four or more fragments. Most preferably, datagrams and their fragments are generated according to a standard protocol, such as the Internet Protocol (IP), in which case the prior art reassembly method is preferably the Clark algorithm described in the Background of the Invention.  
           [0012]    There is therefore provided, according to a preferred embodiment of the present invention, a method for processing a datagram, including:  
           [0013]    receiving an initial fragment of the datagram over a communication link;  
           [0014]    classifying in an initial classification the initial fragment as a first fragment, a middle fragment, or a last fragment of the datagram;  
           [0015]    receiving one or more subsequent fragments over the communication link, following the initial fragment;  
           [0016]    classifying each of the one or more subsequent fragments in respective subsequent classifications so as to find among the subsequent fragments at least one of the first fragment, the middle fragment, and the last fragment of the datagram;  
           [0017]    making a determination, responsive to the initial and the one or more subsequent classifications, whether the datagram is completely constituted by the initial fragment and no more than two of the subsequent fragments; and  
           [0018]    reassembling the datagram responsive to the determination.  
           [0019]    Preferably, each fragment includes a header, and classifying each fragment includes determining the classification of the fragment responsive to data comprised in the header.  
           [0020]    Preferably, receiving the initial fragment and the one or more subsequent fragments includes storing ordering data from a header of each fragment in an ordering buffer and storing payload data conveyed by each fragment in a reassembly buffer, and reassembling the datagram includes reassembling the payload data from the reassembly buffer.  
           [0021]    The method preferably also includes providing a state machine having a plurality of initial states, the state machine existing in one of the initial states responsive to receiving the initial fragment and the initial classification thereof. The state machine preferably also has a plurality of subsequent states, the state machine existing in one of the subsequent states responsive to receiving the initial fragment and the initial classification thereof, and to receiving the one or more subsequent fragments and the respective classifications of the one or more subsequent fragments.  
           [0022]    Preferably, making the determination includes determining that the datagram is not completely constituted by the initial fragment and the no more than two of the subsequent fragments, and transferring the data fragments to a memory for subsequent reassembly responsive to the determination.  
           [0023]    Preferably, the datagram for the method is generated according to an Internet protocol.  
           [0024]    There is further provided, according to a preferred embodiment of the present invention, apparatus for processing a datagram, including:  
           [0025]    a memory which receives an initial fragment and one or more subsequent fragments from a communication link and which stores the fragments; and  
           [0026]    a processor which is adapted to classify each of the fragments as a first fragment, a middle fragment, or a last fragment of the datagram and to make a determination, responsive to the classifications of each of the stored fragments, whether the datagram is completely constituted by the initial fragment and no more than two of the subsequent fragments and to reassemble the datagram responsive to the determination.  
           [0027]    Preferably, each fragment includes a header, and classifying each fragment includes determining the classification of the fragment responsive to data comprised in the header.  
           [0028]    Preferably, the memory includes:  
           [0029]    an ordering buffer which is adapted to store ordering data from a header included in each fragment; and  
           [0030]    a reassembly buffer which is adapted to store payload data conveyed by each fragment; and  
           [0031]    wherein the processor is adapted to reassemble the payload data from the reassembly buffer.  
           [0032]    The apparatus preferably also includes a state machine which is implemented from the memory and the processor, the state machine having a plurality of initial states, and existing in one of the initial states responsive to receiving the initial fragment and the initial classification thereof.  
           [0033]    The state machine preferably has a plurality of subsequent states, the state machine existing in one of the subsequent states responsive to receiving the initial fragment and the initial classification thereof, and to receiving the one or more subsequent fragments and the respective classifications of the one or more subsequent fragments.  
           [0034]    Preferably, making the determination includes determining that the datagram is not completely constituted by the initial fragment and the no more than two of the subsequent fragments, and the processor is adapted to transfer the data fragments within the memory for subsequent reassembly responsive to the determination.  
           [0035]    Preferably, the datagram for the apparatus is generated according to an Internet protocol.  
           [0036]    The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings, in which:  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0037]    [0037]FIG. 1 is a diagram of an Internet Protocol (IP) header  10 , as is known in the art;  
         [0038]    [0038]FIG. 2 is a flowchart showing steps in a first part of an algorithm for processing a fragment of an IP datagram;  
         [0039]    [0039]FIG. 3 is a flowchart showing steps in a second part of the algorithm of FIG. 2 for processing the fragment of the IP datagram;  
         [0040]    [0040]FIG. 4 is a block diagram of a fragment reassembler, according to a preferred embodiment of the present invention;  
         [0041]    [0041]FIG. 5 is a flowchart for reassembling data fragments, according to a preferred embodiment of the present invention; and  
         [0042]    [0042]FIG. 6 is a diagram of a state machine corresponding to the flowchart of FIG. 5, according to a preferred embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0043]    [0043]FIG. 2 is a flowchart  50  showing steps in a first part of a system generally similar to that described by David D. Clark, in Request For Comments (RFC) 815. RFC 815 is described in more detail in the Background of the Invention. In flowchart  50 , as each fragment is received, a fragment-start and a fragment-length are computed, in bytes, using fields  18  and  22  of IP header  10  (FIG. 1). The values of fragment-start and fragment-length are then used in flowchart  50 , by comparing their values with each hole descriptor in turn. In an initial step  52 , values of the first hole are read from the buffer, and in steps  54  and  58  the values are loaded and used to check if the hole contains the received fragment. If, in comparison step  58  the hole does not contain the fragment, the process of checking continues through steps  64  and  56 , until all holes have been checked, in which case an invalidate step  62  determines that the fragment is not valid. If, in comparison step  58 , a hole is determined to contain the fragment, in a validation step  60  the fragment is reported as valid, and the process continues to a second part  70 .  
         [0044]    [0044]FIG. 3 is a flowchart showing steps in second part  70 . Once the fragment has been reported as valid in validation step  60 , second part  70  classifies the fragment as one of four types. The classification is performed by comparing the hole start with the fragment start, and then by comparing the hole end with the fragment end, as shown in comparisons  72 ,  74 , and  76 . The four possible classifications of a valid fragment are:  
         [0045]    Class 1. The fragment start and hole start are the same, and the fragment is shorter than the hole. A previous hole is partly filled by the fragment.  
         [0046]    Class 2. The fragment end and hole end are the same, and the fragment is shorter than the hole. A previous hole is partly filled by the fragment.  
         [0047]    Class 3. The fragment fills the “middle” of an existing hole.  
         [0048]    Class 4. The fragment start and hole start are the same, and the fragment end and hole end are also the same, so that the hole is filled by the fragment.  
         [0049]    After the classification has been made, hole information, such as new hole start and/or end, and hole pointers, are updated.  
         [0050]    The algorithms described with reference to FIGS. 2 and 3 are executed before data from the fragment is copied to a reassembly buffer. Since the header information for holes is stored in the reassembly buffer, delays in accessing the buffer occur since the buffer size required necessitates buffer implementation as a memory external to the processor.  
         [0051]    Reference is now made to FIG. 4, which is a block diagram of a fragment reassembler  90 , according to a preferred embodiment of the present invention. Reassembler  90  receives packets over a communication link  91  in the form of fragments of a datagram and reassembles the fragments into a complete datagram. Data from the reassembled datagram is conveyed further, into to a receiver which contains the reassembler. Reassembler  90  comprises a central processing unit (CPU)  92 , most preferably a reduced instruction set controller (RISC), coupled to a memory  94 . Memory  94  stores instructions which operate CPU  92 , and further comprises a fragment ordering buffer  96  and a fragment reassembly buffer  98 . Ordering buffer  96  stores data concerning the order of received fragments, such as first and last sequence numbers of the fragment, the data for the buffer typically being derived from information in headers of the received fragments. Reassembly buffer  98  stores payload data conveyed by the fragments, storing the data until a CPU  92  decides how the payload data is to be disposed of. Reassembler  90  is most preferably implemented as an application specific integrated circuit (ASIC), or alternatively by any other means known in the art, such as by a combination of custom-built and/or standard devices.  
         [0052]    As described in the Background of the Invention, an Internet Protocol (IP) datagram may be divided into two or more fragments before being transmitted from a transmitter, depending on the size of the datagram and the maximum transmission unit (MTU) of the path from the transmitter. Each fragment produced comprises identifying information in the fragment&#39;s header that enables a receiver of the fragment to identify the connection and socket of the datagram. Each fragment header also comprises sequential information of data conveyed in the fragment, such as a first and last number of bytes of the fragment data, or equivalent information. While the description hereinbelow is directed to reassembling fragments which have been generated according to the Internet Protocol, it will be appreciated that the scope of the present invention applies to any other protocol wherein datagrams are divided into fragments, and wherein the fragments comprise sequential information of data conveyed in the fragments.  
         [0053]    [0053]FIGS. 5 and 6 are respectively a flowchart  100  for reassembling data fragments, and a diagram of a state machine  130  corresponding to the flowchart, according to preferred embodiments of the present invention. Reassembler  90  (FIG. 4) implements flowchart  100  and state machine  130  from instructions stored in memory  94 . In an initial state  132 , corresponding to the start of flowchart  100 , reassembler  90  waits to receive a datagram fragment. In a first receive and classification step  104 , the reassembler receives a first fragment and classifies the fragment as either a first, a middle, or a last fragment. At the end of step  104 , state machine  130  will be in “first (fragment) exists” state  134 , “middle exists” state  136 , or “last exists” state  138 , according to the type of fragment received. In FIG. 6, states such as initial state  132  and state  136  are connected by arrows having descriptions of a fragment required to transfer from one state to another. For example, MIDDLE (1) connecting state  132  to state  136  indicates that the first fragment received by the reassembler (in state  132 ) is a middle fragment; NOT MIDDLE (3) connecting states  142  and  146  indicates that the third fragment received by the reassembler is not a required middle fragment In order to classify the first fragment, CPU  92  uses flag  28  and fragment offset field  30  (FIG. 1). Table I below shows how flag  28  and offset field classify the fragment.  
                               TABLE I                                   Flag 28   Fragment Offset               State   Field 30   Fragment Classification                           Set (1)    0   First part           Set (1)   &gt;0   Middle part           Not set (0)   &gt;0   Last part                      
 
         [0054]    In addition to classifying the fragment, CPU  92  determines start and end values of the fragment, fragment1.start and fragment1.end respectively, in bytes, using length field  18  and offset  30 . Using fragment1.start and/or fragment1.end, CPU  92  calculates connection parameters, consisting of potential values middle_start and/or middle_end that a next fragment might have. The connection parameters are stored in ordering buffer  96 , and data comprised in the fragment is stored in reassembly buffer  98 . The connection parameters calculated depend on the initial classification determined in step  104 , and are listed in Table II below.  
                           TABLE II                                   Fragment               Classification   Connection Parameter                           First part   middle_start = fragment1.end + 1           Middle part   middle_start = fragment1.start               middle_end = fragment1.end           Last part   middle_end = fragment1.start − 1                      
 
         [0055]    In a second step  106  a second fragment is received and CPU  92  determines start and end values of the fragment, fragment2.start and fragment2.end respectively, using length field  18  and offset  30 . The fragment is classified substantially as described above for step  104  with reference to Table I.  
         [0056]    In comparison steps  108  and  109 , the two fragments are compared. Tables III, IV and V below list possible types of the second fragment and comparisons between first and second fragment parameters. The tables give results of the comparison and updates to the connection parameters, where appropriate, and a state that machine  130  is in after the comparison. Tables III, IV, and V apply when the first fragment has been classified as a first part, middle part, and last part respectively.  
                                 TABLE III                           First fragment is First part                Second Fragment   Result   State                       Last part.   First and second   Finished two           middle_start =   fragments make a   fragments total           fragment2.start   complete datagram   state 140           Last part.   Missing middle   Missing middle           middle_start &lt;   part.   state 142           fragment2.start   middle_end =               fragment2.start −               1           Middle part.   Missing last part.   Missing last state           middle_start =   middle_end =   144           fragment2.start   fragment2.end + 1           Middle part.   More than three   More than three           middle_start not   fragments   fragments state           eql       146           fragment2.start           None of the above   Error   First exists state                   134                      
 
         [0057]    [0057]                                 TABLE IV                           First fragment is Middle part                Second Fragment   Result   State                       Middle part.   More than three   More than three           middle_end &lt;   fragments in   fragments state           fragment2.start or   datagram   146           middle_start &gt;           fragment2.end           Last part.   Missing first   Missing first           middle_end + 1 =   part.   state 148           fragment2.start           First part.   Missing last part   Missing last state           middle_start =       144           fragment2.end + 1           None of the above   Error   Middle exists                   state 136                        
         [0058]    [0058]                                 TABLE V                           First fragment is Last part                Second Fragment   Result   State                       First part.   First and second   Finished two           middle_end =   fragments make a   fragments total           fragment2.end   complete datagram   state 140           First part.   Missing middle   Missing middle           middle_end &lt;   part.   state 142           fragment2.end   middle_start =               fragment2.end + 1           Middle part.   Missing first   Missing first           middle_end =   part.   state 148           fragment2.end   middle_start =               fragment2.start           Middle part.   More than three   More than three           middle_end &gt;   fragments   fragments state           fragment2.end       146           None of the above   Error   Middle exists                   state 134                        
         [0059]    If the first and second fragments make a complete datagram, corresponding to the first rows of Tables III and V, comparison  108  is positive. In this case process  100  completes in complete datagram step  110 , corresponding to state machine  130  moving to “Finished two fragments total” state  140 . When comparison  108  is negative, comparison  109  is invoked, to check if there are more than three fragments in the datagram, corresponding to the fourth rows of Tables III and V and the first row of Table IV.  
         [0060]    If comparison  109  is positive, process  100  finishes with an invoke Clark algorithm step  118 , corresponding to machine  130  moving to state  146 . If comparison  109  is negative, process  100  continues to a receive third fragment step  110 , corresponding to state machine  130  being in states  142 ,  144 , or  148 . On receipt of the third fragment CPU  92  determines start and end values of the fragment, fragment3.start and fragment3.end respectively, and in a comparison step  112  the CPU compares these with parameters derived from the two fragments already received. Details of the comparisons are given in Tables VI, VII, and VIII below, corresponding to state machine  130  being in states  148 ,  142 , and  144  respectively. The tables also show the final state of machine  130 .  
                                 TABLE VI                           Missing first fragment state 148                Third Fragment   Result   State                       First part.   Three fragments   Finished three           middle_start =   make a complete   fragments total           fragment3.end   datagram   state 150           First part.   More than 3   More than three           middle_start &gt;   fragments.   fragments state           fragment3.end       146           Middle part.   More than 3   More than three           middle_start ≧   fragments.   fragments state           fragment3.end       146           None of the above   Error   Missing first                   fragment state 148                      
 
         [0061]    [0061]                                 TABLE VII                           Missing middle fragment state 142                Third Fragment   Result   State                       Middle part.   Three fragments   Finished three           middle_start =   make a complete   fragments total           fragment3.start   datagram   state 150           and           middle_end =           fragment3.end           Middle part.   More than 3   More than three           middle_start &lt;   fragments.   fragments state           fragment3.start       146           Middle part.   More than 3   More than three           middle_end &gt;   fragments.   fragments state           fragment3.end       146           None of the above   Error   Missing first                   fragment state 142                        
         [0062]    [0062]                                 TABLE VIII                           Missing last fragment state 144                Third Fragment   Result   State                       Last part.   Three fragments   Finished three           middle_end =   make a complete   fragments total           fragment3.start − 1   datagram   state 150           Last part.   More than 3   More than three           middle_end &lt;   fragments.   fragments state           fragment3.start − 1       146           Middle part.   More than 3   More than three           middle_end ≦   fragments.   fragments state           fragment3.end       146           None of the above   Error   Missing last                   fragment state 144                        
         [0063]    If in comparison  112  it is found that the three received fragments form a complete datagram, process  100  finishes at complete datagram step  114 , corresponding to the first rows of Tables VI, VII, and VIII, and to state machine  130  being in state  150 . If comparison  112  is false, process  100  concludes by transferring to a reassembly method suited to more than three fragments, such as the Clark algorithm. This corresponds to state machine  130  moving from state  146  to a further reassembly state  152 , and to the already received fragments preferably being transferred to a different region of memory  94 . Alternatively, the reassembly method may use links, stored in memory  94 , to the already received fragments.  
         [0064]    Inspection of FIG. 6 shows that states within a rectangle  131  correspond to states where it is known that there are an unknown number of fragments; states within a rectangle  133  correspond to states where it is known that there are more than two fragments; and states within a rectangle  135  correspond to completed states where it is known that there are an two or three fragments.  
         [0065]    It will be appreciated that state machine  130 , by classifying datagram fragments as first, middle, or last fragments, is able to re-assemble datagrams which have been fragmented into up to three fragments extremely efficiently.  
         [0066]    Data networks which operate according to an Ethernet protocol are able to transmit frames having a maximum length of 1518 bytes. A maximum transmission unit (MTU) for each component of the network, such as a router which conveys frames over the network, must be at least 576 bytes; typically, a number of routers within the network have the same values of MTU, such as 576 bytes. Thus, an Ethernet frame of 1518 bytes would be fragmented into three fragments if passing through one or more routers having MTUs of 576 bytes. State machine  130  will efficiently reassemble such fragments, without having to transfer to state  152 , i.e., without having to implement a further reassembly algorithm.  
         [0067]    It will be appreciated that the preferred embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.