Flow table aging optimized for DRAM access

Patent metadata

Field	Value
Publication number	US-11960413-B2
Application number	US-202318114698-A
Country	US
Kind code	B2
Filing date	Feb 27, 2023
Priority date	May 17, 2019
Publication date	Apr 16, 2024
Grant date	Apr 16, 2024

Abstract

A flow table management system can include a hardware memory module communicatively coupled to a network interface card. The hardware memory module is configured to store a flow table including a plurality of network flow entries. The network interface card further includes a flow table age cache configured to store a set of recently active network flows and a flow table management module configured to manage a duration for which respective network flow entries in the flow table stored in the hardware memory module remain in the flow table using the flow table age cache. In some implementations, age information about each respective flow in the flow table is stored in the hardware memory module in an age state table that is separate from the flow table.

First claim

The invention claimed is:

1. A method of managing a flow table, comprising:
providing a hardware memory module coupled to a network component, the hardware memory module storing a flow table including a plurality of entries, each entry corresponding to a network flow, and the hardware memory module storing age information in an age state table, the flow table and the age state table being stored in respective data structures that are separate and independently accessible;
providing on the network component, a flow table age cache configured to store a set of recently active network flows;
providing on the network component, a flow table management module configured to manage a duration for which respective entries in the flow table remain in the flow table by:
updating the flow table age cache with information indicating activity associated with the network flow;
periodically conducting a scan of the entries in the flow table, the scan including for each entry in the flow table:
looking up the network flow associated with the entry in the flow table age cache;
in response to the network flow associated with the entry being found in the flow table age cache, updating timer information for the network flow stored in the memory module; and
in response to the network flow associated with the entry not being found in the flow table age cache, evaluating an age of the entry based on the age information retrieved from the age state table, and removing the entry from the flow table in response to the age of the entry exceeding a threshold time value associated with the network flow.

2. The method of claim 1 , wherein the flow table management module evaluates the age of each entry based on a status of the network flow associated with entry and respective age thresholds that correspond to possible statuses of the network flow.

3. The method of claim 2 , wherein the flow table management module is configured to evaluate the age of a flow entry by comparing a last active timer value stored in association to a timer, and to scan the entries with a periodicity that is less than

1

2

bit
⁢

length
⁢

of
⁢
Last
⁢
Active
⁢

time

times the smallest age threshold associated with the possible statuses.

4. The method of claim 1 , wherein the network component comprises a network interface card of a server.

5. The method of claim 1 , wherein updating timer information for the network flow comprises a resetting an age timer for the network flow.

6. The method of claim 1 , wherein updating the timer information for the network flow comprises modifying a status of the network flow, thereby modifying the threshold time value associated with the network flow.

7. The method of claim 6 , wherein the possible statuses for the network flows comprise TCP flow statuses, including at least an initiation state, an established state, a terminating state, and a closed state.

8. The method of claim 6 , wherein updating the flow table age cache with information indicating activity associated with the network flow comprises changing the status of the network flow from a first of the possible statuses to a second of the possible statuses based on a type of the packet that was processed in association with the network flow.

9. The method of claim 6 , wherein the flow table management module is configured to maintain a multi-bit clock and to maintain for each flow entry in the flow table a last active time value represented by a same number of bits as are used in the multi-bit clock, and wherein evaluating the age of a flow table entry comprises comparing the last active time for the entry in the hardware memory module against a current value of the multi-bit clock.

10. The method of claim 9 , wherein if during the comparison, the last active time value stored for the flow table entry matches the bits of the multi-bit clock, the flow entry is determined to have exceeded the threshold.

11. A flow table management system, comprising:
A hardware memory module configured to store a flow table including a plurality of network flow entries, and to store age information in an age state table, the flow table and the age state table being stored in respective data structures that are separate and independently accessible;
a network component communicatively coupled to the hardware memory module, the network component further comprising:
a memory storing a flow table age cache configured to store a set of recently active network flows;
a processor configured to execute a flow table management module, the flow table management module configured to manage a duration for which respective network flow entries in the flow table stored in the hardware memory module remain in the flow table by:
updating the flow table age cache with information indicating activity associated with the network flow;
periodically conducting a scan of the network flow entries in the flow table, the scan including for each entry in the flow table:
looking up the network flow associated with the entry in the flow table age cache;
in response to the network flow associated with the entry being found in the flow table age cache, updating timer information for the network flow stored in the memory module; and
in response to the network flow associated with the entry not being found in the flow table age cache, evaluating an age of the entry based on the age information retrieved from the age state table, and removing the entry from the flow table in response to the age of the entry exceeding a threshold time value associated with the network flow.

12. The system of claim 11 , wherein the network component comprises a network interface card.

13. The system of claim 11 , wherein the flow table management module is configured to determine the age of each entry based on a status of the network flow associated with entry and respective age thresholds that correspond possible statuses of the network flow.

14. The system of claim 13 , wherein the flow table management module is configured to evaluate the age of a flow entry by comparing a last active timer value stored for the flow entry to a timer, and to scan the entries with a periodicity that is less than

1

2

bit
⁢

length
⁢

of
⁢

Last
⁢

Active
⁢

time

times the smallest age threshold associated with the possible statuses.

15. The system of claim 11 , wherein updating timer information for the network flow comprises a resetting an age timer for the network flow.

16. The system of claim 11 , wherein updating the timer information for the network flow comprises modifying a status of the network flow, thereby modifying the threshold

Assignees

• Google Llc

Inventors

• Wang Weihuang
• Chandra Prashant

Classifications

• H04L47/10

  Flow control; Congestion control · CPC title

• G06F12/123 Primary

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• H04L45/38 Primary

  Flow based routing · CPC title

• G06F12/0246

  in block erasable memory, e.g. flash memory · CPC title

• H04L47/2483

  involving identification of individual flows · CPC title