Method and apparatus for providing a network connection table

• US 20060221977A1
• Filed: 04/01/2005
• Published: 10/05/2006
• Est. Priority Date: 04/01/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Damon, Philippe, Vaidhyanathan, Natarajan, Calvignac, Jean Louis, Verplanken, Fabrice Jean, Basso, Claude, Verrilli, Colin Beaton, Chang, Chih-Jen
• Granted Patent: US 7,577,151 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Method and apparatus for implementing use of a network connection table. In one aspect, searching for network connections includes receiving a packet, and zeroing particular fields of connection information from the packet if a new connection is to be established. The connection information is converted to an address for a location in a direct table using a table access process. The direct table stores patterns and reference information for new and existing connections. The connection information is compared with at least one pattern stored in the direct table at the address to find reference information for the received packet.

Claims

1. A method for searching for network connections, the method comprising:

receiving a packet over a network at a computer system and retrieving connection information from the packet, and zeroing particular fields in the connection information if a new connection is to be established;

converting the connection information to an address for a location in a direct table using a table access process, wherein the direct table stores patterns and associated reference information for new connections and existing connections; and

comparing the connection information with at least one pattern stored in the direct table at the location pointed to by the address to find reference information for the received packet.

2. The method of claim 1 wherein the reference information indicates a connection within the computer system through which to send the received packet.

3. The method of claim 2 wherein the reference information is stored in the same entry of the direct table as the pattern, and wherein a match of the connection information and the pattern allows the reference information stored at that entry to be retrieved from the direct table.

4. The method of claim 1 wherein the table access process is a hash process.

5. The method of claim 4 wherein converting the connection information to an address using a hash process includes using a hash key that is derived from the connection information.

6. The method of claim 5 wherein the hash process moves the byte fields of the hash key which contain the most entropy to the most significant bytes of the hash key.

7. The method of claim 5 wherein the direct table stores 3-tuple patterns having two fields zeroed out, 2-tuple patterns having three fields zeroed out, and 5-tuple patterns having no fields zeroed out, and can store any of these types of patterns in any entry of the direct table.

8. The method of claim 7 wherein when comparing the connection information to patterns in the direct table for a new connection, the address to the location of the direct table is provided using a first hash process, and when comparing the connection information to patterns in the direct table for a established connection, the address to the location is provided using a second, different hash process.

9. The method of claim 1 wherein all of the retrieved connection information is used as a 5-tuple pattern and compared with patterns stored in the direct table for an established connection, and the connection information with particular fields zeroed out is used as a 3-tuple pattern or a 2-tuple pattern and compared with patterns stored in the direct table for a new connection.

10. The method of claim 1 wherein the comparing includes comparing the connection information with patterns stored in a plurality of entries of the direct table until a match is found.

11. The method of claim 10 wherein comparing the connection information includes making primary comparisons using a 3-tuple search pattern and making secondary comparisons using a 2-tuple search pattern, wherein if no primary match is found to a pattern, then a secondary match is used to determine the reference information for the received packet.

12. The method of claim 11 wherein the first secondary match of the 2-tuple search pattern to a pattern in the direct table is used to determine the reference information for the received packet.

13. A method for storing network connection information, the method comprising:

receiving the network connection information;

zeroing particular fields in the network connection information if the network connection information references a new connection;

converting the network connection information to an address in a direct table using a table access process; and

storing the connection information as a pattern and storing connection reference information in the direct table at a location corresponding to the address, wherein the direct table stores connection information and reference information for new connections and existing connections.

14. The method of claim 13 wherein the connection reference information for a network connection is stored in the same entry of the direct table as the pattern, such that when a packet is received that includes network connection information, a match of the network connection information and the pattern allows the reference information stored at that entry to be retrieved from the direct table.

15. The method of claim 13 wherein the table access process is a hash process.

16. The method of claim 15 wherein converting the connection information to an address using a hash process includes using a hash key that is derived from the connection information.

