Efficient packet classification algorithm based on entropy
Authors: 
Michal Kajan, Jan KořenekAuthors Info & Claims
Michal Kajan, Jan KořenekAuthors Info & ClaimsArticle No.: 11, Pages 1 - 2
Abstract
This paper deals with packet classification in high-speed networks. It introduces a novel method for packet classification based on the amount of information stored in the ruleset. Basic principles of the algorithm based on the effort to reduce the amount of the necessary memory space and number of computational steps are presented together with analysis of the input rulesets.
References
[1]
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.
[2]
P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Proc. Hot Interconnects, 1999.
[3]
V. Puš and J. Kořenek. Fast and scalable packet classification using perfect hash functions. In FPGA '09: Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, pages 229--236, New York, NY, USA, 2009. ACM.
[4]
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.
[5]
V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel. Fast and scalable layer four switching. SIGCOMM Comput. Commun. Rev., 28(4):191--202, 1998.
[6]
D. Taylor and J. Turner. Scalable packet classification using distributed crossproducing of field labels. In IEEE INFOCOM 2005, 24th Annual Joint Conference of the IEEE Computer and Communications Societies., pages 269--280, July 2005.
[7]
D. E. Taylor and J. S. Turner. Classbench: a packet classification benchmark. IEEE/ACM Trans. Netw., 15(3):499--511, 2007.
Index Terms
- Efficient packet classification algorithm based on entropy
Recommendations
Scalable packet classification through rulebase partitioning using the maximum entropy hashing
In this paper, we introduce a new packet classification algorithm, which can substantially improve the performance of a classifier. The algorithm is built on the observation that a given packet matches only a few rules even in large classifiers, which ...
A Decomposition-Based Approach for Scalable Many-Field Packet Classification on Multi-core Processors
As a kernel function in network routers, packet classification requires the incoming packet headers to be checked against a set of predefined rules. There are two trends for packet classification: (1) to examine a large number of packet header fields, ...
Tcam-based multi-match packet classification using multidimensional rule layering
Ternary content addressable memory (TCAM) has superior performance for single-match packet classification but not the case for multi-match packet classification. The limitation is caused by TCAM architecture that reports only the first matching rule. To ...
Comments
Information & Contributors
Information
Published In
October 2010
244 pages
ISBN:9781450303798
DOI:10.1145/1872007
- General Chair:
- Bill Lin,
- Program Chairs:
- Jeffrey Mogul,
- Ravishankar Iyer
Copyright © 2010 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
- SIGCOMM: ACM Special Interest Group on Data Communication
- SIGARCH: ACM Special Interest Group on Computer Architecture
- IEEE-CS\TCCA: TC on Computer Arhitecture
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 October 2010
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Research Plan No. MSM
- Vysokého Učení Technického v Brně
Conference
ANCS '10: Symposium on Architecture for Networking and Communications Systems
October 25 - 26, 2010
California, La Jolla
Acceptance Rates
Overall Acceptance Rate 88 of 314 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 156Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 14 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in