research-article

Fast and scalable packet classification using perfect hash functions

Authors:

Jan KorenekAuthors Info & Claims

FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

Pages 229 - 236

https://doi.org/10.1145/1508128.1508163

Published: 22 February 2009 Publication History

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.

References

[1]

A hash function for hash table lookup. http://burtleburtle.net/bob/hash/doobs.html, December 2008.

[2]

IDT Generic Part: 75K72100. http://www.idt.com/?catID=58523&genID=75K72100, June 2008.

[3]

Netfilter: firewalling, NAT and packet managing for Linux. http://www.netfilter.org/, June 2008.

[4]

PF: The OpenBSD Packet Filter. http://www.openbsd.org/faq/pf/, June 2008.

[5]

Xilinx Virtex5 Family FPGAs. Xilinx, Inc.

[6]

N. S. Artan and H. J. Chao. Tribica: Trie bitmap content analyzer for high-speed network intrusion detection. INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 125--133, May 2007.

Digital Library

[7]

F. Baboescu, S. Singh, and G. Varghese. Packet classification for core routers: Is there an alternative to CAMs? In INFOCOM, 2003.

[8]

F. Baboescu and G. Varghese. Scalable packet classification. In SIGCOMM 01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pages 199--210, New York, NY, USA, 2001. ACM.

Digital Library

[9]

Z. J. Czech, G. Havas, and B. S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43(5):257--264, 1992.

Digital Library

[10]

S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor. Longest prefix matching using Bloom filters. In SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 201--212, New York, NY, USA, 2003. ACM.

Digital Library

[11]

S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood. Fast packet classification using Bloom filters. In ANCS 06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, pages 61--70, New York, NY, USA, 2006. ACM.

Digital Library

[12]

W. Eatherton, G. Varghese, and Z. Dittia. Tree bitmap: hardware/software IP lookups with incremental updates. SIGCOMM Computer Communication Review, 34(2):97--122, 2004.

Digital Library

[13]

S. Giordano, F. Oppedisano, G. Procissi, and F. Russo. A novel high-speed micro-flows classification algorithm based on perfect hashing and direct addressing. Global Telecommunications Conference, 2007. GLOBECOM 07. IEEE, pages 448--452, November 2007.

[14]

P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Proc. Hot Interconnects, 1999.

[15]

P. Gupta and N. McKeown. Algorithms for packet classification, 2001.

[16]

P. Gupta, B. Prabhakar, and S. P. Boyd. Near optimal routing lookups with bounded worst case performance. In INFOCOM, pages 1184--1192, 2000.

[17]

T. V. Lakshman and D. Stiliadis. High-speed policy-based packet forwarding using eficient multi-dimensional range matching. SIGCOMM Comput. Commun. Rev., 28(4):203--214, 1998.

Digital Library

[18]

H. Lee, W. Jiang, and V. K. Prasanna. Scalable High-Throughput SRAM-Based Architecture for IP Lookup Using FPGA. In FPL 08. IEEE, 2008.

[19]

J. Li, H. Liu, and K. Sollins. AFBV: a scalable packet classification algorithm. SIGCOMM Comput. Commun. Rev., 32(3):24--24, 2002.

Digital Library

[20]

Y. Lu, B. Prabhakar, and F. Bonomi. Perfect hashing for network applications. Information Theory, 2006 IEEE International Symposium on, pages 2774--2778, July 2006.

[21]

S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. In SIGCOMM 03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 213--224, New York, NY, USA, 2003. ACM.

Digital Library

[22]

H. Song and J. W. Lockwood. Eficient packet classification for network intrusion detection using FPGA. In FPGA 05: Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, pages 238--245, New York, NY, USA, 2005. ACM.

Digital Library

[23]

I. Sourdis, D. Pnevmatikatos, S. Wong, and S. Vassiliadis. A reconfigurable perfect-hashing scheme for packet inspection. Field Programmable Logic and Applications, 2005. International Conference on, pages 644--647, Aug. 2005.

[24]

V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel. Fast and scalable layer four switching. SIGCOMM Comput. Commun. Rev., 28(4):191--202, 1998.

Digital Library

[25]

D. Taylor and J. Turner. Scalable packet classification using distributed crossproducting of field labels. In IEEE INFOCOM 2005, 24th Annual Joint Conference of the IEEE Computer and Communications Societies., pages 269--280, July 2005.

[26]

D. E. Taylor and J. S. Turner. Classbench: a packet classification benchmark. IEEE/ACM Trans. Netw., 15(3):499--511, 2007.

