Vectored-Bloom filter for IP address lookup: Algorithm and hardware architectures

Hayoung Byun, Qingling Li, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The Internet Protocol (IP) address lookup is one of the most challenging tasks for Internet routers, since it requires to perform packet forwarding at wire-speed for tens of millions of incomming packets per second. Efficient IP address lookup algorithms have been widely studied to satisfy this requirement. Among them, Bloom filter-based approach is attractive in providing high performance. This paper proposes a high-speed and flexible architecture based on a vectored-Bloom filter (VBF), which is a space-efficient data structure that can be stored in a fast on-chip memory. An off-chip hash table is infrequently accessed, only when the VBF fails to provide address lookup results. The proposed architecture has been evaluated through both a behavior simulation with C language and a timing simulation with Verilog. The hardware implementation result shows that the proposed architecture can achieve the throughput of 5 million packets per second in a field programmable gate array (FPGA) operated at 100 MHz.

Original languageEnglish
Article number4621
JournalApplied Sciences (Switzerland)
Volume9
Issue number21
DOIs
StatePublished - 1 Nov 2019

Keywords

  • Bloom filter
  • FPGA
  • hardware accelerator
  • IP address lookup
  • vectored-bloom filter

Fingerprint

Dive into the research topics of 'Vectored-Bloom filter for IP address lookup: Algorithm and hardware architectures'. Together they form a unique fingerprint.

Cite this