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

Jungwon Lee, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

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.

Original languageEnglish
Title of host publication2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages38-43
Number of pages6
ISBN (Electronic)9781479916337
DOIs
StatePublished - 16 Sep 2014
Event2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014 - Vancouver, Canada
Duration: 1 Jul 20144 Jul 2014

Publication series

Name2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014

Conference

Conference2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014
Country/TerritoryCanada
CityVancouver
Period1/07/144/07/14

Fingerprint

Dive into the research topics of 'Binary search on trie levels with a bloom filter for longest prefix match'. Together they form a unique fingerprint.

Cite this