Efficiently hashing packet keys into a firewall connection table

• US 8,112,547 B2
• Filed: 06/08/2010
• Issued: 02/07/2012
• Est. Priority Date: 02/23/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Corl, Everett Arthur Jr., Davis, Gordon Taylor, Jeffries, Clark Debs, Perrin, Steven Richard, Takada, Hiroshi, Thio, Victoria Sue
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Woolcock, Madhu
• Application Number:
  US12/796,363
• Publication Number:
  US 20100241746A1
• Time in Patent Office: 609 Days
• Field of Search: 709/223, 709/224, 709/242, 709/245
• US Class Current: 709/244
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/255 Maintenance or indexing of mapping tables
• CPC Class Codes: H04L 61/2557 Translation policies or rules

Abstract

A method for increasing the capacity of a connection table in a firewall accelerator by means of mapping packets in one session with some common security actions into one table entry. For each of five Network Address Translation (NAT) configurations, a hash function is specified. The hash function takes into account which of four possible arrival types a packet at a firewall accelerator may have. When different arrival types of packets in the same session are processed, two or more arrival types may have the same hash value.

Claims

1. A method to map packets comprising:

providing a table for mapping packet values for packets received at a network device;

receiving a packet at the network device;

identifying an arrival type of the packet from a list of arrival types comprising client to server, server to client, firewall to client, and firewall to server;

creating a key for the packet, the key including a set of values followed by a set of bits encoding the arrival type of the packet, wherein in the set of values comprises a source address, a source port, a destination address, and a destination port for the packet;

providing the set of values from the key to a hash function to generate an index value;

searching a tree structure associated with the table for a leaf in the tree matching the index value, wherein the leaf includes a set of actions common to each arrival type in the list; and

using the set of bits to identify actions particular to the arrival type of the packet.

2. The method of claim 1 further comprising:

determining whether the source address for the packet is greater than the destination address for the packet; and

responsive to determining that the source address is not greater than the destination address, switching a value of the source address with a value for the destination address and a value of the source port with a value for the destination port to form a plurality of switched values and providing the plurality of switched values as the set of values provided to the hash function to generate the index value.

3. The method of the claim 1, wherein the set of bits is two bits concatenated with the set of values.

4. The method of claim 1, wherein the tree structure comprises a Patricia Tree structure operatively coupled to the table.

5. A system comprising:

a bus;

a storage device connected to the bus, the storage device storing program code to map packets;

a processing unit connected to the bus, wherein the processing unit is configured to execute the program code to provide a table for mapping packet values for packets received at a network device;

receive a packet at the network device;

identify an arrival type of the packet from a list of arrival types comprising client to server, server to client, firewall to client, and firewall to server;

create a key for the packet, the key including a set of values followed by a set of bits encoding the arrival type of the packet, wherein in the set of values comprises a source address, a source port, a destination address, and a destination port for the packet;

provide the set of values from the key to a hash function to generate an index value;

search a tree structure associated with the table for a leaf in the tree matching the index value, wherein the leaf includes a set of actions common to each arrival type in the list; and

use the set of bits to identify actions particular to the arrival type of the packet.

6. The system of claim 5, wherein the processing unit is further configured to execute the program code to determine whether the source address for the packet is greater than the destination address for the packet;

and switch a value of the source address with a value for the destination address and a value of the source port with a value for the destination port to form a plurality of switched values and providing the plurality of switched values as the set of values provided to the hash function to generate the index value in response to a determination that the source address is not greater than the destination address.

7. The system of claim 5, wherein the tree structure comprises a Patricia Tree structure operatively coupled to the table.

8. The system of claim 5, wherein the set of bits is two bits concatenated with the set of values.

9. The system of claim 5 further including a server operatively coupled to a firewall accelerator, wherein the server is positioned within a data plane.

10. The system of claim 9 further including a firewall operatively coupled to the firewall accelerator wherein the firewall accelerator is positioned within a data plane.

11. The system of claim 10 wherein the firewall includes a programmed computer, wherein the firewall is positioned within a control plane.

12. A program product comprising:

a storage device storing computer executable instructions, said computer executable instructions comprising;

computer executable instructions for providing a table for mapping packet values for packets received at a network device;

computer executable instructions for receiving a packet at the network device;

computer executable instructions for identifying an arrival type of the packet from a list of arrival types comprising client to server, server to client, firewall to client, and firewall to server;

computer executable instructions for creating a key for the packet, the key including a set of values followed by a set of bits encoding the arrival type of the packet, wherein in the set of values comprises a source address, a source port, a destination address, and a destination port for the packet;

computer executable instructions for providing the set of values from the key to a hash function to generate an index value;

computer executable instructions for searching a tree structure associated with the table for a leaf in the tree matching the index value, wherein the leaf includes a set of actions common to each arrival type in the list; and

computer executable instructions for using the set of bits to identify actions particular to the arrival type of the packet.

13. The program product of claim 12 further comprising:

computer executable instructions for determining whether the source address for the packet is greater than the destination address for the packet; and

computer executable instructions responsive to determining that the source address is not greater than the destination address, for switching a value of the source address with a value for the destination address and a value of the source port with a value for the destination port to form a plurality of switched values and providing the plurality of switched values as the set of values provided to the hash function to generate the index value.

14. The program product of claim 12, wherein the set of bits is two bits concatenated with the set of values.

15. The program product of claim 12, wherein the tree structure comprises a Patricia Tree structure operatively coupled to the table.