Exact match hash lookup databases in network switch devices
US9537771B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 28, 2013 |
| Grant date | Jan 3, 2017 |
| Priority date | — |
| Expiry date | Jun 3, 2034 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L49/3009
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In a method for populating a forwarding table, a first hash function is applied to a lookup key to generate a first hash value, a second hash function is applied to the lookup key to generate a second hash value, and a third hash function is applied to the lookup key to generate a third hash value. An offset is determined based on the first hash value and the second hash value. A location for inserting the lookup key is determined based on the offset and the third hash value. It is determined whether the lookup key can be inserted into the forwarding table at the determined location without colliding with a key previously stored at the determined location. When it is determined that the lookup key can be inserted, the lookup key and forwarding information associated with the lookup key are inserted at the determined location.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.