Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (02): 357-360.DOI: 10.3724/SP.J.1087.2013.00357
• Network and communications • Previous Articles Next Articles
WANG Wenyong,REN Chunmei,HUANG Lisheng
Received:
Revised:
Online:
Published:
Contact:
汪文勇,任春梅,黄鹂声
通讯作者:
作者简介:
基金资助:
Abstract: Packet classification technology has been widely used in many network services, and Hierarchical Intelligent Cuttings (HiCuts) algorithm is the most representative multi-dimensional packet classification algorithm. However, due to the uneven distribution of rules, it is difficult to divide rules into different nodes by dividing each domain equally, thus causing the depth of the decision tree increase dramatically, and the time efficiency and space efficiency of the algorithm reduced greatly. By massive statistical analysis, it is found that the rules of rule set are not uniformly distributed within their range. A non-uniform cutting technique named N-HiCuts algorithm was proposed to build decision tree algorithm on the basis of HiCuts. For the uneven distribution domain, non-uniform cutting was adopted on the basis of statistical rules. For the even distribution domain, the equal dividing function was adopted to cut, therefore the efficiency of cutting the rule set is improved. The experimental results show that the overall performance of the proposed algorithm is greatly improved.
Key words: packet classification, Hierarchical Intelligent Cuttings (HiCuts) algorithm, non-uniform cutting, decision tree〖JP〗
摘要: 数据包分类技术广泛应用于许多网络服务当中, HiCuts算法是多维包分类中最具有代表性的数据包分类算法。但由于规则集分布不均匀,通过简单地随机等分某个域很难将规则划分到不同的节点去,从而导致决策树树深度急剧增加,使算法查找的时间效率和空间效率大大降低。通过大量统计分析发现,规则集中的规则域并非均匀分布在其取值范围内,为此,在HiCuts算法的基础上提出了一种利用非均匀切割技术的N-HiCuts算法来构建决策树。算法对于分布不均匀的域依据统计规则进行非均匀切割,对规则集中分布均匀的某些域采用等分函数来进行切割,从而提高每次对规则集进行切割的效率。实验证明,该算法的整体性能得到较大的提高。
关键词: 包分类, 智能层次分割算法, 非均匀切割, 决策树
CLC Number:
TP393.0
WANG Wenyong REN Chunmei HUANG Lisheng. HiCuts classification algorithm based on non-uniform cutting[J]. Journal of Computer Applications, 2013, 33(02): 357-360.
汪文勇 任春梅 黄鹂声. 基于非均匀切割的HiCuts分类算法[J]. 计算机应用, 2013, 33(02): 357-360.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.3724/SP.J.1087.2013.00357
https://www.joca.cn/EN/Y2013/V33/I02/357