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, the authors 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, they also propose an optimization called Set Pruning Multi-way Segment Trees (SPMST) to reduce the tree level and hardware cost. The key feature of their proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables.