Hierarchical trie packet classification algorithm based on expectation-maximization clustering.
Hierarchical trie packet classification algorithm based on expectation-maximization clustering.
复制标题
基于期望最大化聚类的层次trie包分类算法
DOI：
10.1371/journal.pone.0181049
复制
发表时间：
2017
期刊：
影响因子：
3.7
通讯作者：
Zhao J
中科院分区：
文献类型：
--
作者：
Bi XA;Zhao J
随着计算机网络带宽的发展，迫切需要能够处理大规模规则集的报文分类算法。在现有的报文分类算法中，基于层次树的报文分类算法因其广泛的实际应用而成为报文分类研究的一个重要分支。层次Trie虽然有利于节省较大的存储空间，但也存在回溯、空节点等缺点。提出了一种新的报文分类算法--基于期望最大化聚类的层次Trie算法(HTEMC)。首先，通过将规则和数据包映射到一个二维空间，使用形式化的方法来处理包分类问题。其次，根据规则的聚合特征，利用期望最大化算法对规则进行聚类，从而形成多样化的聚类。再次，本文提出了一种基于期望最大化聚类结果的层次Trie算法。最后，本文分别进行了仿真实验和真实环境实验，比较了该算法与其他典型算法的性能，并对实验结果进行了分析。该算法中的层次TRIE结构不仅采用TRIE路径压缩消除回溯，而且解决了TRIE更新效率低的问题，大大提高了算法的性能。
With the development of computer network bandwidth, packet classification algorithms which are able to deal with large-scale rule sets are in urgent need. Among the existing algorithms, researches on packet classification algorithms based on hierarchical trie have become an important packet classification research branch because of their widely practical use. Although hierarchical trie is beneficial to save large storage space, it has several shortcomings such as the existence of backtracking and empty nodes. This paper proposes a new packet classification algorithm, Hierarchical Trie Algorithm Based on Expectation-Maximization Clustering (HTEMC). Firstly, this paper uses the formalization method to deal with the packet classification problem by means of mapping the rules and data packets into a two-dimensional space. Secondly, this paper uses expectation-maximization algorithm to cluster the rules based on their aggregate characteristics, and thereby diversified clusters are formed. Thirdly, this paper proposes a hierarchical trie based on the results of expectation-maximization clustering. Finally, this paper respectively conducts simulation experiments and real-environment experiments to compare the performances of our algorithm with other typical algorithms, and analyzes the results of the experiments. The hierarchical trie structure in our algorithm not only adopts trie path compression to eliminate backtracking, but also solves the problem of low efficiency of trie updates, which greatly improves the performance of the algorithm.
登录
查看更多内容
TW-k-Means：多视图数据的自动两级可变加权聚类算法
影响因子：
8.9
作者：
Chen, Xiaojun;Xu, Xiaofei;Ye, Yunming
通讯作者：
Ye, Yunming
影响因子：
3.7
作者：
Banerjee, Tania;Sahni, Sartaj;Seetharaman, Gunasekaran
通讯作者：
Seetharaman, Gunasekaran
影响因子：
3.7
作者：
Chang, Yeim-Kuan;Su, Cheng-Chien;Hsieh, Sun-Yuan
通讯作者：
Hsieh, Sun-Yuan
FCM 中增强的模糊分区与数据随机性
影响因子：
2
作者：
Jiang, Yizhang;Chung, Fu-Lai;Wang, Shitong
通讯作者：
Wang, Shitong
来自多个加权视图的协作模糊聚类
影响因子：
11.8
作者：
Jiang, Yizhang;Chung, Fu-Lai;Qian, Pengjiang
通讯作者：
Qian, Pengjiang