Priority Area-based Quad-Tree Packet Classification Algorithm and Its Mathematical Framework

Packet classification is an essential function for next-generation Internet routers to provide high quality of service. Packet classification using multiple header fields is a challenging problem that should be performed at wire speed for all incoming packets. This paper proposes a novel mathematical framework for packet classification problem. Then the priority area-based quad-tree (PAQT) packet classification algorithm combining priority search and recursive space decomposition is formally described using the framework. The validity of the PAQT algorithm is mathematically proved for theoretical justification. The proposed mathematical framework can be applied to other packet classification algorithms for formal description and theoretical justification. Extensive simulation results demonstrate that the PAQT algorithm has very good performance compared to other packet classification algorithms in terms of search speed, memory size, and scalability