Network address lookup based on bloom filters

• US 8,018,940 B2
• Filed: 08/13/2008
• Issued: 09/13/2011
• Est. Priority Date: 08/13/2008
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Hao, Fang, Lakshman, Tirunell V., Song, Haoyu, Kodialam, Muralidharan S.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Weidner; Timothy J
• Application Number:
  US12/190,633
• Publication Number:
  US 20100040066A1
• Time in Patent Office: 1,126 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/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• 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 using a Bloom filter that was programmed with the prefixes corresponding to all of the different prefix lengths without having to expand any of the prefixes programmed into the Bloom filter. Membership probes are performed into the Bloom filter using candidate prefix values of a given network address. The Bloom filter can be implemented in a distributed manner using Bloom sub-filters, where each Bloom sub-filter is hashed based on a set of hash functions, where each different hash function in the set corresponds to a different prefix length in the routing table. Each Bloom sub-filter can in turn be implemented using a plurality of practically realizable multi-port memory devices controlled by a port scheduler. False-positive matches can be detected and next-hop information for true-positive matches retrieved using an off-chip, hash-based prefix table.

Claims

1. A method for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the method comprising:

(a) providing 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; and

(b) performing membership probes into the Bloom filter using candidate prefix values for a given network address, wherein;

there are g different prefix lengths in the routing table and g candidate prefix values for each given network address;

the Bloom filter is programmed by hashing each prefix in the routing table into k hash values corresponding to k hash functions

the Bloom filter is implemented using k Bloom sub-filters;

each Bloom sub-filter is associated with a different set of g hash functions; and

each hash value in a set is associated with a different prefix length.

2. The method of claim 1, wherein step (b) comprises hashing each of the g candidate prefix values of the given network address into a set of k hash values for the Bloom filter.

3. The method of claim 1, wherein the g candidate prefix values of the given network address are hashed into the k Bloom sub-filters in parallel.

4. The method of claim 1, wherein:

each different Bloom sub-filter is associated with a different pre-match vector; and

step (b) comprises, for each candidate prefix value;

(b1) hashing the candidate prefix value into a single hash value corresponding to a single hash function in each set to generate a corresponding bit value in a corresponding one of the k pre-match vectors; and

(b2) applying a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector for the Bloom filter.

5. The method of claim 1, wherein each Bloom sub-filter is implemented using t r-port memory devices, wherein t×

r≧

g.

6. The method of claim 5, wherein, for each Bloom sub-filter, step (b) comprises:

(b1) processing g table lookup requests into the t r-port memory devices; and

(b2) collecting processing results for the g table lookup requests to generate corresponding bits of a pre-match vector.

7. The method of claim 6, wherein, if there are more than r table lookup requests for a single r-port memory device for the given network address, then:

step (b1) comprises performing r table lookups corresponding to the r longest prefixes of the more-than-r table lookup requests and skipping the other table lookup requests; and

step (b2) comprises treating the other table lookup requests as if they returned positive matches when generating the corresponding bits of the pre-match vector.

8. The method of claim 1, further comprising:

(c) accessing a prefix table based on one or more matching candidate prefix values identified in step (b).

9. The method of claim 8, wherein, if at least a specified number of longest, matching candidate prefix values identified in step (b) are determined to be false-positive matches in step (c), then step (c) further comprises adding the longest, false-positive matching candidate prefix value to the prefix table along with true next-hop information for the given network address.

10. The method of claim 8, wherein at least one bucket in the prefix table identifies two or more different prefix values, such that the two or more different prefix values are retrieved in one prefix table lookup.

11. The method of claim 8, wherein the prefix table is hashed using two or more hash functions per candidate prefix value.

12. The method of claim 1, wherein step (b) comprises:

(b1) hashing each candidate prefix value using a set of seed hash functions to generate a set of seed hash values for the candidate prefix value; and

(b2) combining two or more of the seed hash values one or more different ways to generate one or more additional hash values for the candidate prefix value.

13. The method of claim 12, wherein step (b2) comprises applying a bit-wise XOR function to the two or more seed hash values to generate each additional hash value.

14. The method of claim 1, wherein:

