Fast packet classification using recursive endpoint-cutting and bucket compression on FPGA

Yeim Kuan Chang, Han Chen Chen

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Packet classification is one of the important functions in today's high-speed Internet routers. Many existing FPGA-based approaches can achieve a high throughput but cannot accommodate the memory required for large rule tables because on-chip memory in FPGA devices is limited. In this paper, we propose a high-throughput and low-cost pipelined architecture using a new recursive endpoint-cutting (REC) decision tree. In the software environment, REC needs only 5-66% of the memory needed in Efficuts for various rule tables. Since the rule buckets associated with leaf nodes in decision trees consume a large portion of total memory, a bucket compression scheme is also proposed to reduce rule duplication. Based on experimental results on Xilinx Virtex-5/6 FPGA, the block RAM required by REC is much less than the existing FPGA-based approaches. The proposed parallel and pipelined architecture can accommodate various tables of 20 K or more rules, in the FPGA devices containing 1.6 Mb block RAM. By using dual-ported memory, throughput of beyond 100 Gbps for 40-byte packets can be achieved. The proposed architecture outperforms most FPGA-based search engines for large and complex rule tables.

Original languageEnglish
Pages (from-to)198-204
Number of pages7
JournalComputer Journal
Issue number2
Publication statusPublished - 2019 Feb 1

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Fast packet classification using recursive endpoint-cutting and bucket compression on FPGA'. Together they form a unique fingerprint.

Cite this