Data structures and state tracking for network protocol processing

• US 9,146,949 B1
• Filed: 12/03/2007
• Issued: 09/29/2015
• Est. Priority Date: 06/24/2003
• Status: Expired due to Fees

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Maufer, Thomas A., Nanda, Sameer, Sidenblad, Paul J., Gyugl, Paul J.
• Primary Examiner(s): Hu, Jensen
• Application Number:
  US11/949,732
• Time in Patent Office: 2,857 Days
• Field of Search: 707/101, 707/747
• US Class Current: 1/1
• 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. A 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. A method and apparatus for network protocol processing are also described.

Claims

1. A method of forming hashing table chains, comprising:

obtaining a first connection hash value, the first connection hash value pointing to a first slot in the hashing table;

obtaining a second connection hash value, the second connection hash value pointing to the first slot in the hashing table;

assigning the second connection hash value to a second slot in the hashing table;

pointing the first slot toward the second slot;

obtaining a third connection hash value, the third connection hash value pointing to the second slot in the hashing table;

moving contents of the second slot to a third slot in the hashing table; and

assigning the third connection hash value to the second slot in the hashing table.

2. The method, according to claim 1, wherein the first connection hash value, the second connection hash value and the third connection hash value are respective hashes of packet information.

3. The method, according to claim 2, wherein the packet information is a packet five-tuple.

4. A computing device for forming hashing table chains, comprising:

a central processing unit (CPU);

a memory coupled to the CPU; and

a network processor unit (NPU) coupled to the CPU and configured to;

obtain a first connection hash value, the first connection hash value pointing to a first slot in the hashing table,

obtain a second connection hash value, the second connection hash value pointing to the first slot in the hashing table,

assign the second connection hash value to a second slot in the hashing table,

point the first slot toward the second slot,

obtain a third connection hash value, the third connection hash value pointing to the second slot in the hashing table,

move contents of the second slot to a third slot in the hashing table, and

assign the third connection hash value to the second slot in the hashing table.

5. The computing device, according to claim 4, wherein the first connection hash value, the second connection hash value and the third connection hash value are respective hashes of packet information.

6. The computing device, according to claim 5, wherein the packet information is a packet five-tuple.

7. The computing device, according to claim 4, wherein the NPU is implemented in hardware.

8. The computing device, according to claim 4, wherein the NPU is implemented in software.

9. The computing device, according to claim 4, wherein the NPU is implemented in combination of hardware and software.

10. A computer-readable storage medium, excluding transitory signal-bearing media, containing a program which, when executed by a processor, causes execution of a method of forming hashing table chains, comprising:

obtaining a first connection hash value, the first connection hash value pointing to a first slot in the hashing table;

obtaining a second connection hash value, the second connection hash value pointing to the first slot in the hashing table;

assigning the second connection hash value to a second slot in the hashing table;

pointing the first slot toward the second slot;

obtaining a third connection hash value, the third connection hash value pointing to the second slot in the hashing table;

moving contents of the second slot to a third slot in the hashing table; and

assigning the third connection hash value to the second slot in the hashing table.