TY - JOUR
T1 - Two-dimensional packet classification algorithm using a quad-tree
AU - Lim, Hyesook
AU - Kang, Min Young
AU - Yim, Changhoon
N1 - Funding Information:
This research was supported by the Ministry of Information and Communications, Korea, under a HNRC-ITRC support program supervised by IITA.
PY - 2007/3/26
Y1 - 2007/3/26
N2 - 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.
AB - 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.
KW - Packet classification
KW - Priority
KW - Quality of services
KW - Recursive decomposition
UR - http://www.scopus.com/inward/record.url?scp=33947189903&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2007.01.004
DO - 10.1016/j.comcom.2007.01.004
M3 - Article
AN - SCOPUS:33947189903
SN - 0140-3664
VL - 30
SP - 1396
EP - 1405
JO - Computer Communications
JF - Computer Communications
IS - 6
ER -