This letter proposes a fast IP address lookup algorithm based on search space reduction. Prefixes are classified into three types according to the nesting relationship and a large forwarding table is partitioned into multiple small trees. As a result, the search space is reduced. The results of analyses and experiments show that the proposed method offers higher lookup and updating speeds along with reduced memory requirements.

This paper proposes a bit-split string matcher architecture for a memory-efficient hardware-based parallel pattern matching engine. In the proposed bit-split string matcher, multiple finite-state machine (FSM) tiles share match vectors to reduce the required number of stored match vectors. By decreasing the memory size for storing match vectors, the total memory requirement can be minimized.

A non-deterministic finite automaton (NFA)-based parallel string matching scheme is proposed. To parallelize the operations of NFAs, a graphic processing unit (GPU) is adopted. Considering the resource occupancy of threads and size of the shared memory, the optimized resource allocation is performed in the proposed string matching scheme. Therefore, the performance is enhanced significantly in all evaluations.

This paper proposes a hardware-based parallel pattern matching engine using a memory-based bit-split string matcher architecture. The proposed bit-split string matcher separates the transition table from the state table, so that state transitions towards the initial state are not stored. Therefore, total memory requirements can be minimized.

This paper proposes a new pattern matching architecture with multi-character processing for deep packet inspection. The proposed pattern matching architecture detects the start point of pattern matching from multi-character input using input text alignment. By eliminating duplicate hardware components using process element tree, hardware cost is greatly reduced in the proposed pattern matching architecture.

This paper proposes a circular bit-vector-mismatches (CBVM) algorithm for approximate circular string matching with k-mismatches. We develop the proposed CBVM algorithm based on the rotation feature of the circular pattern. By reusing the matching information of the previous substring, the next substring of the input string can be processed in parallel.

This paper proposes a pattern partitioning algorithm that maps multiple target patterns onto homogeneous memory-based string matchers. The proposed algorithm adopts the greedy search based on lexicographical sorting. By mapping as many target patterns as possible onto each string matcher, the memory requirements are greatly reduced.

A parallel Aho-Corasick (AC) approach, named PAC-k, is proposed for string matching in deep packet inspection (DPI). The proposed approach adopts graphic processing units (GPUs) to perform the string matching in parallel for high throughput. In parallel string matching, the boundary detection problem happens when a pattern is matched across chunks. The PAC-k approach solves the boundary detection problem because the number of characters to be scanned by a thread can reach the longest pattern length. An input string is divided into multiple sub-chunks with k characters. By adopting the new starting position in each sub-chunk for the failure transition, the required number of threads is reduced by a factor of k. Therefore, the overhead of terminating and reassigning threads is also decreased. In order to avoid the unnecessary overlapped scanning with multiple threads, a checking procedure is proposed that decides whether a new starting position is in the sub-chunk. In the experiments with target patterns from Snort and realistic input strings from DEFCON, throughputs are enhanced greatly compared to those of previous AC-based string matching approaches.