# US 2025/0094497 A1 · Algorithmic tcam based ternary lookup

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0094497 A1
- Document ID: US20250094497A1
- Status: Published application
- Kind: A1
- Application number: 18/966,033
- Filed: 2024-12-02
- Published: 2025-03-20
- Earliest claimed: 2015-09-20
- Assignees: Barefoot Networks, Inc.
- Applicants: Barefoot Networks, Inc.
- Inventors: Patrick Bosshart; Michael G. Ferrara; Jay E.S. Peterson
- Web page: https://patentgrep.com/patent/US20250094497A1

## CPC

- G06F 16/90339: {by using parallel associative memories or content-addressable memories}
- G06F 16/9017: {using directory or table look-up (use of a directory or look-up table in file systems G06F16/13)}
- G11C 7/1072: {for memories with random access ports synchronised on clock signal pulse trains, e.g. synchronous memories, self timed memories}
- G11C 11/40615: {Internal triggering or timing of refresh, e.g. hidden refresh, self refresh, pseudo-SRAMs}
- H04L 45/742: {Route cache; Operation thereof}
- H04L 45/74591: {using content-addressable memories [CAM]}
- G11C 15/04: using semiconductor elements
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 1

Integrated circuit for use in performing packet forwarding-related operations related to incoming packet data, the integrated circuit being configurable to use machine-readable ternary content addressable memory (TCAM) to store, at least in part, table data for use in association with the packet forwarding-related operations, the integrated circuit comprising:
processing hardware to execute compiler-produced program instructions, the compiler-produced program instructions, when executed by the processing hardware resulting in the integrated circuit being configured to perform the packet forwarding-related operations, the packet forwarding-related operations being configurable to comprise:
performing parallel table lookup operations to determine multiple entries in the table data that match, at least in part, at least one portion of the incoming packet data;
selecting, based upon relative priorities associated with the multiple entries, one of the multiple entries that corresponds to a highest one of the relative priorities; and
based upon the one of the multiple entries, determining at least one action to be executed in relation to the incoming packet data;
wherein:
the table data is configurable to comprise multiple table data partitions;
at least one of the multiple table data partitions is configurable to indicate, at least in part, the relative priorities in association with table indices that are associated with the at least one portion of the incoming packet data;
at least one other of the multiple table data partitions is configurable to comprise the multiple entries; and
the table data is configurable to indicate one or more packet processing rules that comprise the at least one action.

### Claim 2 (depends on 1)

The integrated circuit of claim 1, wherein:
at least one additional of the multiple table data partitions is configurable to indicate respective mask data associated with respective entries; and
the respective mask data is to be applied to certain portions of the incoming packet data.

### Claim 3 (depends on 1)

The integrated circuit of claim 1, wherein:
another integrated circuit comprises the machine-readable TCAM.

### Claim 4

Integrated circuit for use in performing packet forwarding-related operations related to incoming packet data, the integrated circuit being configurable to use machine-readable ternary content addressable memory (TCAM) to store, at least in part, table data for use in association with the packet forwarding-related operations, the integrated circuit comprising:
processing hardware to execute compiler-produced program instructions, the compiler-produced program instructions, when executed by the processing hardware resulting in the integrated circuit being configured to perform the packet forwarding-related operations, the packet forwarding-related operations being configurable to comprise:
performing ternary memory table lookup to determine multiple entries in the table data that match, at least in part, at least one portion of the incoming packet data;
selecting, based upon relative priorities associated with the multiple entries, one of the multiple entries that corresponds to a highest one of the relative priorities; and
based upon the one of the multiple entries, determining at least one action to be executed in relation to the incoming packet data;
wherein:
the table data is configurable to comprise multiple portions;
at least one of the multiple portions of the table data is configurable to indicate, at least in part, relative priority data in association with table key data, the relative priority data indicating the relative priorities;
at least one other of the multiple portions of the table data is configurable to comprise the multiple entries; and
the table data is configurable to indicate one or more packet processing rules that comprise the at least one action.

### Claim 5 (depends on 4)

The integrated circuit of claim 4, wherein:
the table data is configurable to indicate respective mask data associated with respective entries; and
the respective mask data is to be applied to one or more portions of the incoming packet data.

### Claim 6 (depends on 4)

The integrated circuit of claim 4, wherein:
the one or more packet processing rules are configurable to indicate:
at least one packet drop;
at least one next packet hop determination; and/or
at least one forwarding port determination.

### Claim 7

