## 2 Pattern-Matching Algorithms Review
### Automaton-Based Technique  
The first step for algorithms implementing the automaton-based technique is creating a finite state machine (FSM) used in the DPI process. An FSM is generated in a pattern-specific fashion before the pattern-matching process, and is employed in the matching process. An FSM consists of a group of nodes called a state, and a set of directed edges with tags that connect the nodes. There is an initial state and a series of acceptance states. Each acceptance state represents one or more patterns. The matching process starts from the initial state and the first byte of the packet payload. When a byte is read from the payload, the process proceeds to the later state according to the edge labels formed related to the current state. If the acceptance state is reached, one or more patterns are detected in the packet payload. In the automaton-based approach, the overall DPI performance highly depends on the pattern-matching efficiency, that is, the efficiency of the FSM [4].  
There are two types of FSMs--a nondeterministic finite automata (NFA) and a DFA. Figure 3 shows examples of a DFA and NFA that accept strings ending in \"101\" from the strings generated using the \(\sum\{0,1\}\) alphabet. Both FSMs are equivalent in terms of expressive power. The main difference between a DFA and NFA is that any DFA state has a single transition leading to a specific state for each character. On the other hand, any NFA state can have multiple transitions to different states for the same character. Thus, a DFA can have only one active state at any time, while an NFA can have more than one active state. As a result, a DFA has an O(1) time transaction cost while an NFA has an O(n\({}^{2}\)m) transaction cost. Here, m represents the number of REs, while n represents the average length of the RE. Accordingly, the computation required for pattern detection will be more intensive in an NFA. Also, as seen in Figure 3, there are more transitions in a DFA comparedto an NFA. Conversion from an NFA to DFA increases the number of states, resulting in memory consumption as large as O(2\({}^{\text{nm}}\)). However, memory consumption is only O(mn) for an NFA. This means more memory space is required for DPI applications, in which pattern detection is performed using the DFA structure. As a result, an NFA and DFA have opposite characteristics in their memory bandwidth requirement and computational density. A DFA requires intensive memory, whereas an NFA needs intensive computations. Most current research aims to balance storage and performance [43; 44; 45].  
(0 \(\cup\) 1)*101 can apply as an RE for the automatons shown in Figure 3. In this direction, the DPI application uses an RE which represents strings ending in 101 during the pattern-matching process. On the other hand, a DPI application that accepts a string set with predefined signatures as input employs a pattern set consisting of strings ending in 101, such as 01101, 00101, or 11101. An RE can represent a group of strings, while a string can represent only itself [4]. Because of their powerful and flexible identification capability, REs are widely used in many open-source and commercial DPI applications [46; 47]. The studies [48; 49; 50] focus on building memory-efficient architectures for the RE pattern-matching process. Furthermore, the study numbered [51]--aiming to improve pattern-matching accuracy and speed--has proposed a new RE-based DPI architecture that can handle unordered packets without network packet buffering and stream reassembly.