From the February 2014 issue
On Adding Bloom Filters to Longest Prefix Matching Algorithms
By Hyesook Lim, Kyuhee Lim, Nara Lee, Kyong-Hye Park
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 parallel matching. However, the applicability of TCAMs presents difficulties due to cost and power dissipation issues. Various algorithms and hardware architectures have been proposed to perform the IP address lookup using ordinary memories such as SRAMs or DRAMs without using TCAMs. Among the algorithms, we focus on two efficient algorithms providing high-speed IP address lookup: parallel multiple-hashing (PMH) algorithm and binary search on level algorithm. This paper shows how effectively an on-chip Bloom filter can improve those algorithms.
Editorials and Announcements
- Get Your Journals as eBooks for Free
- eBooks of issues of TC can now be downloaded from the Computer Society Digital Library
- IEEE Transactions on Computers EIC Albert Zomaya receives two IEEE awards.
- "Cloud Computing" available at computer.org/store
- "Industrial Implementations of Floating-Point Units" available at computer.org/store
- State of the Journal by Albert Y. Zomaya (Jan 2012)
- State of the Journal by Albert Y. Zomaya (May 2011)
- Special Section on Concurrent On-Line Testing and Error/Fault Resilience of Digital Systems (September 2011)
Access Recently Published TC Articles
Subscribe to the RSS feed of latest TC content added to the digital library
Sign up for the Transactions Connection newsletter.
Importance of Coherence Protocols with Network Applications on Multi-Core Processors
Automated Generation of Performance and Dependability Models for the Assessment of Wireless Sensor Networks