Data structures and state tracking for network protocol processing

• US 8,190,767 B1
• Filed: 12/03/2007
• Issued: 05/29/2012
• Est. Priority Date: 06/24/2003
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Maufer, Thomas A., Gyugyi, Paul J., Nanda, Sameer, Sidenblad, Paul J.
• Primary Examiner(s): Chan, Wing
• Assistant Examiner(s): Katsikis, Kostas
• Application Number:
  US11/949,715
• Time in Patent Office: 1,639 Days
• Field of Search: 709/238, 709/223, 709/224
• US Class Current: 709/238
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL

Abstract

Described are data structures, and methodology for forming same, for network protocol processing. A method for creating data structures for firewalling and network address translating is described. A method for creating data structures for physical layer addressing is described. A method for security protocol support using a data structure is described. A method for creating at least one data structure sized responsive to whether a firewall is activated is described. A data structure for routing packets is described. A method of forming hashing table chains is described. Additionally, method and apparatus for tracking packet states is described. More particularly, Transmission Control Protocol (“TCP”) tracking of states for packets is described. In an embodiment, a division between software states and hardware states is made as a packet is processed by both software and hardware. Additionally, method and apparatus for network protocol processing are described. For example, a packet for network address translation having a media access control header is obtained, from which information, including the media access control header, is obtained. The information is parsed into one or more data structures. It is determined whether a network processing unit is in a first round processing mode, or a second round pass-through mode.

Claims

1. A method for data lookup in a network, comprising:

instantiating a first data structure and a second data structure;

populating the first data structure with state information for a packet;

populating the second data structure with packet information for the packet; and

cross-linking the first data structure and the second data structure, the cross-linking including;

hashing at least a portion of the packet information to generate an index; and

storing, in the first data structure, the index in association with the state information, wherein the index cross-links the first data structure and the second data structure with a single value,

wherein the first data structure can be accessed from the second data structure via the single value without having to check for matches involving any other values.

2. The method, according to claim 1, wherein the first data structure is a connection table.

3. The method, according to claim 1, wherein the second data structure is a network address translation table.

4. The method, according to claim 1, wherein the state information includes Transport Control Protocol state.

5. The method, according to claim 1, wherein the packet information comprises a five-tuple of information.

6. The method, according to claim 1, further comprising the steps of:

storing, in the second data structure, the index in association with the packet information; and

generating a third data structure based on the index stored in the second data structure.

7. A computing device for data lookup in a network, comprising:

a central processing unit (CPU);

a memory coupled to the CPU; and

a network processor unit coupled to the CPU and configured to;

instantiate a first data structure and a second data structure,

populate the first data structure with state information for a packet,

populate the second data structure with packet information for the packet, and

cross-link the first data structure and the second data structure, wherein the cross-linking includes hashing at least a portion of the packet information to generate an index and storing in the first data structure the index in association with the state information, wherein the index cross-links the first data structure and the second data structure with a single value,

wherein the first data structure can be accessed from the second data structure via the single value without having to check for matches involving any other values.

8. A method for creating data structures in a network, comprising:

instantiating a first, a second and a third data structure;

populating the first data structure with state information;

populating the second data structure with network address translation information;

populating the third data structure with interface information; and

cross-linking the first data structure and the second data structure to the third data structure, the cross-linking including;

generating an index for the interface information; and

storing the index in the first data structure in association with the state information and in the second data structure in association with the network address translation information, the index cross-linking the first data structure and the second data structure with a single value,

wherein the generating comprises hashing at least a portion of the interface information, and

the first data structure can be accessed from the second data structure via the single value without having to check for matches involving any other values.

9. The method, according to claim 8, further comprising:

instantiating a fourth data structure;

populating the fourth data structure with routing information; and

cross-linking the fourth data structure to the third data structure, the cross-linking including;

storing the index in the fourth data structure in association with the routing information.

10. The method, according to claim 9, wherein the third data structure is an address resolution table.

11. The method, according to claim 10, wherein the first data structure is a connection table.

12. The method, according to claim 11, wherein the populating of the first data structure comprises adding connection information to the first data structure.

13. The method, according to claim 11, wherein the connection information comprises a packet five-tuple of information.

14. The method, according to claim 11, wherein the second data structure is a network address translation table.

15. The method, according to claim 14, wherein the fourth data structure is a routing table.

16. The method, according to claim 8, wherein the interface information comprises a media access control address.

17. The method, according to claim 16, wherein the interface information comprises a virtual local area network identifier.

18. The method, according to claim 17, wherein the interface information comprises an interface mask.