Automatic flow learning in network devices

Patent metadata

Field	Value
Publication number	US-10887240-B2
Application number	US-201916261302-A
Country	US
Kind code	B2
Filing date	Jan 29, 2019
Priority date	Feb 26, 2018
Publication date	Jan 5, 2021
Grant date	Jan 5, 2021

Abstract

In a network device, a flow classification hardware engine is configured to: store flow state information regarding known flows of packets in a flow information table in association with respective assigned flow identifiers (IDs). The assigned flow IDs are from an ordered set of M flow IDs, where M is a positive integer. In response to detecting new flows of packets, the flow classification hardware engine: i) assigns respective flow IDs, from the ordered set of M flow IDs, to the new flows, and ii) creates respective entries in the flow information table for the new flows. An embedded processor periodically, as part of a background process: i) identifies an oldest assigned flow ID, from the ordered set of M flow IDs, and ii) makes storage space in the flow information table corresponding to the oldest assigned flow ID available for a new flow.

First claim

What is claimed is:

1. A network device, comprising:
a packet processor coupled to a plurality of network ports, wherein the packet processor is configured to forward packets between the plurality of network ports, and wherein the packet processor includes:
a first memory, and
a flow classification hardware engine configured to:
store flow state information regarding known flows of packets in a flow information table in the first memory in association with respective assigned flow identifiers (IDs), wherein the assigned flow IDs are from an ordered set of M flow IDs stored in a plurality of ordered memory locations in the first memory, wherein M is a positive integer,
in response to detecting new flows of packets: i) assign respective flow IDs, from the ordered set of M flow IDs, to the new flows, and ii) create respective entries in the flow information table for the new flows, and
in response to detecting a new flow of packets, select an oldest unassigned flow ID from the ordered set of M flow IDs to assign to the new flow based on a location of the oldest unassigned flow ID within the plurality of ordered memory locations, and denote a new oldest unassigned flow ID, from the ordered set of M flow IDs, based on a location of the new oldest unassigned flow ID within the plurality of ordered memory locations; and

an embedded processor that is configured to execute machine readable instructions stored in a second memory coupled to the embedded processor, and wherein the second memory stores instructions that, when executed by the embedded processor, cause the embedded processor to, periodically, as part of a background process: i) identify an oldest assigned flow ID, from the ordered set of M flow IDs, based on a location of the oldest assigned flow ID within the plurality of ordered memory locations, ii) make storage space in the flow information table corresponding to the oldest assigned flow ID available for a new flow, and iii) denote a new oldest assigned flow ID, from the ordered set of M flow IDs, based on a location of the new oldest assigned flow ID within the plurality of ordered memory locations.

2. The network device of claim 1 , wherein:
the flow classification hardware engine includes, or is coupled to, a table associated with known flows;
the flow classification hardware engine is configured to store assigned IDs corresponding to known flows of packets in the table associated with known flows;
wherein the second memory stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned, delete the oldest assigned flow ID from the table associated with known flows.

3. The network device of claim 1 , wherein the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned:
delete, from the flow information table, flow state information regarding a flow corresponding to the oldest assigned flow ID to make storage space in the flow information table available for a new flow.

4. The network device of claim 3 , wherein the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned:
copy the flow state information regarding the flow corresponding to the oldest assigned flow ID from the flow information table to the second memory.

5. The network device of claim 1 , wherein:
the flow classification hardware engine comprises: i) a hash generator, and ii) an exact match table with entries corresponding to hash values associated with known flows;
the exact match table respectively stores assigned flow IDs in entries corresponding to known flows, wherein entries of the exact match table correspond to hash values generated by the hash generator; and
the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned:
delete the oldest assigned flow ID from an entry in the exact match table as part of making the entry available for a new flow.

6. The network device of claim 1 , wherein:
the flow classification hardware engine comprises: a ternary content addressable memory (TCAM) having rows corresponding to known flows;
the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned:
update a row in the TCAM corresponding to the oldest assigned flow ID so that the row no longer corresponds to the flow corresponding to the oldest assigned flow ID and is available to be assigned to a new flow.

7. The network device of claim 6 , wherein:
the flow classification hardware engine further comprises: a table that respectively stores assigned flow IDs in entries corresponding to rows of the TCAM; and
the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to, in conjunction with denoting the oldest assigned flow ID as unassigned:
delete the oldest assigned flow ID from the table that respectively stores assigned flow IDs in entries corresponding to rows of the TCAM in connection with making a row of the TCAM corresponding to the oldest assigned flow ID available for a new flow.

8. The network device of claim 1 , further comprising:
an external processor coupled to the packet processor; and
a third memory coupled to the external processor;
wherein the second memory stores instructions that, when executed by the embedded processor, cause the embedded processor to, send flow state information corresponding to flows to the external processor; and
wherein the third memory stores instructions that, when executed by the external processor, cause the external processor to, in conjunction with receiving flow state information corresponding to the flows from the embedded processor, create flow records corresponding to the flows in the third memory.

9. The network device of claim 1 , wherein:
the flow classification hardware engine configured to, in response to detecting a new flow of packets, select the oldest unassigned flow ID from the ordered set of M flow IDs to assign to the new flow using a first pointer that points to the oldest unassigned flow ID in the plurality of ordered memory locations, and change the first pointer to point to a new oldest unassigned flow ID, from the ordered set of M flow IDs, in the plurality of ordered memory locations; and
the second memory stores instructions that, when executed by the embedded processor, cause the embedded processor to, periodically, as part of a background process:
identify the oldest assigned flow ID using a second pointer that points to the oldest assigned flow ID in the plurality of ordered memory locations, and
denote the new oldest assigned flow ID at least by changing the second pointer to point to the new oldest assigned flow ID in the plurality of ordered memory locations.

10. The network device of claim 9 , wherein:
the flow classification hardware engine is further configured to change the first pointer to point to the new oldest unassigned flow ID at least by incrementing the first pointer after selecting the flow ID indicated by the first pointer; and
the second memory further stores instructions that, when executed by the embedded processor, cause the embedded processor to denote the oldest assigned flow ID as unassigned at least by increment

Assignees

• Marvell Israel Misl Ltd

Inventors

• Mizrahi Tal
• Zemach Rami
• Arad Carmi
• Melman David
• Katan Yosef

Classifications

• H04L43/16

  Threshold monitoring · CPC title

• H04L47/2441 Primary

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title