Research On Storage Optimization Of High-Speed Rule Matching Algorithms

With the rapid increasing of Internet transmission bandwidth and application types becomemore and more various, current network control devices are facing high-capacity rule storageneeds, how to realize storage optimization under the premise of guaranteeing the systemperformance is an issue faced by this project. Traditional rule matching algorithms achieve highmatching speed at the cost of quite high memory consumption, can’t satisfy the demand oflarge-scale rule matching in high-speed network. Combined with the―Uniform Security Controland Management Network for Three Networks Convergence‖project of the National863Program, this dissertation comprehensively analyzes and summarizes the current researches ontypical rule matching algorithms. From the perspective of how to realize large-capacity rulesmatching in high-speed network, it commits itself to study the matching and implementationmethods of pattern and regular expression rules respectively. Its main contributions are outlinedas follows:Analyze the basic theorem of typical rule matching algorithms in detail, make acomprehensive analysis and comparison from the complexity of time and storage, aswell as the difficulty in implementation; point out the advantages and existent problemsof these rule matching algorithms, direct the way to optimize storage structure andimplement the algorithms.Aiming at traditional TCAM-based pattern matching algorithms could not supportlarge-capacity pattern matching, this paper proposes an efficient multi-pattern matchingalgorithm based on dual state coding (DSC-PM), it takes the advantages of low spacecomplexity in NFA and high-speed parallel comparing ability of TCAM, uses thekeywords prefilter to accelerate the disposing process, then constructs the failure treeby reversing the failure transitions to encode the states so as to eliminate the failuretransitions, improves the rule capacity that the algorithm supports. Through thetheoretical analysis and simulation, DSC-PM not only can decrease memory consuminglargely, support large scale pattern matching，but also can provide high searching speedand scalability.Aiming at the state space explosion problem during regular expression matching withDFA in high-speed network, an efficient regular expression matching algorithm basedspecial automata m-HFA(M-REM) has been proposed. It deeply analyzes theconversion relation between two finite state automatas, splits the active statescombination in NFA with a heuristic method, and constructs a special automata m-HFA with several but bounded concurrent active states to finish matching. Theoreticalanalysis and simulation results show: M-REM not only can resolve the state explosionproblem when implementing large scale regular expressions matching, but also canguarantee stable performance in worse case.Combined with the project demand，an integrative deep rule matching engine forhigh-speed network is designed in this paper. This engine adopts the framework ofsoftware and hardware coordination, operating plane and data plane partitioned toimprove the flexibility and scalability of system, and it can both support the pattern andregular expression inspection at line speed. Based on such structure, this dissertationafterwards describes the entry structure of TCAM and several different SRAMs, thestructure of state storage and the matching structure in detail. Performance analysis andexperimental results validate the proposed scheme.