FPGA-based Design And Implementation Of Packet Classification Algorithms

With the continuous development of the Internet infrastructure and applications, the traditional single routing function of the router is unable to meet people’s needs, such as the higher quality requirements of up-and-coming multimedia transmission technology for packet delivery, access restrictions of some specific user for data packets, etc, which require support of packet classification algorithm. Region segmentation algorithm is relatively suitable for handling high-speed packets through comprehensive comparison, such as Hicuts algorithm and Hypercuts algorithms. But this algorithm needs to construct a decision tree before classifying packets, which needs a lot of time. This paper proposes a new regional segmentation algorithm-Hiercuts algorithm, which can limit the maximum height of the decision tree, and reduce the scope of the rule sets building the decision tree by the non-uniform precut. It shows that the memory is used more efficiently through software testing. Finally this paper performs the algorithm on FPGA for functional verification.This paper aims to propose a new packet classification algorithm and improve it. Then we perform software testing and hardware functional verification for it.First, we design a new algorithm—Hiercuts algorithm. Among traditional packet classification algorithms, region segmentation algorithm is relatively suitable for handling high-speed packets, but it spends a lot of time to build the decision tree before classification. Based on the traditional algorithm, we design Hiercuts algorithm that builds a maximum-height-limited of decision trees, which could reduce the preprocessing time.Secondly, Hiercuts algorithm adds a non-uniform precut step before building the decision tree, which could reduce the scope of the rules set building the decision tree, and improve the efficiency of memory through rule storage.Finally, we perform Hiercuts algorithms on the FPGA for functional verification. As a relatively fast packet processing hardware products, that we simulate high rate data packet with FPGA is significant. So we performed the algorithm on the Cyclone Ⅱ successfully.In conclusion, this paper proposes a new algorithm on the basis of traditional algorithms, whose maximum height of the decision tree is limited, while it also reduces the scope of rule sets to build the decision tree by non-uniform pre-cut and storage technology adoption to improve the efficiency of memory usage and classification rate.Finally we performed Hiercuts algorithms on the FPGA for functional verification.