Hashing algorithm for network receive filtering

• US 7,984,180 B2
• Filed: 10/20/2005
• Issued: 07/19/2011
• 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: Riddoch, David J., Chiang, John Mingyung, Yu, Ching, Chu, Der-Ren, Roberts, Derek, Pope, Steve L.
• Primary Examiner(s): BATES, KEVIN T
• Application Number:
  US11/255,124
• Publication Number:
  US 20070115982A1
• Time in Patent Office: 2,098 Days
• Field of Search: 370322-390, 370/392, 370/395.32, 707/6, 708/322, 709/238
• US Class Current: 709/238
• 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 method for processing data packets received from a network, comprising the steps of:

receiving from a computing device an indication of a first maximum extent-of-search and an indication of a second maximum extent-of-search;

iteratively searching a filter table a first time for a matching entry having first comparison criteria that are satisfied by the content of a first incoming data packet received from the network; and

where a matching entry is identified in the step of searching a first time, after no more than a number of iterations indicated by the first maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the matching entry,

iteratively searching the filter table a second time for an entry having comparison criteria that are satisfied by the content of a second incoming data packet received from the network;

where a second matching entry is identified in the step of searching a second time, after no more than a number of iterations indicated by the second maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the second matching entry;

iteratively searching the filter table for a matching entry having comparison criteria that are satisfied by the content of a third incoming data packet received from the network;

where no matching entry is identified in the step of searching a third time, after the number of iterations indicated by the first maximum extent-of-search, delivering the packet to a default receive queue in the host;

iteratively searching the filter table a fourth time for a matching entry having comparison criteria that are satisfied by the content of a fourth incoming data packet received from the network; and

where no matching entry is identified in the step of searching a fourth time, after the number of iterations indicated by the second maximum extent-of-search, delivering the packet to a default receive queue in the host.

2. A method according to claim 1, further comprising the steps of:

if no matching entry is identified in the step of searching a second time, after the number of iterations indicated by the second maximum extent-of-search, delivering the packet to a default receive queue in the host.

3. A method according to claim 1, wherein the first maximum extent-of-search applies to a first incoming data packet type, and a second maximum extent-of-search applies to a second incoming data packet type,

and wherein the first and second incoming data packet types are distinguished at least by protocol type.

4. A method according to claim 1, wherein the first comparison criteria comprise first values for a first set of comparison fields,

and wherein the step of iteratively searching a filter table for a matching entry having first comparison criteria comprises the step of iteratively searching the filter table for an entry having values in the first set of comparison fields that match corresponding fields in a header in the incoming packet.

5. A method according to claim 4, wherein the first set of comparison fields includes source and destination IP address fields and source and destination port fields.

6. A method according to claim 4, wherein the first set of comparison fields includes a destination IP address field and a destination port field, but excludes any source IP address fields and any source port fields.

7. A method according to claim 4, wherein no matching entry is identified in the step of searching a first time, after the number of iterations indicated by the first maximum extent-of-search, further comprising the steps of:

iteratively searching the filter table an additional time for an entry having a second set of comparison fields that all match corresponding fields in the header of the first incoming data packet received from the network, the second set of comparison fields excluding at least one field included in the first set of comparison fields;

if a matching entry is identified in the step of searching an additional time, after no more than a number of iterations indicated by an additional maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the matching entry.

8. A method according to claim 7, wherein the first set of comparison fields includes source and destination IP address fields and source and destination port fields,

and wherein the second set of comparison fields includes the destination IP address field and the destination port field and excludes the source IP address field and the source port field.

9. A method according to claim 1, wherein no matching entry is identified in the step of iteratively searching a filter table for a matching entry having first comparison criteria after the number of iterations indicated by the first maximum extent-of-search, further comprising the steps of:

iteratively searching the filter table an additional time for an entry having second comparison criteria that are satisfied by the content of the first incoming data packet received from the network, the second comparison criteria being less restrictive than the first comparison criteria;

if a matching entry is identified in the step of searching an additional time, after no more than a number of iterations indicated by an additional maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the matching entry.

10. A method according to claim 9, further comprising the step of, if no matching entry is identified in the step of searching an additional time, after the number of iterations indicated by the additional maximum extent-of-search, delivering the packet to a default receive queue in the host.

11. A method according to claim 9, further comprising the step of receiving from the computing device an indication of the additional maximum extent-of-search.

12. A method according to claim 9, wherein the number of iterations indicated by the additional maximum extent-of-search differs from the number of iterations indicated by first maximum extent-of-search.

