Dynamically generating flows with wildcard fields

• US 9,602,398 B2
• Filed: 10/31/2013
• Issued: 03/21/2017
• 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, Jesse E. IV, Zhou, Andy
• Primary Examiner(s): Lai, Michael C
• Application Number:
  US14/069,284
• Publication Number:
  US 20150081833A1
• Time in Patent Office: 1,237 Days
• US Class Current: 1/1
• 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 that forwards packets according to flow entries, a method comprising:

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

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

dynamically generating the new flow entry by un-wildcarding each match field of the new flow entry that corresponds to a match field that is consulted in matching the packet against a set of flow entries in a set of flow tables, wherein the new flow entry has at least one wildcard field remaining;

performing a set of actions on the packet according to the new flow entry; and

storing the new flow entry in the flow cache to process any subsequent packet that matches each non-wildcard field of the new flow entry.

2. The method of claim 1, wherein dynamically generating the new flow entry comprises:

comparing a value of a match field of a flow entry in the set of flow tables against a header field value of the packet; and

un-wildcarding the match field of the new flow entry when the header field value of the packet matches the value of the match field of the flow entry.

3. The method of claim 1, wherein dynamically generating the new flow entry comprises identifying a matching flow entry in a flow table of the set of flow tables.

4. The method of claim 3, wherein dynamically generating the new flow entry further comprises un-wildcarding one or more fields of the new flow entry based on an action associated with the matching flow entry.

5. The method of claim 3, wherein the matching flow entry is a first matching flow entry, wherein dynamically generating the new flow entry further comprises searching the same flow table or another flow table for a second matching flow entry if the first matching flow entry specifies a resubmit action.

6. The method of claim 1, wherein dynamically generating the new flow entry comprises using a hash-based algorithm to search for one or more matching flow entries in the set of flow tables while un-wildcarding each match 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 set of flow tables, starting with infrequently changing match fields and progressing to frequently changing fields.

8. The method of claim 1, wherein dynamically generating the new flow entry comprises using a decision tree algorithm to search for one or more matching flow entries in the set of flow tables while un-wildcarding each match field that is consulted during the search.

9. The method of claim 1, 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 non-wildcard field of the new flow entry stored in the flow cache; and

in response to the determination, performing the set of actions on the second packet without consulting the set of flow tables.

10. The method of claim 1, wherein the new flow entry includes a plurality of wildcard match fields.

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

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

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

dynamically generating the new flow entry by un-wildcarding each match field of the new flow entry that corresponds to a match field that is consulted in matching the packet against a set of flow entries in a set of flow tables, wherein the new flow entry has at least one wildcard field remaining;

performing a set of actions on the packet according to new flow entry; and

storing the new flow entry in the flow cache to process any subsequent packet that matches each non-wildcard field of the new flow entry.

12. The non-transitory machine readable medium of claim 11, wherein the set of instructions for dynamically generating the new flow entry comprises sets of instructions for:

comparing a value of a match field of a flow entry in the set of flow tables against a header field value of the packet; and

un-wildcarding the match field of the new flow entry when the header field value of the packet matches the value of the match field of the flow entry.

13. The non-transitory machine readable medium of claim 11, wherein the set of instructions for dynamically generating the new flow entry comprises a set of instructions for identifying a matching flow entry in a flow table of the set of flow tables.

14. The non-transitory machine readable medium of claim 13, wherein the set of instructions for dynamically generating the new flow entry further comprises a set of instructions for un-wildcarding one or more fields of the new flow entry based on an action associated with the matching flow entry.

15. The non-transitory machine readable medium of claim 13, wherein the matching flow entry is a first matching flow entry, wherein the set of instructions for dynamically generating the new flow entry further comprises a set of instructions for searching the same flow table or another flow table for a second matching flow entry if the first matching flow entry specifies a resubmit action.

16. The non-transitory machine readable medium of claim 11, wherein the set of instructions for dynamically generating the new flow entry comprises a set of instructions for using a hash-based algorithm to search for one or more matching flow entries in the set of flow tables while un-wildcarding each match 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 set of flow tables, starting with infrequently changing match fields and progressing to frequently changing fields.

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

19. The non-transitory machine readable medium of claim 11, 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 non-wildcard field of the new flow entry stored in the flow cache; and

performing, in response to the determination, the set of actions on the second packet without consulting the set of flow tables.

20. The non-transitory machine readable medium of claim 11, wherein the new flow entry includes a plurality of wildcard match fields.