Optimizing Decomposition-Based Packet Classification Implementation on FPGAs

Hardware implementations of Internet Protocol (IP) classification algorithms have been proposed by the research community over the years to realize high speed routers and Internet backbone. Decomposition-based IP classification algorithms are desirable for hardware implementation due to their parallel search on multiple fields. These algorithms consist of two phases: independent searches on each packet field in the first phase followed by the second phase where the results from the first phase are combined. However, the primary challenge in implementing this high-level approach lies in the second phase, i.e. how to efficiently combine the results of the single field searches. In this paper, we propose a systolic-array-based architecture on FPGA focusing on the combining techniques in phase two. The proposed approach exploits the rich logic resources on FPGA and achieves high throughput by deeply pipelining the architecture. We show the area analysis of the design to demonstrate the efficiency in on-chip resource usage. We also experimentally evaluate the impact of the size of the input rule set and number of matching rules from first phase on the performance of our design. We compare our design against the Bit Vector algorithm, another decomposition-based classification method, and demonstrate that our design is more efficient with respect to logic resource usage and is feasible for large rule sets. Post place and route result using a state-of-the-art FPGA device shows that the design can sustain a throughput of 107 Gbps, for a rule set consisting of up to 64K rules.