Research And Implementation Of High Performance Packet Classification On GPU

The performance of internet is now insufficient in corresponding to the expanding scale and rocketing workload.As a core function of network device including router and switch,packet classification deals with 5-tuple rule match problem which to some extent decides the throughput of packet and thus impact the efficiency of the entire network.On the other hand,in Software Defined Networking(SDN),a typical next general internet architecture,the core problem in data domain is OpenFlow flow table lookup,which essentially is packet classification with more fields,more rules,and more frequent update.Thus efficient,flexible and scalable packet classification has become a realistic and challenging problem.This paper focuses on packet classification,the essential problem in the internet packet processing,specifically the algorithm optimizing in the collaborative framework of CPU/GPU and has acquired some achievements.First,to explore general issues how GPU accelerate packet classification,classic al-gorithm HiCuts is modified and accelerated by GPU.In the meantime,Netmap,a high performance packet input/output framework,is introduced to build a simple collaborative CPU/GPU packet processing framework to evaluate the end-to-end performance.The ex-periments show that GPU acceleration greatly improves the performance of HiCuts,though it' s still a long way to achieve line-speed processing since the HiCuts has not taken the full advantage of GPU hardware merit.Therefore,this paper designed a new algorithm based on bitmap merge which combines the parallel mechanism and memory visiting character-istic,using CUDA to optimize details in the algorithm design.Result of experiments has shown this algorithm achieved an acceleration from 2.3 to 9.5 times on GPU compared to HiCuts.In the last part of the paper,a tree form data structure and its corresponding classifi-cation algorithm based on bit splitting has been developed to combine OpenFlow flow table lookup demands and GPU hardware merit.The tests indicate that this algorithm applies not only multidimensional,great scale rule-set cases,but also high frequent rule-set update operation.