Set pruning segment trees for packet classification

Yeim-Kuan Chang, Hsin Mao Chen

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

3 Citations (Scopus)

Abstract

Nowadays, multi-field packet classification is one of the most important technologies to support various services in next generation routers. In this paper, we propose a segment tree based parallel SRAM-based pipelined architecture called Set Pruning Segment Trees (SPST) for multi-dimensional packet classification. For solving the memory blowup problem, a grouping scheme called Partition by Length (PL) is used to reduce the rule duplications in SPST. Additionally, we also propose an optimization called Set Pruning Multi-way Segment Trees (SPMST) to reduce the tree level and hardware cost. The key feature of our proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables. The proposed pipelined architecture can achieve a throughput of 89.4 Gbps for minimum sized packets with dual port memory on Xilinx Virtex-5 FPGA device.

Original languageEnglish
Title of host publicationProceedings - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
Pages688-694
Number of pages7
DOIs
Publication statusPublished - 2011 Jun 3
Event25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011 - Biopolis, Singapore
Duration: 2011 Mar 222011 Mar 25

Publication series

NameProceedings - International Conference on Advanced Information Networking and Applications, AINA
ISSN (Print)1550-445X

Other

Other25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
CountrySingapore
CityBiopolis
Period11-03-2211-03-25

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Set pruning segment trees for packet classification'. Together they form a unique fingerprint.

Cite this