Lightweight Traffic-Aware Packet Classification for Continuous Operation

Packet classification is primarily used by network devices, such as routers and firewalls, to do additional processing for a specific subset of packets. Such additional processing includes packet filtering, quality of service (QoS), and differentiated services (DiffServ). Most of the existing packet classification algorithms reported in the literature exploits the characteristics of filtering or classifier rules in optimizing their techniques. However, the seminal observation made by Gupta and McKeown that a given packet matches only few rules in the classifier shows promise to another direction that packet classifier´s average performance can be improved by exploiting the locality in the incoming traffic pattern. In this paper, we undertook the investigation of finding the feasibility of exploiting the locality in traffic to improve packet classifier´s average performance. Our lightweight traffic-aware packet classifier reorganizes its internal data structure (rule tree) based on the traffic pattern to reduce the search time for the most frequently visited rules in the rule-set. Unlike existing traffic-adaptive packet classifier requiring a separate, offline reorganization phase, our approach performs reorganization online with little overhead, resulting in higher throughput without compromising the accuracy. Experimental results on our test bed show that our traffic-adaptive packet classifier incurs small number of memory accesses (i.e. less time per packet) in order to classify the packet.