Exact match lookup in network switch devices
US9171030B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 9, 2013 |
| Grant date | Oct 27, 2015 |
| Priority date | — |
| Expiry date | Jan 9, 2033 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/7453
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In a method for populating a lookup table, a plurality of hash tables are provided. Each hash table is accessed by a respective hash function. A plurality of hashed values for a key are generated using the hash functions corresponding to the plurality of hash tables. The plurality of hashed values are used to determine whether the key can be inserted into one or more hash tables of the plurality of hash tables without colliding with keys previously stored at respective locations corresponding to the determined hashed values. When it is determined that the key can be inserted into multiple hash tables, it is then determined which one of the multiple hash tables is populated with the greatest number of keys. The hash table that is populated with the greatest number of keys is selected for insertion of the key, and the key is inserted into the selected hash table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.