基于多维空间动态划分与RFC的包分类改进算法

陈小雨; 陆月明

doi:10.11959/j.issn.2096-109x.2018024

您当前的位置：

首页 >

文章列表页 >

基于多维空间动态划分与RFC的包分类改进算法

论文 | 更新时间：2024-06-03

- 基于多维空间动态划分与RFC的包分类改进算法
- Improved packet classification algorithm based on multidimensional space dynamic division and RFC
- 网络与信息安全学报 2018年4卷第3期页码：35-41
- 作者机构：
  
  1. 北京邮电大学信息与通信工程学院，北京 100876
  2. 可信分布式计算与服务教育部重点实验室，北京 100876
- 作者简介：
  
  [ "陈小雨（1993-），男，北京人，北京邮电大学硕士生，主要研究方向为分布式计算与信息安全。" ]
  [ "陆月明（1969-），男，江苏苏州人，北京邮电大学教授、博士生导师，主要研究方向为分布式计算、信息安全。" ]
- 基金信息：
  
  国家重点研究计划基金资助项目;The National Key R＆D Program of China(2016YFB0800302)
- DOI：10.11959/j.issn.2096-109x.2018024
  中图分类号： TP393.08
- 网络首发：2018-03，
  
  纸质出版：2018-03-15
- 稿件说明：
移动端阅览
陈小雨, 陆月明. 基于多维空间动态划分与RFC的包分类改进算法[J]. 网络与信息安全学报, 2018,4(3):35-41.

Xiaoyu CHEN, Yueming LU. Improved packet classification algorithm based on multidimensional space dynamic division and RFC[J]. Chinese Journal of Network and Information Security, 2018, 4(3): 35-41.
陈小雨, 陆月明. 基于多维空间动态划分与RFC的包分类改进算法[J]. 网络与信息安全学报, 2018,4(3):35-41. DOI： 10.11959/j.issn.2096-109x.2018024.

Xiaoyu CHEN, Yueming LU. Improved packet classification algorithm based on multidimensional space dynamic division and RFC[J]. Chinese Journal of Network and Information Security, 2018, 4(3): 35-41. DOI： 10.11959/j.issn.2096-109x.2018024.

摘要

针对 RFC 算法随着规则集规模的增加，占用的内存空间以近似指数规模骤然增大的问题，提出了一种改进型的包分类算法 HRFC（Hybrid-RFC）。该算法通过决策树完成规则集多维空间的动态划分，借助多阶段缩减树完成对每个子集的映射，从而实现包的快速高效分类。实验表明，该算法能够在保障分类速度的同时，有效地降低空间开销。

Abstract

According to the existing problem that memory usage grows exponentially with the size increase of rule set in RFC (recursive flow classification) algorithm

an improved packet classification algorithm

HRFC (Hybrid-RFC) was put forward.The new algorithm completes the dynamic division of a multidimensional space rule set by a decision tree

accomplishes the mapping of each subset with multiple phase reduction trees

so as to realize fast and efficient packet classification.The simulation results show that the new algorithm can reduce the space usage effectively while guaranteeing the performance of classification speed.

关键词

Keywords

references

林闯 , 单志广 , 任丰原 . 计算机网络的服务质量 [M ] . 北京 : 清华大学出版社 , 2004 .

LIN C , SHAN Z G , REN F Y . Service quality of computer netwoek [M ] . Beijing : Tsinghua University PressPress , 2004 .

JOSEPH D A , TAVAKOLI A , STOICA I . A policy-aware switching layer for data centers [C ] // ACM SIGCOMM 2008 Conference on Data Communication . 2008 : 51 - 62 .

万云凯 , 嵩天 , 刘苗苗 , 等 . 流量自适应的多维度包分类方法研究 [J ] . 计算机学报 , 2017 , 40 ( 7 ): 543 - 1555 .

WANG Y K , SONG T , LIU M M , et al . Study on multidimensionalpacket classification method of Flow self-adaptation [J ] . Chinese Journal of Computers , 2017 , 40 ( 7 ): 1543 - 1555 .

肖玮 , 陈性元 , 包义保 , 等 . 基于多级关联信号树的高效可重构网包分类方法研究 [J ] . 高技术通讯 , 2014 , 24 ( 9 ): 928 - 934 .

XIAO W , CHEN X Y , BAO Y B , et al . The efficient econfigurable network packet classification method based on multilevel correlation signal tree [J ] . Chinese High Technology Letters , 2014 , 24 ( 9 ): 928 - 934 .

ZANE F , NARLIKAR G , BASU A . Coolcams:power-efficient TCAMs for forwarding engines [C ] // Joint Conference of the IEEE Computer and Communications . 2003 : 42 - 52 .

KNUTH D . Fundamental algorithms:sorting and searching [DB/OL ] . https://www.researchgate.net/publication/243573812_ Fundamental_algorithms_vol_3_sorting_and_searching https://www.researchgate.net/publication/243573812_ Fundamental_algorithms_vol_3_sorting_and_searching .

TSUCHIYA P F . A search algorithm for table entries with noncontiguous wildcarding [DB/OL ] . https://www.researchgate.net/ publication/2804328_A_Search_Algorithm_for_Table_Entries_with_Non-contiguous_Wildcarding https://www.researchgate.net/ publication/2804328_A_Search_Algorithm_for_Table_Entries_with_Non-contiguous_Wildcarding .

SRINIVASAN V , VARGHESE G , SURI S , et al . Fast and scalable layer four switching [C ] // ACM Sigcomm'98 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communication . 1998 : 191 - 202 .

SRINIVASAN V , SURI S , VARGHESE G . Packet classification using tuple space search [J ] . Sigcomm Computer Communication Review , 1999 , 29 ( 4 ): 135 - 146 .

GUPTA P , MCKEOWN N . Packet classification on multiple fields [J ] . Sigcomm Computer Communication Review , 1999 , 29 ( 4 ): 147 - 160 .

LAKSHMAN T V , STILIADIS D . High-speed policy-based packet forwarding using efficient multi-dimensional range matching [EB/OL ] // https://www.researchgate.net/publication/2505564_High- Speed_Policybased_Packet_Forwarding_Using_Efficient_Multi-dimensional_Ra nge_Matching https://www.researchgate.net/publication/2505564_High- Speed_Policybased_Packet_Forwarding_Using_Efficient_Multi-dimensional_Ra nge_Matching .

GUPTA P , MCKEOWN N . Classifying packets with hierarchical intelligent cuttings [EB/OL ] . https://www.researchgate.net/publication/3215123_Classifying_packets_with_hierarchical_intelligent_cuttings https://www.researchgate.net/publication/3215123_Classifying_packets_with_hierarchical_intelligent_cuttings .

SINGH S , BABOESCU F , VARGHESE G , et al . Packet classification using multidimensional cutting [C ] // Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications . 2003 : 213 - 224 .

PAK W , BAHK S . FRFC:fast table building algorithm for recursive flow classification [J ] . IEEE Communications Letters , 2010 , 14 ( 12 ): 1182 - 1184 .

TRIVEDI U , JANGIR M L . An optimized RFC algorithm with incremental update [C ] // The International Conference on Advances in Computing,Communications and Informatics . 2014 : 120 - 127 .

TAYLOR D E . ClassBench:a packet classification benchmark [J ] . IEEE//ACM Transactions on Networking , 2007 , 15 ( 3 ): 499 - 511 .

浏览量

2101

下载量

CSCD

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

提交

工具集

关联资源

暂无数据