A new hierarchical packet classification algorithm

Hyesook Lim, Soohyun Lee, Earl E. Swartzlander

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

Packet classification is one of the most challenging functions in Internet routers since it involves a multi-dimensional search that should be performed at wire-speed. Hierarchical packet classification is an effective solution which reduces the search space significantly whenever a field search is completed. However, the hierarchical approach using binary tries has two intrinsic problems: back-tracking and empty internal nodes. To avoid back-tracking, the hierarchical set-pruning trie applies rule copy, and the grid-of-tries uses pre-computed switch pointers. However, none of the known hierarchical algorithms simultaneously avoids empty internal nodes and back-tracking. This paper describes various packet classification algorithms and proposes a new efficient packet classification algorithm using the hierarchical approach. In the proposed algorithm, a hierarchical binary search tree, which does not involve empty internal nodes, is constructed for the pruned set of rules. Hence, both back-tracking and empty internal nodes are avoided in the proposed algorithm. Two refinement techniques are also proposed; one for reducing the rule copy caused by the set-pruning and the other for avoiding rule copy. Simulation results show that the proposed algorithm provides an improvement in search performance without increasing the memory requirement compared with other existing hierarchical algorithms.

Original languageEnglish
Pages (from-to)3010-3022
Number of pages13
JournalComputer Networks
Volume56
Issue number13
DOIs
StatePublished - 5 Sep 2012

Keywords

  • Back-tracking
  • Binary search tree
  • Packet classification
  • Set-pruning

Fingerprint

Dive into the research topics of 'A new hierarchical packet classification algorithm'. Together they form a unique fingerprint.

Cite this