Methods, systems, and computer program products for processing a packet with layered headers using a data structure that positionally relates the layered headers

BACKGROUND OF THE INVENTION

[0001] The present invention relates to packet processing methods, systems, and computer program products, and, more particularly, to methods, systems, and computer program products for processing packets with layered headers.

[0002] The Internet Protocol (IP) resides within layer three (network layer) of the Open Systems Interconnection (OSI) model. IP may provide connection or datagram service between nodes in a network. An IP host may encapsulate data with an IP header, which is then passed to the data link layer. The data link protocol may encapsulate the IP header and data with its own header and then pass the encapsulated packet to the physical layer, where the packet may be encapsulated with yet another header, for transmission into the network as a serial bit stream.

[0003] The fields used in an IP header for IP Version 4 are shown in FIG. 1. The first field is the version of IP used to create the header. Networks running an older IP version may not be able to process packets encapsulated with headers associated with a newer IP version. An Internet Header Length (IHL) field follows the version field and specifies the length of the IP header in 32-bit words. A type-of-service field follows the IHL field and specifies the quality of service in terms of delay, reliability, and throughput to be applied to the packet. A total length field follows the type-of-service field and specifies the length of the IP header and the data, which follow the IP header. Note that the data may comprise a transport layer header, such as a TCP/UDP header and/or a security header, such as an IP Security Protocol (IPSec) header, along with user payload/data.

[0004] An identification (ID) field is used to correlate fragments of a data unit. For example, when a data unit is fragmented, an ID number may be assigned to the various fragments to allow the receiver to match the IDs and reassemble the packet. Three flag bits follow the identification field with one of the bits being hard coded to zero, one of the bits indicating whether fragmentation is allowed, and one of the bits indicating whether the present packet is the last fragment. A fragment offset field follows the flags field and indicates where in the datagram this particular fragment belongs. The first fragment has an offset of zero.

[0005] A time-to-live field indicates the amount of time that the packet may remain in the system. The time-to-live field is implemented as a hop counter. Each time the packet traverses through a router, the router decrements this field by one. The packet is destroyed once the time-to-live field reaches zero. This field may prevent undeliverable packets from cycling endlessly through the network. A protocol field follows the time-to-live field and specifies the next level protocol associated with the user payload/data. The Internet Assigned Numbers Authority (IANA) maintains a list of recognized protocols and numbers associated therewith at their Web site www.iana.org. A header checksum follows the protocol field and is a checksum on only the header portion of the IP packet.

[0006] Routers and gateways in a network may use the source and destination IP addresses to route the IP packet. An options field may be included and may be used for specific applications, such as network control and/or debugging. A padding field follows the optional options field to ensure that the IP header ends on a 32-bit boundary.

[0007] When a packet is traversing nodes or stations in a network, it may become encapsulated with multiple IP headers. Examples of such encapsulation are described in Internet Engineering Task Force (IETF) Request for Comment (RFC) document 2003 entitled “<i>IP Encapsulation within IP,” </i>by C. Perkins, October, 1996 (hereinafter “RFC 2003”), IETF RFC document 2004 entitled “<i>Minimal Encapsulation Within IP,” </i>by C. Perkins, October, 1996 (hereinafter “RFC 2004), IETF RFC document 2406 entitled “<i>IP Encapsulating Security Payload </i>(<i>ESP</i>),” by S. Kent, November 1998 (hereinafter “RFC 2406”), and IETF RFC document 3173 entitled <i>“IP Payload Compression Protocol </i>(<i>IPComp</i>)” by A. Shacham et al., September 2001 (hereinafter “RFC 3173”), the disclosures of which are hereby incorporated herein by reference. In processing IP packets with multiple, layered headers, a conventional packet processor system may parse down from the outer IP header to the inner IP header(s) to examine the protocol field in an inner IP header to determine how to process the IP packet. Conventional packet processor systems may be hard coded in hardware and/or software with offsets used to parse an IP packet with multiple IP headers. Likewise, IP Version 6 follows a similar strategy with nested headers at the beginning of the packet, which constitute different protocol wrappers. Unfortunately, such packet processor systems may need to be re-designed or reconfigured if packet header sizes and/or layouts change

