Installing and managing flows in a flow table cache

• US 9,569,368 B2
• Filed: 12/13/2013
• Issued: 02/14/2017
• Est. Priority Date: 12/13/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Jackson, Ethan J.
• Primary Examiner(s): Musa, Abdelnabi O
• Application Number:
  US14/106,379
• Publication Number:
  US 20150169457A1
• Time in Patent Office: 1,159 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory

Abstract

Some embodiments provide a physical forwarding that installs flows in a flow table cache and uses the flows to process packets. In addition, the physical forwarding element iterates through each flow and validates the flow. In some embodiments, the physical forwarding element performs the installation and validation operations in a multi-threaded manner. The physical forwarding element in some such embodiments includes a set of one or more upcall handlers to install flows in the cache, and a set of one or more revalidators to validate the flows in the cache. In its own thread, an upcall handler may run independently of each revalidator in the set of revalidators. In another thread, a revalidator may run independently of each upcall handler and each other revalidator.

Claims

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

generating and installing flows in a cache, wherein each flow is generated using at least one rule, from a flow table, which specifies performing a set of actions on incoming packets;

validating one or more of the flows that are installed in the cache by determining whether a set of actions in each flow matches a corresponding rule in the flow table, wherein each flow is assigned to a separate execution thread to be validated; and

removing or modifying each flow that has a different set of actions than a corresponding rule in the flow table in order to improve a performance of packet processing, wherein said generating and installing flows are executed in a first set of execution threads and said validating, removing, and modifying are executed in a second, different set of execution threads.

2. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for:

determining whether each flow has expired; and

removing a flow from the cache when the flow has expired.

3. The non-transitory machine readable medium of claim 2, wherein the program further comprises a set of instructions for determining that a flow has expired when the flow has not been used to process a packet in a set time period.

4. The non-transitory machine readable medium of claim 1, wherein the set of instructions for validating each flow comprises a set of instructions for finding a rule that matches the flow'"'"'s match fields and determining if a set of actions associated with the rule matches the set of actions associated with the flow.

5. The non-transitory machine readable medium of claim 4, wherein the set of instructions for modifying each flow that has a different set of actions comprises a set of instructions for changing the set of actions associated with the flow to be the same as the set of actions associated with the rule when the sets of actions are different.

6. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for updating statistics relating to the flow.

7. The non-transitory machine readable medium of claim 6, wherein the statistics comprises at least one of a packet counter and a byte counter.

8. The non-transitory machine readable of claim 1, wherein the program further comprises sets of instructions for:

finding a matching flow for a packet in the cache; and

generating and installing a flow in the cache that corresponds to the packet when a matching flow is not found.

9. A method of processing packets, the method comprising:

generating and installing flows in a cache, wherein each flow is generated using at least one rule, from a flow table, which specifies performing a set of actions on incoming packets;

validating one or more of the flows that are installed in the cache by determining whether a set of actions in each flow matches a corresponding rule in the flow table, wherein each flow is assigned to a separate execution thread to be validated; and

removing or modifying each flow that has a different set of actions than a corresponding rule in the flow table in order to improve a performance of packet processing, wherein said generating and installing flows are executed in a first set of execution threads and said validating, removing, and modifying are executed in a second, different set of execution threads.

10. The method of claim 9 further comprising:

determining whether each flow has expired; and

removing a flow from the cache when the flow has expired.

11. The method of claim 9 further comprising determining that a flow has expired when the flow has not been used to process a packet in a set time period.

12. The method of claim 9, wherein validating each flow comprises finding a rule that matches the flow'"'"'s match fields and determining if a set of actions associated with the rule matches the set of actions associated with the flow.

13. The method of claim 12, wherein modifying each flow that has a different set of actions comprises changing the set of actions associated with the flow to be the same as the set of actions associated with the rule when the sets of actions are different.

14. The method of claim 9 further comprising updating statistics relating to the flow.

15. The method of claim 14, wherein the statistics comprises at least one of a packet counter and a byte counter.

16. The method of claim 9 further comprising:

finding a matching flow for a packet in the cache; and

when a matching flow is not found, generating and installing a flow in the cache that corresponds to the packet.