the g candidate prefix values of the given network address are hashed into the k Bloom sub-filters in parallel;

each different Bloom sub-filter is associated with a different pre-match vector;

step (b) comprises, for each candidate prefix value;

(b1) hashing the candidate prefix value into a single hash value corresponding to a single hash function in each set to generate a corresponding bit value in a corresponding one of the k pre-match vectors, wherein;

the candidate prefix value is hashed using a set of seed hash functions to generate a set of seed hash values for the candidate prefix value; and

two or more of the seed hash values are combined by applying a bit-wise XOR function in one or more different ways to generate one or more additional hash values for the candidate prefix value; and

(b2) applying a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector for the Bloom filter;

each Bloom sub-filter is implemented using t r-port memory devices, wherein t×

r≧

g;

for each Bloom sub-filter, step (b1) comprises;

(b1i) processing g table lookup requests into the t r-port memory devices; and

(b1ii) collecting processing results for the g table lookup requests to generate corresponding bits of the pre-match vector;

if there are more than r table lookup requests for a single r-port memory device for the given network address, then;

step (b1i) comprises performing r table lookups corresponding to the r longest prefixes of the more-than-r table lookup requests and skipping the other table lookup requests; and

step (b1ii) comprises treating the other table lookup requests as if they returned positive matches when generating the corresponding bits of the pre-match vector;

further comprising (c) accessing a prefix table based on one or more matching candidate prefix values identified in step (b);

if at least a specified number of longest, matching candidate prefix values identified in step (b) are determined to be false-positive matches in step (c), then step (c) further comprises adding the longest, false-positive matching candidate prefix value to the prefix table along with true next-hop information for the given network address;

at least one bucket in the prefix table identifies two or more different prefix values, such that the two or more different prefix values are retrieved in one prefix table lookup; and

the prefix table is hashed using two or more hash functions per candidate prefix value.

15. An apparatus for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the apparatus comprising:

a Bloom filter adapted to be 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; and

a routing processor adapted to perform membership probes into the Bloom filter using candidate prefix values for a given network address, wherein;

there are g different prefix lengths in the routing table and g candidate prefix values for each given network address;

the Bloom filter is programmed by hashing each prefix in the routing table into k hash values corresponding to k hash functions;

the Bloom filter is implemented using k Bloom sub-filters;

each Bloom sub-filter is associated with a different set of g hash functions; and

each hash value in a set is associated with a different prefix length.

16. The apparatus of claim 15, wherein the Bloom filter and the routing processor are implemented on a single chip.

17. The apparatus of claim 15, wherein the apparatus is adapted to hash the g candidate prefix values of the given network address into the k Bloom sub-filters in parallel.

18. The apparatus of claim 15, wherein:

each different Bloom sub-filter is associated with a different pre-match vector; and

for each candidate prefix value, the apparatus is adapted to;

(1) hash the candidate prefix value into a single hash value corresponding to a single hash function in each set to generate a corresponding bit value in a corresponding one of the k pre-match vectors; and

(2) apply a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector for the Bloom filter.

19. The apparatus of claim 15, wherein each Bloom sub-filter is implemented using:

t r-port memory devices, wherein t×

r≧

g;

a port scheduler adapted to process g table lookup requests into the t r-port memory devices; and

a collector adapted to collect processing results for the g table lookup requests to generate corresponding bits of a pre-match vector.

20. The apparatus of claim 19, wherein, if there are more than r table lookup requests for a single r-port memory device for the given network address, then:

the port scheduler performs r table lookups corresponding to the r longest prefixes of the more-than-r table lookup requests and skips the other table lookup requests; and

the collector treats the other table lookup requests as if they returned positive matches when generating the corresponding bits of the pre-match vector.

21. The apparatus of claim 15, wherein the apparatus is operably coupled to a prefix table that is accessed by the apparatus based on one or more matching candidate prefix values identified during the membership probes.

22. The apparatus of claim 21, wherein, if at least a specified number of longest, matching candidate prefix values are determined to be false-positive matches, then the apparatus adds the longest, false-positive matching candidate prefix value to the prefix table along with true next-hop information for the given network address.

