Method and apparatus for providing a network connection table

• US 7,577,151 B2
• Filed: 04/01/2005
• Issued: 08/18/2009
• Est. Priority Date: 04/01/2005
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Vu; Thong H
• Application Number:
  US11/096,571
• Publication Number:
  US 20060221977A1
• Time in Patent Office: 1,600 Days
• Field of Search: 370/395, 370/466, 370/390, 713/201, 726/11, 709/245, 717/109
• US Class Current: 370/395.32
• 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 for devices on a network, the method comprising:

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

zeroing particular fields in the connection information in response to the packet being a connection-starting packet that establishes a new connection, and not zeroing the particular fields in response to the packet being provided for an existing connection;

converting the connection information to an address for a location in a direct table using a table access process, wherein the direct table stores a plurality of patterns and associated reference information, at least two of the stored patterns having different types, wherein each of the patterns of the first type indicates an associated new connection is available and each of the patterns of the second type is associated with using an associated existing connection; 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 first type of stored pattern is a 3-tuple pattern having two fields zeroed out or a 2-tuple pattern having three fields zeroed out, and the second type of stored pattern is a 5-tuple pattern having no fields zeroed out, and wherein the direct table 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 on the connection information, 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 on the connection information.

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

10. The method of claim 1 wherein the comparing includes comparing the connection information with the 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 created from the connection information and making secondary comparisons using a 2-tuple search pattern created from the connection information, 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 one of the patterns in the direct table is used to determine the reference information for the received packet.

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

receiving the network connection information;

zeroing particular fields in the network connection information in response to the network connection information setting up and making available a new connection, and not zeroing the particular fields in response to the network connection information being provided for an existing 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 that are available for connection, and existing connections that have been established.

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 thee 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 on the network connection information, and when storing 5-tuple patterns for established connections, the address to the direct table is provided using a second, different hash process on the network connection information.

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 for devices on a network, the apparatus comprising:

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

a mechanism for zeroing particular fields in the connection information in response to the packet being a connection-starting packet that establishes a new connection, and not zeroing the particular fields in response to the packet being provided for an existing connection;

a mechanism 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 a plurality of patterns and associated reference information, at least two of the stored patterns having different types, wherein each of the patterns of the first type indicates an associated new connection is available and each of the patterns of the second type is associated with using an associated existing connection; and

a mechanism 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 mechanism for converting the connection information to an address using a hash process includes a mechanism 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 mechanism for comparing uses all of the retrieved connection information for an established connection as a 5-tuple pattern to be compared with at least one of the patterns stored in the direct table, and uses the connection information with zeroed out particular fields for a new connection as a 3-tuple pattern or a 2-tuple pattern to be compared with at least one of the patterns stored in the direct table.

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 available 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 available 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.