SUMMARY OF THE INVENTION

[0008] According to some embodiments of the present invention, a first header of a packet is processed to obtain a first protocol. The first protocol is used as a key to read a record from a data structure in which the first protocol is associated with an offset in a second header of the packet. The second header of the packet is processed based on the offset in the second header to obtain a second protocol. Advantageously, by positionally relating the position of the protocol field in the second header of the packet with an offset stored in a data structure, if packet sizes and/or layouts should change, then the offset information in the data structure may be updated without the need to redesign and/or reconfigure hardware and/or software in a packet processor.

[0009] In other embodiments of the present invention, the record read from the data structure may associate the first protocol with an enable flag. The second header of the packet may be processed based on the offset in the second header to obtain the second protocol if the enable flag is set. The enable flag may allow a “base” set of protocols to be stored in non-volatile storage and copied to volatile storage upon system initialization. Thereafter, certain protocols may be disabled by use of the enable bit.

[0010] In still other embodiments of the present invention, the record read from the data structure may associate the first protocol with an offset to a payload/data portion of the packet.

[0011] In still other embodiments of the present invention, the packet may be processed based on an operation associated with the second protocol, such as a packet transform operation.

[0012] In still further embodiments of the present invention, the record read from the data structure may associate the first protocol with an operation flag and the packet may be processed based on an operation associated with the an operation flag.

[0013] In still further embodiments of the present invention, the second protocol may be used as a key to read a second record from the data structure in which the second protocol is associated with an operation flag. The packet may be processed based on an operation associated with the operation flag.

[0014] Although described primarily above with respect to method embodiments of the present invention, it will be understood that the present invention may be embodied as methods, systems, and computer program products.

BRIEF DESCRIPTION OF THE DRAWINGS

[0015] Other features of the present invention will be more readily understood from the following detailed description of specific embodiments thereof when read in conjunction with the accompanying drawings, in which:

[0016]FIG. 1 is a diagram that illustrates a structure of a conventional Internet Protocol (IP) packet header;

[0017]FIG. 2 is a diagram that illustrates a packet processing system in accordance with some embodiments of the present invention;

[0018]FIG. 3 is a diagram that illustrates a packet with layered headers in accordance with some embodiments of the present invention;

[0019]FIG. 4 is a flowchart that illustrates exemplary operations for processing a packet with layered headers in accordance with some embodiments of the present invention;

[0020]FIG. 5 is a diagram that illustrates an IP version <b>4</b> protocol data structure in accordance with some embodiments of the present invention;

[0021]FIG. 6 is a flowchart that illustrates further exemplary operations for processing a packet with layered headers in accordance with some embodiments of the present invention; and

[0022]FIG. 7 is a diagram that illustrates an IP version <b>6</b> protocol data structure in accordance with some embodiments of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0023] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the claims. Like reference numbers signify like elements throughout the description of the figures.

[0024] Embodiments of the present invention are described herein in the context of processing a packet. It will be understood that the term “packet” means a unit of information that may be transmitted electronically as a whole from one device to another. Accordingly, as used herein, the term “packet” may encompass such terms of art as “frame” or “message,” which may also be used to refer to a unit of transmission.

[0025] The present invention may be embodied as systems, methods, and/or computer program products. Accordingly, the present invention may be embodied in hardware and/or in software (including firmware, resident software, micro-code, etc.). Furthermore, the present invention may take the form of a computer program product on a computer-usable or computer-readable storage medium having computer-usable or computer-readable program code embodied in the medium for use by or in connection with an instruction execution system. In the context of this document, a computer-usable or computer-readable medium may be any medium that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

[0026] The computer-usable or computer-readable medium may be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a nonexhaustive list) of the computer-readable medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, and a portable compact disc read-only memory (CD-ROM). Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory.