23. The apparatus of claim 21, wherein:

at least one bucket in the prefix table identifies two or more different prefix values, such that the two or more different prefix values are retrieved in one prefix table lookup by the apparatus; and

the apparatus is adapted to hash into the prefix table using two or more hash functions per candidate prefix value.

24. The apparatus of claim 15, wherein the apparatus is adapted to:

(1) hash each candidate prefix value using a set of seed hash functions to generate a set of seed hash values for the candidate prefix value; and

(2) combine two or more of the seed hash values one or more different ways to generate one or more additional hash values for the candidate prefix value.

25. The apparatus of claim 24, wherein the apparatus is adapted to generate each additional hash value by applying a bit-wise XOR function to the two or more seed hash values.

26. A method for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the method comprising:

(a) providing 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;

(b) performing membership probes into the Bloom filter using candidate prefix values for a given network address;

(c) accessing a prefix table based on one or more matching candidate prefix values identified in step (b), wherein, if at least a specified number of longest, matching candidate prefix values identified in step (b) are determined to be false-positive matches in step (c), then step (c) further comprises adding the longest, false-positive matching candidate prefix value to the prefix table along with true next-hop information for the given network address.

27. A method for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the method comprising:

(a) providing 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;

(b) performing membership probes into the Bloom filter using candidate prefix values for a given network address;

(c) accessing a prefix table based on one or more matching candidate prefix values identified in step (b), wherein at least one bucket in the prefix table identifies two or more different prefix values, such that the two or more different prefix values are retrieved in one prefix table lookup.

28. A method for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the method comprising:

(a) providing 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;

(b) performing membership probes into the Bloom filter using candidate prefix values for a given network address; and

(c) accessing a prefix table based on one or more matching candidate prefix values identified in step (b), wherein the prefix table is hashed using two or more hash functions per candidate prefix value.

29. A method for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the method comprising:

(a) providing 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; and

(b) performing membership probes into the Bloom filter using candidate prefix values for a given network address, wherein step (b) comprises;

(b1) hashing each candidate prefix value using a set of seed hash functions to generate a set of seed hash values for the candidate prefix value; and

(b2) combining two or more of the seed hash values one or more different ways to generate one or more additional hash values for the candidate prefix value.

30. The method of claim 29, wherein step (b2) comprises applying a bit-wise XOR function to the two or more seed hash values to generate each additional hash value.

31. An apparatus for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the apparatus comprising:

a Bloom filter adapted to be 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; and

a routing processor adapted to perform membership probes into the Bloom filter using candidate prefix values for a given network address, wherein;

the apparatus is operably coupled to a prefix table that is accessed by the apparatus based on one or more matching candidate prefix values identified during the membership probes; and

if at least a specified number of longest, matching candidate prefix values are determined to be false-positive matches, then the apparatus adds the longest, false-positive matching candidate prefix value to the prefix table along with true next-hop information for the given network address.

32. An apparatus for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the apparatus comprising:

a Bloom filter adapted to be 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; and

a routing processor adapted to perform membership probes into the Bloom filter using candidate prefix values for a given network address, wherein;

the apparatus is operably coupled to a prefix table that is accessed by the apparatus based on one or more matching candidate prefix values identified during the membership probes;

at least one bucket in the prefix table identifies two or more different prefix values, such that the two or more different prefix values are retrieved in one prefix table lookup by the apparatus; and

the apparatus is adapted to hash into the prefix table using two or more hash functions per candidate prefix value.

33. An apparatus for performing a network address lookup for a routing table having prefixes of a plurality of different prefix lengths, the apparatus comprising:

a Bloom filter adapted to be 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; and

a routing processor adapted to perform membership probes into the Bloom filter using candidate prefix values for a given network address, wherein the apparatus is adapted to;

(1) hash each candidate prefix value using a set of seed hash functions to generate a set of seed hash values for the candidate prefix value; and

(2) combine two or more of the seed hash values one or more different ways to generate one or more additional hash values for the candidate prefix value.

34. The apparatus of claim 33, wherein the apparatus is adapted to generate each additional hash value by applying a bit-wise XOR function to the two or more seed hash values.