Method for longest prefix matching in a content addressable memory
US6237061A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jan 5, 1999 |
| Grant date | May 22, 2001 |
| Priority date | — |
| Expiry date | Jan 5, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/90339
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A ternary content addressable memory is employed to perform a longest prefix match search. Each CAM cell within the ternary CAM has an associated mask cell so that the CAM cells may be individually masked so as to effectively store either a logic 0, a logic 1, or a don't care for compare operations. For example, Classless Inter-Domain Routing (CIDR) addresses are pre-sorted and loaded into the ternary CAM such that the CAM entry having the longest prefix is located at the lowest numerical address or index of the ternary CAM, and the CAM entry with the shortest prefix is located at the highest numerical address or index. The prefix portions of the CIDR addresses are used to set the mask cells associated with each CAM entry such that during compare operations, only the unmasked prefix portion of each CAM entry is compared to an incoming destination address stored as the CAM search key. Since each CAM entry is masked according to an associated prefix value, the ternary CAM requires only one search operation to locate the CAM entry having the longest matching prefix.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.