New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms

Ju Hyoung Mun, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

IP address lookup operation determines the longest prefix matching each incoming destination address. As a fundamental operation for packet forwarding at Internet routers, search speed for routing table lookup is the most important performance metric. Previous researches have shown that the search performance of trie-based algorithms can be improved by adding on-chip Bloom filters. In these algorithms, an on-chip Bloom filter identifies the membership of a node in an off-chip trie, and the number of trie accesses is reduced, because the Bloom filter can filter out accesses to non-existing nodes in the trie. In this paper, we propose a new method of utilizing a Bloom filter for the IP address lookup problem. In the previous Bloom filter-based approach, false positiveness has to be identified by accessing the off-chip trie for every positive result, since false positives can produce wrong results. In our proposed approach, the false positiveness of a Bloom filter is not necessarily identified by making false positives not mislead the search. Hence the number of off-chip trie accesses are significantly reduced. Simulation results show that the best matching prefix can be found with a single off-chip access in average and in the worst-case with the reasonable size of a Bloom filter in our proposed method.

Original languageEnglish
Article number7122873
Pages (from-to)1558-1565
Number of pages8
JournalIEEE Transactions on Computers
Volume65
Issue number5
DOIs
StatePublished - 1 May 2016

Keywords

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

Fingerprint

Dive into the research topics of 'New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms'. Together they form a unique fingerprint.

Cite this