[0027] The present invention is described herein with reference to flowchart and/or block diagram illustrations of methods, systems, and computer program products in accordance with exemplary embodiments of the invention. It will be understood that each block of the flowchart and/or block diagram illustrations, and combinations of blocks in the flowchart and/or block diagram illustrations, may be implemented by computer program instructions and/or hardware operations. These computer program instructions may be provided to a processor of a general purpose computer, a special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart and/or block diagram block or blocks.

[0028] These computer program instructions may also be stored in a computer usable or computer-readable memory that may direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer usable or computer-readable memory produce an article of manufacture including instructions that implement the function specified in the flowchart and/or block diagram block or blocks.

[0029] The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions that execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart and/or block diagram block or blocks.

[0030] Referring now to FIG. 2, a packet processing system <b>200</b> is illustrated that comprises a processor <b>205</b> and a memory <b>210</b>, in accordance with some embodiments of the present invention. The processor <b>205</b> communicates with the memory <b>210</b> via an address/data bus <b>215</b>. The processor <b>205</b> may be, for example, a commercially available or custom microprocessor. In some embodiments, the processor may be implemented as a packet processing state machine. The memory <b>210</b> is representative of one or more memory devices containing the software and data used by the processor <b>205</b> to process a packet, in accordance with some embodiments of the present invention. The memory <b>210</b> may include, but is not limited to, the following types of devices: cache, ROM, PROM, EPROM, EEPROM, flash, SRAM, and DRAM. To allow the packet processing system <b>200</b> to be updated with new software and/or data, particularly in field settings, writeable memory devices may be used. As shown in FIG. 2, the memory <b>210</b> comprises a protocol data structure <b>220</b> that may facilitate processing of packets with layered headers as will be described in detail hereafter, in accordance with some embodiments of the present invention.

[0031] Although FIG. 2 illustrates an exemplary packet processing system architecture that may facilitate processing of packets with layered headers in accordance with some embodiments of the present invention, it will be understood that the present invention is not limited to such a configuration but is intended to encompass any configuration capable of carrying out operations described herein. Moreover, it will be further appreciated that the functionality of the packet processing system <b>200</b> may also be implemented using discrete hardware components, one or more application specific integrated circuits (ASICs), or a programmed digital signal processor or microcontroller. As mentioned above with respect to the memory <b>210</b>, however, a programmable packet processing system <b>200</b> may allow the protocol data structure <b>220</b> to be updated, even in field settings, when changes are made to packet sizes and/or formats.

[0032] In some embodiments of the present invention, the packet processing system <b>200</b> may be used to implement one or more packet transform modules that comprise all or part of a plurality of transform modules that are coupled to each other in a series or pipelined configuration to perform packet transforms and/or cryptographic operations associated, for example, with the IPSec protocol as described in U.S. patent application Ser. No. ______, filed concurrently herewith, and entitled Methods, Systems, and Computer Program Products for Processing a Packet-Object Using Multiple Pipelined Processing Modules, the disclosure of which is hereby incorporated herein by reference.

[0033] Referring now to FIG. 3, a packet <b>300</b> comprising multiple layered headers, in accordance with some embodiments of the present invention, is illustrated. The packet <b>300</b> may be an IP packet, for example, and comprises a first (outer) IP header <b>305</b> that encapsulates a second (inner) IP header <b>310</b> and an IP payload/data portion <b>315</b>. Optionally, a packet-object header <b>320</b> may be used, which encapsulates the entire packet <b>300</b>. The packet-object header <b>320</b> may comprise information for processing the packet <b>300</b> in a pipelined processing system as described in U.S. patent application Ser. No. ______, entitled Methods, Systems, and Computer Program Products for Processing a Packet-Object Using Multiple Pipelined Processing Modules. Although only two layered IP headers <b>305</b> and <b>310</b> are shown, the packet <b>300</b> may comprise additional IP headers as described in RFC 2003, RFC 2004, RFC 2406, and/or RFC 3173. The IP payload/data <b>315</b> may comprise a user payload/data, such as a UDP or TCP payload, and, in some embodiments, may include cryptographic header(s)/information for IPSec processing, such as, but not limited to, an authentication header (AH), an encapsulating security payload (ESP), AH authentication data, and/or ESP authentication data.

