Invention Grant
- Patent Title: Algorithmic TCAM based ternary lookup
-
Application No.: US15094914Application Date: 2016-04-08
-
Publication No.: US10318587B1Publication Date: 2019-06-11
- Inventor: Patrick Bosshart , Michael G. Ferrara , Jay E. S. Peterson
- Applicant: Barefoot Networks, Inc.
- Applicant Address: US CA Santa Clara
- Assignee: BAREFOOT NETWORKS, INC.
- Current Assignee: BAREFOOT NETWORKS, INC.
- Current Assignee Address: US CA Santa Clara
- Agency: Adeli LLP
- Main IPC: G11C7/10
- IPC: G11C7/10 ; G06F16/903 ; G11C11/406 ; G06F16/901 ; G06F16/00 ; G11C11/40 ; G06F16/90

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.
Public/Granted literature
- US20190179971A1 ALGORITHMIC TCAM BASED TERNARY LOOKUP Public/Granted day:2019-06-13
Information query