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

Yeim-Kuan Chang, Han Chen Chen

Research output: Contribution to journalArticle

Abstract

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
Volume62
Issue number2
DOIs
Publication statusPublished - 2019 Feb 1

Fingerprint

Field programmable gate arrays (FPGA)
Data storage equipment
Throughput
Random access storage
Decision trees
Search engines
Routers
Internet
Costs

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{e05fa927b4974e50b7bcbc07ef5e31fe,
title = "Fast packet classification using recursive endpoint-cutting and bucket compression on FPGA",
abstract = "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.",
author = "Yeim-Kuan Chang and Chen, {Han Chen}",
year = "2019",
month = "2",
day = "1",
doi = "10.1093/comjnl/bxy052",
language = "English",
volume = "62",
pages = "198--204",
journal = "Computer Journal",
issn = "0010-4620",
publisher = "Oxford University Press",
number = "2",

}

Fast packet classification using recursive endpoint-cutting and bucket compression on FPGA. / Chang, Yeim-Kuan; Chen, Han Chen.

In: Computer Journal, Vol. 62, No. 2, 01.02.2019, p. 198-204.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Chang, Yeim-Kuan

AU - Chen, Han Chen

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85062689296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062689296&partnerID=8YFLogxK

U2 - 10.1093/comjnl/bxy052

DO - 10.1093/comjnl/bxy052

M3 - Article

VL - 62

SP - 198

EP - 204

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 2

ER -