Machine-readable instructions to be executed by an integrated circuit, the integrated circuit for use in performing packet forwarding-related operations related to incoming packet data, the integrated circuit being configurable to use machine-readable ternary content addressable memory (TCAM) to store, at least in part, table data for use in association with the packet forwarding-related operations, the integrated circuit comprising processing hardware, the instructions, when executed by the integrated circuit, resulting in the integrated circuit being configured for performance of certain operations comprising:
storing, at least in part, in the machine-readable TCAM, the table data; and
executing, by the processing hardware, compiler-produced program instructions, the compiler-produced program instructions, when executed by the processing hardware resulting in the integrated circuit being configured to perform the packet forwarding-related operations, the packet forwarding-related operations being configurable to comprise:
performing parallel table lookup operations to determine multiple entries in the table data that match, at least in part, at least one portion of the incoming packet data;
selecting, based upon relative priorities associated with the multiple entries, one of the multiple entries that corresponds to a highest one of the relative priorities; and
based upon the one of the multiple entries, determining at least one action to be executed in relation to the incoming packet data;
wherein:
the table data is configurable to comprise multiple table data partitions;
at least one of the multiple table data partitions is configurable to indicate, at least in part, the relative priorities in association with table indices that are associated with the at least one portion of the incoming packet data;
at least one other of the multiple table data partitions is configurable to comprise the multiple entries; and
the table data is configurable to indicate one or more packet processing rules that comprise the at least one action.

### Claim 8 (depends on 7)

The machine-readable instructions of claim 7, wherein:
at least one additional of the multiple table data partitions is configurable to indicate respective mask data associated with respective entries; and
the respective mask data is to be applied to certain portions of the incoming packet data.

### Claim 9 (depends on 7)

The machine-readable instructions of claim 7, wherein:
another integrated circuit comprises the machine-readable TCAM.

### Claim 10

Machine-readable instructions to be executed by an integrated circuit, the integrated circuit for use in performing packet forwarding-related operations related to incoming packet data, the integrated circuit being configurable to use machine-readable ternary content addressable memory (TCAM) to store, at least in part, table data for use in association with the packet forwarding-related operations, the integrated circuit comprising processing hardware, the instructions, when executed by the integrated circuit, resulting in the integrated circuit being configured for performance of certain operations comprising:
storing, at least in part, in the machine-readable TCAM, the table data; and
executing, by the processing hardware, compiler-produced program instructions, the compiler-produced program instructions, when executed by the processing hardware resulting in the integrated circuit being configured to perform the packet forwarding-related operations, the packet forwarding-related operations being configurable to comprise:
performing ternary memory table lookup to determine multiple entries in the table data that match, at least in part, at least one portion of the incoming packet data;
selecting, based upon relative priorities associated with the multiple entries, one of the multiple entries that corresponds to a highest one of the relative priorities; and
based upon the one of the multiple entries, determining at least one action to be executed in relation to the incoming packet data;
wherein:
the table data is configurable to comprise multiple portions;
at least one of the multiple portions of the table data is configurable to indicate, at least in part, relative priority data in association with table key data, the relative priority data indicating the relative priorities;
at least one other of the multiple portions of the table data is configurable to comprise the multiple entries; and
the table data is configurable to indicate one or more packet processing rules that comprise the at least one action.

### Claim 11 (depends on 10)

The machine-readable instructions of claim 10, wherein:
the table data is configurable to indicate respective mask data associated with respective entries; and
the respective mask data is to be applied to one or more portions of the incoming packet data.

### Claim 12 (depends on 10)

The machine-readable instructions of claim 10, wherein:
the one or more packet processing rules are configurable to indicate:
at least one packet drop;
at least one next packet hop determination; and/or
at least one forwarding port determination.

### Claim 13

A network switch for performing packet forwarding-related operations related to a network and incoming packet data to be received via the network, the network switch being configurable to use machine-readable ternary content addressable memory (TCAM) in association with the packet forwarding-related operations, the network switch comprising:
ports to be coupled to the network; and
an integrated circuit coupled to the ports, the integrated circuit comprising:
processing hardware to execute compiler-produced program instructions, the compiler-produced program instructions, when executed by the processing hardware resulting in the integrated circuit being configured to perform the packet forwarding-related operations, the packet forwarding-related operations being configurable to comprise:
performing parallel table lookup operations to determine multiple entries in the table data that match, at least in part, at least one portion of the incoming packet data;
selecting, based upon relative priorities associated with the multiple entries, one of the multiple entries that corresponds to a highest one of the relative priorities; and
based upon the one of the multiple entries, determining at least one action to be executed in relation to the incoming packet data;
wherein:
the table data is configurable to comprise multiple table data partitions;
at least one of the multiple table data partitions is configurable to indicate, at least in part, the relative priorities in association with table indices that are associated with the at least one portion of the incoming packet data;
at least one other of the multiple table data partitions is configurable to comprise the multiple entries; and
the table data is configurable to indicate one or more packet processing rules that comprise the at least one action.

### Claim 14 (depends on 13)

The network switch of claim 13, wherein:
at least one additional of the multiple table data partitions is configurable to indicate respective mask data associated with respective entries; and
the respective mask data is to be applied to certain portions of the incoming packet data.

### Claim 15 (depends on 13)

The network switch of claim 13, wherein:
another integrated circuit comprises the machine-readable TCAM.