Hashing algorithm for network receive filtering

• US 20070115982A1
• Filed: 10/20/2005
• Published: 05/24/2007
• Est. Priority Date: 10/20/2005
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Level 5 Networks, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Riddoch, David, Pope, Steve, Roberts, Derek, Yu, Ching, Chu, Der-Ren, Chiang, John
• Granted Patent: US 7,984,180 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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;

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 a matching entry is identified in the step of searching 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.

2. 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, further comprising the steps of:

receiving from the computing device an indication of the second maximum extent-of-search;

iteratively searching a 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;

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 second maximum extent-of-search, delivering the packet to a receive queue in the computing device that is indicated by the matching entry; and

if no matching entry is identified in the step of searching 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 2, 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 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 after the number of iterations indicated by the first maximum extent-of-search, further comprising the steps of:

iteratively searching the filter table a second 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 a second time, after no more than a number of iterations indicated by a second 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 searching after the number of iterations indicated by the first maximum extent-of-search, further comprising the steps of:

iteratively searching the filter table a second 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 a second time, after no more than a number of iterations indicated by a second 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 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.

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

12. A method according to claim 9, wherein the number of iterations indicated by the second 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, receiving from the computing device an indication of a second maximum extent-of-search, the second 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 a second maximum extent-of-search, iteratively searching the filter table a second time for a matching entry having first comparison criteria that are satisfied by the content of a second 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 second 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 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 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 searching 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 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;

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 the number of iterations indicated by the first maximum extent-of-search, delivering the 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 a second time for an entry having second 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 the number of iterations indicated by the first maximum extent-of-search, delivering the packet to a second default receive queue in the host, the second 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 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 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.

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 packet toward a target process selected in dependence upon header information in the header of the packet.

27. A method according to claim 26, 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,

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, 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 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; and

programming the network interface device with an indication of a first maximum extent-of-search to which the network interface device should search in the filter table before delivering an incoming packet to a default receive queue.

33. A method according to claim 32, wherein the step of programming a receive filter table accessible to the network interface device comprises the step of programming, into a first entry in the receive filter table, an indication of a first receive queue and an indication of first criteria for testing against incoming packets,

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:

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, wherein the first maximum extent-of-search 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,

further comprising the step of programming the network interface device with an indication of a second 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 second maximum extent-of-search indicating 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 first incoming data packet, the second 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 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.

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 wherein the step of programming a receive filter table accessible to the network interface device further comprises the step of programming, into a second entry in the receive filter table, an indication of a second receive queue and an indication of second criteria for testing against incoming packets, further comprising the steps of:

programming the network interface device with an indication of a second 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; and

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, for use with a plurality of processors each having a respective kernel receive queue, comprising the steps of:

searching a filter table for an entry matching the content of a first incoming data packet received from the network; and

where no matching entry is identified in the step of searching;

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

delivering the packet to the selected one of the kernel receive queues.

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.