Kyuhee Lim
ABSTRACT
This paper proposes a new IP address lookup using a Bloom filter. The proposed algorithm is based on binary search on trie levels, and a Bloom filter pre-filters the levels which do not have matching nodes in performing the binary search on levels. Hence the number of memory access which affects the search performance is greatly reduced. Simulation result shows that an IPv6 address lookup can be performed with 1--3 memory accesses in average for an IPv6 routing data set with 1096 prefixes.
- M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, Scalable high speed IP routing lookups. Proc. ACM SIGCOMM, pp. 25--35, 1997 Google Scholar
Digital Library
- B. Bloom, Space/time tradeoffs in hash coding with allowable errors, Commun. ACM, 13(7), pp. 422--426, 1970. Google ScholarDigital Library
- Sarang Dharmapurikar, Praveen Krishamurthy, and David E. Taylor, Longest prefix matching using bloom filters, IEEE/ACM Transactions on Networking, 14(2), pp. 397--409, 2006 Google ScholarDigital Library
- S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, Fast Packet Classification Using Bloom Filters, ACM/IEEE ANCS, 2006. Google ScholarDigital Library
- Alagukonar Ganapathy Alagupriya, Packet Classification Algorithms Using Bloom Filters, Ewha Womans UniversityGoogle Scholar
- IPv6 Operational Report. June 2008. DOI=http://net-stats.ipv6.tilab.com/bgp/bgp-table-snapshot.txt/Google Scholar
Index Terms
- Binary search on levels using a Bloom filter for IPv6 address lookup
Recommendations
A fast and scalable IPv4 and 6 address lookup algorithm
Due to Internet's exponential growth in the last few years, we face two serious problems. First, the network becomes congested. Second, the number of IP addresses is not enough for distribution. For network congestion, we use fibers in the backbone of ...
On Adding Bloom Filters to Longest Prefix Matching Algorithms
High-speed IP address lookup is essential to achieve wire-speed packet forwarding in Internet routers. Ternary content addressable memory (TCAM) technology has been adopted to solve the IP address lookup problem because of its ability to perform fast ...
IP address lookup for internet routers using balanced binary search with prefix vector
We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence ...
Comments