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

Kyuhee Lim, Kyunghye Park, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

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.

Original languageEnglish
Title of host publicationANCS'09
Subtitle of host publicationSymposium on Architecture for Networking and Communications Systems
Pages185-186
Number of pages2
DOIs
StatePublished - 2009
Event2009 Symposium on Architecture for Networking and Communications Systems, ANCS'09 - Princeton, NJ, United States
Duration: 19 Oct 200920 Oct 2009

Publication series

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

Conference

Conference2009 Symposium on Architecture for Networking and Communications Systems, ANCS'09
Country/TerritoryUnited States
CityPrinceton, NJ
Period19/10/0920/10/09

Keywords

  • binary search on levels
  • Bloom filter
  • hash table
  • IP address lookup
  • IPv6

Fingerprint

Dive into the research topics of 'Binary search on levels using a Bloom filter for IPv6 address lookup'. Together they form a unique fingerprint.

Cite this