Branch tire packet classification algorithm based on single-linkage clustering

As the core of network devices is the packet classification technology, the performance influences the development of computer networks. Therefore, researches on the packet classification are of principal theoretical and practical significance. This paper presents a branch trie packet classification algorithm based on the single-linkage clustering (BTSLC). The algorithm includes the preprocessing stage and the matching stage. In the preprocessing stage, packets and rules are firstly mapped to rectangular areas in the two-dimensional space by the formalization method. Then the single-linkage algorithm is used to cluster the formalized rules. In the matching stage, a branch trie is firstly constructed then the matching process is followed. The structure of the branch trie in the algorithm not only wipes out the backtracking by employing the trie path compression but also solves the trie update inefficient problem, which would enhance the performance of the algorithm to a large extent. Finally, the simulation experiments and the actual environmental experiments are carried out to evaluate our algorithm’s performances, and some algorithms are used as the comparison groups. The experimental findings indicate that our algorithm has better performance in the searching speed, memory requirement and rule update.