Digital Library

Cited By

Orsak MBenes T(2021)High-speed stateful packet classifier based on TSS algorithm optimized for off-chip memories2021 24th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS)10.1109/DDECS52668.2021.9417060(151-156)Online publication date: 7-Apr-2021
https://doi.org/10.1109/DDECS52668.2021.9417060
Chang YChi T(2019)Hash-based OpenFlow Packet Classification on Heterogeneous System Architecture2019 Eleventh International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN.2019.8806091(300-305)Online publication date: Jul-2019
https://doi.org/10.1109/ICUFN.2019.8806091
Orosz PTothfalusi TVarga P(2019)FPGA-Assisted DPI Systems: 100 Gbit/s and BeyondIEEE Communications Surveys & Tutorials10.1109/COMST.2018.287619621:2(2015-2040)Online publication date: Oct-2020
https://doi.org/10.1109/COMST.2018.2876196
Show More Cited By

Index Terms

Fast and scalable packet classification using perfect hash functions
1. Hardware
  1. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors

Recommendations

Field-split parallel architecture for high performance multi-match packet classification using FPGAs
SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

Multi-match packet classification is a critical function in network intrusion detection systems (NIDS), where all matching rules for a packet need to be reported. Most of the previous work is based on ternary content addressable memories (TCAMs) which ...
Large-scale wire-speed packet classification on FPGAs
FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

Multi-field packet classification is a key enabling function of a variety of network applications, such as firewall processing, Quality of Service differentiation, traffic billing, and other value added services. Although a plethora of research has been ...
Scalable packet classification on FPGA

Multi-field packet classification has evolved from traditional fixed 5-tuple matching to flexible matching with arbitrary combination of numerous packet header fields. For example, the recently proposed OpenFlow switching requires classifying each packet ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

February 2009

302 pages

ISBN:9781605584102

DOI:10.1145/1508128

General Chair:
Paul Chow
University of Toronto, Canada
,
Program Chair:
Peter Cheung
Imperial College London, UK

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 February 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FPGA '09

Sponsor:

FPGA '09: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 22 - 24, 2009

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
665
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Orsak MBenes T(2021)High-speed stateful packet classifier based on TSS algorithm optimized for off-chip memories2021 24th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS)10.1109/DDECS52668.2021.9417060(151-156)Online publication date: 7-Apr-2021
https://doi.org/10.1109/DDECS52668.2021.9417060
Chang YChi T(2019)Hash-based OpenFlow Packet Classification on Heterogeneous System Architecture2019 Eleventh International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN.2019.8806091(300-305)Online publication date: Jul-2019
https://doi.org/10.1109/ICUFN.2019.8806091
Orosz PTothfalusi TVarga P(2019)FPGA-Assisted DPI Systems: 100 Gbit/s and BeyondIEEE Communications Surveys & Tutorials10.1109/COMST.2018.287619621:2(2015-2040)Online publication date: Oct-2020
https://doi.org/10.1109/COMST.2018.2876196
Kekely MKekely LKorenek J(2018)Memory Aware Packet Matching Architecture for High-Speed Networks2018 21st Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2018.00017(1-8)Online publication date: Aug-2018
https://doi.org/10.1109/DSD.2018.00017
Jin ZFinkel H(2018)Bob Jenkins Lookup3 Hash Function on OpenCL FPGA Platform2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8621960(4736-4741)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8621960
Kekely MKorenek J(2017)Packet Classification with Limited Memory Resources2017 Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2017.61(179-183)Online publication date: Aug-2017
https://doi.org/10.1109/DSD.2017.61
Dobai RKorenek JSekanina L(2017)Evolutionary design of hash function pairs for network filtersApplied Soft Computing10.1016/j.asoc.2017.03.00956:C(173-181)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.asoc.2017.03.009
István ZAlonso GBlott MVissers K(2015)A Hash Table for Line-Rate Data ProcessingACM Transactions on Reconfigurable Technology and Systems10.1145/26295828:2(1-15)Online publication date: 24-Mar-2015
https://dl.acm.org/doi/10.1145/2629582
Tong DZhou SPrasanna V(2015)High-Throughput Online Hash Table on FPGAProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop10.1109/IPDPSW.2015.149(105-112)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPSW.2015.149
Qu YPrasanna V(2015)Power-efficient range-match-based packet classification on FPGA2015 25th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2015.7293937(1-8)Online publication date: Sep-2015
https://doi.org/10.1109/FPL.2015.7293937
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents