关键词: 包分类, 智能层次分割算法, 非均匀切割, 决策树

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〗