PERFORMING A MULTI-STAGE LOOKUP TO CLASSIFY PACKETS

• US 20170237664A1
• Filed: 05/01/2017
• Published: 08/17/2017
• 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
• Granted Patent: US 10,498,638 B2
• Time in Patent Office: 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-20. -20. (canceled)

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

receiving a packet comprising a set of header fields;

defining a wildcard mask for the packet, wherein the wildcard mask is initially set as entirely wildcarded;

for each of a plurality of header fields over which a set of rules match, until either (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;

performing a lookup for the header field; and

un-wildcarding the corresponding header field of the wildcard mask;

generating a rule for processing subsequent packets based on a matching rule and the un-wildcarded header fields of the wildcard mask.

22. The method of claim 21, 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, wherein performing the lookup for each header field comprises performing a look up of one or more of the stages of the table.

23. The method of claim 22, wherein the set of stages comprises at least one of a first stage associated with a set of register or metadata fields, a second stage associated with a set of metadata and network layer 2 (L2) fields, a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields;

and a fourth stage associated with each set of fields.

24. The method of claim 22, wherein the rules are stored as hash values in each stage, wherein performing the look up comprises performing a hash-based search algorithm.

25. The method of claim 22, 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.

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

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

28. 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 set of header fields;

defining a wildcard mask for the packet, wherein the wildcard mask is initially set as entirely wildcarded;

for each of a plurality of header fields over which a set of rules match, until either (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;

performing a lookup for the header field; and

un-wildcarding the corresponding header field of the wildcard mask;

generating a rule for processing subsequent packets based on a matching rule and the un-wildcarded header fields of the wildcard mask.

29. The non-transitory machine readable medium of claim 28, 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, wherein the set of instructions for performing the lookup for each header field comprises a set of instructions for performing a look up of one or more of the stages of the table.

30. The non-transitory machine readable medium of claim 29, wherein the set of stages comprises at least one of a first stage associated with a set of register or metadata fields, a second stage associated with a set of metadata and network layer 2 (L2) fields, a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields;

and a fourth stage associated with each set of fields.

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

32. The non-transitory machine readable medium of claim 29, 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.

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

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

35. 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 set of header fields;

defining a wildcard mask for the packet, wherein the wildcard mask is initially set as entirely wildcarded;

for each of a plurality of header fields over which a set of rules match, until either (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;

performing a lookup for the header field; and

un-wildcarding the corresponding header field of the wildcard mask;

generating a rule for processing subsequent packets based on a matching rule and the un-wildcarded header fields of the wildcard mask.

36. The electronic device of claim 35, 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, wherein the set of instructions for performing the lookup for each header field comprises a set of instructions for performing a look up of one or more of the stages of the table.

37. The electronic device of claim 35, wherein the set of stages comprises at least one of a first stage associated with a set of register or metadata fields, a second stage associated with a set of metadata and network layer 2 (L2) fields, a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields;

and a fourth stage associated with each set of fields.

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

39. The electronic device of claim 35, 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.

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