High performance hash-based lookup for packet processing in a communication network
US9009165B2 · kind B2 · utility
5Cited by
6References
18Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Jan 10, 2013 |
| Grant date | Apr 14, 2015 |
| Priority date | — |
| Expiry date | May 19, 2033 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L47/2441
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The present invention relates to methods and apparatus for performing a lookup on a hash table stored in external memory. An index table stored in local memory is used to perform an enhanced lookup on the hash table stored in external memory. The index table stores signature patterns that are derived from the hash keys stored in the hash entries. Using the stored signature patterns, the packet processing node predicts which hash key is likely to store the desired data. The prediction may yield a false positive, but will never yield a false negative. Thus, the hash table is accessed only once during a data lookup.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.