Packet classification using a bloom filter in a leaf-pushing area-based quad-trie

Hyesook Lim, Ha Young Byun

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

6 Scopus citations

Abstract

Packet classification is one of the most essential functions that Internet routers should perform at wire-speed for every incoming packet. An area-based quad-trie (AQT) for packet classification has an issue in search performance since many rule nodes can be encountered in a search procedure. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to improve the search performance of the leaf-pushing AQT further. The proposed algorithm builds a leaf-pushing AQT using a Bloom filter and a hash table stored in on-chip memories. The level of a rule node and a pointer to a rule database are identified by sequentially querying the Bloom filter and by accessing the hash table, respectively.

Original languageEnglish
Title of host publicationANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages183-184
Number of pages2
ISBN (Electronic)9781467366335
DOIs
StatePublished - 18 May 2015
Event11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015 - Oakland, United States
Duration: 7 May 20158 May 2015

Publication series

NameANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Conference

Conference11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015
Country/TerritoryUnited States
CityOakland
Period7/05/158/05/15

Keywords

  • area-based quad-trie
  • Bloom filter
  • leaf-pushing
  • packet classification

Fingerprint

Dive into the research topics of 'Packet classification using a bloom filter in a leaf-pushing area-based quad-trie'. Together they form a unique fingerprint.

Cite this