[0034] Referring now to FIG. 4, exemplary operations for processing a packet with layered headers, in accordance with some embodiments of the present invention, begin at block <b>400</b> where a first packet header (e.g., first IP header <b>305</b> of FIG. 3) is processed to obtain a first protocol (e.g., protocol field of FIG. 1). Some networks may process packets differently based on the protocol associated with the packet. For example, a network may reject packets associated with Web traffic, but may accept packets associated with e-mail traffic. Thus, it may be desirable to parse a packet with layered headers to evaluate the underlying protocol(s) associated with the packet.

[0035] In accordance with some embodiments of the present invention, the first protocol is used as a key to read a record from the protocol data structure <b>220</b> at block <b>405</b> to obtain an offset to a second packet header (e.g., second IP header <b>310</b> of FIG. 3). This is illustrated, for example, in FIG. 5 where an exemplary data structure <b>500</b> is shown that may be used as the protocol data structure <b>220</b>, in accordance with some embodiments of the present invention. As shown in FIG. 5, the data structure <b>500</b> comprises a table of records with each record comprising a protocol field, an enable field, and offset in next header field, an offset to payload field, and a flag field. The protocol field corresponds to the protocol field in a packet header. The enable field may be implemented as a binary, “yes” or “no” field that indicates whether to parse a packet for encapsulated headers/protocols. The offset in next header field indicates a location of a protocol field in an encapsulated header. The offset to payload field indicates a location of a payload/data portion of the packet (e.g., IP payload/data <b>315</b> of FIG. 3). The flag field may indicate operations to be performed on the packet for a particular protocol. For example, such operations may include packet-processing operations for extracting the source and/or destination port addresses. The protocol data structure <b>220</b> is not limited to these fields and may comprise additional fields or may exclude one or more of the fields illustrated in FIG. 5, in accordance with various embodiments of the present invention. Moreover, although a table is shown in FIG. 5, other data structure types may be used without departing from the principles of the present invention.

[0036] Returning to the description of FIG. 4, a record from the protocol data structure is read at block <b>405</b> using the first protocol as a key to obtain an offset in a second (inner) packet header. Based on the example shown in FIG. 5, the offset to the protocol field in the second packet header for protocol <b>4</b> as the first (outer) packet header protocol is nine bytes. Thus, at block <b>410</b>, the second packet header may be processed based on the offset in the next header obtained from the protocol data structure <b>220</b> to obtain a second protocol. The packet may then be processed based on one or more operations associated with the first and/or second protocol, such as packet transform operations and/or extraction of source and/or destination port addresses.

[0037] Referring now to FIG. 6, exemplary operations for processing a packet with layered headers, in accordance with some embodiments of the present invention, will now be described. Operations begin at block <b>600</b> where a base pointer is obtained to a first (outer) packet header (e.g., first IP header <b>305</b> of FIG. 3). In some embodiments, it may be desirable to process packets differently based on a particular protocol version, such as different IP version. Thus, at block <b>605</b>, a determination may be made whether the packet is an IP version <b>6</b> packet. If the packet is an IP version <b>6</b> packet, then operations continue at block <b>610</b> where the packet is processed to obtain a first protocol from the first packet header. In the context of IPSec, a set of “selectors” may be extracted from a packet for processing. These selectors may include the “transport” protocol and the TCP/UDP source and/or destination port addresses. Accordingly, at block <b>610</b>, pointers may be set to the source and destination port addresses in the first packet header. Finally, based on the size of the first packet header (e.g., the IHL field of FIG. 1), the base pointer may be set to point to the end of the first packet header (i.e., the beginning of information following the first packet header). If the packet is not an IP version 6 packet, then the operations of block <b>610</b> are performed at block <b>615</b> for the non-IPv6 packet.

