NDLI: Algorithms for advanced packet classification with ternary CAMs

Please wait, while we are loading the content...

Metarouting

One more bit is enough

OpenDHT: a public DHT service and its uses

Using redundancy to cope with failures in a delay tolerant network

On the predictability of large transfer TCP throughput

Fast hash table lookup using extended bloom filter: an aid to network processing

Mining anomalies using traffic feature distributions

Walking the tightrope: responsive yet stable traffic engineering

Declarative routing: extensible routing with declarative queries

The internet and identifiers

HLP: a next generation inter-domain routing protocol

Limitations of equation-based congestion control

Meridian: a lightweight network location service without virtual coordinates

Idle sense: an optimal access method for high throughput and fairness in rate diverse wireless LANs

Improving accuracy in end-to-end packet loss measurement

Algorithms for advanced packet classification with ternary CAMs

BLINC: multilevel traffic classification in the dark

Rigorous specification and conformance testing techniques for network protocols, as applied to TCP, UDP, and sockets

Towards a global IP anycast service

Implications of autonomy for the expressiveness of policy routing

The power of explicit congestion notification

A case study in building layered DHT applications

ExOR: opportunistic multi-hop routing for wireless networks

Profiling internet backbone traffic: behavior models and applications

Dynamic pipelining: making IP-lookup truly scalable

A DoS-limiting network architecture

Policing congestion response in an internetwork using re-feedback

Towards an evolvable internet architecture

Algorithms for advanced packet classification with ternary CAMs

Content Provider	ACM Digital Library
Author	Lakshminarayanan, Karthik Venkatachary, Srinivasan Rangarajan, Anand
Abstract	Ternary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using TCAMs: reducing range expansion and multi-match classification.Our first algorithm addresses the problem of expansion of rules with range fields¿to represent range rules in TCAMs, a single range rule is mapped to multiple TCAM entries, which reduces the utilization of TCAMs. We propose a new scheme called Database Independent Range PreEncoding (DIRPE) that, in comparison to earlier approaches, reduces the worst-case number of TCAM entries a single rule maps on to. DIRPE works without prior knowledge of the database, scales when a large number of ranges is present, and has good incremental update properties.Our second algorithm addresses the problem of finding multiple matches in a TCAM. When searched, TCAMs return the first matching entry; however, new applications require either the first few or all matching entries. We describe a novel algorithm, called Multi-match Using Discriminators (MUD), that finds multiple matches without storing any per-search state information in the TCAM, thus making it suitable for multi-threaded environments. MUD does not increase the number of TCAM entries needed, and hence scales to large databases.Our algorithms do not require any modifications to existing TCAMs and are hence relatively easy to deploy. We evaluate the algorithms using real-life and random databases.
Starting Page	193
Ending Page	204
Page Count	12
File Format	PDF
ISBN	1595930094
DOI	10.1145/1080091.1080115
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-08-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Multi-match Range Ternary cams Packet classification
Content Type	Text
Resource Type	Article

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

Algorithms for advanced packet classification with ternary CAMs

TCAM-Based Packet Classification Using Multi-stage Scheme

Algorithms for advanced packet classification with ternary CAMs (2005)

Design of multi-field IPv6 packet classifiers using ternary CAMs

Packet classifiers in ternary CAMs can be smaller

High-Speed Packet Classification with Efficient Parallel Range Match for IP Network Applications

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

Field-split parallel architecture for high performance multi-match packet classification using FPGAs

Efficient multi-match packet classification with tcam.

Algorithms for advanced packet classification with ternary CAMs

Similar Documents

Algorithms for advanced packet classification with ternary CAMs

TCAM-Based Packet Classification Using Multi-stage Scheme

Algorithms for advanced packet classification with ternary CAMs (2005)

Design of multi-field IPv6 packet classifiers using ternary CAMs

Packet classifiers in ternary CAMs can be smaller

High-Speed Packet Classification with Efficient Parallel Range Match for IP Network Applications

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

Field-split parallel architecture for high performance multi-match packet classification using FPGAs

Efficient multi-match packet classification with tcam.

Algorithms for advanced packet classification with ternary CAMs