Date Added: Nov 2012
Packet classification is primarily used by network devices, such as routers and firewalls, to do additional processing such as packet filtering, and Quality-of-Service (QoS) for a specific subset of network packets. In decision tree based packet classification system, packets are classified by searching in the tree data structure. Tree search presents significant challenges because it requires a number of unpredictable and irregular memory accesses. Since packet classification is per-packet operation and memory latency (caused by cache and TLB misses) is considerably high, any technique that can reduce cache and TLB misses can be useful in practice for improving lookup time in packet classification.