An FSM State Table Compressing Method Based on Deep Packet Inspection

Recent advances in network packet processing focus on payload inspection for applications that include content-based billing, layer-7 switching and Internet security. Most of the applications in this family compile the fingerprints to finite state machine （FSM）, and then process packets based on state transition table. There are two kinds of FSM: deterministic finite automaton （DFA） and nondeterministic finite automaton （NFA）. DFA is fast but needs more memory, while NFA needs little memory but is slow. There is little time for every packet to be processed in payload inspection, so DFA is always preferred. To solve the state transition table explosion problem of regular expression pattern matching using DFA, a set intersected precode （SI-precode） method is introduced. SI-precode codes all input symbols before the conversion from regular expressions to DFA, and the space of FSM state transition table is then reduced by compressing the input symbols. Experiments based on L7-filter are employed to show that the memory space would save 87% to 97% for single pattern FSM, and 59% for multiple-pattern FSM with 50 patterns. SI-precode doee not affect the performance in the case of the architecture combining software and hardware. For pure software implementation, the performance decreases 2% to 4%.