Performing a multi-stage lookup to classify packets
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22)
-
Specification