Embodiments are described for automata models for use in deep packet inspection. Various embodiments are described for a new automata model, Overlay DFA (ODFA), which captures state replication in DFAs. Additional embodiments include combining the ODFA model with a D2FA model to provide an Overlay Delayed Input DFA (OD2FA). As the DFA model captures transition sharing, the OD2FA model captures both state replication and transition sharing. Algorithms are disclosed for efficiently constructing the OD2FA model and for implementing the OD2FA model in Ternary Content Addressable Memory (TCAM).
Please help me write a proper abstract based on the patent claims. CLAIM: 1. (ODFA algorithm) A computer-implemented method for implementing regular expression matching, comprising: receiving, by one or more processors, (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern; identifying, by one or more processors, a plurality of deterministic finite automata (DFA) state groups, each of the plurality of DFA state groups having a common nondeterministic finite automata (NFA) state and including DFA source states and DFA destination states; grouping, by one or more processors, each of the plurality of DFA state groups into overlay DFA (ODFA) super states such that replicated transitions between DFA source states grouped within the same source ODFA super state and the same DFA destination state are aggregated as a single transition between the source ODFA super state and the DFA destination state; constructing, by one or more processors, an ODFA model by replacing the plurality of DFA state groups with the plurality of OFDA super states based upon the received plurality of regular expressions; executing, by one or more processors, the plurality of regular expressions in accordance with the model of the ODFA model to identify search pattern matches within the plurality of data packets; and performing, by one or more processors, deep packet inspection on the plurality of data packets based upon identified search pattern matches. 2. (Claim 1 above gives a generic example of super state to DFA states, this clarifies that the destination state is also a super state) The computer-implemented method of claim 1, wherein the same DFA destination state is from among a plurality of common destination DFA state groups corresponding to each of the DFA source states constituting the source ODFA super state, and further comprising: grouping the plurality of common destination DFA state groups into a destination ODFA super state such that replicated transitions between (i) DFA source states constituting the source ODFA super state and (ii) the DFA destination states constituting the destination ODFA super state are aggregated as a single transition between the source ODFA super state and the destination ODFA super state. 3. (Portion of OFDA algorithm that maximizes the number of transitions that are grouped into super state transitions) The computer-implemented method of claim 1, wherein the act of grouping comprises: grouping a maximum number of DFA state groups into a plurality of OFDA super states based upon the received plurality of regular expressions. 4. (Best case scenario—every state replaced with a super state and a reduction of 50% state transitions) The computer-implemented method of claim 1, wherein a first total number of state transitions corresponding to the plurality of DFA state groups is greater than a second total number of ODFA super state transitions by a factor of 2. 5. (Implementation of super states as a TCAM entry) The computer-implemented method of claim 1, further comprising: building a ternary content addressable memory (TCAM) table from the ODFA model such that the single transition between the source ODFA super state and the DFA destination state represents a single TCAM table entry. 6. A non-transitory, tangible computer-readable medium storing machine readable instructions that, when executed by a processor, cause the processor to: receive (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern; identify a plurality of deterministic finite automata (DFA) state groups, each of the plurality of DFA state groups having a common nondeterministic finite automata (NFA) state and including DFA source states and DFA destination states; group each of the plurality of DFA state groups into overlay DFA (ODFA) super states such that replicated transitions between DFA source states grouped within the same source ODFA super state and the same DFA destination state are aggregated as a single transition between the source ODFA super state and the DFA destination state; construct an ODFA model by replacing the plurality of DFA state groups with the plurality of OFDA super states based upon the received plurality of regular expressions; execute the plurality of regular expressions in accordance with the model of the ODFA model to identify search pattern matches within the plurality of data packets; and perform deep packet inspection on the plurality of data packets based upon identified search pattern matches. 7. The non-transitory, tangible computer-readable medium of claim 6, wherein the same DFA destination state is from among a plurality of common destination DFA state groups corresponding to each of the DFA source states constituting the source ODFA super state, and further including instructions that, when executed by the processor, cause the processor to: group the plurality of common destination DFA state groups into a destination ODFA super state such that replicated transitions between (i) DFA source states constituting the source ODFA super state and (ii) the DFA destination states constituting the destination ODFA super state are aggregated as a single transition between the source ODFA super state and the destination ODFA super state. 8. The non-transitory, tangible computer-readable medium of claim 6, wherein the instructions to group each of the plurality of DFA state groups into overlay DFA (ODFA) super states further includes instructions that, when executed by the processor, cause the processor to: group a maximum number of DFA state groups into a plurality of OFDA super states based upon the received plurality of regular expressions. 9. The non-transitory, tangible computer-readable medium of claim 6, wherein a first total number of state transitions corresponding to the plurality of DFA state groups is greater than a second total number of ODFA super state transitions by a factor of 2. 10. The non-transitory, tangible computer-readable medium of claim 6, further including instructions that, when executed by the processor, cause the processor to: build a ternary content addressable memory (TCAM) table from the ODFA model such that the single transition between the source ODFA super state and the DFA destination state represents a single TCAM table entry. 11. (OD2FA model) A computer-implemented method for implementing regular expression matching, comprising: receiving, by one or more processors, (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern; identifying, by one or more processors, a plurality of default transitions between deterministic finite automata (DFA) states in a DFA transition function based upon the plurality of received regular expressions, each of the default transitions representing a plurality of common transitions between DFA states and constituting a deferment transition, constructing, by one or more processors, a delayed DFA (D2FA) model by replacing the plurality of common transitions with their corresponding default transitions; identifying, by one or more processors, a plurality of D2FA state groups within the D2FA state model, each of the plurality of D2FA state groups having a common DFA state and including D2FA source states and D2FA destination states; grouping, by one or more processors, each of the plurality of D2FA state groups into overlay D2FA (OD2FA) super states such that (i) replicated transitions between D2FA source states grouped within the same source OD2FA super state and D2FA destination states grouped within the same destination OD2FA super state are aggregated as a single transition between the source OD2FA super state and the destination OD2FA super state, and (ii) deferment transition relationships between D2FA states are represented as transitions between one or more OD2FA super states; constructing, by one or more processors, an OD2FA model by replacing the plurality of D2FA state groups with the plurality of OD2FA super states based upon the received plurality of regular expressions; executing, by one or more processors, the plurality of regular expressions in accordance with the OD2FA model to identify search pattern matches within the plurality of data packets; and performing, by one or more processors, deep packet inspection on the plurality of data packets based upon identified search pattern matches. 12. (OD2FA Construction Algorithm—previously an independent claim) The computer-implemented method of claim 11, wherein the act of constructing the OD2FA model comprises: constructing a plurality of OD2FAs from each of the plurality of regular expressions; grouping each of the plurality of OD2FAs into OD2FA pairs; constructing a second plurality of OD2FAs from the OD2FA pairs; and repeating the acts of grouping and constructing the plurality of OD2FAs from grouped OD2FA pairs to construct the OD2FA model for the plurality of regular expressions. 13. The method according to claim 11, further comprising: building a ternary content addressable memory (TCAM) table from the OD2FA model; and processing characters to be extracted from the plurality of data packets by utilizing the TCAM table to process one of the characters in a period of time. 14. The method according to claim 1, further comprising: building a ternary content addressable memory (TCAM) table from the OD2FA model; and processing the characters to be extracted from the data packets by utilizing the TCAM table to process more than one of the characters in a period of time. 15. The method according to claim 11, further comprising: storing, by one or more processors, the deferment transition relationships on a super state level as deferment transitions between one or more OD2FA super states. 16. A non-transitory, tangible computer-readable medium storing machine readable instructions that, when executed by a processor, cause the processor to: receive (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern; identify a plurality of default transitions between deterministic finite automata (DFA) states in a DFA transition function based upon the plurality of received regular expressions, each of the default transitions representing a plurality of common transitions between DFA states and constituting a deferment transition, construct a delayed DFA (D2FA) model by replacing the plurality of common transitions with their corresponding default transitions; identify a plurality of D2FA state groups within the D2FA state model, each of the plurality of D2FA state groups having a common DFA state and including D2FA source states and D2FA destination states; group each of the plurality of D2FA state groups into overlay D2FA (OD2FA) super states such that (i) replicated transitions between D2FA source states grouped within the same source OD2FA super state and D2FA destination states grouped within the same destination OD2FA super state are aggregated as a single transition between the source OD2FA super state and the destination OD2FA super state, and (ii) deferment transition relationships between D2FA states are represented as transitions between one or more OD2FA super states; construct an OD2FA model by replacing the plurality of D2FA state groups with the plurality of OD2FA super states based upon the received plurality of regular expressions; execute the plurality of regular expressions in accordance with the OD2FA model to identify search pattern matches within the plurality of data packets; and perform deep packet inspection on the plurality of data packets based upon identified search pattern matches. 17. The non-transitory, tangible computer-readable medium of claim 16, wherein the instructions to construct the OD2FA model further including instructions that, when executed by the processor, cause the processor to: construct a plurality of OD2FAs from each of the plurality of regular expressions; group each of the plurality of OD2FAs into OD2FA pairs; construct a second plurality of OD2FAs from the OD2FA pairs; and repeat the acts of grouping and constructing the plurality of OD2FAs from grouped OD2FA pairs to construct the OD2FA model for the plurality of regular expressions. 18. The non-transitory, tangible computer-readable medium of claim 16, further including instructions that, when executed by the processor, cause the processor to: build a ternary content addressable memory (TCAM) table from the OD2FA model; and process characters to be extracted from the plurality of data packets by utilizing the TCAM table to process one of the characters in a period of time. 19. The non-transitory, tangible computer-readable medium of claim 16, further including instructions that, when executed by the processor, cause the processor to: build a ternary content addressable memory (TCAM) table from the OD2FA model; and process the characters to be extracted from the data packets by utilizing the TCAM table to process more than one of the characters in a period of time. 20. The non-transitory, tangible computer-readable medium of claim 16, further including instructions that, when executed by the processor, cause the processor to: store the deferment transition relationships on a super state level as deferment transitions between one or more OD2FA super states.