Range tree-linked list hierarchical search structure for packet classification on FPGAs

Field Programmable Gate Arrays (FPGAs) satisfying the abundant parallelism and high operating frequency demands are the most promising platform to realize SRAM-based pipelined architectures for high-speed packet classification. Due to the restrictions of the state-of-the-art FPGAs on the number of I/O pins and on-chip memory, larger filter databases can hardly be accommodated by the current approaches. Therefore, new data structures which are frugal with the memory are lately in high demand. In this paper, two stage range tree-linked list hierarchical search structure (RLHS) is introduced for packet classification. Our proposed structure comprising range tree in Stage 1 and linked lists in Stage 2, resolves backtracking and memory inefficiency problems in the pipelined hardware implementation of hierarchical search structures. We further present a categorization algorithm that partitions an input ruleset based on the field characteristics of rules to reduce the memory requirement. Each partition has an individual RLHS with specialized node structures free from redundant fields used for storing wildcards and range points. Our design is realized on an SRAM-based parallel and pipelined architecture using FPGAs to achieve high throughput. Utilizing a state-of-the-art FPGA, RLHS architecture can sustain a 404 million packets per second throughput or 129 Gbps (for the minimum packet size of 40 Bytes) while maintaining packet input order and supporting in-place non-blocking rule updates.