A deterministic finite state machine, also known as deterministic finite automata (DFA), may be generally described as a finite state machine that accepts a string of input symbols, and will either accept the string or reject the string, depending on whether the DFA is in an accepting state or a non-accepting state after the last symbol is processed.
FIG. 1 shows a prior art communication system 100 incorporating a DFA unit 125 for processing an input data packet 109 that is fed into system 100 via input/output 130. Input data packet 109, which is a component of a data stream containing many such data packets, contains two portions—a header 115 and a payload 110. The header 115 is used for control, routing and messaging functions, while the payload 110 carries information in the form of digital data. A string of data symbols (bytes) contained in header 115 can be processed first to determine what actions can be carried out upon payload 110 by one or more applications executed on system 100. The processing of header 115 can be carried out by sequentially presenting each byte contained in the string of data symbols of header 115 as address bytes for addressing content addressable memory (CAM) 105. This addressing process flow is indicated in FIG. 1 by dotted link 116, which is a symbolic representation of the actual process wherein addresses are transmitted from input/output 130 to CAM 105 via system bus 145.
CAM 105 can be configured to contain a classification list, such as an Access Control List (ACL), wherein each entry of the classification list can be stored in different address locations, and further wherein the entries conform to a row-format having two distinct fields. The first of the two fields is used for identifying a match against a set of header bytes presented to CAM 105, while the second field provides results data, in the form of various deny/permit flags for example.
In operation, when a set of bytes of header 115 is presented to CAM 105, a search is carried out to determine if any of the contents of CAM 105 match these header bytes. The set of header bytes which are presented for comparison with the ACL entry form a “key.” The key should match an ACL entry of CAM 105. Note that based on the setting of the associated wildcard mask with each CAM entry, some of the bits compared may be “don't13 care.” If a match is found in a particular row, the contents of the second field of that particular row is output as a first match result from CAM 105. The first match result is transported via link 117 and system bus 145, to processor 120, which is also communicatively coupled to system bus 145.
The match results can be processed using a software program stored in a suitable memory device, such as memory 135, and executed by processor 120. If the results derived from execution of the software program indicate that payload 110 can be accessed, digital data in the form of character strings carried in payload 110 can then be coupled into DFA unit 125 for what is known as Deep Packet Inspection (DPI). This DPI process flow is indicated in FIG. 1 by dotted link 118, which is a symbolic representation of data transmitted from input/output 130 to DFA unit 125 via system bus 145.
As can be appreciated, the use of DFA unit 125 incorporates execution of a state machine. The state machine is executed by using a state diagram that is stored in a suitable memory of system 100. For example in FIG. 1, the state diagram 155 is stored in memory 135 and provided to DFA unit 125 for execution of the state machine.
The generation of the state diagram 155 is typically carried out using a compiler 150. Compiler 150 may be implemented as a software program that is resident in a personal computer (not shown) for example. In operation, a payload data template 140 can be created for incorporation into state diagram 155 one or more decision nodes for identifying various bytes of data being carried in payload 110. Payload data template 140 is first translated into regular expressions 145 using a suitable regular language. Regular expressions 150 can then be fed into compiler 150 for generating state diagram 155, which can be stored in memory 135 to enable DFA unit 125 to execute Deep Packet Inspection of payload 110.
In summary, prior art communication system 100 incorporates two distinct procedures for processing the two portions of an input data packet 109. Header data 115 is processed via a first process using a CAM 105 in conjunction with a processor 120 that executes a software program designed for header processing; while payload data 110 is processed by DFA unit 125 using state diagram 155 that is generated from a payload data template 140. The generation of state diagram 155 involves converting payload data template 140 into regular expressions 145, which is then provided to compiler 150 in order to compile state diagram 155.