Longest prefix matching using bloom filters

By Sarang Dharmapurikar, Praveen Krishnamurthy, David E. Taylor. IEEE/ACM Transactions on Networking, 2003

344 citations recorded by the source corpus.

We introduce the first algorithm that we are aware of to employ Bloom filters for longest prefix matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address prefix membership in sets of prefixes sorted by prefix length. We show that use of this algorithm for Internet Protocol (IP) routing lookups results in a search engine providing better performance and scalability than TCAM-based approaches. The key feature of our technique is that the performance, as determined by the number of dependent memory accesses per lookup, can be 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. Our approach is equally attractive for Internet Protocol Version 6 (IPv6) which uses 128-bit destination addresses, four times longer than IPv4. We present a basic version of our approach along with optimizations leveraging previous advances in LPM algorithms. We also report results of performance simulations of our system using snapshots of IPv4 BGP tables and extend the results to IPv6. Using less than 2 Mb of embedded RAM and a commodity SRAM device, our technique achieves average performance of one hash probe per lookup and a worst case of two hash probes and one array access per lookup.

Subfields: Computer Networks and Communications, Hardware and Architecture, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/95e833e80b25fe7765a631a19e2e955e126f42cf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

In Materials Chemistry

Citations in the corpus

Non-commercial Research and Educational Use including without Limitation Use in Instruction at Your Institution, Sending It to Specific Colleagues That You Know, and Providing a Copy to Your Institution's Administrator. All Other Uses, Reproduction and Distribution, including without Limitation Comm (2005, neutral): “We omit effects of the anisotropy in J lm which are to modify slightly the observed values of D lm and which are negligible for proton–proton couplings.”
Cuckoo Filter: Practically Better Than Bloom (2014, methodology): “Counting Bloom filters [12] have been suggested for multiple applications [24, 25, 9], but they generally use 3–4× space to retain the same false positive rate as a space-optimized Bloom filter.”
Theory and Practice of Bloom Filters for Distributed Systems (2012, methodology): “Performance analysis indicates that average performance approaches one hash probe pe lookup with less than 8 bits per prefix [79].”
A reality check for content centric networking (2011, methodology): “LPM can be implemented either in hardware using a TCAM or in software using a multi-bit trie [13, 14] or Bloom filters [12].”
Named Data Networking (NDN) Project (2010, methodology): “This basic scheme has already been evaluated in the context of IP lookup for IPv4 and IPv6 [23], demonstrating that modern, cost-effective ASICs have resources sufﬁcient to maintain between 32 and 100 concurrent on-chip Bloom ﬁlters.”
An Improved Construction for Counting Bloom Filters (2006, methodology): “Counting Bloom filters have been explicitly used in several papers, including for example [7, 8, 9, 10, 12, 18, 19].”