Performing a multi-stage lookup to classify packets

• US 10,498,638 B2
• Filed: 05/01/2017
• Issued: 12/03/2019
• Est. Priority Date: 09/15/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Jackson, Ethan J., Rajahalme, Jarno
• Primary Examiner(s): Lai, Michael C
• Application Number:
  US15/583,969
• Publication Number:
  US 20170237664A1
• Time in Patent Office: 946 Days
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Some embodiments provide a method for a forwarding element that forwards packets. The method receives a packet. The method performs a first stage lookup of a hash table for a first hash of a first set of header fields and un-wildcards bits of a wildcard mask that corresponds to the first set of header fields. If a matching hash is found in the first stage lookup, the method performs a second stage lookup of the hash table for a second hash of a second set of header fields and un-wildcards bits of the wildcard mask that corresponds to the second set of header fields. The method identifies a matching rule for the packet. The method generates a flow based on the matching rule and the wildcard mask, wherein the flow is used to process each other packets that match each bit which is un-wildcarded.

Claims

1. A method for generating a cached rule for processing packets, the method comprising:

receiving a packet comprising a plurality of header fields over which a set of rules match;

defining a wildcard mask for the packet, comprising a different field corresponding to each header field of the packet, each field of the wildcard mask initially indicating a wildcard value;

modifying the wildcard mask by, for each of the plurality of header fields of the packet over which the set of rules match, performing a lookup for the header field and un-wildcarding the corresponding field of the wildcard mask until (i) lookups are performed for all of the header fields in the plurality of header fields or (ii) a lookup for a header field does not identify a matching rule; and

generating a rule for processing subsequent packets, the generated rule comprising a set of un-wildcarded fields based on a matching rule of the set of rules and the un-wildcarded fields of the modified wildcard mask.

2. The method of claim 1, wherein the set of rules are stored in a table comprising a set of stages, each stage comprising a rule to match one or more header fields of the received packet, wherein performing the lookup for each header field comprises performing a lookup of one or more of the stages of the table.

3. The method of claim 2, wherein the set of stages comprises at least one of (i) a first stage associated with a set of register or metadata fields, (ii) a second stage associated with a set of metadata and network layer 2 (L2) fields, (iii) a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields and (iv) a fourth stage associated with each set of fields.

4. The method of claim 2, wherein the rules are stored as hash values in each stage, wherein performing the lookup comprises performing a hash-based search algorithm.

5. The method of claim 2, wherein the table further comprises an action for forwarding a packet, wherein the rule generated for processing subsequent packets comprises the action to apply to the subsequent packets.

6. The method of claim 2, wherein when a lookup for a header field in a stage does not identify a matching rule no further lookup is performed in the table.

7. The method of claim 1, wherein the wildcard mask comprises a plurality of patterns, each pattern comprising a set of bits associated with one or more header fields of the packet header.

8. The method of claim 1, wherein generating the rule comprises, for each field in the wildcard mask that is un-wildcarded, setting the value of a field of the generated rule to comprise one of (i) a value of the corresponding header field of the received packet and (ii) a value of a corresponding field of the matching rule.

9. The method of claim 1, wherein the wildcard mask comprises a field corresponding to a metadata field in the matching rule that does not correspond to a header field of the received packet.

10. A non-transitory machine readable medium storing a program that when executed by at least one processing unit generates a cached rule for processing packets, the program comprising sets of instructions for:

receiving a packet comprising a plurality of header fields over which a set of rules match;

defining a wildcard mask for the packet, comprising a different field corresponding to each header field of the packet, each field of the wildcard mask initially indicating a wildcard value;

modifying the wildcard mask by, for each of the plurality of header fields of the packet over which the set of rules match, performing a lookup for the header field and un-wildcarding the corresponding field of the wildcard mask until (i) lookups are performed for all of the header fields in the plurality of header fields or (ii) a lookup for a header field does not identify a matching rule; and

generating a rule for processing subsequent packets, the generated rule comprising a set of un-wildcarded fields based on a matching rule of the set of rules and the un-wildcarded fields of the modified wildcard mask.

11. The non-transitory machine readable medium of claim 10, wherein the set of rules are stored in a table comprising a set of stages, each stage comprising a rule to match one or more header fields of the received packet, wherein the set of instructions for performing the lookup for each header field comprises a set of instructions for performing a lookup of one or more of the stages of the table.

12. The non-transitory machine readable medium of claim 11, wherein the set of stages comprises at least one of (i) a first stage associated with a set of register or metadata fields, (ii) a second stage associated with a set of metadata and network layer 2 (L2) fields, (iii) a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields, and (iv) a fourth stage associated with each set of fields.

13. The non-transitory machine readable medium of claim 11, wherein the rules are stored as hash values in each stage, wherein the set of instructions for performing the lookup comprises a set of instructions for performing a hash-based search algorithm.

14. The non-transitory machine readable medium of claim 11, wherein the table further comprises an action for forwarding a packet, wherein the rule generated for processing subsequent packets comprises the action to apply to the subsequent packets.

15. The non-transitory machine readable medium of claim 11, wherein when a lookup for a header field in a stage does not identify a matching rule no further lookup is performed in the table.

16. The non-transitory machine readable medium of claim 10, wherein the wildcard mask comprises a plurality of patterns, each pattern comprising a set of bits associated with one or more header fields of the packet header.

17. An electronic device comprising:

at least one processing unit; and

a storage, which stores a program that when executed by the at least one processing unit generates a cached rule for processing packets, the program comprising sets of instructions for;

receiving a packet comprising a plurality of header fields over which a set of rules match;

defining a wildcard mask for the packet, comprising a different field corresponding to each header field of the packet, each field of the wildcard mask initially indicating a wildcard value;

modifying the wildcard mask by, for each of the plurality of header fields of the packet over which the set of rules match, performing a lookup for the header field and un-wildcarding the corresponding field of the wildcard mask until (i) lookups are performed for all of the header fields in the plurality of header fields or (ii) a lookup for a header field does not identify a matching rule; and

generating a rule for processing subsequent packets, the generated rule comprising a set of un-wildcarded fields based on a matching rule of the set of rules and the un-wildcarded fields of the modified wildcard mask.

18. The electronic device of claim 17, wherein the set of rules are stored in a table comprising a set of stages, each stage comprising a rule to match one or more header fields of the received packet, wherein the set of instructions for performing the lookup for each header field comprises a set of instructions for performing a lookup of one or more of the stages of the table.

19. The electronic device of claim 18, wherein the set of stages comprises at least one of (i) a first stage associated with a set of register or metadata fields, (ii) a second stage associated with a set of metadata and network layer 2 (L2) fields, (iii) a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields, and (iv) a fourth stage associated with each set of fields.

20. The electronic device of claim 18, wherein the rules are stored as hash values in each stage, wherein the set of instructions for performing the lookup comprises a set of instructions for performing a hash-based search algorithm.

21. The electronic device of claim 18, wherein the table further comprises an action for forwarding a packet, wherein the rule generated for processing subsequent packets comprises the action to apply to the subsequent packets.

22. The electronic device of claim 18, wherein when a lookup for a header field in a stage does not identify a matching rule no further lookup is performed in the table.