 |
 |
|
|
|
Abstract: Regular expression (RegEx) matching plays an important role in various network, security and database applications. Deterministic finite automata (DFA) is the preferred representation to achieve online RegEx matching in backbone networks, because of its one single pass over inputs for multiple RegExes and guaranteed performance of O(1) memory bandwidth per symbol. However, DFA may occupy prohibitive amounts of memory due to the explosive growth in its state size. In this work, we propose Series DFA (SDFA) to address the problem. The main idea is to cut a complex RegEx into several ordered and small RegExes carefully, and then concatenate their compact DFAs in series to match. Experimental results show that SDFA can achieve significant reduction in memory size at the cost of limited number of memory bandwidth.
|