Set Pruning Segment Trees for Packet Classification

Nowadays, multi-field packet classification is one of the most important technologies to support various services in next generation routers. In this paper, we propose a segment tree based parallel SRAM-based pipelined architecture called Set Pruning Segment Trees (SPST) for multi-dimensional packet classification. For solving the memory blowup problem, a grouping scheme called Partition by Length (PL) is used to reduce the rule duplications in SPST. Additionally, we also propose an optimization called Set Pruning Multi-way Segment Trees (SPMST) to reduce the tree level and hardware cost. The key feature of our proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables. The proposed pipelined architecture can achieve a throughput of 89.4 Gbps for minimum sized packets with dual port memory on Xilinx Virtex-5 FPGA device.