NDLI: A Multi-dimensional Progressive Perfect Hashing for High-Speed String Matching

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

Message from the General Chair

Message from the Technical Program Chairs

External Reviewers

Keynote Speakers

Ally: OS-Transparent Packet Inspection Using Sequestered Cores

400 Gb/s Programmable Packet Parsing on a Single FPGA

Chain-Based DFA Deflation for Fast and Scalable Regular Expression Matching Using TCAM

AC-Suffix-Tree: Buffer Free String Matching on Out-of-Sequence Packets

E-AHRW: An Energy-Efficient Adaptive Hash Scheduler for Stream Processing on Multi-core Servers

Predictive Model-Based Thermal Management for Network Applications

HPC-Mesh: A Homogeneous Parallel Concentrated Mesh for Fault-Tolerance and Energy Savings

Accelerating Sketch-Based Computations with GPU: A Case Study for Network Traffic Change Detection

Efficient Implementation of Dynamic Protocol Stacks

Fast and Compact Regular Expression Matching Using Character Substitution

Fast Content Distribution on Datacenter Networks

Fast Path Performance of Packet Cache Router Using Multi-core Network Processor

Inferring Packet Processing Behavior Using Input/Output Monitors

Modeling Filtering Predicates Composition with Finite State Automata

Netbench: Framework for Evaluation of Packet Processing Algorithms

Routing Optimization for Ensemble Routing

COPSS: An Efficient Content Oriented Publish/Subscribe System

A Scalability Study of Enterprise Network Architectures

FIFO Service with Differentiated Queueing

A Canonical Multicore Architecture for Network Routers

ReClick - A Modular Dataplane Design Framework for FPGA-Based Network Virtualization

Non-crypto Hardware Hash Functions for High Performance Networking ASICs

A Multi-dimensional Progressive Perfect Hashing for High-Speed String Matching

SMILER: Towards Practical Online Traffic Classification

Experiences in Co-designing a Packet Classification Algorithm and a Flexible Hardware Platform

Split: Optimizing Space, Power, and Throughput for TCAM-Based Classification

A Dynamically Adapting Network Programming Framework

Encrypted Packet Forwarding in Virtualized Networks

File-Aware P2P Traffic Classification and Management

Hacking NetCOPE to Run on NetFPGA-10G

Hardware Precomputation of Entropy for Anomaly Detection

On High QoS Constraints over Shared Resource Networks

Performance Measurement of Name-Centric Content Distribution Methods

Virtual Network Mapping with Traffic Matrices

Streaming Solutions for Fine-Grained Network Traffic Measurements and Analysis

A Passive Network Appliance for Real-Time Network Monitoring

LEISURE: A Framework for Load-Balanced Network-Wide Traffic Measurement

Publisher's Information

A Multi-dimensional Progressive Perfect Hashing for High-Speed String Matching

Content Provider	ACM Digital Library
Author	Xu, Yang Ma, Lei Chao, H. Jonathan Liu, Zhaobo
Abstract	Aho-Corasick (AC) automaton is widely used for multi-string matching in today's Network Intrusion Detection System (NIDS). With fast-growing rule sets, implementing AC automaton with a small memory without sacrificing its performance has remained challenging in NIDS design. In this paper, we propose a multi-dimensional progressive perfect hashing algorithm named P2-Hashing, which allows transitions of an AC automaton to be placed in a compact hash table without any collision. P2-Hashing is based on the observation that a hash key of each transition consists of two dimensions, namely a source state ID and an input character. When placing a transition in a hash table and causing a collision, we can change the value of a dimension of the hash key to rehash the transition to a new location of the hash table. For a given AC automaton, P2-Hashing first divides all the transitions into many small sets based on the two-dimensional values of the hash keys, and then places the sets of transitions progressively into the hash table until all are placed. Hash collisions that occurred during the insertion of a transition will only affect the transitions in the same set. The proposed P2-Hashing has many unique properties, including fast hash index generation and zero memory overhead, which are very suitable for the AC automaton operation. The feasibility and performance of P2-Hashing are investigated through simulations on the full Snort (6.4k rules) and Clam AV (54k rules) rule sets, each of which is first converted to a single AC automaton. Simulation results show that P2-Hashing can successfully construct the perfect hash table even when the load factor of the hash table is as high as 0.91.
Starting Page	167
Ending Page	177
Page Count	11
File Format	PDF
ISBN	9780769545219
DOI	10.1109/ANCS.2011.33
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-10-03
Access Restriction	Subscribed
Subject Keyword	Aho-corasick automaton perfect hash table hash collision multi-string matching
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