Longest prefix matching for network address lookups using bloom filters

Abstract

Methods and systems for 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.

1 . A method for performing a network address lookup, said method comprising the steps of:
 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; and   performing membership probes to said Bloom filters by using predetermined prefixes of a network address.   
   
   
       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 0 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 , further comprising:
 utilizing a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths.   
   
   
       15 . The method according to  claim 14 , wherein for every prefix length represented in said direct lookup array, a number of worst case hash probes is reduced by one. 
   
   
       16 . 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.   
   
   
       17 . The method according to  claim 16 , further comprising:
 calculating a primary hash value over said one of said prefixes.   
   
   
       18 . The method according to  claim 17 , 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.   
   
   
       19 . The method according to  claim 18 , 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.   
   
   
       20 . The method according to  claim 18 , 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. 
   
   
       21 . 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; and   means for performing membership queries to said Bloom filters by using predetermined prefixes of an network address.   
   
   
       22 . The system according to  claim 21 , further comprising a hash table operable to store said prefixes. 
   
   
       23 . The system according to  claim 22  wherein said hash table comprises a single hash table containing all of the prefixes. 
   
   
       24 . The system according to  claim 22 , wherein said hash table comprises a plurality of hash tables, each containing prefixes of a particular length. 
   
   
       25 . The system according to  claim 21 , wherein the Bloom filters comprise a bit vector of a plurality of bits. 
   
   
       26 . The system according to  claim 25  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. 
   
   
       27 . The method according to  claim 22 , 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. 
   
   
       28 . The system according to  claim 21 , further comprising:
 a direct lookup array for initial prefix lengths and asymmetric Bloom filters for the rest of the prefix lengths.   
   
   
       29 . The system according to  claim 28 , wherein for every prefix length represented in said direct lookup array, a number of worst case hash probes is reduced by one. 
   
   
       30 . The system according to  claim 28 , 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.   
   
   
       31 . The system according to  claim 21 , wherein multiple mini-Bloom filters are proportionally allocated according to a prefix distribution. 
   
   
       32 . The system according to  claim 31 , wherein on-chip resources are allocated to individual Bloom filters in units of mini-Bloom filters instead of bits. 
   
   
       33 . The system according to  claim 32 , 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.   
   
   
       34 . The system according to  claim 33 , further comprising:
 means for calculating a primary hash value over said one of said prefixes.   
   
   
       35 . The system according to  claim 34 , 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.   
   
   
       36 . The system according to  claim 35 , 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.