Research Of Regular Expression Matching Technology Based On Two-stage Memory

With the high development of the Internet, the security problems caused by the Internet’s openness have become more and more serious. Deep packet inspection is one of the key technologies of network security, in order to detect the features of malicious information or protocols, it uses predefined rule sets to match with the payloads of packets. Regular expression matching is the primary means of deep packet inspection, but in which the matching performance and storage requirement contradict each other. The Gigabit Networks require line-speed matching, and the increasingly complex rule sets require memory with large capacity. However, most of the memories can not have both large capacity and high throughput. This contradiction brings a huge challenge to regular expression matching technology, new ideas and methods are needed to solve this problem basically.This paper proposes a matching engine with two-stage memory model by the first time. The high speed of the first-level memories can guarantee a high performance, and the big capacity of second-level memories can solve the storage problem. By combining the two kinds of memories, the engine obtains a high throughput at a low cost.The main work and contributions of this dissertation are shown as follows:1) This thesis clarifies that the throughput and capacity requirements are the main contradiction in matching, and proposes a matching method with two-stage memory by the first time. A series of simulation experiments of matching reveals that the access probabilities of states follow the Zipf distribution, which was very opportune for two-stage memory structure. 2) The state migration process in packet matching is modeled with Markov chain, and the Steady-State vector is treated as states access probabilities in theory. Furthermore, we discuss the method to compute Steady-State vector and implement it in coding. Simulation experiments show that Steady-State vector of this model can accurately describe the state access probabilities. 3) Based on the open network platform of Net Magic, a regular expression matching system with two-stage memory architecture is realized. The multi-block RAM in FPGA is configured as multi-engine, As a result, the matching speed is accelerated multi-times. The results show that the system can reach a high throughput and the storage cost reduces significantly at the same time.