Detail publikace

Fast and scalable packet classification using perfect hash functions

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

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@inproceedings{BUT33726,
  author="Viktor {Puš} and Jan {Kořenek}",
  title="Fast and scalable packet classification using perfect hash functions",
  annote="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.",
  address="Association for Computing Machinery",
  booktitle="Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays",
  chapter="33726",
  edition="Association for Computing Machinery",
  howpublished="print",
  institution="Association for Computing Machinery",
  year="2009",
  month="may",
  pages="229--236",
  publisher="Association for Computing Machinery",
  type="conference paper"
}