Packet Classification Technology Based On Single-linkoge And Expectation-maximization Rule Clustering

The Core equipment of computer networks is the router and firewall. Packet classification technology is the key technology of these core devices, which restricts the development of computer network bandwidth, therefore, study packet classification has important practical significance and application prospects. Existing packet classification technique is mainly divided into software-based and hardware-based technology, software-based technology mainly through the complex data structures to construct packet classification algorithm, such algorithm presence performance bottleneck; hardware-based technology to accelerate packet classification process by designing dedicated hardware architecture, such algorithm costly, not easy to expand. This paper using cluster analysis theory and packet classification aggregate characteristics will packet classification problem mapped into the space point locate problems, and design appropriate packet classification algorithms to improve the performance of packet classification. For FAQs existing packet classification algorithms exist, the article mainly does the following work:(1) Proposed a packet Classification problem formal method based on geometric space. The method first will the data packets and rules which in the rule base mapped into the space rectangular area, and secondly to take the center of the rectangular area on behalf of the packet or rules, packet classification problems will eventually be transformed into the space the point and the point distance problem. It’s shown that the use of the rule base of the methods is easy to cluster analysis, and to achieve efficient matching of the data packets and the rule base.(2) Proposed a branch of the tree packet classification algorithm based on single-linkoge clustering. The algorithm is divided into two stages. First, the pre-processing stage, the use of packet Classification problem formal method will the data packets and rules which in the rule base mapped into the space point and then using a single-linkoge algorithm for clustering formalized rules forming a plurality of clusters; second, packet matching stage, constructed in accordance with the existing cluster tree branch and matching process completed packet. Experimental results show that this method match the high efficiency packet, packet classification with high accuracy, is a rule base to support large-scale and efficient packet classification algorithms.(3) Proposed a hierarchical Trie algorithm for packet classification based on expectation-maximization clustering.Firstly, the use of packet Classification problem formal method will the data packets and rules which in the rule base mapped into the space point and then using Expectation-Maximization algorithm for clustering formalized rules forming a plurality of clusters;finally constructed in accordance with the existing cluster the hierarchical tree and matching process completed packet.The algorithm of the hierarchical Trie structure not only adopted Terry path compression eliminates backtracking, but also to solve the difficult problem of trie update, greatly improved the performance of the algorithm.