High Throughput Multi-Pipeline Packet Classifier on FPGA
Abstract
Packet classification is one of the most important functions in the router design. This is to support a variety of network functionalities. Pipeline-based decision tree is one of the best choices for increasing throughput on packet classification. SRAM-based and hardware-based solutions are often used to develop a high speed packet classification engine. However, SRAM-based solutions suffer from throughput degradation, delay variation and memory overflow. Moreover, hardware-based solutions suffer from fast update and non-linear structure. To address these problems, we proposed a FPGA-based multi-pipeline architecture for 5-tuple rules into multiple subsets to build a decision tree with high throughput and fast update. To fit the current largest rule-set in the FPGA device, several optimization techniques are proposed that maximize the resource utilization while sustaining high throughput. In this architecture look up tables (LUTs) are used instead of memory blocks. Partial reconfiguration in Field Programmable Gate Array (FPGA) used to reduce the time that is needed to change the behavior of architecture. The implementation results show that our architecture can store over 10K real-life rules in LUTs of a single Xilinx Virtex-6 FPGA, and sustain over 120 Gbps (i.e. 3× OC-768 rate) throughput for minimum size (40 Bytes) packets.
Keywords
Packet Classification, Pipeline-Based Decision Tree, Rule Set, Field Programmable Gate Array (FPGA)