Method and apparatus for allocating and using range identifiers as input values to content-addressable memories
US6775737B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 9, 2001 |
| Grant date | Aug 10, 2004 |
| Priority date | — |
| Expiry date | Oct 4, 2022 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L69/22
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Methods and apparatus are disclosed for allocating and using range identifiers as input values to associative memories, especially binary content-addressable memories (CAMs) and ternary content-addressable memories (TCAMs). In one implementation, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result. One implementation uses a trie representation of a range tree of the intervals to derive the unique identifiers. Moreover, one implementation evaluates and selects among various possible trie representations, especially to determine identifiers such that a TCAM prefix may match multiple intervals corresponding to a desired range.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.