MAC address table search unit
US5914938A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Nov 19, 1996 |
| Grant date | Jun 22, 1999 |
| Priority date | — |
| Expiry date | Nov 19, 2016 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L61/00
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A search key having a first length is presented to a universal hashing process. The search key is hashed using a universal hash function to generate a bucket ID having a second length, smaller than the first length. The bucket ID is used to address a table stored in a computer readable medium and a pointer is retrieved from an associated storage location. The pointer is used to index a hash bucket containing one or more entries, each of which can be compared to the search key to determine whether any of the entries match the search key. For the case where the method is used in a Ethernet switch, the search key may comprise a virtual LAN identification and media access control address. The table is made up of number of hash buckets, each of which may have one or more entries. New entries are stored in one of the hash buckets according to the universal hash function so long as no overflows of any hash bucket would be created. If a bucket overflow would result from the storing operation, a new hash function is automatically selected so that no hash bucket overflows will result when the new entry is stored in a new table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.