NDLI: Packet classifiers in ternary CAMs can be smaller

Content Provider	ACM Digital Library
Author	Wang, Jia Shukla, Ashutosh Agrawal, Dheeraj Dong, Qunfeng Banerjee, Suman
Abstract	Serving as the core component in many packet forwarding, differentiating and filtering schemes, packet classification continues to grow its importance in today's IP networks. Currently, most vendors use Ternary CAMs (TCAMs) for packet classification. TCAMs usually use brute-force parallel hardware to simultaneously check for all rules. One of the fundamental problems of TCAMs is that TCAMs suffer from range specifications because rules with range specifications need to be translated into multiple TCAM entries. Hence, the cost of packet classification will increase substantially as the number of TCAM entries grows. As a result, network operators hesitate to configure packet classifiers using range specifications. In this paper, we optimize packet classifier configurations by identifying semantically equivalent rule sets that lead to reduced number of TCAM entries when represented in hardware. In particular, we develop a number of effective techniques, which include: trimming rules, expanding rules, merging rules, and adding rules. Compared with previously proposed techniques which typically require modifications to the packet processor hardware, our scheme does not require any hardware modification, which is highly preferred by ISPs. Moreover, our scheme is complementary to previous techniques in that those techniques can be applied on the rule sets optimized by our scheme. We evaluate the effectiveness and potential of the proposed techniques using extensive experiments based on both real packet classifiers managed by a large tier-1 ISP and synthetic data generated randomly. We observe significant reduction on the number of TCAM entries that are needed to represent the optimized packet classifier configurations.
Starting Page	311
Ending Page	322
Page Count	12
File Format	PDF
ISSN	01635999
DOI	10.1145/1140103.1140313
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	34
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Ternary cam Semantic equivalence Packet classification
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Packet classifiers in ternary CAMs can be smaller

Algorithms for advanced packet classification with ternary CAMs

ClassiPl: an architecture for fast and flexible packet classification

Packet classification in large ISPs:design and evaluation of decision tree classifiers

Design of multi-field IPv6 packet classifiers using ternary CAMs

Packet classifiers in ternary CAMs can be smaller (2006)

Bit weaving: a non-prefix approach to compressing packet classifiers in TCAMs

Topological transformation approaches to optimizing TCAM-based packet classification systems

Bit Weaving: A Non-Prefix Approach to Compressing Packet Classifiers in TCAMs

Packet classifiers in ternary CAMs can be smaller

Similar Documents

Packet classifiers in ternary CAMs can be smaller

Algorithms for advanced packet classification with ternary CAMs

ClassiPl: an architecture for fast and flexible packet classification

Packet classification in large ISPs:design and evaluation of decision tree classifiers

Design of multi-field IPv6 packet classifiers using ternary CAMs

Packet classifiers in ternary CAMs can be smaller (2006)

Bit weaving: a non-prefix approach to compressing packet classifiers in TCAMs

Topological transformation approaches to optimizing TCAM-based packet classification systems

Bit Weaving: A Non-Prefix Approach to Compressing Packet Classifiers in TCAMs

Packet classifiers in ternary CAMs can be smaller