Detail publikačního výsledku

Fast and scalable packet classification using perfect hash functions

PUŠ, V.; KOŘENEK, J.

Originální název

Fast and scalable packet classification using perfect hash functions

Anglický název

Fast and scalable packet classification using perfect hash functions

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

Packet classification is an important operation for applications suchas routers, firewalls or intrusion detection systems. Many algorithmsand 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. Thesolution is based on problem decomposition and is aimed at the highestnetwork speeds. A unique property of the algorithm is the constant timecomplexity in terms of external memory accesses. The algorithm performsexactly two external memory accesses to classify a packet. Using FPGAand one commodity SRAM chip, a throughput of 150 million packets persecond can be achieved. This makes throughput of 100 Gbps for theshortest packets. Further performance scaling is possible with more orfaster SRAM chips.

Anglický abstrakt

Packet classification is an important operation for applications suchas routers, firewalls or intrusion detection systems. Many algorithmsand 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. Thesolution is based on problem decomposition and is aimed at the highestnetwork speeds. A unique property of the algorithm is the constant timecomplexity in terms of external memory accesses. The algorithm performsexactly two external memory accesses to classify a packet. Using FPGAand one commodity SRAM chip, a throughput of 150 million packets persecond can be achieved. This makes throughput of 100 Gbps for theshortest packets. Further performance scaling is possible with more orfaster SRAM chips.

Klíčová slova

classification, FPGA, perfect hash function

Klíčová slova v angličtině

classification, FPGA, perfect hash function

Autoři

PUŠ, V.; KOŘENEK, J.

Rok RIV

2010

Vydáno

28.05.2009

Nakladatel

Association for Computing Machinery

Místo

New York

ISBN

978-1-60558-410-2

Kniha

Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays

Edice

Association for Computing Machinery

Strany od

229

Strany do

236

Strany počet

8

URL

https://www.fit.vut.cz/research/publication/8952/

BibTex

@inproceedings{BUT33726,
  author="Viktor {Puš} and Jan {Kořenek}",
  title="Fast and scalable packet classification using perfect hash functions",
  booktitle="Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays",
  year="2009",
  series="Association for Computing Machinery",
  pages="229--236",
  publisher="Association for Computing Machinery",
  address="New York",
  isbn="978-1-60558-410-2",
  url="https://www.fit.vut.cz/research/publication/8952/"
}

Dokumenty

fpga57-pus