System and method for searching an associative memory utilizing first and second hash functions

• US 6,434,662 B1
• Filed: 11/02/1999
• Issued: 08/13/2002
• Est. Priority Date: 11/02/1999
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kedem, Gershon, Greene, Spencer
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/432,138
• Time in Patent Office: 1,015 Days
• Field of Search: 711/216, 711/220, 711/108, 711/212, 370/381, 370/382, 370/383, 370/389, 370/392, 370/393
• US Class Current: 711/108
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

A system and method form searching an associative memory using input key values and first and second hashing sections. Key values (Kn) can be hashed in the first hashing section (102) to generate first output values H₁(Kn) that access a first store (104). The first store or memory portion (104) can include “leaf” pointer entries (106-2) and “chunk pointer” entries (106-3). A leaf pointer entry (106-2) points at data associated with an applied key value. A chunk pointer entry (106-3) includes pointer data. If a chunk pointer entry (106-3) is accessed, the key value (Kn) is hashed in the second hashing section (108) to generate second output values H₂(Kn) that access a second store or memory portion (110). Second hashing section (108) hashes key values (Kn) according to selection data SEL stored in a chunk pointer entry (106-3). The system may also include a first memory portion accessed according to address values from the first hashing section and a second memory portion accessed according to address values that include outputs from the second hash section and a chunk base address value. The hash based associative system allows for the selection of a second hash function that has been precomputed at table build time to be perfect with respect to a small set of colliding key values, provides a deterministic search time independent of the number of table entries or width of the search key, and allows for pipelining to achieve highest search throughput.

Claims

1. A system, comprising:

a first hash function calculator that hashes a search key value into a first output value;

a first store accessed by the first output value;

a second hash function calculator that hashes the search key value according to hashing criteria stored in a first store entry accessed by the first output value, the search key value being hashed into a second output value; and

a second store accessed according to the second output value and at least one value stored in the first store entry.

2. The system of claim 1, wherein:

the first hash function calculator includes a Galois field multiplier.

3. The system of claim 1, wherein:

the first hash function calculator includes a Galois field divider.

4. The system of claim 1, wherein:

the first store includes leaf entries having data associated with the key value of the leaf entry.

5. The system of claim 1, wherein:

the first store includes pointer entries that include hashing criteria and a chunk base address.

6. The system of claim 1, wherein:

the hashing criteria includes a value that selects a particular hash function from a number of hash functions.

7. The system of claim 1, wherein:

the second hash function calculator includes a Galois field multiplier and the hashing criteria include a multiplicand for the Galois field multiplier.

8. The system of claim 1, wherein the second hash function calculator includes:

a Galois field multiplier having an output coupled to a plurality of modulo circuits; and

a multiplexer for selecting an output of one modulo circuit according to the hashing criteria.

9. The system of claim 1, wherein the search key value is from a domain of size D1, the first output value is from a range of size R1<

D1, and the second output value is from a range of size R2<

D1.

10. The system of claim 1, wherein the second output value comprises a collision-free hash value.

11. The system of claim 1, wherein:

the hashing criteria includes a value that determines a width of the second output value.

12. The system of claim 11, wherein:

the width of the second output value is from 2¹ to 2⁸.

13. An associative memory system for receiving an input key value, the system comprising:

a first memory accessed by a first hash function calculator;

a second memory accessed by a second hash function calculator;

the first hash function calculator receiving key values and providing first output values according to a first hash function;

the second hash function calculator generating a second output value based on key values and pointer data from the first memory, the pointer data corresponding to at least two key values and including parameter data and a chunk base address; and

a combiner combining the second output value with the chunk base address to generate a second memory address.

14. The system of claim 13, wherein:

the first memory includes a random access memory.

15. The system of claim 13, wherein:

the second memory includes a random access memory.

16. The system of claim 13, wherein:

the first hash function includes the operation

17. The system of claim 13, wherein:

the second hash function calculator includes the operation

18. The system of claim 13, wherein:

the first output values are first memory addresses.

19. The system of claim 13, wherein the second output value comprises a collision-free hash value.

20. A method of implementing an associative memory, comprising the steps of:

hashing an input key to generate a first output value;

accessing a first store entry according to the first output value;

if the accessed first store entry is not a chunk pointer entry, comparing against stored key data, and either reporting a null result, or retrieving and delivering data; and

if the accessed first store entry is a chunk pointer entry, retrieving chunk pointer data, hashing the input key according to the chunk pointer data to generate a second output value, and accessing a second store entry according to the second output value.

21. The method of claim 20, wherein:

the chunk pointer data includes parameter data and chunk base data; and

the step of hashing the input key according to the chunk pointer data includes;

hashing the input key with a hashing function determined by the parameter data to generate a hash output value; and

combining the hash output value and the chunk base data to generate the second output value.

22. The method of claim 20, wherein:

each chunk pointer designates the start of a chunk, each chunk including x entries; and

the step of hashing the input key according to the chunk pointer data includes hashing the input key into an output space x.

23. The method of claim 20, wherein:

each chunk pointer designates the start of a chunk, each chunk including x entries; and

the step of hashing the input key according to the chunk pointer data includes hashing the input key into an output space x.

24. The method of claim 20, wherein the second output value comprises a collision-free hash value.