On adding bloom filters to longest prefix matching algorithms

Hyesook Lim, Kyuhee Lim, Nara Lee, Kyong Hye Park

Research output: Contribution to journalArticlepeer-review

47 Scopus citations

Abstract

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. A performance evaluation using actual backbone routing data with 15,000-220,000 prefixes shows that by adding a Bloom filter, the complicated hardware for parallel access is removed without search performance penalty in parallel-multiple hashing algorithm. Search speed has been improved by 30-40 percent by adding a Bloom filter in binary search on level algorithm.

Original languageEnglish
Article number6263242
Pages (from-to)411-423
Number of pages13
JournalIEEE Transactions on Computers
Volume63
Issue number2
DOIs
StatePublished - Feb 2014

Keywords

  • Bloom filter
  • IP address lookup
  • Internet
  • binary search on levels
  • leaf pushing
  • longest prefix matching
  • multihashing
  • router

Fingerprint

Dive into the research topics of 'On adding bloom filters to longest prefix matching algorithms'. Together they form a unique fingerprint.

Cite this