A high-speed and memory efficient pipeline architecture for packet classification

Yeim-Kuan Chang, Yi Shang Lin, Cheng Chien Su

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.

Original languageEnglish
Title of host publicationProceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010
Pages215-218
Number of pages4
DOIs
Publication statusPublished - 2010 Jul 9
Event18th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2010 - Charlotte, NC, United States
Duration: 2010 May 22010 May 4

Publication series

NameProceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010

Other

Other18th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2010
CountryUnited States
CityCharlotte, NC
Period10-05-0210-05-04

Fingerprint

Pipelines
Field programmable gate arrays (FPGA)
Data storage equipment
Routers
Throughput
Experiments

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Chang, Y-K., Lin, Y. S., & Su, C. C. (2010). A high-speed and memory efficient pipeline architecture for packet classification. In Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010 (pp. 215-218). [5474045] (Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010). https://doi.org/10.1109/FCCM.2010.40
Chang, Yeim-Kuan ; Lin, Yi Shang ; Su, Cheng Chien. / A high-speed and memory efficient pipeline architecture for packet classification. Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010. 2010. pp. 215-218 (Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010).
@inproceedings{73e2c70aff7b40a5b4ef2ebd21773f1c,
title = "A high-speed and memory efficient pipeline architecture for packet classification",
abstract = "Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.",
author = "Yeim-Kuan Chang and Lin, {Yi Shang} and Su, {Cheng Chien}",
year = "2010",
month = "7",
day = "9",
doi = "10.1109/FCCM.2010.40",
language = "English",
isbn = "9780769540566",
series = "Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010",
pages = "215--218",
booktitle = "Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010",

}

Chang, Y-K, Lin, YS & Su, CC 2010, A high-speed and memory efficient pipeline architecture for packet classification. in Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010., 5474045, Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010, pp. 215-218, 18th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2010, Charlotte, NC, United States, 10-05-02. https://doi.org/10.1109/FCCM.2010.40

A high-speed and memory efficient pipeline architecture for packet classification. / Chang, Yeim-Kuan; Lin, Yi Shang; Su, Cheng Chien.

Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010. 2010. p. 215-218 5474045 (Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A high-speed and memory efficient pipeline architecture for packet classification

AU - Chang, Yeim-Kuan

AU - Lin, Yi Shang

AU - Su, Cheng Chien

PY - 2010/7/9

Y1 - 2010/7/9

N2 - Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.

AB - Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.

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

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

U2 - 10.1109/FCCM.2010.40

DO - 10.1109/FCCM.2010.40

M3 - Conference contribution

SN - 9780769540566

T3 - Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010

SP - 215

EP - 218

BT - Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010

ER -

Chang Y-K, Lin YS, Su CC. A high-speed and memory efficient pipeline architecture for packet classification. In Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010. 2010. p. 215-218. 5474045. (Proceedings - IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2010). https://doi.org/10.1109/FCCM.2010.40