Binary search on trie levels with a bloom filter for longest prefix match

Citations Over Time

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.

Related Papers

• → Name prefix matching using bloom filter pre-searching for content centric network(2016)42 cited
• → On reducing false positives of a bloom filter in trie-based algorithms(2014)8 cited
• → Dual-load Bloom filter: Application for name lookup(2019)17 cited
• → On Reducing False Positives of a Bloom Filter in Trie-Based Algorithms(2015)1 cited
• → Summary prefix tree: An over DHT indexing data structure for efficient superset search(2017)1 cited