Hash functions for applications such as network address lookup

• US 7,990,973 B2
• Filed: 08/13/2008
• Issued: 08/02/2011
• Est. Priority Date: 08/13/2008
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Hao, Fang, Song, Haoyu, Kodialam, Muralidharan S.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Weidner; Timothy J
• Application Number:
  US12/190,684
• Publication Number:
  US 20100040067A1
• Time in Patent Office: 1,084 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/7459 using Bloom filters
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

In one embodiment, IP lookup into a routing table having prefixes of different prefix lengths is performed by hashing a candidate prefix value to generate a plurality of hash values, where m seed hash values are generated by applying m seed hash functions and one or more additional hash values are generated by combining two or more of the seed hash values in different ways, e.g., using a bit-wise XOR function. The hash values are used to perform membership probes into a Bloom filter programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter.

Claims

1. A processor-implemented method for generating a plurality of hash values for an input key, the method comprising:

(a) hashing the input key using a set of seed hash functions to generate a set of seed hash values for the input key, wherein the input key is a candidate prefix value for a given network address;

(b) combining two or more of the seed hash values one or more different ways to generate one or more additional hash values for the input key; and

(c) using the seed hash values and one or more additional hash values to perform membership probes into a Bloom filter programmed with prefix values of a routing table having a plurality of different prefix lengths.

2. The method of claim 1, wherein the Bloom filter is programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter.

3. The method of claim 1, wherein the method is implemented in hardware.

4. The method of claim 1, wherein the method is implemented in software.

5. The method of claim 1, wherein:

the set of seed hash functions comprises m seed hash functions;

step (a) generates m seed hash values; and

step (b) generates no more than 2^m−

m−

1 additional hash values.

6. The method of claim 1, wherein:

step (b) comprises applying a bit-wise XOR function to the two or more seed hash values to generate each additional hash value;

the Bloom filter is programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter;

the set of seed hash functions comprises m seed hash functions;

step (a) generates m seed hash values; and

step (b) generates no more than 2^m−

m−

1 additional hash values.

7. An apparatus for generating a plurality of hash values for an input key, the apparatus comprising:

two or more seed hash function elements adapted to hash the input key using a set of seed hash functions to generate a set of seed hash values for the input key, wherein the input key is a candidate prefix value for a given network address;

one or more seed hash value combiners adapted to combine two or more of the seed hash values one or more different ways to generate one or more additional hash values for the input key; and

apparatus for using the seed hash values and one or more additional hash values to perform membership probes into a Bloom filter programmed with prefix values of a routing table having a plurality of different prefix lengths.

8. The apparatus of claim 7, wherein the Bloom filter is programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter.

9. The apparatus of claim 7, wherein the apparatus is implemented in hardware.

10. The apparatus of claim 7, wherein the apparatus is implemented with use of software.

11. The apparatus of claim 7, wherein:

the set of seed hash functions comprises m seed hash functions;

the two or more seed hash function elements are adapted to generate m seed hash values; and

the one or more seed hash value combiners are adapted to generate no more than 2^m−

m−

1 additional hash values.

12. The apparatus of claim 7, wherein:

each seed hash value combiner is adapted to apply a bit-wise XOR function to the two or more seed hash values to generate a corresponding additional hash value;

the Bloom filter is programmed with the prefixes corresponding to all of the different prefix lengths in the routing table without having to expand any of the prefixes programmed into the Bloom filter;

the set of seed hash functions comprises m seed hash functions;

the two or more seed hash function elements are adapted to generate m seed hash values; and

the one or more seed hash value combiners are adapted to generate no more than 2^m−

m−

1 additional hash values.