MultilayerTuple: A General, Scalable and High-performance Packet Classification Algorithm for Software Defined Network System

Packet classification is one of the core components in Software Defined Network (SDN) systems, e.g., Open vSwitch. However, the current packet classification algorithm Tuple Space Search (TSS), which is implemented in SDN systems, has low lookup speed and can be attacked. Although some algorithms that support incremental updates are proposed to improve the lookup speed, e.g., TupleMerge and PartitionSort, but are not general and scalable to apply in SDN systems and replace TSS. In this paper, we propose a general, scalable, and high-performance packet classification algorithm MultilayerTuple. MultilayerTuple reduces the number of tuples by splitting the prefix lengths of rules into ranges in each layer, then creates the next layer to replace the long rule chain recursively. The experimental results demonstrate that compared to TSS, TupleMerge, and PartitionSort, MultilayerTuple achieves 21.8x, 2.1x, 2.2x lookup speed and 2.3x, 12.3x, 8.5x update speed. Furthermore, we have implemented MultilayerTuple in the OpenFlow table and MegaFlow cache of Open vSwitch, and it achieves 16.0x and 10.2x lookup speed than TSS. Especially when TSE attack happens, MultilayerTuple can effectively defend against it.