A quad-trie conditionally merged with a decision tree for packet classification

Hyesook Lim, Youngju Choe, Miran Shim, Jungwon Lee

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Trie-based algorithms and decision tree-based algorithms are well-known packet classification solutions which show trade-off between throughput performance and memory requirement. The trie-based algorithms require small memory since each rule is stored exactly once, but they do not provide high throughput because of rule comparison at every rule node. The decision tree-based algorithms provide high throughput since the number of rules compared with an input packet can be controlled as a limited number, but they require excessive amount of memory because of high degree of rule replication. This paper proposes to combine these two types of algorithms. The proposed algorithm primarily constructs a trie and then applies a decision tree for nodes having more rules than a threshold value. Simulation results show that the throughput performance is improved by up to 41 times compared with the trie, and the memory requirement is reduced by up to 38 times compared with the decision tree, so that the performance of both is within a tolerable range for practical implementation.

Original languageEnglish
Article number6739056
Pages (from-to)676-679
Number of pages4
JournalIEEE Communications Letters
Volume18
Issue number4
DOIs
StatePublished - Apr 2014

Keywords

  • HiCuts
  • Packet classification
  • area-based quad-trie
  • decision tree

Fingerprint

Dive into the research topics of 'A quad-trie conditionally merged with a decision tree for packet classification'. Together they form a unique fingerprint.

Cite this