Dynamically generating flows with wildcard fields

• US 10,382,324 B2
• Filed: 02/27/2017
• Issued: 08/13/2019
• Est. Priority Date: 09/15/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Pettit, Justin, Jackson, Ethan J., Gross, IV, Jesse E., Zhou, Andy
• Primary Examiner(s): Lai, Michael C
• Application Number:
  US15/443,351
• Publication Number:
  US 20170171065A1
• Time in Patent Office: 897 Days
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Some embodiments of the invention provide a switching element that receives a packet and processes the packet by dynamically generating a flow entry with a set of wildcard fields. The switching element then caches the flow entry and processes any subsequent packets that have header values that match the flow entry'"'"'s non-wildcard match fields. In generating the flow, the switching element initially wildcards some of all of match fields and generates a new flow entry by un-wildcarding each match field that was consulted or examined to generate the flow entry.

Claims

1. For a managed forwarding element, a method comprising:

receiving a packet that does not match any entry in a flow cache;

initializing a new entry, to be stored in the flow cache for processing the packet, with a plurality of wildcard fields;

modifying the new entry for the flow cache by processing the packet through a set of stages that each comprises sets of rules, by matching the packet against the sets of rules at each stage and un-wildcarding each field of the new entry that corresponds to a field of a rule of the sets of rules in one of the stages that was consulted in matching a field of the packet against the sets of rules; and

storing the new entry, with at least one wildcard field remaining, in the flow cache to use in processing subsequent packets that match fields of the new entry that are not wildcard fields.

2. The method of claim 1, wherein the new entry in the flow cache comprises a set of actions to perform on packets that match the fields of the new entry that are not wildcard fields, the method further comprising performing the set of actions on the packet according to the new entry in the flow cache.

3. The method of claim 2, wherein the packet is a first packet, the method further comprising:

receiving a second packet;

determining that a header of the second packet has values that match each field of the new entry stored in the flow cache that is not a wildcard field; and

in response to the determination, performing the set of actions on the second packet according to the new entry in the flow cache.

4. The method of claim 1, wherein modifying the new entry for the flow cache comprises:

comparing a value of a match field of a rule in the sets of rules against a header field value of the packet; and

un-wildcarding a match field of the new entry corresponding to the match field of the rule when the header field value of the packet matches the value of the match field of the rule.

5. The method of claim 1, wherein modifying the new entry for the flow cache comprises un-wildcarding one or more fields of the new entry based on an action associated with a particular rule that matches the header field value of the packet.

6. The method of claim 1, wherein modifying the new entry for the flow cache comprises using a hash-based algorithm to search for one or more matching rules in the sets of rules while un-wildcarding each field that is consulted during the search.

7. The method of claim 6, wherein the hash-based algorithm performs a multi-staged search of the sets of rules, starting with infrequently changing fields and progressing to frequently changing fields.

8. The method of claim 6, wherein using the hash-based algorithm comprises:

placing each rule in one of the sets of rules in one of a set of hash tables based on a set of fields that the rule matches;

performing a hash table lookup of a set of fields of the packet in each hash table; and

un-wildcarding each field of the new entry that corresponds to a field of a rule that was consulted.

9. The method of claim 1, wherein modifying the new entry for the flow cache comprises using a decision tree algorithm to search for one or more matching rules in the sets of rules while un-wildcarding each match field that is consulted during the search.

10. The method of claim 1, wherein un-wildcarding each field of the new entry comprises un-wildcarding each field of the new entry that corresponds to a field of a rule that was compared with a field in the packet irrespective of whether there was a match between the field in the rule and the field of the packet.

11. The method of claim 1, wherein un-wildcarding each field of the new entry comprises un-wildcarding a field of the new entry only when the field of the new entry corresponds to a field of a rule that was matched to a field in the packet.

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

receiving a packet that does not match any entry in a flow cache;

initializing a new entry, to be stored in the flow cache for processing the packet, with a plurality of wildcard fields;

modifying the new entry for the flow cache by processing the packet through a set of stages that each comprises sets of rules, by matching the packet against the sets of rules at each stage and un-wildcarding each field of the new entry that corresponds to a field of a rule of the sets of rules in one of the stages that was consulted in matching a field of the packet against the sets of rules; and

storing the new entry, with at least one wildcard field remaining, in the flow cache to use in processing subsequent packets that match fields of the new entry that are not wildcard fields.

13. The non-transitory machine readable medium of claim 12, wherein the new entry in the flow cache comprises a set of actions to perform on packets that match the fields of the new entry that are not wildcard fields, wherein the program further comprises a set of instructions for performing the set of actions on the packet according to the new entry in the flow cache.

14. The non-transitory machine readable medium of claim 13, wherein the packet is a first packet, the program further comprising sets of instructions for:

receiving a second packet;

determining that a header of the second packet has values that match each field of the new entry stored in the flow cache that is not a wildcard field; and

performing, in response to the determination, the set of actions on the second packet according to the new entry in the flow cache.

15. The non-transitory machine readable medium of claim 12, wherein the set of instructions for modifying the new entry for the flow cache comprises sets of instructions for:

comparing a value of a match field of a rule in the sets of rules against a header field value of the packet; and

un-wildcarding a match field of the new entry corresponding to the match field of the rule when the header field value of the packet matches the value of the match field of the rule.

16. The non-transitory machine readable medium of claim 12, wherein the set of instructions for modifying the new entry for the flow cache comprises a set of instructions for using a hash-based algorithm to search for one or more matching rules in the sets of rules while un-wildcarding each field that is consulted during the search.

17. The non-transitory machine readable medium of claim 16, wherein the hash-based algorithm performs a multi-staged search of the sets of rules, starting with infrequently changing fields and progressing to frequently changing fields.

18. The non-transitory machine readable medium of claim 12, wherein the set of instructions for modifying the new entry for the flow cache comprises a set of instructions for using a decision tree algorithm to search for one or more matching rules in the sets of rules while un-wildcarding each match field that is consulted during the search.

19. The non-transitory machine readable medium of claim 12, wherein the set of instructions for un-wildcarding each field of the new entry comprises a set of instructions for un-wildcarding each field of the new entry that corresponds to a field of a rule that was compared with a field in the packet irrespective of whether there was a match between the field in the rule and the field of the packet.

20. The non-transitory machine readable medium of claim 12, wherein the set of instructions for un-wildcarding each field of the new entry comprises a set of instructions for un-wildcarding a field of the new entry only when the field of the new entry corresponds to a field of a rule that was matched to a field in the packet.