A Sorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification

The advent of software-defined networking (SDN) leads to two key challenges for packet classification on the dramatically increased dynamism and dimensionality. Although packet classification is a well-studied problem, no existing solution satisfies these new requirements without sacrificing classification speed. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification, but support neither fast updates nor high dimensionality. The tuple space search (TSS) algorithm used in Open vSwitch achieves fast updates and high dimensionality but not high-speed packet classification. In this paper, we propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving high-speed packet classification, fast updates, and high dimensionality. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than the TSS. Second, it allows the use of multi-dimensional interval trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that The PartitionSort is an order of magnitude faster than the TSS in classifying packets while achieving comparable update time. The PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while achieving a competitive classification time. Finally, the PartitionSort is scalable to an arbitrary number of fields and requires only linear space.