The Research Of Multi-pattern Matching Algorithm In Network Firewall

The string pattern matching algorithm is a classic research direction in the field of computer science.With the increased demand for connecting more devices to internet of things,IPv4 has not fully met the needs so IPv6 emerges as the times require.IPv6 can expand further address space.But in the transformation from IPv4 to IPv6,more information is produced on the Internet.Thus,in network firewall some stricter requirements such as more and more pattern sets,continuously increased network flow,etc.show that the performance of pattern matching algorithm needs urgently improving.Firstly,this thesis introduces the background of relevant research,some classic theory of pattern matching algorithm,the classic thought and the arithmetic of search tree.After analyzing the basic AC algorithm,this thesis puts forward the improved thought of AC algorithm.According to the analysis of chapter 2,in the process of making AC algorithm,Go To list is essentially a finite-state machine.When saving Go To list,many different methods can be used.Through a large number of experiments Predecessors use the form of Trie-tree for saving the Go To list to balance saving space and working efficiency.So,the thesis will focus on improving Trie-tree to improve the efficiency of AC algorithm.Secondly,this thesis puts forward the thought of using B-tree and its different forms to improve AC algorithm.In the former description,Trie-tree is usually used for operating strings.Trie-tree saving same prefixes of strings will save more space than it saving all strings.But more resources also will be consumed If Trie-tree saves larger strings.Accordingly,in IPv6 network,the efficiency of AC algorithm can't certainly satisfy the needs of new demands.B-tree is a multi-way search tree and usually applied to database as an index so it has more branches but less hierarchies.When huge amounts of data saved on memory disk are read or written B-tree can efficiently reduce read-write times on the disk to avoid looking up frequently.Though the cost of time spent on mechanical disk needn't be considered in the process of making AC algorithm,the thought that B-tree can reduce read-write times can be applied to AC algorithm.Lastly,the thesis tests and compares with the performances of AC algorithm,AC-BM algorithm and the improved algorithm.In the course of the experiments,for the reason that IPv6 attacks were made in simulated environment,the results of the experiments will have some differences in contrast to real environment.In the results of experiments,it is clear that,on one hand,when schemas data increase the improved algorithm successfully keeps ideal performance,on the other hand,when schemas data are smaller or the length of recognition mode is limited the performance in the improved algorithm is not better than that in AC algorithm.Next,the issue should be emphasized.