NDLI: Tcam-based multi-match packet classification using multidimensional rule layering

Content Provider	ACM Digital Library
Author	Chang, Dao-Yuan Wang, Pi-Chung
Copyright Year	2016
Description	Author Affiliation: National Chung Hsing University, Taichung, Taiwan, ROC(Wang, Pi-Chung; Chang, Dao-Yuan)
Abstract	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 cope with the limitation, previous algorithms use extra TCAM entries or accesses, or both, to fulfill multi-match packet classification. These algorithms also reorder rules; thus, a multi-match classifier based on these algorithms cannot maintain performance for single-match packet classification. In other words, all matching rules must be yielded to determine the highest priority matching rule. In this paper, we present a TCAM-based scheme for multi-match packet classification without single-match penalty. Our scheme partitions a rule set based on range layering, which can be applied to achieve range encoding. The rule partitioning generates rule subsets which satisfy that the rules in a subset are mutually disjoint. Each rule is then tagged a bitmap for subset identification to fulfill multi-match packet classification. Two approaches, loose coupling and tight coupling, are derived with different search procedures while incorporating range encoding. Both approaches can maintain original rule order, but with different performance tradeoff. We also present a refinement which uses all available TCAM entries to improve the performance of multi-match packet classification. The experimental results show that combining range encoding with multi-match packet classification has advantages of storage efficiency and speed superiority. The capability of supporting single-match packet classification also provides better flexibility of applying different packet actions.
Starting Page	1125
Ending Page	1138
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	Geometric intersection Multi-match Packet classification Range encoding 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

Topological transformation approaches to TCAM-based packet classification

Optimal in/out TCAM encodings of ranges

Efficient gray-code-based range encoding schemes for packet classification in TCAM

Efficient Gray-Code-Based Range Encoding Schemes for Packet Classification in TCAM

Optimal In/Out TCAM Encodings of Ranges

Topological Transformation Approaches to TCAM-Based Packet Classification

Exploiting order independence for scalable and expressive packet classification

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

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

Tcam-based multi-match packet classification using multidimensional rule layering

Similar Documents

Topological transformation approaches to TCAM-based packet classification

Optimal in/out TCAM encodings of ranges

Efficient gray-code-based range encoding schemes for packet classification in TCAM

Efficient Gray-Code-Based Range Encoding Schemes for Packet Classification in TCAM

Optimal In/Out TCAM Encodings of Ranges

Topological Transformation Approaches to TCAM-Based Packet Classification

Exploiting order independence for scalable and expressive packet classification

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

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

Tcam-based multi-match packet classification using multidimensional rule layering