通信学报

• • 上一篇    下一篇

基于统计的高效决策树分组分类算法

陈立南,刘 阳,马 严,黄小红,赵庆聪,魏 伟   

  1. 1. 北京邮电大学 信息网络中心,北京 100876;2. 北京信息科技大学 信息管理学院,北京 100192; 3. 国家计算机网络应急技术处理协调中心,北京 100029;4. 移动互联网安全技术国家工程实验室,北京 100876
  • 出版日期:2014-10-25 发布日期:2014-12-16
  • 基金资助:
    国家高技术研究发展计划(“863”计划)基金资助项目(2013AA014702);北京市教委科研计划:基于数据流回放和标注的数据集生成技术研究基金资助项目(KM201311232017);中央高校基本科研业务费基金资助项目(2014PTB-00-04, 2014ZD03-03);中国下一代互联网基金资助项目(CNGI-12-02-027);DNSLAB基金资助项目

Efficent-cutting packet classification algorithm based on the statistical decision tree

  • Online:2014-10-25 Published:2014-12-16

摘要: 基于决策树的分组分类算法因易于实现和高效性,在快速分组分类中广泛使用。决策树算法的基本目标是构造一棵存储高效且查找时间复杂度低的决策树。设计了一种基于规则集统计特性和评价指标的决策树算法——HyperEC 算法。HyperEC算法避免了在构建决策树过程中决策树高度过高和存储空间膨胀的问题。HyperEC算法对IP地址长度不敏感,同样适用于IPv6的多维分组分类。实验证明,HyperEC算法当规则数量较少时,与HyperCuts基本相同,但随着规则数量的增加,该算法在决策树高度、存储空间占用和查找性能方面都明显优于经典的决策树算法。

Abstract: Packet classification algorithms based on decision tree are easy to implement and widely employed in high-speed packet classification. The primary objective of constructing a decision tree is minimal storage and searching time complexity. An improved decision-tree algorithm is proposed based on statistics and evaluation on filter sets. HyperEC algorithm is a multiple dimensional packet classification algorithm. The proposed algorithm allows the tradeoff between storage and throughput during constructing decision tree. For it is not sensitive to IP address length, it is suitable for IPv6 packet classification as well as IPv4. The algorithm applies a natural and performance-guided decision-making process. The storage budget is preseted and then the best throughput is achieved. The results show that the HyperEC algorithm outperforms the HiCuts and HyperCuts algorithm, improving the storage and throughput performance and scalable to large filter sets.

No Suggested Reading articles found!