Partitioned 2D Set-Pruning Segment Trees with Compressed Buckets for Multi-Dimensional Packet Classification.

This article focuses on the design and evaluation of a parallel and pipelined architecture called Set-Pruning Segment Trees with Buckets (SPSTwB) for multi-dimensional packet classification in next-generation routers. SPSTwB reduces memory consumption and rule duplication through a novel partitioning scheme, bucket merging, and rule grouping, enabling efficient handling of large rule tables (up to 100,000 rules) generated by ClassBench. Implemented on a Xilinx Virtex-7 FPGA, the architecture achieves a throughput of 134 Gbps while using significantly less on-chip memory compared to existing schemes, and supports fast incremental rule updates. The design also incorporates power-saving techniques and demonstrates competitive performance against state-of-the-art FPGA-based packet classification methods. Future work aims to enhance update operations and extend applicability to Software-Defined Networking (SDN) environments.