Partitioning and filtering a search space of particular use for determining a longest prefix match thereon
US7403526B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | May 17, 2004 |
| Grant date | Jul 22, 2008 |
| Priority date | — |
| Expiry date | Jun 11, 2026 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Disclosed are, inter alia, methods, apparatus, data structures, computer readable media, mechanisms, and means for partitioning and filtering a search space of particular use for determining a longest prefix match thereon, such as for routing packets. One implementation uses one or more filtering mechanisms to filter portions of a lookup word against a first set of lookup values, such as, but not limited to the value of any corresponding portion of any entry in the search space. A set of possible matching prefixes defined by consecutive matching portions of the lookup word from the highest-order position are determined, and lookup operations are typically performed in parallel on each of these possible matching prefixes to generate a set of matching results (if any), which is typically used to identify the longest matching prefix.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.