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

8 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

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A high-speed and memory efficient pipeline architecture for packet classification'. Together they form a unique fingerprint.

  • 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