Scalable packet classification through maximum entropy hashing

In this paper we propose a new packet classification algorithm, which can substantially improve the performance of a classifier by decreasing the rulebase lookup latency. The algorithm hierarchically partitions the rulebase into smaller independent sub-rulebases by employing hashing. By using the same hash key used in the partitioning a classifier only needs to look up the relevant sub-rulebase 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 simulations of our proposed algorithm on synthetic rulebases of size 1K to 500K entries using real 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 magnitude with just two-levels of partitioning. Both the space and time complexity of the algorithm exhibit linearity in terms of the size of a rulebase, suggesting a good scalable solution for the packet classification with a large rulebase.