Multi-pipelined and memory-efficient packet classification engines on FPGAs

A packet classification task incorporated in network firewalls to recognize and sift threats or unauthorized network accesses is accomplished by checking incoming packet headers against a pre-defined filter set. Plenty of solutions to reduce the memory requirement of filter set storage and accommodate packet classification to line rates have been proposed over the past decade. Among all the existing approaches, hierarchical data structures maintain great memory performance however their hardware realization suffers from two issues: (i) backtracking and (ii) memory inefficiency. In this paper, we propose two data structures denoted range tree-linked list hierarchical search structure (RLHS  ) and value-coded trie structure with ϵϵ-branch property (VCϵVCϵ) for packet classification. RLHS resolves backtracking by exploiting range tree in Stage 1 and linked list data structure in Stage 2 overcomes the memory inefficiency. VCϵVCϵ trie that naturally does not involve backtracking problem, solves memory inefficiency issue by comprising a fixed size bin at each node. Apart from conventional binary trie, a new rule is inserted into the first available bin on the path of this rule in a VCϵVCϵ trie, and ϵϵ-branch property is utilized in case all the bins are full. We also propose a rule categorization algorithm that partitions an input ruleset by considering the field features of rules to minimize the memory requirement. To support the proposed data structures, we designed high throughput SRAM-based parallel and pipelined architectures on Field Programmable Gate Arrays (FPGAs).