Two-dimensional packet classification algorithm using a quad-tree

Hyesook Lim, Min Young Kang, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


For the last few years, there is an explosive growth in the development and the deployment of network applications that transmit and receive audio and video over the Internet. In order for such multimedia applications to function properly, networks need to provide the level of performance, which is called the quality of services (QoS). An essential element for the Internet routers to provide the QoS is the packet classification which classifies incoming packets into classified flows. Based on the pre-defined rules composed of multiple header fields, incoming packets are classified into a specific flow, and packets are treated differently according to the classified flow. Efficient packet classification algorithms have been widely studied, but none of known algorithms except the linear search considers the priority of rules in constructing the data structure of classification tables. In this paper, we propose a priority-based quad-tree (PQT) algorithm for packet classification. In constructing a quad-tree generated based on recursive space decomposition, the priority of rules is primarily considered in the proposed algorithm. In the simulation using the class-bench databases, the proposed algorithm achieves very good performance in the required memory size and reasonable performance in the classification speed. The proposed algorithm also provides good scalability toward large classifiers.

Original languageEnglish
Pages (from-to)1396-1405
Number of pages10
JournalComputer Communications
Issue number6
StatePublished - 26 Mar 2007

Bibliographical note

Funding Information:
This research was supported by the Ministry of Information and Communications, Korea, under a HNRC-ITRC support program supervised by IITA.


  • Packet classification
  • Priority
  • Quality of services
  • Recursive decomposition


Dive into the research topics of 'Two-dimensional packet classification algorithm using a quad-tree'. Together they form a unique fingerprint.

Cite this