A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification

Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.