Research On Regular Expression Matching Algorithm For Network Packet

With the Internet becoming an integrated business platform, various new applications areemerging, information capacity is growing steady and network interface rate is increasing rapidly.As the key component of security and refined organization, packet inspection meets thechallenge of high transmit rate and memory consumption. To solve the problems above,searchers focused on high performance regular expression matching (REM) mechanisms. In thisdissertation, REM algorithms are studied mainly in three aspects: improving the matching speed,reducing the memory consumption and supporting multi-stream matching.To improve the matching speed, a novel REM algorithm MC-DFA is proposed by analyzingthe architecture that could match multi-characters per cycle. By combining the single charactertransitions in standard DFA, MC-DFA can match multi-characters per cycle which increase thematching speed significantly. To reduce the memory redundancy that introduced bymulti-characters, a deep compress algorithm for state transition table is also proposed inMC-DFA. Experimental results in FPGA show that MC-DFA can achieve6.7Gbps throughput.To reduce the memory use of DFA, a hybrid automata architecture SC-HFA which based onstate constrains is proposed by analyzing the problem that states number increased exponentiallywhile translate NFA to DFA. By dividing the NFA states set into several groups, SC-HFA putsthe states that would cause the exponential increase into different groups and leads to a hybridarchitecture which reduces the states. Simulation shows that SC-HFA could reduce75%states.To deal with the concurrent streams in reality network, a novel scheme VLSM-HFA whichbased on time-division multiplexing is proposed for REM. For multi-stream supporting,VLSM-HFA introduces distributed memory to save and load matching states of different streams.By combining the MC-DFA and SC-HFA together, VLSM-HFA can achieve high performance inmatching speed and memory consumption. With a new variable length switching method,VLSM-HFA ensures the fast switching among streams. FPGA implementation shows that with3386rules, VLSM-HFA can process131concurrent streams and achieve9.6Gbps throughput.In conclusion, with the foundation of theoretic analysis, this dissertation studies highperformance REM via algorithm design and platform evaluation. The theoretic analysis providesfundamental for researches while platform implementation evaluates the correctness of relatedalgorithms and provides reference design for other network processing systems.