Efficient matching of TCAM rules using hash tables in RAM
US10068034B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 7, 2016 |
| Grant date | Sep 4, 2018 |
| Priority date | — |
| Expiry date | Mar 15, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG11C7/1009
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method includes extracting classification keys from a collection of data items. A corpus of rules for matching to the classification keys is received, each rule including a respective set of unmasked bits having corresponding bit values, and at least some of the rules also include masked bits. Rule patterns are extracted from the corpus, each rule pattern defining a respective sequence of masked and unmasked bits to which one or more of the rules conforms. Multiple hash tables are defined in a RAM, each is used for searching for a rule that matches a given classification key. A match result of a given rule in a given hash table is also indicative of which of the other hash tables are to be used for subsequent searching. The data items are classified by matching the respective classification keys to the rules using one or more of the hash tables.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.