Method and system for performing longest prefix matching for network address lookup using bloom filters

• US 7,602,785 B2
• Filed: 02/09/2005
• Issued: 10/13/2009
• Est. Priority Date: 02/09/2004
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Krishnamurthy, Praveen, Taylor, David Edward, Dharmapurikar, Sarang
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): Foud; Hicham B
• Application Number:
  US11/055,767
• Publication Number:
  US 20050195832A1
• Time in Patent Office: 1,707 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

The present invention relates to a method and system of performing parallel membership queries to Bloom filters for Longest Prefix Matching, where address prefix memberships are determined in sets of prefixes sorted by prefix length. Hash tables corresponding to each prefix length are probed from the longest to the shortest match in the vector, terminating when a match is found or all of the lengths are searched. The performance, as determined by the number of dependent memory accesses per lookup, is held constant for longer address lengths or additional unique address prefix lengths in the forwarding table given that memory resources scale linearly with the number of prefixes in the forwarding table. For less than 2 Mb of embedded RAM and a commodity SRAM, the present technique achieves average performance of one hash probe per lookup and a worst case of two hash probes and one array access per lookup.

Claims

1. A method of performing a network address lookup, comprising:

grouping forwarding prefixes from a routing table by prefix length;

associating each of a plurality of Bloom filters with a unique prefix length;

programming each of said plurality of Bloom filters with said prefixes corresponding to said associated unique prefix length;

performing membership probes to said Bloom filters by using predetermined prefixes of a network address; and

utilizing a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths;

wherein said direct lookup array comprises;

storing prefixes of not more than a predetermined number for a predetermined length, in a binary trie;

performing Controlled Prefix Expansion (CPE) in a CPE trie for a stride length equal to said predetermined number;

writing a next hop associated with each leaf at a level of said CPE trie corresponding to said predetermined number to an array slot addressed by bits that label a path from a root of said CPE trie to said leaf; and

searching said array using bits of said network address of said predetermined number to index into said array.

2. The method according to claim 1, further comprising:

storing said prefixes in a hash table.

3. The method according to claim 2, wherein said hash table comprises a single hash table containing all of the prefixes.

4. The method according to claim 2, wherein said hash table comprises a plurality of hash tables, each containing prefixes of a particular length.

5. The method according to claim 1 wherein the Bloom filters comprise a bit vector of a plurality of bits.

6. The method according to claim 5 further comprising providing a plurality of counting Bloom filters, each corresponding to one of the plurality of Bloom filters and each counting Bloom filter comprising a plurality of counters corresponding to the plurality of bits in its corresponding Bloom filter.

7. The method according to claim 1, wherein said Bloom filters are characterized by a false positive probability greater than zero and a false negative probability of zero.

8. The method according to claim 2, wherein the step of performing membership probes comprises the step of probing the hash table corresponding to said prefix lengths represented in a match vector in an order of longest prefix to shortest prefix.

9. The method according to claim 8, wherein probing of said hash tables is terminated when a match is found, and all of said prefix lengths represented in said match vector are searched.

10. The method according to claim 7, wherein the false positive probability is the same for all of said Bloom filters such that performance is independent of prefix distribution.

11. The method according to claim 5, further comprising:

providing asymmetric Bloom filters by proportionally allocating an amount of an embedded memory per Bloom filter based on said Bloom filter'"'"'s current share of a total number of prefixes while adjusting a number of hash functions of said Bloom filters to maintain a minimal false positive probability.

12. The method according to claim 9, wherein a number of hash probes to said hash table per lookup is held constant for network address lengths in said routing table that are greater than a predetermined length.

13. The method according to claim 9, wherein a number of dependent memory accesses per network lookup is held constant for additional unique prefix lengths in a forwarding table, provided that memory resources scale linearly with a number of prefixes in said routing table.

14. The method according to claim 1, wherein for every prefix length represented in said direct lookup array, a number of worst case hash probes is reduced by one.

15. The method according to claim 5, further comprising:

uniformly distributing prefixes of a predetermined length across a set of mini-Bloom filters; and

storing each of said prefixes in only one of said mini-Bloom filters.

16. The method according to claim 15, further comprising:

calculating a primary hash value over said one of said prefixes.

17. The method according to claim 16, further comprising:

storing said one of said prefixes in said one of said mini-Bloom filters pointed to by said primary hash value, within said set.

18. The method according to claim 17, further comprising:

dispatching a given network address to all sets of mini-Bloom filters for distinct prefix lengths on a tri-state bus in said probing process.

19. The method according to claim 17, wherein a same primary hash value is calculated on said network address to determine which of said mini-Bloom filters within a corresponding set should be probed with a given prefix.

20. A system for performing a network address lookup, comprising:

means for sorting forwarding prefixes from a routing table by prefix length;

means for associating each of a plurality of Bloom filters with a unique prefix length;

means for programming each of said plurality of Bloom filters with said prefixes corresponding to said associated unique prefix length;

means for performing membership queries to said Bloom filters by using predetermined prefixes of a network address; and

a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths;

wherein said direct lookup array comprises;

prefixes of not more than a predetermined number for a predetermined length, in a binary trie;

means for performing Controlled Prefix Expansion (CPE) in a CPE trie for a stride length equal to said predetermined number;

means for writing a next hop associated with each leaf at a level of said CPE trie corresponding to said predetermined number to an array slot addressed by bits labeling a path from a root of said CPE trie to said leaf; and

means for searching said array using bits of said network address of said predetermined number to index into said array.

21. The system according to claim 20, further comprising a hash table operable to store said prefixes.

22. The system according to claim 21 wherein said hash table comprises a single hash table containing all of the prefixes.

23. The system according to claim 21, wherein said hash table comprises a plurality of hash tables, each containing prefixes of a particular length.

24. The system according to claim 20, wherein the Bloom filters comprise a bit vector of a plurality of bits.

25. The system according to claim 24 further comprising a plurality of counting Bloom filters, each corresponding to one of the plurality of Bloom filters and each counting Bloom filter comprising a plurality of counters corresponding to the plurality of bits in its corresponding Bloom filter.

26. The system according to claim 21, wherein the means for performing membership queries comprises the means for probing the hash table corresponding to said prefix lengths represented in a match vector in an order of longest prefix to shortest prefix.

27. The system according to claim 20, wherein for every prefix length represented in said direct lookup array, a number of worst case hash probes is reduced by one.

28. The system according to claim 20, further comprising:

means for utilizing CPE to reduce a number of said Bloom filters such that a maximum of two hash probes and one array access per network lookup is achieved.

29. The system according to claim 20, wherein multiple mini-Bloom filters are proportionally allocated according to a prefix distribution.

30. The system according to claim 29, wherein on-chip resources are allocated to individual Bloom filters in units of mini-Bloom filters instead of bits.

31. The system according to claim 30, further comprising:

means for uniformly distributing prefixes of a predetermined length across a set of mini-Bloom filters; and

means for storing each of said prefixes in only one of said mini-Bloom filters.

32. The system according to claim 31, further comprising:

means for calculating a primary hash value over said one of said prefixes.

33. The system according to claim 32, further comprising:

means for storing said one of said prefixes in said one of said mini-Bloom filters pointed to by said primary hash value, within said set.

34. The system according to claim 33, further comprising:

means for dispatching a given network address to all sets of mini-Bloom filters for distinct prefix lengths on a tri-state bus in said probing process.