Performance evaluation and improvement of algorithmic approaches for packet classification

Packet classification is crucial to the implementation of several advanced services that require the capability to distinguish traffic in different flows, such as firewalls, intrusion detection systems and many QoS implementations. Although hardware solutions, such as TCAMs, provide high search rate, they do not scale to large rulesets. Instead, some of the most promising algorithmic research embraces the practice of leveraging the data redundancy in real-life rulesets to improve high performance packet classification. In this paper, we provide a general framework for discerning relationships and distinctions of the design-space of existing packet classification algorithms. We deeply studied several best-known algorithms, such as RFC, HiCuts and HyperCuts according to this framework and suggest for each algorithm an improved scheme. All algorithms we studied, along with their improved version, are objectively accessed using both real-life and synthetic rulesets. The C source codes we wrote for these algorithms are publicly shared on our web-site. 1 1