An Improved DFA for Fast Regular Expression Matching

Modern network devices need to perform deep packet in- spection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement reg- ular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for determinis- tic finite automata (orthogonal to previous solutions), called Delta Finite Automata (δFA), which considerably reduces states and transitions and requires a transition per char- acter only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.