NETWORK ADDRESS LOOKUP BASED ON BLOOM FILTERS

• US 20100040066A1
• Filed: 08/13/2008
• Published: 02/18/2010
• Est. Priority Date: 08/13/2008
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hao, Fang, Lakshman, Tirunell V., Song, Haoyu, Kodialam, Muralidharan S.
• Granted Patent: US 8,018,940 B2
• Time in Patent Office: Days
• US Class Current: 370/395.310
• 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 (e.g., 301) 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 (e.g., 352).

2. The invention of claim 1, wherein:

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

the Bloom filter is programmed by hashing each prefix in the routing table into k hash values (e.g., H_i,j) corresponding to k hash functions.

3. The invention of claim 2, wherein (e.g., FIG. 4) step (b) comprises sequentially hashing each of the g candidate prefix values of the given network address into a set (e.g., 402) of k hash values for the Bloom filter.

4. The invention of claim 2, wherein (e.g., FIG. 5):

the Bloom filter is implemented using k Bloom sub-filters (e.g., 504);

each Bloom sub-filter is associated with a different set (e.g., 502) of g hash functions; and

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

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

6. The invention of claim 4, wherein:

each different Bloom sub-filter is associated with a different pre-match vector (e.g., 506); and

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

(b1) hashing (e.g., 502) 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 (e.g., 508) a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector (e.g., 304) for the Bloom filter.

7. The invention of claim 4, wherein each Bloom sub-filter is implemented using t r-port memory devices (e.g., 604), wherein t'"'"'r≧

g.

8. The invention of claim 7, wherein, for each Bloom sub-filter, step (b) comprises:

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

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

9. The invention of claim 8, 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.

10. The invention of claim 1, further comprising:

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

11. The invention of claim 10, 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.

12. The invention of claim 10, 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.

13. The invention of claim 10, wherein the prefix table is hashed using two or more hash functions per candidate prefix value.

14. The invention 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.

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

16. The invention of claim 1, 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 (e.g., H_i,j) corresponding to k hash functions;

the Bloom filter is implemented using k Bloom sub-filters (e.g., 504);

each Bloom sub-filter is associated with a different set (e.g., 502) of g hash functions;

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

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 (e.g., 506);

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

(b1) hashing (e.g., 502) 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 (e.g., 508) a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector (e.g., 304) for the Bloom filter.

each Bloom sub-filter is implemented using t r-port memory devices (e.g., 604), wherein t×

r≧

g;

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

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

(b1ii) collecting (e.g., 606) 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.

17. 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 (e.g., 301) 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 (e.g., 306) adapted to perform membership probes into the Bloom filter using candidate prefix values for a given network address (e.g., 352).

18. The invention of claim 17, wherein the Bloom filter and the routing processor are implemented on a single chip.

19. The invention of claim 17, wherein:

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

the Bloom filter is programmed by hashing each prefix in the routing table into k hash values (e.g., H_i,j) corresponding to k hash functions.

20. The invention of claim 19, wherein (e.g., FIG. 5):

the Bloom filter is implemented using k Bloom sub-filters (e.g., 504);

each Bloom sub-filter is associated with a different set (e.g., 502) of g hash functions; and

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

21. The invention of claim 20, 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.

22. The invention of claim 20, wherein:

each different Bloom sub-filter is associated with a different pre-match vector (e.g., 506); and

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

(1) hash (e.g., 502) 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 (e.g., 508) a logical AND function to corresponding bits in the k pre-match vectors to generate a corresponding bit in a match vector (e.g., 304) for the Bloom filter.

23. The invention of claim 20, wherein each Bloom sub-filter is implemented using:

t r-port memory devices (e.g., 604), wherein t×

r≧

g;

a port scheduler (e.g., 602) adapted to process g table lookup requests into the t r-port memory devices; and

a collector (e.g., 606) adapted to collect processing results for the g table lookup requests to generate corresponding bits of a pre-match vector (e.g., 506)

24. The invention of claim 23, 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.

25. The invention of claim 17, 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.

26. The invention of claim 25, 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.

27. The invention of claim 25, 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.

28. The invention of claim 17, 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.

29. The invention of claim 28, 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.

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

means for providing a Bloom filter (e.g., 301) 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

means for performing membership probes into the Bloom filter using candidate prefix values for a given network address (e.g., 352).