Efficient packet classification on FPGAs also targeting at manageable memory consumption

Packet classification involving multiple fields is used in the area of network intrusion detection, as well as to provide quality of service and value-added network services. With the ever-increasing growth of the Internet and packet transfer rates, the number of rules needed to be handled simultaneously in support of these services has also increased. Field-Programmable Gate Arrays (FPGAs) provide good platforms for hardware-software co-designs that can yield high processing efficiency for highly complex applications. However, since FPGAs contain rather limited user-programmable resources, it becomes necessary for any FPGA-based packet classification algorithm to compress the rules as much as possible in order to achieve a widely acceptable on-chip solution in terms of performance and resource consumption; otherwise, a much slower external memory will become compulsory. We present a novel FPGA-oriented method for packet classification that can deal with rules involving multiple fields. This method first groups the rules based on their number of important fields, then attempts to match two fields at a time and finally combines the constituent results to identify longer matches. Our design with a single FPGA yields a larger than 9.68 Gbps throughput and has a small memory consumption of around 256Kbytes for more than 10,000 rules. This memory consumption is the lowest among all previously proposed FPGA-based designs for packet classification. Our scalable design can easily be extended to achieve a higher than 10Gbps throughput by employing multiple FPGAs running in parallel.