Memory-efficient recursive scheme for multi-field packet classification

Multi-field packet classification is not only an indispensable and challenging functionality of existing network devices, but it also appears as flow tables lying at the heart of the forwarding plane of software defined networking age. Despite almost two decades of research, algorithmic solutions still fall short of meeting the line-speed of high-performance network devices. Although decomposition-based approaches, such as cross-producting and recursive flow classification (RFC), can achieve high lookup rate by performing a parallel search on chunks of the packet header, both of them suffer from memory explosion problem during aggregation. In this study, the authors propose an HybridRFC, a memory-efficient recursive scheme for multi-field packet classification. By addressing the embedded problem of the RFC caused by uncontrollably expanded cross-product tables, HybridRFC can not only reduce the memory consumption to a practical level but also improve pre-processing performance significantly. Experimental results show that the memory requirement of HybridRFC is two orders of magnitude less than RFC, as well as three orders of speed-up on the performance of table building on average.