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

Li-nan CHEN; Yang LIU; Yan MA; Xiao-hong HUANG; Qing-cong ZHAO; Wei WEI

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

您当前的位置：

首页 >

文章列表页 >

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

New network technology and its application | 更新时间：2024-06-05

- Efficent-cutting packet classification algorithm based on the statistical decision tree
- Journal on Communications Vol. 35, Issue Z1, Pages: 58-64(2014)
- 作者机构：
  
  1. 北京邮电大学信息网络中心，北京 100876
  2. 北京信息科技大学信息管理学院，北京 100192
  3. 国家计算机网络应急技术处理协调中心，北京 100029
  4. 移动互联网安全技术国家工程实验室，北京 100876
- 作者简介：
- 基金信息：
  
  The National High Technology Research and Development Program of China(863 Program)(2013AA014702);Fundamental Research Funds for the Central Universities(2014PTB-00-04);Fundamental Research Funds for the Central Universities(2014ZD03-03);China Next Generation Internet Project(CNGI-12-02-027)
- DOI：10.3969/j.issn.1000-436x.2014.z1.012
  CLC： TP393.03
- Online First：2014-10，
  
  Published：25 October 2014
- 稿件说明：
移动端阅览
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：

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 .

Views

689

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient privacy-preserving decision tree classification protocol

BCP-based joint delegation learning model and protocol

Information entropy based match field cutting algorithm

Vertical handoff research based on cognitive self-selection decision tree

Implementation of P2P nodes detection based on decision tree

Related Author

Haojin ZHU

Qingqi PEI

Jiayi PENG

Lichuan MA

Tao FENG

Weijie TAN

Youliang TIAN

Kang XIANG

Related Institution

The State Key Laboratory of Integrated Services Networks, Xidian University

Shaanxi Key Laboratory of Blockchain and Secure Computing

The Department of Computer Science and Engineering, Shanghai Jiao Tong University

Institute for Metrology and Calibration of Guizhou

State Key Laboratory of Public Big Data, College of Computer Science and Technology, Guizhou University

AI问答

⁰