SCALABLE, DETERMINISTIC AND UPDATABLE FLOW PROCESSING FRAMEWORK TO ACCELERATE SOFTWARE DEFINED NETWORKING
To accomplish high-performance and granular traffic control across a great number of network devices, flow processing in an OpenFlow switch is of great importance for any Software Defined Networking (SDN) architecture. The fundamental challenge is to classify incoming packets efficiently according to a pipeline of flow tables characterized by numerous fields and match types. So far current packet classification algorithms is not able to process a flow table with an arbitrary number of fields and any match type due to several crucial drawbacks, especially scalability, incremental update and nondeterminism. To address the new challenge we propose an innovative decomposition algorithm. Meanwhile we propose three different schemes to process flow tables with only exactmatch, prefix match and classic quintuple match. They are (1) a highly deterministic hashing scheme featured by efficient collision resolution, (2) a hierarchical hashing scheme featured by taking advantage of bitmap and hashing techniques, and (3) a divide-and-conquer scheme based on Ternary Content Addressable Memory (TCAM) hardware by addressing the range expansion problem. Together with the proposed decomposition algorithm, these four approaches cover all categories of match types and comprise a high-performance table lookup accelerator to boost flow processing in an OpenFlow switch. As far as we know, our proposed decomposition scheme is the first efficient approach toaddressing multidimensional match problem in an OpenFlow flow table with an arbitrary number of fields and any match type. And our proposed high-performance table lookup accelerator is the first comprehensive proposal to process the entire OpenFlow table pipeline by covering all categories of match types and any number of fields. The accelerator is available to be implemented and deployed in either software or hardware devices with respect to a variety of performance and cost circumstances.