NDLI: Finding nonequivalent classifiers in boolean space to reduce tcam usage

Content Provider	ACM Digital Library
Author	Xu, Yang Chao, H. Jonathan Wei, Rihua
Copyright Year	2016
Description	Author Affiliation: New York University Polytechnic School of Engineering and Tensorcom Inc.(Chao, H. Jonathan; New york university polytechnic school of engineering (xu, Yang; Wei, Rihua))
Abstract	Packet classification is one of the major challenges today in designing high-speed routers and firewalls, as it involves sophisticated multi-dimensional searching. Ternary content addressable memory (TCAM) has been widely used to implement packet classification, thanks to its parallel search capability and constant processing speed. However, TCAMs have limitations of high cost and high power consumption, which ignite the desire to reduce TCAM usage. Recently, many works have been presented on this subject due to two opportunities. One is the well-known range expansion problem for packet classifiers to be stored in TCAM entries. The other is that there often exists redundancy among rules. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. Unlike previous schemes that compress classifiers by converting the original classifiers to semantically equivalent classifiers, the BP technique innovatively finds semantically nonequivalent classifiers to achieve compression by performing block-based permutations on the rules represented in Boolean Space. We have developed an efficient heuristic approach to find permutations for compression and have designed its hardware implementation by using a field-programmable gate array (FPGA) to preprocess incoming packets. Our experiments with ClassBench classifiers and Internet Service Provider (ISP) real-life classifiers show that the proposed BP technique can significantly reduce 31.88% TCAM entries on average, in addition to the reduction contributed by other state-of-the-art schemes.
Starting Page	968
Ending Page	981
Page Count	14
File Format	PDF
ISSN	10636692
Volume Number	24
Issue Number	2
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-04-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Classifier minimization Field-programmable gate array (FPGA) Logic optimization Packet classification Ternary content-addressable memory (TCAM)
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

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

Z-TCAM: An SRAM-based Architecture for TCAM

G-AETCAM: Gate-Based Area-Efficient Ternary Content-Addressable Memory on FPGA

TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs

PC-DUOS+: A TCAM Architecture for Packet Classifiers

PC-DUOS+: A TCAM Architecture for Packet Classifiers

FPGA Implementation of SRAM-based Ternary Content Addressable Memory

Scalable Ternary Content Addressable Memory implementation using FPGAs

Reconfigurable computing using content addressable memory for improved performance and resource usage

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

Finding nonequivalent classifiers in boolean space to reduce tcam usage

Similar Documents

Z-TCAM: An SRAM-based Architecture for TCAM

G-AETCAM: Gate-Based Area-Efficient Ternary Content-Addressable Memory on FPGA

TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs

PC-DUOS+: A TCAM Architecture for Packet Classifiers

PC-DUOS+: A TCAM Architecture for Packet Classifiers

FPGA Implementation of SRAM-based Ternary Content Addressable Memory

Scalable Ternary Content Addressable Memory implementation using FPGAs

Reconfigurable computing using content addressable memory for improved performance and resource usage

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

Finding nonequivalent classifiers in boolean space to reduce tcam usage