1 / 2020-07-25 13:30:07

<>DynamicTuple: A Dynamic Programming Based Tuple Formulation for High Speed Packet Classification

Packet Classification

The frequent rule updating in Software Defined Networking and cloud computing requires the packet classification algorithm to perform fast packet matching and flow table updating simultaneously. The existing algorithms, e.g. decision-tree-based or hash-based, achieve fast packet classification at the sacrifice of the rule updating or vice versa. We propose a Dynamic Programming based Tuple Formulation (DynamicTuple) algorithm for both fast packet classification and online rule updating simultaneously. DynamicTuple builds a performance model of tuple based packet classification and exploits dynamic programming to find the appropriate tuple formulation to minimize the lookup time. The experimental results demonstrate that DynamicTuple achieves 27.8x, 4.6x, 4.5x classification speed and 3.7x, 6.8x, 7.9x updating speed compared to TSS, TupleMerge, PartitionSort.