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

• US 9,996,467 B2
• Filed: 12/13/2013
• Issued: 06/12/2018
• 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:
  US14/106,355
• Publication Number:
  US 20150169451A1
• Time in Patent Office: 1,642 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 for execution by at least one processing unit, the program comprising sets of instructions for:

setting a maximum number of flow entries allowed in a flow cache to a first maximum number, each of a plurality of the flow entries used for processing packets that match a set of match conditions of the flow entry;

with the first maximum number of flow entries stored in the flow cache, iterating through the flow cache to perform a set of operations on each flow entry in the flow cache;

determining a duration of time spent for said iterating through the flow cache to perform said set of operations; and

based on the determined duration, changing the maximum number of flow entries allowed in the flow cache from the first maximum number to a second, different maximum number.

2. The non-transitory machine readable medium of claim 1, wherein the set of instructions for changing the maximum number of flow entries comprises a set of instructions for increasing the maximum number of flow entries allowed in the flow cache when the duration is less than a threshold duration.

3. The non-transitory machine readable medium of claim 1, wherein the set of instructions for changing the maximum number of flow entries comprises a set of instructions for reducing the maximum number of flow entries allowed in the flow cache when the duration is greater than a threshold duration.

4. The non-transitory machine readable medium of claim 3, wherein the threshold duration is a first threshold duration, wherein the set of instructions for changing the maximum number of flow entries comprises sets of instructions for:

reducing the maximum number of flow entries allowed in the flow cache by a first amount when the duration is greater than the first threshold duration; and

reducing the maximum number of flow entries allowed in the flow cache by a second, different amount that is less than the first amount when the duration is greater than a second threshold duration, the second threshold duration being shorter than the first threshold duration.

5. The non-transitory machine readable medium of claim 1, wherein the set of instructions for changing the maximum number of flow entries comprises a set of instructions for using an additive-increase/multiplicative-decrease (AIMD) algorithm to respectively increase or decrease the number of flow entries allowed in the flow cache.

6. The non-transitory machine readable medium of claim 1, wherein the set of operations includes validating the flow entry against one or more other flow entries in one or more flow tables.

7. The non-transitory machine readable medium of claim 6, wherein the set of instructions for validating comprises sets of instructions for:

determining whether the flow entry remains valid based on the one or more other flow entries; and

removing the flow entry from the flow cache or updating the flow entry if the flow entry is not valid.

8. The non-transitory machine readable medium of claim 1, wherein the set of operations includes updating statistical data relating to the flow entry.

9. The non-transitory machine readable medium of claim 1, wherein the set of operations includes determining whether the flow entry has expired and removing the flow entry from the flow cache if the flow has expired.

10. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for installing a particular flow entry in the flow cache based on one or more flow entries from a set of one or more flow tables.

11. For a forwarding element, a method of adjusting the size of a cache, the method comprising:

setting a maximum number of flow entries allowed in a flow cache to a first maximum number, each of a plurality of the flow entries used for processing packets that match a set of match conditions of the flow entry;

with the first maximum number of flow entries stored in the flow cache, iterating through the flow cache to perform a set of operations on each flow entry in the flow cache;

determining a duration of time spent for said iterating through the flow cache to perform said set of operations; and

based on the determined duration, changing the maximum number of flow entries allowed in the flow cache from the first maximum number to a second, different maximum number.

12. The method of claim 11, wherein the changing the maximum number of flow entries comprises increasing the maximum number of flow entries allowed in the flow cache when the duration is less than a threshold duration.

13. The method of claim 11, wherein changing the maximum number of flow entries comprises reducing the maximum number of flow entries allowed in the flow cache when the duration is greater than a threshold duration.

14. The method of claim 13, wherein the threshold duration is a first threshold duration, wherein changing the maximum number of flow entries comprises:

reducing the maximum number of flow entries allowed in the flow cache by a first amount when the duration is greater than the first threshold duration; and

reducing the maximum number of flow entries allowed in the flow cache by a second, different amount that is less than the first amount when the duration is greater than a second threshold duration, the second threshold duration being shorter than the first threshold duration.

15. The method of claim 11, wherein changing the maximum number of flow entries comprises using an additive-increase/multiplicative-decrease (AIMD) algorithm to respectively increase or decrease the number of flow entries allowed in the flow cache.

16. The method of claim 11, wherein the set of operations includes validating the flow entry against one or more other flow entries in one or more flow tables.

17. The method of claim 16, wherein validating comprises:

determining whether the flow entry remains valid based on the one or more other flow entries; and

removing the flow entry from the flow cache or updating the flow entry if the flow entry is not valid.

18. The method of claim 11, wherein the set of operations includes updating statistical data relating to the flow entry.

19. The method of claim 11, wherein the set of operations includes determining whether the flow entry has expired and removing the flow entry from the flow cache if the flow has expired.

20. The method of claim 11 further comprising installing a particular flow entry in the flow cache based on one or more flow entries from a set of one or more flow tables.