DynamicTuple: The dynamic adaptive tuple for high-performance 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 the Dynamic Adaptive Tuple (DynamicTuple) for both fast packet classification and 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. When the rules keep updating, DynamicTuple can retain the proper tuples and rebuild the improper tuples, thus the tuple in DynamicTuple is dynamic adaptive. The experimental results demonstrate that DynamicTuple achieves 33.1x, 5.6x, 5.7x classification speed and 2.9x, 11.0x, 8.5x updating speed compared to Tuple Space Search, TupleMerge, PartitionSort. By implementing DynamicTuple, the OpenFlow table of Open vSwitch achieves 26.6x classification speed.