13. A method according to claim 1, further comprising the steps of:

after the step of iteratively searching the filter table for a matching entry having first comparison criteria, receiving from the computing device an indication of an additional maximum extent-of-search, the additional maximum extent-of-search indicating a number of iterations different from that indicated by the first maximum extent-of-search;

after the step of receiving from the computing device an indication of an additional maximum extent-of-search, iteratively searching the filter table an additional time for a matching entry having first comparison criteria that are satisfied by the content of an additional incoming data packet received from the network; and

only if a matching entry is identified in the step of searching a second time, after no more than a number of iterations indicated by the additional maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the matching entry.

14. A method according to claim 1, further comprising the steps of:

receiving from the computing device a plurality of entries for the filter table; and

programming the plurality of entries into the filter table.

15. A method according to claim 1, wherein the first comparison criteria comprise first values for a first set of comparison fields,

and wherein the step of iteratively searching a filter table for a matching entry having first comparison criteria comprises the step of comparing the values in the first set of comparison fields of each i'"'"'th entry in the filter table to the corresponding fields in the header of the first incoming data packet, for sequentially incrementing values of k from 0 up to one less than the number of iterations indicated by the first maximum extent-of-search, or until the matching entry is identified, whichever occurs earlier, where:

i(k)=(h1(key)+k*h2(key))modulo M,

key is a value dependent upon header information in the header of the first incoming data packet,

h1 and h2 are mathematical functions, and

M is the total index range of the filter table.

16. A method according to claim 1, wherein the first comparison criteria comprise first values for a first set of comparison fields,

and wherein the filter table comprises P sub-tables each of which can hold M entries, P being an integer greater than or equal to 1,

and wherein the step of iteratively searching a first time comprises the step of comparing the values in the first set of comparison fields of each i(k)'"'"'th entry in each of the filter sub-tables to the corresponding fields in the header of the first incoming data packet, for sequential values of k incrementing from 0 up to one less than the number of iterations indicated by the first maximum extent-of-search, or until the matching entry is identified, whichever occurs earlier, where:

i(k)=(h1(key)+k*h2(key))modulo m,

key is a value dependent upon header information in the header of the first incoming data packet, and

h1 and h2 are mathematical functions.

17. A method according to claim 16, wherein the key is a first function of the header information if the first incoming data packet has a first data packet type, and is a second function of the header information different from the first function, if the incoming data packet has a second data packet type.

18. A method according to claim 16, wherein the function h2(key) is given by:

h2(key)=(key*2−

1) modulo M.

19. A method according to claim 1, further comprising the step of, if no matching entry is identified in the step of iteratively searching a filter table for a matching entry having first comparison criteria, after the number of iterations indicated by the first maximum extent-of-search, delivering the packet to a first default receive queue in the host.

20. A method according to claim 19, wherein the step of delivering the packet to a receive queue in the computing device that is indicated by a matching entry comprises the step of writing data from the packet into 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 step of delivering the packet to a first default receive queue in the host comprises the step of writing data from the packet into memory in the computing device that is accessible only to kernel level processes.

21. A method according to claim 1, further comprising the step of:

where no matching entry is identified in the step of iteratively searching a filter table for a matching entry having first comparison criteria, after the number of iterations indicated by the first maximum extent-of-search, delivering the first packet to a first default receive queue in the host.

22. A method according to claim 21, further comprising the steps of:

iteratively searching the filter table an additional time for an entry having additional comparison criteria that are satisfied by the content of an additional incoming data packet received from the network; and

where no matching entry is identified in the step of searching an additional time, after the number of iterations indicated by the first maximum extent-of-search, delivering the additional packet to an additional default receive queue in the host, the additional default receive queue being different from the first default receive queue.

23. A method according to claim 21, for use where the computing device includes a plurality of default receive queues,

further comprising the step of selecting the first default receive queue from among the plurality of default receive queues in dependence upon the content of the first incoming data packet.

24. A method according to claim 21, wherein the first comparison criteria comprise first values for a first set of comparison fields,

and wherein the filter table comprises P sub-tables each of which can hold M entries, P being an integer greater than or equal to 1,

and wherein the step of iteratively searching a filter table for a matching entry having first comparison criteria comprises the step of comparing the comparison fields of each i(k)'"'"'th entry in each of the filter sub-tables to the corresponding fields in the header of the first incoming data packet, for sequential values of k incrementing from 0 up to one less than the number of iterations indicated by the first maximum extent-of-search, or until the matching entry is identified, whichever occurs earlier, where:

