Hybrid longest prefix match and fixed match searches
US6792423B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 28, 2000 |
| Grant date | Sep 14, 2004 |
| Priority date | — |
| Expiry date | Mar 7, 2022 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and system for finding a longest matching prefix for an input keyword from among multiple prefixes. The prefixes are data strings of varying lengths wherein prefixes of length n or greater are probabilistically a longest prefix match. The method of the present invention begins by mapping the prefixes of length greater than or equal to n1, that is, in the interval [n1, L], into a first lookup system. Remaining prefixes of length less than n1 but greater than or equal to n2, that is, in the interval [n2, n1−1], are mapped into a second index utilizing a second hash function, wherein n2 is less than n1. Further lookup systems on prefixes having lengths in the intervals [n3, n2−1], [n4, n3−1], and so on, may also be utilized, as determined by optimization studies and the statistics of routing tables.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.