Fast Deep Packet Inspection With a Dual Finite Automata
Deep packet inspection, in which packet payloads are matched against a large set of patterns, is an important algorithm in many networking applications. Non-deterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) are the basis of existing algorithms. However, both NFA and DFA are not ideal for real-world rule-sets: NFA has the minimum storage, but the maximum memory bandwidth; while DFA has the minimum memory bandwidth, but the maximum storage. Specifically, NFA and DFA cannot handle the presence of character sets, wildcards, and repetitions of character sets or wildcards in real-world rule-sets. In this paper, the authors propose and evaluate a dual Finite Automaton (dual FA) to address these shortcomings.