Research On High Throughput Regular Expression Matching Algorithm In Deep Packet Inspection

As the key technology of deep packet inspection, regular expression matching providessignificant effect on network security and reliability. Combined with the fundamental techniqueresearch task of the “New Generation Network with High Trustability” project of the NationalHigh-Tech Research and Development Program of China (863Program), this dissertation mainlyresearches on high throughput regular expression matching algorithm based on deterministicfinite automaton, in order to meet the requirement of deep packet inspection.A deterministic finite automaton and transition table are builded in the process of regularexpression matching firstly, then the input character and the current state pointer are combinedand used as the address to lookup the next state pointer in the transition table. Therefore, thenumber of input characteres which can be dealed with at one clock, and the matching speed andaccessed number of transiton table are the three factores of regular expression matching speed.The thesis researches on these aspects, and an algorithm based on Bloom filter is proposed forexceptive regular expressions firstly, then a parallel architecture for general regular expressions.Lastly, combined with D2FA algorithm, an algorithm based on TCAM is proposed to improve thematching speed of single data stream, the main contents include:1) An efficient regular expression matching algorithm based on Bloom filter is proposed.The process of regular expression matching is divided up into inspection of strings and therelationship of them to avoid state explosion cased by ambiguity of metacharacters. Thensuspicions strings are detected by multi-Bloom filter engines and it only needs the result ofrelationship matching when there is a string matching. So taking advantage of this feature,relationship matching engine can deal with strings which are not matched simultaneity toimprove the matching speed.2) A parallel architecture for high throughput DFA-based regular expression matchingalgorithm is proposed. The DFA was partitioned into head DFA and tail DFA based on theaccessed probability of states acquired from a mathematical madel, and head DFA is stored in thememory with short access time to improve the matching speed of transition table. In addition, itimproves the matching speed higly processing multi-flows simultaneity.3) A regular expression matching algorithm based on TCAM is proposed to solve thedelayed input character problem of D2FA algorithm caused by default transition. The states withdefault transition are encoded based on the features of TCAM so that they can match whenemploy the default transition. In addition, the algorithm improves the matching speed higly byrepetitively storing TCAM entries of some states shifted eight bits once.