i(k) =(h1(key) +k*h2(key)) modulo M,

key is a value dependent upon header information in the header of the first incoming data packet, and

h1 and h2 are mathematical functions,

the method further comprising the step of selecting the first default receive queue from among the plurality of receive queues in dependence upon the key.

25. A method according to claim 21, wherein the step of delivering the first packet to a first default receive queue in the host comprises the step of writing data from the first packet into memory in the computing device that is accessible only to kernel level processes.

26. A method according to claim 21, further comprising the step of, in response to receipt of the packet into the first default receive queue, the computing device forwarding data from the first packet toward a target process selected in dependence upon header information in the header of the first packet.

27. A method according to claim 26, wherein the step of delivering the first packet to a first default receive queue in the host comprises the step of writing data from the first packet into memory in the computing device that is accessible only to kernel level processes,

and wherein the target process is a user level process.

28. A method according to claim 21, wherein the first comparison criteria comprise first values for a first set of comparison fields, further comprising, prior to the step of iteratively searching a filter table for a matching entry having first comparison criteria, the step of iteratively searching the filter table preliminarily for an entry having a preliminary set of comparison fields that all match corresponding fields in the header of the first incoming data packet received from the network,

wherein no matching entry is identified in the step of searching the filter table preliminarily, after the number of iterations indicated by a preliminary maximum extent-of-search,

and wherein the first set of comparison fields excludes at least one field included in the preliminary set of comparison fields.

29. A method according to claim 28, further comprising the step of receiving from the computing device an indication of the preliminary maximum extent-of-search.

30. A method according to claim 28, wherein the number of iterations indicated by the preliminary maximum extent-of-search differs from the number of iterations indicated by first maximum extent-of-search.

31. A method according to claim 28, wherein the preliminary set of comparison fields includes source and destination IP address fields and source and destination port fields,

and wherein the first set of comparison fields includes the destination IP address field and the destination port field and excludes the source IP address field and the source port field.

32. A method for controlling a network interface device, for use with a host computing device having a plurality of network data receive queues, comprising the steps of:

programming a receive filter table in a memory accessible to the network interface device, each entry in the receive filter table identifying a receive queue to which incoming packets are to be delivered if their content satisfies criteria indicated by the entry, wherein a first entry in the receive filter table contains an indication of a first receive queue and an indication of first criteria for testing against incoming packets and a second entry in the receive filter table contains an indication of a second receive queue and an indication of second criteria for testing against incoming packets;

programming a memory in the network interface device with a first maximum extent-of-search which indicates a first maximum number of search iterations that the network interface device should perform while searching for an entry having a first set of comparison fields that all match corresponding fields in the header of a first incoming data packet received from the network and programming the network interface device with a second maximum extent-of-search which indicates a second maximum number of search iterations that the network interface device should perform while searching for an entry having a second set of comparison fields that all match corresponding fields in the header of a second incoming data packet received from the network,

the network interface device iteratively searching a filter table a first time for a matching entry having first comparison criteria that are satisfied by the content of a first incoming data packet received from the network;

where a matching entry is identified in the step of searching a first time, after no more than a number of iterations indicated by the first maximum extent-of-search, the network interface device delivering the packet to a receive queue in the computing device that is indicated by the matching entry;

the network interface device iteratively searching the filter table a second time for an entry having comparison criteria that are satisfied by the content of a second incoming data packet received from the network;

where a second matching entry is identified in the step of searching a second time, after no more than a number of iterations indicated by the second maximum extent-of-search, the network interface device delivering the packet to a receive queue in the computing device that is indicated by the second matching entry;

the network interface device iteratively searching the filter table for a matching entry having comparison criteria that are satisfied by the content of a third incoming data packet received from the network;

where no matching entry is identified in the step of searching a third time, after the number of iterations indicated by the first maximum extent-of-search, the network interface device delivering the packet to a default receive queue in the host;

the network interface device iteratively searching the filter table a fourth time for a matching entry having comparison criteria that are satisfied by the content of a fourth incoming data packet received from the network; and

where no matching entry is identified in the step of searching a fourth time, after the number of iterations indicated by the second maximum extent-of-search, the network interface device delivering the packet to a default receive queue in the host.

33. A method according to claim 32,

further comprising the step of receiving first data into the first queue in response to receipt by the network interface device of an incoming packet having content satisfying the first criteria.

34. A method according to claim 33, further comprising the step of receiving second data into the default receive queue in response to receipt by the network interface device of a second packet whose content does not satisfy the first criteria.

