Publication Details

Fast and scalable packet classification using perfect hash functions

PUŠ Viktor and KOŘENEK Jan. Fast and scalable packet classification using perfect hash functions. In: Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays. Association for Computing Machinery. New York: Association for Computing Machinery, 2009, pp. 229-236. ISBN 978-1-60558-410-2.
Czech title
Rychlá a škálovatelná klasifikace paketů s využitím perfektních hashovacích funkcí
Type
conference paper
Language
english
Authors
Puš Viktor, Ing. (DCSY FIT BUT)
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT)
Keywords

classification, FPGA, perfect hash function

Abstract

Packet classification is an important operation for applications such as routers, firewalls or intrusion detection systems. Many algorithms and hardware architectures for packet classification have been created, but none of them can compete with the speed of TCAMs in the worst case. We propose new hardware-based algorithm for packet classification. The solution is based on problem decomposition and is aimed at the highest network speeds. A unique property of the algorithm is the constant time complexity in terms of external memory accesses. The algorithm performs exactly two external memory accesses to classify a packet. Using FPGA and one commodity SRAM chip, a throughput of 150 million packets per second can be achieved. This makes throughput of 100 Gbps for the shortest packets. Further performance scaling is possible with more or faster SRAM chips.

Published
2009
Pages
229-236
Proceedings
Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays
Series
Association for Computing Machinery
Conference
Seventeenth ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, Californi, US
ISBN
978-1-60558-410-2
Publisher
Association for Computing Machinery
Place
New York, US
BibTeX
@INPROCEEDINGS{FITPUB8952,
   author = "Viktor Pu\v{s} and Jan Ko\v{r}enek",
   title = "Fast and scalable packet classification using perfect hash functions",
   pages = "229--236",
   booktitle = "Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays",
   series = "Association for Computing Machinery",
   year = 2009,
   location = "New York, US",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-60558-410-2",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8952"
}
Files
Back to top