[0038] At block <b>620</b>, a determination is made whether the first protocol is in the protocol data structure <b>220</b> (e.g., the table of FIG. 5). In various embodiments of the present invention, separate protocol data structures <b>220</b> may be defined for different packet protocol versions or formats. For example, different protocol data structures <b>220</b> may be defined for IP version 6 environments and IP version 4 environments. FIG. 5 illustrates an exemplary protocol data structure <b>220</b> for an IP version 4 environment while FIG. 7 illustrates an exemplary protocol data structure <b>220</b> for an IP version 6 environment. If the first protocol is not in the protocol data structure <b>220</b>, then the protocol, source port address, and/or destination port address may be returned at block <b>630</b>. If the first protocol is in the protocol data structure <b>220</b>, however, then operations continue at block <b>640</b> where a determination is made whether an enable flag is set in the protocol data structure <b>220</b> for the first protocol. Advantageously, the enable flag may allow a “base” set of protocols to be stored in non-volatile storage and copied to volatile storage upon system initialization. Thereafter, certain protocols may be disabled by use of the enable bit. If the enable flag is not set, then an encapsulated header is not processed and operations conclude at block <b>630</b> as discussed above.

[0039] If, however, the enable flag is set (e.g., the enable flag is set for protocols <b>55</b>, <b>51</b>, and <b>108</b> in FIG. 5), then the flag field from the protocol data structure <b>220</b> is examined at block <b>650</b> to determine which set of packet processing operations to perform. As shown in FIG. 5, each protocol is associated with a different flag value. In some embodiments, however, protocols may share a common flag value as encapsulated headers for those protocols may be processed similarly. At block <b>660</b>, a second (inner) packet header may be processed to obtain a second protocol based on the offset in the next header from the protocol data structure <b>220</b>. Using a first protocol value of 51 as an example, FIG. 5 shows the offset to the protocol field in the second packet header as being zero bytes. In addition, the protocol data structure <b>220</b> may also be used to process the payload/data field and/or other fields in the second packet header. Again, using a first protocol value of 51 as an example, FIG. 5 shows the offset to the payload as being 24 bytes. In some embodiments, the offset to payload field in the protocol data structure <b>220</b> may contain an offset that facilitates the extraction of the source and/or destination port addresses. Thus, at block <b>660</b>, pointers may be set to the source and/or destination port addresses. Finally, in some embodiments, the base pointer may be set to the end of the second packet header (i.e., the beginning of information following the second packet header) if it is possible to have one or more additional encapsulated headers.

[0040] Operations continue at block <b>620</b> where a determination is made whether there is an additional encapsulated protocol that is in the protocol data structure. The loop may repeat until all encapsulated headers that are in the protocol data structure <b>220</b> are processed. It will be understood that the protocols illustrated in FIG. 5, IP mobility (<b>55</b>), authentication header (<b>51</b>), IP in IP (<b>4</b>), and IP payload compression protocol (<b>108</b>), and the protocols illustrated in FIG. 6, IPv6 hop by hop option (<b>0</b>), routing header for IPv6 (<b>43</b>), destination options for IPv6 (<b>60</b>), and authentication header (<b>51</b>) are merely exemplary and that other protocols may be used in accordance with various embodiments of the present invention.

[0041] The flowcharts of FIGS. 4 and 6 illustrate the architecture, functionality, and operations of some embodiments of the packet processing system <b>200</b>. In this regard, each block represents a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that in other implementations, the function(s) noted in the blocks may occur out of the order noted in FIGS. 4 and 6. For example, two blocks shown in succession may, in fact, be executed substantially concurrently or the blocks may sometimes be executed in the reverse order, depending on the functionality involved.

[0042] Many variations and modifications can be made to the preferred embodiments without substantially departing from the principles of the present invention. All such variations and modifications are intended to be included herein within the scope of the present invention, as set forth in the following claims.