| Packet classification is the core technology of network service implementation.It searches the operations or tasks to be performed by packets in a set of rules according to the principle of highest priority matching.With the development of new generation network technology,the classification rules,both in scale and dimension,have increased significantly,which leads to the decline of packet classification efficiency and becomes the bottleneck of network performance.The existing methods have made some achievements in optimizing the classification efficiency.However,analyzing the current packet classification algorithm,there is still a distance from the line speed requirements,which directly affects and limits the application scalability of network devices in the new generation Internet architecture.The industry generally uses distributed computing methods to process massive data.However,there are often redundancy and conflicts between rules.Directly grouping rules will lead to problems such as rule replication and semantic inconsistency.Therefore,distributed computing methods are difficult to be directly applied to packet classification technology.Firstly,this thesis introduces the performance requirements of packet classification technology,algorithm theoretical extremum and difficulties,as well as the research status at home and abroad.Then,based on the research and analysis of the existing packet classification algorithms,a parallel packet classification algorithm based on multi-dimensional matrix is proposed to improve the speed of packet classification.The implementation process of the algorithm includes four steps:(1)Preprocessing the original rules,mapping the rules in the multi-dimensional matrix space through the rule mapping method to form a series of independent cell spaces;(2)In each node,the multi-dimensional matrix space where the rules are located is divided in turn to construct the classification decision tree;(3)Based on the number of deployed distributed computing nodes and the number of branches in each decision subtree,distributing each subtree to the computing nodes as evenly as possible;(4)According to the packet classification method based on decision tree,distributing the large-scale data packets and carrying out the classification operation.Experiments are carried out using the parallel packet classification system based on Java platform.Focusing on the classification efficiency index,a large number of packet classification experiments are carried out according to different size of classification rules,data packets and different computing nodes.It is verified that the parallel fast classification algorithm based on multidimensional matrix in this thesis has good classification performance.The algorithm is a useful attempt for the packet classification problem facing the new generation network,and it is helpful for the research and development of the field of packet classification. |
