Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing

Abstract—In this paper, we introduce a new packet classifica-tion algorithm, which can substantially improve the performance of a classifier. The algorithm is built on the observation that a given packet matches only a few rules even in large classifiers, which sug-gests that most of rules are independent in any given rulebase. The algorithm hierarchically partitions the rulebase into smaller inde-pendent subrulebases based on hashing. By using the same hash key used in the partitioning a classifier only needs to look up the relevant subrulebase to which an incoming packet belongs. For an optimal partitioning of rulebases, we apply the notion of maximum entropy to the hash key selection. We performed the detailed simu-lations of our proposed algorithm on synthetic rulebases of size 1 K to 500 K entries using real-life packet traces. The results show that the algorithm can significantly outperform existing classifiers by reducing the size of a rulebase by more than four orders of magni-tude with just two-levels of partitioning. Both the time complexity and the space complexity of the algorithm exhibit linearity in terms of the size of a rulebase. This suggests that the algorithm can be a good scalable solution for medium to large rulebases. Index Terms—Computer networks, firewalls, network perfor-mance, packet classification. I