Back to results
US 7,680,806 B2Granted
Reducing overflow of hash table entries
AssigneeCisco Technology, Inc.
InventorJianguo Qian
Life of this patent
Estimating the term…
Abstract
An apparatus and method for reducing overflow in a hash table lookup mechanism that moves entries from full or nearly full buckets in one hash table to less full buckets of another hash table. The number of bucket overflows caused by hashing input addresses can be reduced.
Claims8
A method comprising:
- hashing a new entry with a first hash function (FHF), implemented by hardware in a forwarding engine, to generate a first FHF index to a first hash table (FHT);
- hashing the new entry with a second hash function (SHF), implemented by hardware in the forwarding engine, to generate a first SHF index to a second hash table (SHT), with the first and second hash tables each having a plurality of buckets identified by an index and with each bucket including a plurality of cells for holding entries where the FHF and SHF are different and uncorrelated hash functions;
- accessing a first FHT bucket with the first FHF index utilizing logic in the forwarding engine;
- accessing a first SHT bucket with the first SHF index utilizing logic in the forwarding engine;
- hashing a first FHT entry from a first FHT cell in the first FHT bucket of the first hash table with the second hash function to index a second SHT bucket in the second hash table if the first FHT bucket of the first hash table and the first SHT bucket of the second hash table each hold J entries, where J is a positive integer;
- moving only the first FHT entry to the second SHT bucket of the second hash table, utilizing logic in the forwarding engine, if the number of entries held in the second SHT bucket is less than J;
- and
- storing the new entry in the first FHT cell of the first FHT bucket of the first hash table utilizing logic in the forwarding engine.
5 more elements
An apparatus comprising:
- a memory system holding a first hash table (FHT) and a second hash table (SHT), with the first and second hash tables having a plurality of buckets identified by an index and with each bucket including a plurality of cells for holding entries, and with the memory system also holding computer program code;
- hardware logic coupled to said memory system configured to access said first and second hash tables and configured to hash a new entry with a first hash function (FHF) to generate a first FHF index to the first hash table, hash the new entry with a second hash function (SHF) to generate a first SHF index to the second hash table where the FHF and SHF are different and uncorrelated hash functions, access a first FHT bucket with the first FHF index, access a first SHT bucket with the first SHF index, hash a first FHT entry from a first FHT cell in the first FHT bucket of the first hash table with the second hash function to index a second SHT bucket in the second hash table if the first FHT bucket of the first hash table and the first SHT bucket of the second hash table each hold J entries, where J is a positive integer, move only the first FHT entry to the second SHT bucket of the second hash table if the number of entries held in the second SHT bucket is less than J, and store the new entry in the first FHT cell of the first FHT bucket of the first hash table.
Dependencies are inferred from the claim text.