Hashing algorithm for network receive filtering

• US 8,959,095 B2
• Filed: 06/16/2011
• Issued: 02/17/2015
• Est. Priority Date: 10/20/2005
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: SolarFlare Communications Incorporated (Advanced Micro Devices, Inc.)
• Inventors: Pope, Steve L., Roberts, Derek, Riddoch, David J., Yu, Ching, Chiang, John Mingyung, Chu, Der-Ren
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US13/162,421
• Publication Number:
  US 20110246489A1
• Time in Patent Office: 1,342 Days
• Field of Search: 707/625, 707/648, 707/674, 707/741, 707/747, 707/754, 707/769, 707/922, 709/203, 709/235, 709/238, 709/240, 370/389, 370/392
• US Class Current: 707/754
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/162 involving adaptations of sockets based mechanisms secure socket layer H04L63/168
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y10S 707/922 Communications

Abstract

Roughly described, a network interface device is assigned a maximum extent-of-search. A hash function is applied to the header information of each incoming packet, to generate a hash code for the packet. The hash code designates a particular subset of the table within which the particular header information should be found, and an iterative search is made within that subset. If the search locates a matching entry before the search limit is exceeded, then the incoming data packet is delivered to the receive queue identified in the matching entry. But if the search reaches the search limit before a matching entry is located, then device delivers the packet to a default queue, such as a kernel queue, in the host computer system. The kernel is then responsible for delivering the packet to the correct endpoint.

Claims

1. A network interface device for processing data packets received from a network, for use with a computing device, comprising:

a memory having stored therein a filter table having a plurality of filter entries, each filter entry including respective comparison criteria and identifying a respective queue in the computing device to which matching incoming data packets are to be delivered;

storage containing a value indicating a first search limit;

logic which, in response to receipt by the network interface device of a first incoming data packet;

calculates a first hash key in dependence upon content of the data packet, the first hash key identifying a first hash bucket in the filter table;

performs a first iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network, the first search beginning in the first hash bucket, proceeding according to a predetermined search algorithm, and terminating in response to identification of a matching entry or reaching of the first search limit, whichever occurs earlier, the first search limit being different than the total number of filter entries that can be reached beginning in the first hash bucket and proceeding using the predetermined search algorithm; and

if a matching entry was identified by the first iterative search before the first search limit was reached, forwards the packet to the receive queue in the computing device that is indicated by the matching entry.

2. A device according to claim 1, wherein the storage further contains a value indicating a second search limit,

wherein the logic, if the first search limit was reached before a matching entry was identified by the first iterative search, further:

calculates a second hash key in dependence upon content of the data packet, the second hash key identifying a second hash bucket in the filter table;

performs a second iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the data packet received from the network, the second search beginning in the second hash bucket, proceeding according to a predetermined search algorithm, and terminating in response to identification of a matching entry or reaching of the second search limit, whichever occurs earlier; and

if a matching entry was identified by the second iterative search before the second search limit was reached, forwards the packet to the receive queue in the computing device that is indicated by the matching entry,

wherein the comparison criteria in each of the filter entries in the second hash bucket are less restrictive than the comparison criteria in each of the filter entries in the first hash bucket.

3. A device according to claim 2, wherein the logic, if the second search limit was reached before a matching entry was identified by the second iterative search, forwards the first incoming data packet to a default receive queue in the computing device,

wherein the receive queue in the computing device that is indicated by the matching entry if a matching entry was identified by the first iterative search before the first search limit was reached, comprises memory in the computing device that is accessible to a first user level process without requiring a context switch to a process having greater privilege than the first user level process,

wherein the receive queue in the computing device that is indicated by the matching entry if a matching entry was identified by the second iterative search before the second search limit was reached, comprises memory in the computing device that is accessible to a second user level process without requiring a context switch to a process having greater privilege than the second user level process,

and wherein the default receive queue in the computing device is accessible only to kernel level processes.

4. A device according to claim 1, wherein the storage further contains a value indicating a second search limit,

wherein the first incoming data packet is of a first data packet type,

and wherein the logic, in response to receipt by the network interface device of a second incoming data packet of a second data packet type different from the first data packet type:

calculates a second hash key in dependence upon content of the second data packet, the second hash key identifying a second hash bucket in the filter table, the second search limit being different than the number of filter entries in the second hash bucket;

performs a second iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the second data packet received from the network, the second search beginning in the second hash bucket, proceeding according to a predetermined search algorithm, and terminating in response to identification of a matching entry or reaching of the second search limit, whichever occurs earlier; and

if a matching entry was identified by the second iterative search before the second search limit was reached, forwards the second packet to the receive queue in the computing device that is indicated by the matching entry.

5. A device according to claim 4, wherein the storage further contains a value indicating a third search limit,

wherein the logic, if the second search limit was reached before a matching entry was identified by the second iterative search, further:

calculates a third hash key in dependence upon content of the data packet, the third hash key identifying a third hash bucket in the filter table;

performs a third iterative search of entries in the filter table for a matching entry whose comparison criteria are satisfied by content of the second data packet received from the network, the third search beginning in the third hash bucket, proceeding according to a predetermined search algorithm, and terminating in response to identification of a matching entry or reaching of the third search limit, whichever occurs earlier; and

if a matching entry was identified by the third iterative search before the third search limit was reached, forwards the packet to the receive queue in the computing device that is indicated by the matching entry,

wherein the comparison criteria in each of the filter entries in the third hash bucket are less restrictive than the comparison criteria in each of the filter entries in the second hash bucket,

wherein the comparison criteria in each of the filter entries comprises values for a set of comparison fields,

wherein the second iterative search searches the filter table for a filter entry having values in the comparison fields which all match values in corresponding fields in the incoming packet,

and wherein the third iterative search searches the filter table for a filter entry having values in a proper subset of the comparison fields which all match values in corresponding fields in the incoming packet, those of the comparison fields not in the subset being disregarded in the third iterative search.

6. A device according to claim 5, wherein the logic, if the third search limit was reached before a matching entry was identified by the third iterative search, forwards the second incoming data packet to a default receive queue in the computing device.

7. A device according to claim 6, wherein the receive queue in the computing device that is indicated by the matching entry if a matching entry was identified by the third iterative search before the third search limit was reached, comprises memory in the computing device that is accessible to a user level process without requiring a context switch to a process having greater privilege than the user level process,

and wherein the default receive queue in the computing device is accessible only to kernel level processes.

8. A device according to claim 1, wherein the logic, if the first search limit was reached before a matching entry was identified by the first iterative search, forwards the first incoming data packet to a default receive queue in the computing device,

wherein the receive queue in the computing device that is indicated by the matching entry if a matching entry was identified by the first iterative search before the first search limit was reached, comprises memory in the computing device that is accessible to a user level process without requiring a context switch to a process having greater privilege than the user level process,

and wherein the default receive queue in the computing device is accessible only to kernel level processes.