poster

Binary search on levels using a Bloom filter for IPv6 address lookup

Authors:

Kyuhee Lim,

Kyunghye Park,

Hyesook LimAuthors Info & Claims

ANCS '09: Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Pages 185 - 186

https://doi.org/10.1145/1882486.1882534

Published: 19 October 2009 Publication History

Get Access

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.

References

[1]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, Scalable high speed IP routing lookups. Proc. ACM SIGCOMM, pp. 25--35, 1997

Digital Library

Google Scholar

[2]

B. Bloom, Space/time tradeoffs in hash coding with allowable errors, Commun. ACM, 13(7), pp. 422--426, 1970.

Digital Library

Google Scholar

[3]

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

Digital Library

Google Scholar

[4]

S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, Fast Packet Classification Using Bloom Filters, ACM/IEEE ANCS, 2006.

Digital Library

Google Scholar

[5]

Alagukonar Ganapathy Alagupriya, Packet Classification Algorithms Using Bloom Filters, Ewha Womans University

Google Scholar

[6]

IPv6 Operational Report. June 2008. DOI=http://net-stats.ipv6.tilab.com/bgp/bgp-table-snapshot.txt/

Google Scholar

Cited By

View all

Ghosh ABarik LRout SRawat BJena PPatra S(2023)Enhancing Traffic Engineering Policy in SDN Addressing TCAM limitations using Bloom Filters2023 4th IEEE Global Conference for Advancement in Technology (GCAT)10.1109/GCAT59970.2023.10353347(1-6)Online publication date: 6-Oct-2023
https://doi.org/10.1109/GCAT59970.2023.10353347
Mun JLim H(2016)New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based AlgorithmsIEEE Transactions on Computers10.1109/TC.2015.244485065:5(1558-1565)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TC.2015.2444850
Nikolenko SKogan KRetvari GBerczi-Kovacs EShalimov A(2016)How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFCOMW.2016.7562132(521-526)Online publication date: Apr-2016
https://doi.org/10.1109/INFCOMW.2016.7562132
Show More Cited By

Index Terms

Binary search on levels using a Bloom filter for IPv6 address lookup
1. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ANCS '09: Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

October 2009

227 pages

ISBN:9781605586304

DOI:10.1145/1882486

General Chairs:
Peter Onufryk
IDT
,
K. K. Ramakrishnan
AT&T Labs - Research
,
Program Chairs:
Patrick Crowley
Washington University in St. Louis
,
John Wroclawski
USC

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

ANCS '09

Sponsor:

SIGCOMM
SIGARCH
IEEE-CS\TCCA

ANCS '09: Symposium on Architecture for Networking and Communications Systems

October 19 - 20, 2009

New Jersey, Princeton

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
227
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ghosh ABarik LRout SRawat BJena PPatra S(2023)Enhancing Traffic Engineering Policy in SDN Addressing TCAM limitations using Bloom Filters2023 4th IEEE Global Conference for Advancement in Technology (GCAT)10.1109/GCAT59970.2023.10353347(1-6)Online publication date: 6-Oct-2023
https://doi.org/10.1109/GCAT59970.2023.10353347
Mun JLim H(2016)New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based AlgorithmsIEEE Transactions on Computers10.1109/TC.2015.244485065:5(1558-1565)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TC.2015.2444850
Nikolenko SKogan KRetvari GBerczi-Kovacs EShalimov A(2016)How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFCOMW.2016.7562132(521-526)Online publication date: Apr-2016
https://doi.org/10.1109/INFCOMW.2016.7562132
Lim HLim KLee NPark K(2014)On Adding Bloom Filters to Longest Prefix Matching AlgorithmsIEEE Transactions on Computers10.1109/TC.2012.19363:2(411-423)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TC.2012.193
Ghosh SDas OMajumdar A(2013)Data Structures for IP Lookups, A Comparative Analysis with Scalability to IPV6Intelligent Computing, Networking, and Informatics10.1007/978-81-322-1665-0_124(1201-1208)Online publication date: 18-Dec-2013
https://doi.org/10.1007/978-81-322-1665-0_124
Lim HLee N(2011)Survey and Proposal on Binary Search Algorithms for Longest Prefix MatchIEEE Communications Surveys & Tutorials10.1109/SURV.2011.061411.00095Online publication date: 2011
https://doi.org/10.1109/SURV.2011.061411.00095
Lim HYim CSwartzlander Jr. E(2010)Priority Tries for IP Address LookupIEEE Transactions on Computers10.1109/TC.2010.3859:6(784-794)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1109/TC.2010.38

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A fast and scalable IPv4 and 6 address lookup algorithm

On Adding Bloom Filters to Longest Prefix Matching Algorithms

IP address lookup for internet routers using balanced binary search with prefix vector