Dynamically adjusting the number of flows allowed in a flow table cache

• US 10,380,019 B2
• Filed: 06/11/2018
• Issued: 08/13/2019
• 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): Faal, Baboucarr
• Application Number:
  US16/005,506
• Publication Number:
  US 20180300244A1
• Time in Patent Office: 428 Days
• Field of Search: None
• 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

Abstract

Some embodiments provide a physical forwarding element that dynamically adjusts the number of flows allowed in a flow table cache. In adjusting, the physical forwarding element initially sets the maximum number of flows allowed in the cache. From the flow table cache, the physical forwarding then iterates through the set maximum number of flows and records the length of time it took to iterate through the flows. Based on the duration, the physical forwarding element then automatically adjusts the size of the flow table cache by increasing or decreasing the number of flows allowed in the cache. Alternatively, the physical forwarding element may choose to keep the cache size the same based on the duration.

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 flow entries in a cache, wherein each flow entry is generated using at least one flow entry, from a flow table, that specifies performing a set of actions on incoming packets; and

validating one or more of the flow entries that are installed in the cache by determining whether a set of actions in each flow entry matches a set of actions of a corresponding flow entry in the flow table, said validating comprising;

for each flow entry in the cache in which the set of actions matches the set of actions of a corresponding flow entry in the flow table, maintaining the flow entry in the cache; and

for each flow entry in the cache in which the set of actions does not match the set of actions of a corresponding flow entry in the flow table, removing or modifying the flow entry in the cache;

wherein said generating and installing flow entries are executed in a first execution thread and said validating, removing, and modifying are executed in a second, different execution thread.

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

determining whether each flow entry has expired; and

removing a flow entry from the cache when the flow entry 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 entry has expired when the flow entry 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 particular flow entry in the cache comprises a set of instructions for finding a flow entry in the flow table that matches the particular flow entry'"'"'s match fields and determining if a set of actions associated with the flow entry matches the set of actions associated with the particular flow entry.

5. The non-transitory machine readable medium of claim 4, wherein the set of instructions for modifying each particular flow entry in the cache that has a different set of actions comprises a set of instructions for changing the set of actions associated with the particular flow entry to be the same as the set of actions associated with the flow entry in the flow table 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 entry.

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 a set of instructions for iterating through each flow entry in the cache.

9. 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 entry in the cache that corresponds to the packet when a matching flow is not found in the cache.

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

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

validating one or more of the flow entries that are installed in the cache by determining whether a set of actions in each flow entry matches a set of actions of a corresponding flow entry in the flow table, said validating comprising;

for each flow entry in the cache in which the set of actions matches the set of actions of a corresponding flow entry in the flow table, maintaining the flow entry in the cache; and

for each flow entry in the cache in which the set of actions does not match the set of actions of a corresponding flow entry in the flow table, removing or modifying the flow entry in the cache;

wherein said generating and installing flow entries are executed in a first execution thread and said validating, removing, and modifying are executed in a second, different execution thread.

11. The method of claim 10 further comprising:

determining whether each flow entry has expired; and

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

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

13. The method of claim 10, wherein validating each particular flow entry in the cache comprises finding a flow entry in the flow table that matches the particular flow entry'"'"'s match fields and determining if a set of actions associated with the flow entry matches the set of actions associated with the particular flow entry.

14. The method of claim 13, wherein modifying each particular flow entry in the cache that has a different set of actions comprises changing the set of actions associated with the particular flow entry to be the same as the set of actions associated with the flow entry in the flow table when the sets of actions are different.

15. The method of claim 10 further comprising updating statistics relating to the flow entry.

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

17. The method of claim 10 further comprising iterating through each flow entry in the cache.

18. The method of claim 10 further comprising:

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

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