1. Field of the Invention
This invention relates to digital communication systems, and more particularly to packet-switched communication systems.
2. Description of the Related Art
Request for Comment (RFC) 791, Internet Protocol (September 1981), and other RFCs define the Internet Protocol (IP) that is used for packet-switched communication networks. Information to be transmitted is divided into digital data blocks called datagrams, each of which has a header that includes the addresses of the sender (source) and intended receiver (destination), among other items of information. IP modules in the sender and receiver use the addresses to direct datagrams toward their destinations. In general, an IP module is a software program that is executed by a suitable electronic processor.
An IP datagram can be fragmented, which is to say the datagram can be split into several smaller packets, or fragments, when the network allows only smaller chunks of data to travel through the network. The several fragments that are the parts of an original datagram are sent separately through the network and have to be reassembled at their destination, reconstructing the original datagram.
Information located in communication protocol layers above the IP layer, such as the source and destination port addresses, is sometimes used to identify a unique context of an original IP datagram. Such information is not available in all fragments of the datagram, and thus the context of the original datagram cannot be recognized immediately from fragments formed by standard IP fragmentation mechanisms.
Sections 1.4, 2.3, and 3.2 of RFC 791 describe fragmentation and how fragments are identified and reassembled into an original datagram using data fields in the packet headers. Datagrams are typically fragmented by IP modules in gateways and reassembled at destination IP modules in destination IP hosts (e.g., computers), although other arrangements are permitted within networks and by agreement.
FIG. 1 depicts the format of an IP packet header according to IP version 4 (IPv4) described in Section 3.1 of RFC 791. As shown, the header includes six groups, or words, of 32 bits each that are transmitted last-bit first. Each 32-bit word includes one or more fields of digital information that identifies the packet with which the header is associated. The fields in an IPv4 header include Version, Type of Service, Total Length, Identification (ID), Flags, Fragment Offset, Time to Live (TtL), Protocol, Header Checksum, Source and Destination Addresses, and Options. The Options field has a variable length up to 40 bytes, and padding to the 32-bit word length may be provided.
After the header, which cannot be fragmented, an IPv4 packet includes a variable-length data (payload) field, which can be fragmented. Information in the fragmentable part of a datagram can include the source and destination ports and information according to another protocol. For example, an Authentication Header (AH) or Encapsulating Security Payload (ESP) protocol packet may carry encrypted Transmission Control Protocol (TCP) or User Datagram Protocol (UDP) traffic.
The ID, Flags, and Fragment Offset fields in an IPv4 packet header are used for identifying datagram fragments. According to RFC 791, the 16-bit ID field is assigned by the sender to aid in reassembling an original datagram from fragments. Of the 3-bit Flags field, bit 0 must be zero, bit 1 is a “don't fragment” flag, and bit 2 is a “more fragments” flag. If bit 1 is 0, then the datagram may be fragmented if necessary, and if bit 1 is 1, then the datagram shall not be fragmented. If bit 2 is 0, then this packet is the last fragment, and if bit 2 is 1, then there are more fragments. The 13-bit Fragment Offset field indicates where in the datagram this fragment belongs. The fragment offset is measured, i.e., fragments are counted, in units of 8 octets (64 bits), and the first fragment has offset zero. Thus, 8192 fragments of 8 octets each are permitted by IPv4, and an unfragmented datagram has bit 2=0 in the Flags field and Fragment Offset=0.
Even when IPv4 packets that are fragments of an original datagram arrive out of order, the information in the header of every packet enables fragments to be identified. By using bit 2 of the Flags field, it is possible to know whether or not more fragments are expected for the current datagram. If there are more fragments to come, then the current packet is considered a fragment; if there are no more fragments to come, but the Fragment Offset is not 0, then the current packet is considered the last fragment of a larger (unfragmented) datagram.
Section 3.2 of RFC 791 describes a datagram reassembly procedure that is performed only at the final destination with allocated reassembly resources, including a data buffer, a header buffer, a fragment block bit table, a total data length field, and a timer. The data from a fragment is placed in the data buffer according to its fragment offset and length, and bits are set in the fragment block bit table corresponding to the fragment blocks received. For each datagram, a buffer identifier is computed as the concatenation of the Source and Destination address, Protocol, and ID fields.
IP version 6 (IPv6) uses 64-bit words in headers that are arranged in a manner similar to IPv4. FIG. 2A depicts the format of an IPv6 packet header in 32-bit words. The fields in an IPv6 header include Version, Traffic Class, Flow Label, Payload Length, Next Header, Hop Limit, and Source and Destination IP Addresses. After the header, an IPv6 packet includes a variable-length data (payload) field, which can be fragmented and includes source and destination ports. The IPv6 header is simpler than the IPv4 header in that it has a fixed size with no variable-size Options field, and no fragmentation information, if any.
The fragmentation information that may be carried by the IPv4 Options field is handled in IPv6 as “option” headers that are chained through the use of the Next Header field. FIG. 2B depicts the IPv6 header format of a fragment, including an 8-bit Next Header field, an 8-bit Reserved field, a 13-bit Fragment Offset field, a 2-bit Reserved field, a 1-bit More Fragments field, and 32-bit Identification field. The fragmentation header is always the last of the “unfragmentable” headers (in IPv4, the 20-60 byte IP header is the unfragmentable header). This makes for one of the differences between IPv4 and IPv6: it is not always possible from an IPv6 header to see what the payload protocol is. The Next Header field has the identification of the next “option” header, which can be a payload protocol value, such as “UDP”, “TCP”, “AH”, or “ESP”, if there are no other options before the UDP, TCP, AS or ESP packets.
The essence of the datagram fragmentation mechanism in IPv6 is more or less the same as IPv4. An unfragmentable part of the datagram stays more or less intact (only the fragmentation information changes), and a fragmentable part of the datagram is broken up and sent as a number of fragments. The Fragment Offset is zero in the first fragment, and all fragments except the last have a “more fragments” flag set. This results in four types of packets, from a fragmentation point of view, in both IPv4 and IPv6: unfragmented; initial fragment; non-initial fragment, more-fragments flag set; and non-initial fragment, more-fragments flag not set (i.e., the last fragment) In IPv4, a packet's type can be determined from the packets header. In IPv6, a packet must be scanned for either a fragment header or a header that is part of the “fragmentable part” in order to know if the packet is a fragment or not.
U.S. Patent Application No. US 2006/0262808 by Lin et al. states that it describes a flow-through architecture for fragmentation and reassembly of tunnel packets in network devices, including a hardware pipeline without typical store-and-forward operations. Incoming fragmented packets are reassembled.
“Resolve IP Fragmentation, MTU, MSS, and PMTUD Issues with GRE and IPSEC”, Document ID 25885, Cisco (Oct. 2, 2006), which is available at http://www.cisco.com/warp/public/105/pmtud_ipfrag.html, also describes datagram reassembly from fragments, and notes that fragmentation increases receiver overhead because the receiver must allocate memory for arriving fragments and combine them into a datagram after all fragments are received.
As noted above, other problems with typical IP datagram fragmentation and reassembly involve difficulty in recognizing the context of an unfragmented datagram when information identifying the context is not available in all fragments of the datagram.