A Modular Approach to Packet Classification Algorithms and Results

The ability to classify packets according to pre-defined rules is critical to providing many sophisticated value-added services, such as security, QoS, load balancing, traffic accounting, etc. Various approaches to packet classification have been studied in the literature with accompanying theoretical bounds. Practical studies with results applying in large number of filters (from 4K to 1 million) are rare. In this paper, we take a practical and modular approach to the problem of packet classification. Specifically, we propose and study a novel approach to packet classification which combines heuristic tree search with the use of filter buckets. Besides high performance and reasonable storage requirement, our algorithm is unique in the sense that it can adapt to the input packet distribution by taking into account the relative filter usage. To evaluate our algorithms, we have developed realistic model of large scale filter tables, and used those to drive extensive experimentation. The results demonstrate practicality of our algorithms for even up to 1 million filters.