Binary search on trie levels with a bloom filter for longest prefix match
Authors:
- 1 July 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 38-43
Abstract
As one of efficient IP address lookup approaches, binary search on trie levels (BSL) provides high-speed search performance. It has been recently studied that the search performance of BSL algorithms can be further improved by adding a Bloom filter. The Bloom filter has a role identifying whether there is a node beforehand so that unnecessary trie accesses can be avoided. Leaf-pushing BSL (LBSL) algorithm performs the binary search on trie levels in a leaf-pushing trie. Since every prefix is located in leaves in this trie, it has an advantage that the search can be immediately finished when a prefix is encountered. However, because of prefix replication caused in the leaf-pushing process, the trie becomes dense, and hence adding a Bloom filter does not give much impact in improving the search performance. The motivation of this paper is to keep the sparseness of a trie to get search performance improvement by a Bloom filter in performing the binary search on trie levels in a leaf-pushing trie. The proposed algorithm defines control levels, and an internal prefix is pushed up to the closest control level. By limiting the levels of leaf-pushing, the prefix replication is significantly reduced, and hence a Bloom filter can provide an increased efficiency. Simulations using 5 actual routing sets with different sizes show that the search performance improvement by a Bloom filter is more significant than in the previous LBSL approach, and the average number of trie accesses is 2 to 3 in performing an IP address lookup in our proposed algorithm.Keywords
This publication has 8 references indexed in Scilit:
- Reducing False Positives of a Bloom Filter using Cross-Checking Bloom FiltersApplied Mathematics & Information Sciences, 2014
- On Adding Bloom Filters to Longest Prefix Matching AlgorithmsIEEE Transactions on Computers, 2012
- Tuple Pruning Using Bloom Filters for Packet ClassificationIEEE Micro, 2010
- Binary search on prefix lengths for ip address lookupIEEE Communications Letters, 2006
- Longest prefix matching using bloom filtersIEEE/ACM Transactions on Networking, 2006
- Survey and taxonomy of IP address lookup algorithmsIEEE Network, 2001
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999
- Scalable high speed IP routing lookupsACM SIGCOMM Computer Communication Review, 1997