Research On Storage Optimization Of Multi-field Packet Classifation Algorithm

With the rapid growth of network scale, a variety of new network applications emerge, andthe network bandwidth keeps on increasing, which demands the backbone equipments such asrouters and switches providing better performance. As a key functionality for many Internetapplications such as Firewall、Intrusion Detection、QoS、VPN, Multi-field Packet Classificationis now facing great challenge.The increasing complexity of the rules makes the hardware-basedmulti-field packet classification algorithm’s memory consumption rise sharply. Packetclassification algorithms based on TCAM or RAM mostly can process packets at wire-speed,but limited by the capacity of the high-speed memory chip, multi-field packet classificationalgorithms must solve the problem of consuming too much memory under the circumstance ofhigh speed netmork and large volume complex rule set. Combined with the demands of theNational863Project “Uniform Security Control and Management Network for Three NetworksConvergence”, we firstly give a comprehensive summary of the results in the area of packetclassification, then focus on multi-field packet classification algorithm for storage optimization,the major research and innovationpoints are as follows:For complex rule set, we proposed an improved decision tree based HyperSplit packetclassification algorithm. By analyzing the cause of too much memory usage, we modifyand design the heuristic algorithms to choose the cutting points and dimensions andeliminate redundancy, rule replication is greatly reduced, redundant rules and nodesremoved, and the decision tree’s structure is optimized. Simulation results demonstratethat compared with the existing work, independent of rule set’s type and characteristic,the algorithm can greatly reduce memory usage to HyperSplit’s70%-80%withoutincrease in the number of memory accesses and ensure that packets can be processed atwire speed.For large-capacity rule set, we propose a multiple decision tree packet classificationalgorithm based on rule set partitioning. On the condition of controlling the number ofsub-sets, heuristics are used to partition the rule set as to separate overlapping rules.Cascading decision-tree structure is proposed to lowering the tree’s height and reducingsearch time. Theoretical analysis shows that space complexity has been reduced severaltimes as traditional single decision-tree algorithms. Simulation results demonstrate thatthe algorithm greatly reduces memory usage to less than EffiCuts’s70%with FW ruleset and has better dimension scalability when comparing with EffiCuts, but takes a bitmore pre-processing time.For the multiple decision tree packet classification algorithm based on rule setpartitioning, we propose a parallel multiple pipelines architecture and an effectivetree-to-pipeline mapping scheme as to achieve balanced memory distribution over allthe stages while sustaining a state-of-art throughput of one packet per clock cycle，which helps increasing the memory usage rate of the system. Based on the proposedmultiple pipeline architecture above, taking full advantages of FPGA’s parallelism characteristic, We design a multi-engine packet classification system on a single FPGAchip. Analyzing theoretically, our engine can achieve a high throughput and supportlarge rule set, which can fully meet the current needs of packet classification problems.