NDLI: An ultra high throughput and memory efficient pipeline architecture for multi-match packet classification without TCAMs

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

CacheCard: caching static and dynamic content on the NIC

Evaluating regular expression matching engines on network and general purpose processors

A NFA-based programmable regular expression match engine

Design and performance analysis of a DRAM-based statistics counter array architecture

Weighted random oblivious routing on torus networks

Divide and discriminate: algorithm for deterministic and fast hash lookups

SPC-FA: synergic parallel compact finite automaton to accelerate multi-string matching with low memory

An ultra high throughput and memory efficient pipeline architecture for multi-match packet classification without TCAMs

Software radio: a broad change in RF communications systems design

Simplifying data path processing in next-generation routers

LaFA: lookahead finite automata for scalable regular expression detection

High throughput architecture for packet classification using FPGA

Motivating future interconnects: a differential measurement analysis of PCI latency

Design of a scalable nanophotonic interconnect for future multicores

Range Tries for scalable address lookup

Memory optimization for packet classification algorithms

Co-match: fast and efficient packet inspection for multiple flows

Networking hardware: what drives innovation?

Exploitation and threat analysis of open mobile devices

An adaptive hash-based multilayer scheduler for L7-filter on a highly threaded hierarchical multi-core server

A block-based reservation architecture for the implementation of large packet buffers

A novel 3D layer-multiplexed on-chip network

Progressive hashing for packet processing using set associative memory

ISP managed peer-to-peer

Experience with high-speed automated application-identification for network-management

Revisiting the internet hourglass: core strength vs. middle-age spread

OASis: towards extensible open-architecture services platforms

Interfacing to a virtualized network infrastructure through network service abstractions

EINIC: an architecture for high bandwidth network I/O on multi-core processors

Implementing URL-based forwarding on a network processor-based router platform

Accelerating OpenFlow switching with network processors

Parallelization of Snort on a multi-core platform

Multiplexing endpoints of HCA to achieve scalability for MPI applications: design, implementation and performance evaluation with uDAPL

Testbed for evaluating worm containment systems

Micro Secure Socket Layer (MSSL) for micro server

External storage middleware for wireless devices with limited resources

A path combinational method for multiple pattern matching

Designing high-speed packet processing tasks at arbitrary levels of abstraction: implementation and evaluation of a MIXMAP system

A lock-free, cache-efficient shared ring buffer for multi-core architectures

SANS: a scalable architecture for network intrusion prevention with stateful frontend

Hash-based routing for scalable datacenters

A novel hybrid SRAM/DRAM memory architecture for fast packet buffers

Theoretic analysis of finite automata for memory-based pattern matching

Binary search on levels using a Bloom filter for IPv6 address lookup

A mobile healthcare system using IMS and the HL7 framework

An ultra high throughput and memory efficient pipeline architecture for multi-match packet classification without TCAMs

Content Provider	ACM Digital Library
Author	Zhang, Zhuoyuan Xu, Yang Chao, H. Jonathan Liu, Zhaobo
Abstract	The emergence of new network applications like network intrusion detection system, packet-level accounting, and load-balancing requires packet classification to report all matched rules, instead of only the best matched rule. Although several schemes have been proposed recently to address the multi-match packet classification problem, most of them require either huge memory or expensive Ternary Content Addressable Memory (TCAM) to store the intermediate data structure, or suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multi-match packet classification from the complicated multi-dimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree in multiple hash tables at different stages of the pipeline, the pipeline can achieve a high throughput via the inter-stage parallel access to hash tables. To exploit further intra-stage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables with minimum overhead. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCut and B2PC schemes in classification speed by at least one order of magnitude, while with a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 19.5 Gbps and 91 Gbps.
Starting Page	189
Ending Page	198
Page Count	10
File Format	PDF
ISBN	9781605586304
DOI	10.1145/1882486.1882537
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-10-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Signature tree Tcam Hash table Packet classification
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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