Longest prefix match lookup using hash function
US7089240B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 2004 |
| Grant date | Aug 8, 2006 |
| Priority date | — |
| Expiry date | Jul 8, 2024 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and apparatus are used for finding the longest prefix match in a variable length prefix search when searching a direct table within a routing table structure of a network processor. The search through the routing table structure is expedited by hashing a first segment of an internet protocol address with a virtual private network number followed by concatenating the unhashed bits of the IP address to the result of the hash operation to form an input key. Patterns are compared a bit at a time until an exact match or the best match is found. The search is conducted in a search tree that provides that the matching results will be the best possible match.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.