|
|
 |
| |
|
|
|
Priority Area-based Quad-Tree Packet Classification Algorithm and Its Mathematical Framework |
|
|
|
PP: 9-20 |
|
|
|
Author(s) |
|
|
|
Hyesook Lim,
Changhoon Yim,
Earl E. Swartzlander, Jr.,
|
|
|
|
Abstract |
|
|
| 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. |
|
|
|
|
|
|
|
