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

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

doi:10.3969/j.issn.1000-436x.2014.z1.012

您当前的位置：

首页 >

文章列表页 >

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

网络新技术及其应用 | 更新时间：2024-06-05

- 基于统计的高效决策树分组分类算法
- Efficent-cutting packet classification algorithm based on the statistical decision tree
- 通信学报 2014年35卷第Z1期页码：58-64
- 作者机构：
  
  1. 北京邮电大学信息网络中心，北京 100876
  2. 北京信息科技大学信息管理学院，北京 100192
  3. 国家计算机网络应急技术处理协调中心，北京 100029
  4. 移动互联网安全技术国家工程实验室，北京 100876
- 作者简介：
  
  [ "陈立南（1972-），女，黑龙江勃利人，北京邮电大学博士生，北京信息科技大学副教授，主要研究方向为新一代互联网关键技术等。" ]
  [ "刘阳（1978-），男，辽宁营口人，国家计算机网络与应急技术处理协调中心工程师，主要研究方向为信息安全。" ]
  [ "马严（1955-），男，北京人，北京邮电大学教授、博士生导师，主要研究方向为基于TCP/IP网络的网络管理技术、网络安全技术、移动 IP 技术、IPv6 技术及其应用。" ]
  [ "黄小红（1978-），女，广东河源人，博士，北京邮电大学信息网络中心主任，主要研究方向为下一代互联网关键技术。" ]
  [ "赵庆聪（1978-），女，山西祁县人，博士，北京信息科技大学副教授，主要研究方向为信息安全、信息管理。" ]
  [ "魏伟（1989-），男，湖北宜昌人，北京邮电大学硕士生，主要研究方向为 IPv6数据分组分类算法。" ]
- 基金信息：
  
  国家高技术研究发展计划（“863”计划）基金资助项目(2013AA014702);中央高校基本科研业务费基金资助项目(2014PTB-00-04);中央高校基本科研业务费基金资助项目(2014ZD03-03);中国下一代互联网基金资助项目(CNGI-12-02-027)
- DOI：10.3969/j.issn.1000-436x.2014.z1.012
  中图分类号： TP393.03
- 网络出版日期：2014-10，
  
  纸质出版日期：2014-10-25
- 稿件说明：
移动端阅览
陈立南, 刘阳, 马严, 等. 基于统计的高效决策树分组分类算法[J]. 通信学报, 2014,35(Z1):58-64.

Li-nan CHEN, Yang LIU, Yan MA, et al. Efficent-cutting packet classification algorithm based on the statistical decision tree[J]. Journal on communications, 2014, 35(Z1): 58-64.
陈立南, 刘阳, 马严, 等. 基于统计的高效决策树分组分类算法[J]. 通信学报, 2014,35(Z1):58-64. DOI： 10.3969/j.issn.1000-436x.2014.z1.012.

Li-nan CHEN, Yang LIU, Yan MA, et al. Efficent-cutting packet classification algorithm based on the statistical decision tree[J]. Journal on communications, 2014, 35(Z1): 58-64. DOI： 10.3969/j.issn.1000-436x.2014.z1.012.

摘要

摘要：基于决策树的分组分类算法因易于实现和高效性，在快速分组分类中广泛使用。决策树算法的基本目标是构造一棵存储高效且查找时间复杂度低的决策树。设计了一种基于规则集统计特性和评价指标的决策树算法——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.

关键词

Keywords

references

HYAFIL L , RIVEST R L . Constructing optimal binary decision trees is NP-complete [J ] . Inf Process Lett , 1976 ,( 5 ): 15 - 17 .

MURPHY O J , MCCRAW R L . Designing storage efficient decision trees [J ] . IEEE Transaction on Computers , 1991 , 40 ( 3 ): 315 - 320 .

WOO T Y C . A modular approach to packet classification:algorithms and results [A ] . IEEE International Conference on Computer Communications [C ] . 2000 . 1213 - 1222 .

GUPTA P , MCKEOWN N . Packet classification using hierarchical intelligent cuttings [A ] . IEEE High-Performance Interconnects [C ] . 1999 . 34 - 41 .

SINGH S , BABOESCU F , VARGHESE G , et al . Packet classification using multidimensional cutting [A ] . ACM Special Interest Group on Data Communication [C ] . 2003 . 213 - 224 .

TAYLOR D E , TURNER J S . ClassBench:a packet classification benchmark [A ] . IEEE International Conference on Computer Communications [C ] . 2005 . 2068 - 2079 .

SONG H Y , TURNER J S . ABC:adaptive binary cuttings for multidimensional packet classification [J ] . IEEE Transactions on Networking , 2013 , 21 ( 1 ): 98 - 109 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

高效的决策树隐私分类服务协议

基于BCP的联合委托学习模型及协议

基于信息熵的匹配域裁剪算法

基于认知自选择决策树的垂直切换方法研究

基于决策树的P2P节点识别技术研究