Utilizing 2-D leaf-pushing for packet classification

Jungwon Lee, Hayoung Byun, Ju Hyoung Mun, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Packet classification is one of the most challenging functionalities performed by routers at wire-speed for every incoming packet. For search spaces composed of multiple rules represented geometrically, various space decomposition algorithms have been studied to provide effective search methods. While an area-based quad-trie (AQT) provides a simple and intuitive way of mapping the geometrical search space into a two-dimensional (2-D) trie structure, it does not provide high-speed classification performance because the mapping is incomplete. This paper proposes the application of leaf-pushing into the 2-D trie to improve the classification performance of the AQT. The leaf-pushing AQT provides a more effective method of searching rules covering each input packet in the decomposed space. We also discuss an efficient implementation technique for our algorithm using a Bloom filter and a hash table. Simulation results show that our proposed leaf-pushing AQT improves the packet classification performance up to 37 times for sets with up to 100,000 rules compared with the AQT. To be compared with other space decomposition algorithms, a refined structure of the leaf-pushing AQT is also proposed. Simulation results show that the proposed refined structure provides an effective space decomposition method as well as the balance between memory requirements and classification speed, while most of other space decomposition algorithms show a trade-off between them.

Original languageEnglish
Pages (from-to)116-129
Number of pages14
JournalComputer Communications
StatePublished - 1 May 2017

Bibliographical note

Publisher Copyright:
© 2017 Elsevier B.V.


  • Area-based quad-trie
  • Bloom filter
  • Decision tree
  • Internet
  • Leaf pushing
  • Packet classification
  • Router
  • Trie


Dive into the research topics of 'Utilizing 2-D leaf-pushing for packet classification'. Together they form a unique fingerprint.

Cite this