17. The method of claim 16 wherein the direct table stores 3-tuple patterns having two fields zeroed out, 2-tuple patterns having three fields zeroed out, and 5-tuple patterns having no fields zeroed out, and can store any of these types of patterns in any entry of the direct table.

18. The method of claim 17 wherein when storing 3-tuple patterns and 2-tuple patterns for new connections, the address to the direct table is provided using a first hash process, and when storing 5-tuple patterns for established connections, the address to the direct table is provided using a second, different hash process.

19. The method of claim 13 wherein the zeroing particular fields in the network connection information includes zeroing out fields to create a 3-tuple pattern or a 2-tuple pattern.

20. The method of claim 19 wherein the 3-tuple pattern is created by zeroing out Source Address and Source Port fields in the pattern, and the 2-tuple pattern is created by zeroing out Source Address, Source Port, and Destination Address fields in the pattern.

21. The method of claim 13 wherein when storing a pattern for an established connection, the connection information is stored as a 5-tuple pattern in the direct table, and when storing a pattern for a new connection, the connection information is stored as a 3-tuple pattern or a 2-tuple pattern in the direct table with the particular fields zeroed out.

22. The method of claim 13 wherein a pattern and reference information for a new connection is stored in the direct table when a server application requests that a connection be set up.

23. The method of claim 13 wherein a pattern and reference information for an established connection is stored in the direct table when a packet is received at a server storing the direct table from a client across a network.

24. An apparatus for searching for network connections, the apparatus comprising:

means for receiving a packet over a network at a computer system and retrieving connection information from the packet

means for zeroing particular fields in the connection information if a new connection is to be established;

means for converting the connection information to an address for a location in a direct table using a table access process, wherein the direct table stores patterns and associated reference information for new connections and existing connections; and

means for comparing the connection information with at least one pattern stored in the direct table at the location pointed to by the address to find reference information for the received packet.

25. The apparatus of claim 24 wherein the reference information indicates a connection within the computer system through which to send the received packet, wherein the reference information is stored in the same entry of the direct table as the pattern, and wherein a match of the connection information and the pattern allows the reference information stored at that entry to be retrieved from the direct table.

26. The apparatus of claim 24 wherein the table access process is a hash process, and wherein the means for converting the connection information to an address using a hash process includes means for using a hash key that is derived from the connection information.

27. The apparatus of claim 26 wherein the direct table stores 3-tuple patterns having two fields zeroed out, 2-tuple patterns having three fields zeroed out, and 5-tuple patterns having no fields zeroed out, and can store any of these types of patterns in any entry of the direct table.

28. The apparatus of claim 24 wherein when the means for comparing uses all of the retrieved connection information as a 5-tuple pattern to be compared with patterns stored in the direct table for an established connection, and uses the connection information with zeroed out particular fields as 3-tuple pattern or a 2-tuple pattern to be compared with patterns stored in the direct table for a new connection.

29. An apparatus allowing storing and searching of network connection information, the apparatus comprising:

a direct table provided in memory and operative to store network connection information including 3-tuple and 2-tuple patterns for new network connections and 5-tuple patterns for established network connections, and associated reference information pointing to network connections; and

a search mechanism implemented on a network adapter device and coupled to the direct table, the search mechanism operative to search for network connection information in the direct table when a packet including connection information is received over a network, wherein the search mechanism creates a search pattern from the packet connection information, the search pattern used for searching for a matching pattern in the direct table to find the associated reference information.

30. The apparatus of claim 29 wherein the 3-tuple and 2-tuple patterns are 5-tuples having a plurality of fields zeroed out, and wherein the search pattern created for a new connection is a 3-tuple or a 2-tuple pattern which is a 5-tuple having a plurality of fields zeroed out.

31. The apparatus of claim 29 wherein the search mechanism converts the packet connection information into a hash key to be used with a hash process to locate a row in the direct table having a pattern matching the search pattern.