A High-speed Software And Hardware Cooperative Flow Table Based On Elephant Flow Offloading

With the rapid development of cloud computing,network functions virtualization(NFV)has been more and more widely used.However,with the rapid improvement of the network link rate,the performance defects of NFV are becoming increasingly prominent.It has become an industry trend to use intelligent network cards and dedicated hardware acceleration cards to accelerate the virtual network functions.As one of the basic functional components of network forwarding equipment and network security equipment,the performance of flow table has an important impact on the overall performance of network equipment and system.This thesis studies the design and implementation of flow table based on software hardware collaboration.The traffic of the network data flow follows the Pareto distribution.The sum of the traffic of a few data flows accounts for the majority of the total traffic(this kind of data flow is called "elephant flow"),while the sum of the traffic of most other data flows only accounts for a small part of the total traffic(this kind of data flow is called "mouse flow").The basic idea of this thesis is to offload the most frequent and time-consuming operation in the flow table-the line speed lookup operation of the elephant flow table into the hardware,while the insertion and deletion operations of the elephant flow table and all the operations of the mouse flow table are implemented by software.Through the above design of software and hardware cooperation,it is ensured that the implemented flow table has both the high performance of hardware flow table and the flexibility of software flow table.Specifically,the main work of this thesis is as follows:1)To optimize the performance of flow table lookup in software data plane,this thesis studies the exact matching method of flow table based on cuckoo hash table.The existing highperformance cuckoo hash table algorithm is mainly based on the bucket width first search.This thesis finds that its disadvantage is that its insertion time will increase exponentially with the size of the data,and its insertion time at high load is about 4-5 times that at low load.In order to solve this problem,this thesis puts forward two measures to improve it,one is to limit the maximum access times of bucket insertion under high load,and the other is a new extended bucket insertion algorithm.The experimental results show that the insertion time of the proposed algorithm is about 1.5 times that of the low load algorithm under the high load condition,rather than 4-5 times that of the improved algorithm.At the same time,when there is an extended bucket,the search rate of the improved algorithm is also increased by about 5%.The cost of the improved algorithm is that compared with the improved algorithm,the storage space of the improved algorithm increases by about 6.5%.2)Aiming at the problem that hardware resources are limited and cannot support largescale flow table offloading,combined with the characteristics of network flow distribution,this thesis studies the flow table offloading scheme based on elephant flow detection.Only the most frequent lookup operations of elephant flow table are offloaded to hardware,and the insertion and deletion operations of elephant flow table,as well as all the operations of mouse flow table are implemented by software.Firstly,this thesis studies the high-speed packet random sampling scheme for elephant flow detection,and determines two system parameters: packet sampling frequency(1 ‰)and elephant flow classification threshold through experiments.Under the low false positive rate of 1.4%,the recall rate is more than 96%.Then,this thesis designs a hardware offloading scheme of flow table for elephant flow.The main process is as follows: 1)build a small-scale hash table to store the elephant flow table items in the FPGA intelligent network card;2)Search the elephant stream packet by packet,and record the search result value on the packet header;3)Perform actions on the data packets with successful lookup according to the recorded value,and transfer the data packets with failed lookup to the software flow table for subsequent operations.At the same time,in order to reduce the implementation complexity of the hardware flow table,this thesis constructs the same hash table structure as the hardware flow table in the software.Its main functions are as follows: 1)in the software,simulate the hardware hash table insertion process for all elephant flows that exceed the threshold value,and compare the flow before and after the hash table location where the conflict occurs.The high flow occupies the location,and the low flow is discarded.2)Update the hardware flow table synchronously.The experimental results show that the proposed scheme of offloading only elephant flow lookup operation has higher throughput and lower delay than the existing hardware flow table scheme,and consumes significantly less FPGA resources than the existing schemes.3)Based on the above research,this thesis implements a large-scale data surface flow table system with software and hardware cooperation based on DPDK and Xilinx U200 hardware accelerator.Firstly,this thesis combines the optimized cuckoo hash table algorithm with the high-performance data plane of DPDK to implement the high-performance software flow table based on DPDK.Secondly,based on DPDK user mode driver and Xilinx QDMA interface,this thesis implements a high-performance software and hardware interaction channel with a bandwidth of 95.61 Gbps.Finally,the software flow table and hardware flow table are combined to build a large-scale software and hardware collaborative flow table based on elephant flow detection.The experimental results show that compared with the original software flow table in DPDK,the software and hardware collaborative flow table system designed and implemented in this thesis achieves a 64%-123% search performance improvement.