A multi-pipeline architecture for high-speed packet classification

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

17 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)84-96
Journal / PublicationComputer Communications
Volume54
Online published18 Aug 2014
Publication statusPublished - 1 Dec 2014

Abstract

In typical algorithmic packet classification methods, the data structure is tailored for the given ruleset. It is common among published algorithmic methods that the worst case number of memory accesses per classification depends on the properties of the ruleset, such as the distribution of the address prefixes and port ranges. As a result, existing methods cannot assure constant classification rate. A novel multi-pipeline architecture for packet classification is presented in this paper. Our method has outstanding performance in both space and time. We incorporate the prefix inclusion coding scheme to achieve outstanding memory efficiency. For rulesets with 10 thousand rules, the storage cost of our method is between 16 and 24.5 bytes per rule. The hardware uses fixed-length linear pipelines. Hence, the classification rate is constant regardless of the ruleset properties. To demonstrate the feasibility of our method, the proposed architecture is implemented on a Virtex-6 FPGA and the device can achieve a classification rate of 340 million packets per second. Power dissipation of the device is about 1.43 W.

Research Area(s)

  • Packet classification, Pipelined processing, Prefix inclusion coding