A Memory-Efficient Deterministic Finite Automaton-Based Bit-Split String Matching Scheme Using Pattern Uniqueness in Deep Packet Inspection

摘要: This paper proposes a memory-efficient bit-split string matching scheme for deep packet inspection (DPI). When the number of target patterns becomes large, memory requirements engine become critical issue. The proposed reduces using uniqueness in deterministic finite automaton (DFA)-based matching. pattern grouping extracts set unique from patterns. In patterns, is not suffix any other Therefore, DFA constructed with when only one can be matched an output state. matching, multiple finite-state machine (FSM) tiles several input bit groups are adopted order to reduce stored state transitions. However, storing vectors large because each vector used identify whether its own or not. our research, applied FSM For memory-based stores match index indicate pattern. significantly decreased by matchers experimental results show that storage cost compared previous methods.