Hierarchical packet classification using a Bloom filter and rule-priority tries

A. G. Alagu Priya, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

Packet classification techniques have received significant attention in the network literature over the past 10 years, due to its fundamental role in the Internet routers. In recent years, Bloom filter, which is an efficient data structure for membership queries, becomes popular in the network applications. Though Bloom filter allows an error called "false positives," the efficiency and the space saving overweigh this drawback when the false positive rate is properly controlled. In this paper, we proposed a packet classification algorithm based on a hierarchical approach. While the same data structure is used both for the source and the destination prefix fields in most of other hierarchical packet classification algorithms, our proposed hierarchical packet classification algorithm uses a Bloom filter for the source prefix field and a trie structure for the destination prefix field. The Bloom filter is primarily employed to pre-filter the sub-strings of the source address which have no match for the source prefixes of a given rule set. For the sub-strings with a positive result from the Bloom filter, rule-priority tries constructed based on a destination prefix field determine the highest priority rule matching the input packet for entire rule fields. Since the Bloom filter requires a small amount of memory, it is implemented with an on-chip memory or a fast cache, and hence the off-chip memory accesses are not occurred in the first stage of the hierarchical approach in the proposed algorithm. The proposed packet classification algorithm also provides incremental update. To compare the performance of the proposed packet classification algorithm with other related algorithms, extensive simulations for various algorithms are performed. The simulation result shows that the proposed algorithm renders a better performance in terms of average and worst-case search performance and memory requirement.

Original languageEnglish
Pages (from-to)1215-1226
Number of pages12
JournalComputer Communications
Volume33
Issue number10
DOIs
StatePublished - 15 Jun 2010

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (2010-0000483). This research was also supported by the MKE (The Ministry of Knowledge Economy), Korea, under the HNRC (Home Network Research Center) – ITRC (Information Technology Research Center) support program supervised by the National IT Industry Promotion Agency (NIPA-2010-C1090-1011-0010).

Keywords

  • All-length Bloom filter
  • Best matching rule
  • Hashing
  • Packet classification
  • Rule-priority trie

Fingerprint

Dive into the research topics of 'Hierarchical packet classification using a Bloom filter and rule-priority tries'. Together they form a unique fingerprint.

Cite this