Algorithmic TCAM based ternary lookup

Patent metadata

Field	Value
Publication number	US-11687594-B2
Application number	US-201916383448-A
Country	US
Kind code	B2
Filing date	Apr 12, 2019
Priority date	Sep 20, 2015
Publication date	Jun 27, 2023
Grant date	Jun 27, 2023

Abstract

An algorithmic TCAM based ternary lookup method is provided. The method stores entries for ternary lookup into several sub-tables. All entries in each sub-table have a sub-table key that includes the same common portion of the entry. No two sub-tables are associated with the same sub-table key. The method stores the keys in a sub-table keys table in TCAM. Each key has a different priority. The method stores the entries for each sub-table in random access memory. Each entry in a sub-table has a different priority. The method receives a search request to perform a ternary lookup for an input data item. A ternary lookup into the ternary sub-table key table stored in TCAM is performed to retrieve a sub-table index. The method performs a ternary lookup across the entries of the sub-table associated with the retrieved index to identify the highest priority matched entry for the input data item.

First claim

What is claimed is:

1. A method for forwarding data messages by performing matching operations on a network switch comprising ternary content addressable memory (TCAM) and random access memory (RAM), the method comprising:
at the network switch:
receiving a data message comprising a set of header values;
using the set of header values to perform a lookup operation on a key table stored in the TCAM to identify a plurality of records stored in the RAM, each record storing (i) a first data tuple to compare with the header value set and (ii) a second data tuple to use to effectuate a forwarding decision to forward the data message;
comparing the first data tuples of the identified plurality of records retrieved from the RAM in parallel with the header value set of the data message to determine any of the first data tuples that match the header value set; and
in response to determining that multiple first data tuples match the data message's header value set, using the second data tuple of the matching record with a highest priority in order to effectuate a forwarding operation for the data message.

2. The method of claim 1 , wherein comparing the first data tuples with the header value set comprises performing longest prefix match (LPM) operations.

3. The method of claim 2 , wherein (i) the first data tuple is an Internet Protocol (IP) address, and (ii) each record of the plurality of records comprises an IP network prefix that begins with a same set of bits.

4. The method of claim 1 , wherein using the set of header values comprises retrieving an index value from a key table entry that is identified through the key table lookup operation, said index value identifying the plurality of records in the RAM.

5. The method of claim 4 , comprising using the index value to retrieve the first data tuple from the plurality of records for the comparing the first data tuples in parallel with the header value set.

6. The method of claim 4 , wherein at least one entry in the key table comprises (i) a key and (ii) an index value to output when a data message's header value set matches the entry's key.

7. The method of claim 6 , wherein at least one entry in the key table further comprises an associated mask identifying a set of wildcard values in the key.

8. The method of claim 3 , wherein at least one record in a sub-table comprises at least one wildcard value for the first data tuple.

9. The method of claim 1 , wherein a number of bits in the first data tuples is fewer than a number of bits in the header value set.

10. A method for performing a service operation on a data message received by a network element comprising ternary content addressable memory (TCAM) and random access memory (RAM), the method comprising:
at the network element:
receiving a data message comprising a set of header values;
using the set of header values to perform a lookup operation on a key table stored in the TCAM to identify a plurality of service rules stored in the RAM, each service rule storing (i) a data tuple to compare with the header value set and (ii) an action parameter for performing a service action on the data message;
comparing the data tuples of the identified plurality of service rules retrieved from the RAM in parallel with the header value set of the data message to determine any of the data tuples that match the header value set; and
in response to determining that multiple data tuples match the data message's header value set, using the action parameter of the matching record with a highest priority in order to perform the service operation on the data message.

11. The method of claim 10 , wherein the service operation is a firewall operation, the service rules are firewall rules, and the action parameters comprises permit and drop actions.

12. The method of claim 10 , wherein at least one service rule comprises a mask identifying a set of wildcard values for the service rule.

13. The method of claim 10 , wherein the plurality of service rules comprise rules for a set of access control lists (ACLs) for a firewall.

14. The method of claim 10 , wherein using the header value set to perform a lookup operation on a key table comprises retrieving an index value from a key table entry that is identified through the lookup operation on the key table, said index value identifying the plurality of service rules stored in the RAM.

15. The method of claim 14 , comprising using the retrieved index value to retrieve the data tuples from the identified plurality of service rules, in order to compare the data tuples in parallel with the header value set.

16. The method of claim 10 , wherein at least one entry in the key table comprises (i) a key and (ii) an index value to output when a data message's header value set matches the entry's key.

17. The method of claim 16 , wherein at least one entry in the key table further comprises an associated mask identifying a set of wildcard values in the key.

18. The method of claim 10 , wherein at least one service rule in a sub-table comprises at least one wildcard value for the data tuple.

19. A network switch for performing a ternary lookup, the network switch comprising:
a random access memory (RAM) configured to store a plurality of records;
a ternary content addressable memory (TCAM) configured to store a key table;
for a data message received by the network switch, perform a lookup operation on the key table stored in the TCAM to identify a plurality of records stored in the RAM, each record to store (i) a first data tuple to compare with a header value set of the data message and (ii) a second data tuple to use to effectuate a forwarding decision to forward the data message;
wherein the first data tuples of the identified plurality of records retrieved from the RAM are compared in parallel with the header value set of the data message to determine any of the first data tuples that match the header value set, and in response to determining that multiple first data tuples match the data message's header value set, the second data tuple of the matching record with a highest priority is used to effectuate a forwarding operation for the data message.

20. The network switch of claim 19 , wherein the first data tuples are compared with the header value set by performing longest prefix match (LPM) operations.

21. The network switch of claim 19 , wherein (i) the first data tuple is an Internet Protocol (IP) address, and (ii) each record comprises an IP network prefix that begins with a same set of bits.

Assignees

• Barefoot Networks Inc

Inventors

• Bosshart Patrick
• Ferrara Michael G
• Peterson Jay E S

Classifications

• G06F16/90339 Primary

  by using parallel associative memories or content-addressable memories · CPC title

• H04L45/742 Primary

  Route cache; Operation thereof · CPC title

• H04L45/74591

  using content-addressable memories [CAM] · CPC title

• G11C11/40615

  Internal triggering or timing of refresh, e.g. hidden refresh, self refresh, pseudo-SRAMs · CPC title

• G11C15/04

  using semiconductor elements · CPC title