TY - GEN
T1 - Binary search on trie levels with a bloom filter for longest prefix match
AU - Lee, Jungwon
AU - Lim, Hyesook
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/9/16
Y1 - 2014/9/16
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84908599713&partnerID=8YFLogxK
U2 - 10.1109/HPSR.2014.6900879
DO - 10.1109/HPSR.2014.6900879
M3 - Conference contribution
AN - SCOPUS:84908599713
T3 - 2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014
SP - 38
EP - 43
BT - 2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR 2014
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 1 July 2014 through 4 July 2014
ER -