35. A method according to claim 34, wherein the content of the second packet satisfies none of the criteria indicated in the table.

36. A method according to claim 34, wherein the default queue is not identified anywhere in the table.

37. A method according to claim 34, further comprising the steps of:

the host computing device identifying a particular destination user level process in dependence upon the content of the second data packet; and

delivering the second data from the default queue to the particular destination user level process.

38. A method according to claim 34, wherein the step of receiving the first data into the first queue comprises the step of receiving the first data into 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 step of receiving second data into the default receive queue comprises the step of receiving the second data into memory in the computing device that is accessible only to kernel level processes.

39. A method according to claim 32, further comprising the step of receiving second data into the default receive queue in response to receipt by the network interface device of a second packet whose content does satisfy the first criteria.

40. A method according to claim 32, wherein the step of programming a receive filter table comprises the step of programming a plurality of entries in the receive filter table with:

values for a respective set of comparison fields, and

an identification of a destination receive queue to which incoming packets are to be delivered if the respective set of comparison fields match corresponding fields in a header in the incoming packet.

41. A method according to claim 40,

further comprising the step of programming the network interface device with an indication of an additional maximum extent-of-search to which the network interface device should search in the filter table after failing to find an entry having a first set of comparison fields that all match corresponding fields in the header of the first incoming data packet and before delivering an incoming packet to a default receive queue, the additional maximum extent-of-search indicating an additional maximum number of search iterations that the network interface device should perform while searching for an entry having an additional set of comparison fields that all match corresponding fields in the header of a first incoming data packet, the additional set of comparison fields excluding at least one field included in the first set of comparison fields.

42. A method according to claim 41, wherein the first set of comparison fields includes source and destination IP address fields and source and destination port fields,

and wherein the additional set of comparison fields includes the destination IP address field and the destination port field and excludes the source IP address field and the source port field.

43. A method according to claim 32, further comprising the steps of:

receiving first data into a first queue from the network interface device in response to receipt by the network interface device of an incoming packet; and

reprogramming the first maximum extent-of-search indication in the network interface device after the step of receiving.

44. A method according to claim 32, wherein the first maximum extent-of-search applies to a first incoming data packet type and the second maximum extent-of-search applies to a second incoming data packet type, second maximum extent-of-search indicating a maximum extent-of-search to which the network interface device should search in the filter table for incoming packets of a second incoming data packet type, before delivering an incoming packet to a default receive queue, the second criteria including an indication of the second incoming data packet type, further comprising the step of:

receiving second data into the second queue in response to receipt by the network interface device of an incoming packet of the second incoming data packet type and having content satisfying the second criteria.

45. A method according to claim 32, wherein the step of programming a receive filter table, for first criteria to be associated with a predetermined first receive queue, comprises the step of iteratively searching through an accessible copy of the filter table, at successive entries i(k), for sequentially incrementing values of k where:

i(k)=(h1(key)+k*h2(key))modulo M,

key is a value dependent upon the first criteria,

h1 and h2 are mathematical functions, and

M is the total index range of the filter table.

46. A method according to claim 45, wherein the key is a first function of the first criteria if the first criteria requires that a matching incoming packet has a first data packet type, and is a second function of the first criteria different from the first function, if the first criteria requires that a matching incoming packet has a second data packet type.

47. A method for processing data packets received from a network by a network interface device, for use with a plurality of processors each having a respective kernel receive queue, comprising the steps of:

the network interface device iteratively searching a filter table for a matching entry having first comparison criteria that are satisfied by the content of a first incoming data packet received from the network; and

where no matching entry is identified in the step of searching after no more than a number of iterations indicated by a first maximum extent-of-search,

selecting a first kernel receive queue of a first one of the processors in dependence upon the content of the first incoming data packet; and

delivering the first data packet to the selected first kernel receive queue;

further comprising the steps of;

iteratively searching the filter table a second time for an entry having comparison criteria that are satisfied by the content of a second incoming data packet received from the network; and

where no matching entry is identified in the step of searching a second time, after no more than a number of iterations indicated by a second maximum extent-of-search, selecting a second kernel receive queue of a second one of the processors in dependence upon the content of the second incoming data packet and delivering the second data packet to the selected second kernel receive queue.

48. A method according to claim 47, wherein the step of selecting a selected one of the kernel receive queues comprises the step of performing a hash function on at least one header field of the first incoming packet.

49. A method according to claim 47, wherein the step of selecting a selected one of the kernel receive queues comprises the step of performing the Toeplitz function on at least one header field of the first incoming packet.