Granted Patent B2

US 12,218,840 · App. 16/902,371 · Granted Feb 4, 2025

Inventors: Manasi Deval (Portland, OR); Elazar Cohen (Haifa, IL); Shaul Yifrach (Haifa, IL); Parthasarathy Sarangam (Portland, OR)

Assignee: Intel Corporation

H04L45/7453H04L45/38H04L45/54H04L45/74591H04L69/22

Abstract

Claims (85)

1. A method implemented on a platform including a processor, host memory, and a network interface, comprising:

implementing a plurality of match-action tables in host memory, the plurality of match-action tables containing match-action entries comprising key-value pairs and configured to implement a multi-hash scheme employing a respective hash index for each match-action table;

implementing an exact match (EM) cache on the network interface in which a portion of the match-action entries are cached in the EM cache;

receiving a first packet at a port of the network interface;

generating a key from data contained in the first packet;

performing a lookup of the EM cache using the key; and

when a match of a match-action entry is found in the EM cache, performing an action defined by the match-action entry.

2. The method of claim 1 , further comprising:

when the lookup of the EM cache results in a miss,

using the key to perform a multi-hash search of the plurality of match-action tables in host memory to detect a match-action entry matching the key; and

when there is a matching match-action entry that is found, performing the action in the match-action entry.

3. The method of claim 2 , wherein a match-action entry is found, further comprising adding an entry to the EM cache corresponding to the match-action entry that is found.

4. The method of claim 2 , wherein the multi-hash search of the plurality of match-action tables in host memory results in a miss, further comprising:

determining a match-action table among the plurality of match-action tables in which a new match-action entry is to be added;

adding the new match-action entry to that match-action table;

adding a collision hint identifying one or more potential locations of the new match-action entry.

5. The method of claim 4 , further comprising providing a hint to the network interface relating to the new match-action entry that has been added.

6. The method of claim 4 , further comprising:

returning information to the network interface indicating the multi-hash search of the plurality of match-action tables in host memory resulted in a miss; and

performing an action via the network interface corresponding to a default action to be performed when a multi-hash search of the plurality of match-action tables in host memory results in a miss.

7. The method of claim 1 , further comprising:

implementing a first aging-out mechanism for the plurality of match-action tables in host memory including host memory aging information; and

implementing a second aging-out mechanism for the EM cache on the network interface including cache aging information;

wherein when a new match-action entry with an aging timer is added to one of the plurality of match-action tables, population of the new match-action entry into the EM cache causes an update to the cache aging information.

8. The method of claim 1 , further comprising:

removing a match-action entry from a match-action table in host memory;

sending a hint to the network interface to remove a corresponding match-action entry from the EM cache; and

when a corresponding match item entry is present is the EM cache, removing the match item entry from the EM cache.

9. A network interface, configured to be installed in a host platform having a processor and host memory in which a plurality of match-action tables containing match-action entries are stored, each match-action table having a hash index, comprising:

a first port;

a packet processing pipeline;

an exact match (EM) cache in which a plurality of match-action entries cached from the plurality of match-action tables in host memory are stored;

circuitry, including circuitry in the packet processing pipeline to,

forward a packet received at the first port to the packet processing pipeline;

generate, via the packet processing pipeline, a key derived from data in the packet; and

perform a lookup of the EM cache using the key by,

inputting the key to a plurality of hash calculators in parallel to generate a plurality of hashed key indexes;

performing a first EM match search using a first hashed key index; and

when a match of a match-action entry is found in the EM cache using the first hashed key index, performing an action defined by the match-action entry.

10. The network interface of claim 9 , wherein the lookup of the EM cache further comprises:

detecting the first EM match search using the first hashed key results in a miss, and in response thereto,

inspecting a collision hint table to determine one or more additional hashed key indexes to search with; and

searching the EM cache using the one or more additional hashed key indexes.

11. The network interface of claim 10 , further comprising a content addressable memory (CAM) and circuitry to implement the collision hint table in the CAM.

12. The network interface of claim 10 , further comprising circuitry to:

determine there are no matching entries in the EM cache for the key; and

forward the key to the host memory.

13. The network interface of claim 12 , further comprising circuitry to:

receive a new match-action entry to be cached in the EM cache; and

insert the new match-action entry into the EM cache.

14. The network interface of claim 9 , further comprising:

an EM aging data structure; and

circuitry to age-out match-action entries in the EM cache using the EM aging data structure.

15. A system, comprising:

a processor having a plurality of cores;

memory, coupled to the processor;

software instructions configured to be executed on one or more of the plurality of cores to cause the system to,

implement a plurality of match-action tables in the memory, the match-actions tables configured to store a plurality of match-action entries at respective indexes in each match action table; and

perform a lookup into the plurality of match-action tables using a multi-hash scheme;

a network interface including:

a first port;

a packet processing pipeline; and

an exact match (EM) cache in which a plurality of match-action entries cached from the plurality of match-action tables in memory are stored,

wherein the system is configured to atomically add and remove match-action entries in the EM cache and the plurality of match-action tables.

16. The system of claim 15 , wherein the network interface further comprises circuitry to:

receive a packet at the first port;

generate a key derived from data in the packet; and

perform a lookup of the EM cache using the key by,

inputting the key to a plurality of hash calculators in parallel to generate a plurality of hashed key indexes;

performing a first EM match search using a first hashed key index; and

when a match of a match-action entry is found in the EM cache using the first hashed key index, performing an action defined by the match-action entry.

17. The system of claim 16 , wherein the network interface further comprises circuitry to:

detect the first EM match search using the first hashed key results in a miss, and in response thereto,

inspect a collision hint table to determine one or more additional hashed key indexes to search with; and

search the EM cache using the one or more additional hashed key indexes.

18. The system of claim 17 , wherein the network interface further comprises circuitry to:

determine there are no matching match-action entries in the EM cache for the key; and

forward the key to the memory,

and wherein execution of the software instructions on one or more processor cores enables the system to perform a lookup of the plurality of match-action tables with the key to find a matching match-action entry.

19. The system of claim 18 , wherein in response to finding a match-action entry in a match-action table, the software instructions are configured, upon execution by a processor core, to forward information to the network interface associated with the matching match-action entry, and wherein the circuitry in the network interface is further configured to insert a new match-action entry in the EM cache corresponding to the matching match-action entry.

20. The system of claim 18 , wherein the software instructions are configured, upon execution by one or more processor cores, to:

detect there are no match-action entries in the plurality of match-action tables that match the key; and, in response thereto

employ the key to generate a new match-action entry using a multi-hash scheme;

insert the new match-action entry into one of the plurality of match-action tables; and

insert a collision hint corresponding to the new match-action entry in a collision hint table.

Assignments (1)

Continuity (1)

References Cited (15)