School of Information and Communication Engineering, Dalian University of Technology, Dalian, China

---

Abstract—A time efficient algorithm based on Bloom filters is proposed to solve the problem of longest prefix matching in IP lookups. It is distinguished from the existing algorithms by three features. Firstly, a first-byte indexing table is established before querying the Bloom filters, so that the impact of positive false inherent to Bloom filters on IP lookups is reduced. Secondly, only twelve Bloom filters are required for prefix query, as is based on the uniform distribution of various prefix lengths. Thirdly, update of routing tables is supported by associating a counter with each bit in the bit vectors of the Bloom filters. Performance analysis and experimental results show the efficacy of the proposed algorithm in decreasing the time complexity of IP lookups.

Index Terms—Bloom filters, IP lookups, longest prefix matching, time efficient algorithm

[PDF]

Cite: Ming Yu and Dongju Wang, " A Time Efficient Algorithm Based on Bloom Filters for Longest Prefix Matching in IP Lookups," Journal of Computers vol. 8, no. 10, pp. 2724-2729, 2013.