Performing a multi-stage lookup to classify packets
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.
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.