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

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

Abstract

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.

Key words: RFC, packet classification, decision tree, division

CLC Number:

TP393.08

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.

Figures/Tables 10

References 1

[1]	LIN C , SHAN Z G , REN F Y . Service quality of computer netwoek[M]. Beijing: Tsinghua University PressPress, 2004.
[2]	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.
[3]	万云凯, 嵩天, 刘苗苗 ,等. 流量自适应的多维度包分类方法研究[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.
[4]	肖玮, 陈性元, 包义保 ,等. 基于多级关联信号树的高效可重构网包分类方法研究[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.
[5]	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.
[6]	KNUTH D . Fundamental algorithms:sorting and searching[DB/OL]. .
[7]	TSUCHIYA P F . A search algorithm for table entries with noncontiguous wildcarding[DB/OL]. .
[8]	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.
[9]	SRINIVASAN V , SURI S , VARGHESE G . Packet classification using tuple space search[J]. Sigcomm Computer Communication Review, 1999,29(4): 135-146.
[10]	GUPTA P , MCKEOWN N . Packet classification on multiple fields[J]. Sigcomm Computer Communication Review, 1999,29(4): 147-160.
[11]	LAKSHMAN T V , STILIADIS D . High-speed policy-based packet forwarding using efficient multi-dimensional range matching[EB/OL]// .
[12]	GUPTA P , MCKEOWN N . Classifying packets with hierarchical intelligent cuttings[EB/OL]. .
[13]	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.
[14]	PAK W , BAHK S . FRFC:fast table building algorithm for recursive flow classification[J]. IEEE Communications Letters, 2010,14(12): 1182-1184.
[15]	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.
[16]	TAYLOR D E . ClassBench:a packet classification benchmark[J]. IEEE//ACM Transactions on Networking, 2007,15(3): 499-511.
[1]	林闯, 单志广, 任丰原 . 计算机网络的服务质量[M]. 北京: 清华大学出版社, 2004.

Metrics

Recommended 0

No Suggested Reading articles found!

规则	F1(3 bit)	F2(3 bit)
R1	001	001
R2	01*	0**
R3	001	100
R4	01*	100
R5	01*	10*
R6	***	0**

规则	SA	DA	SP	DP	PROT
R0	239.3.196.91/32	13.77.63.217/32	161:161	80 :65535	0x11/0xFF
R1	135.140.20.248/32	188.244.7.189/32	53 :53	42 :42	0x06/0xFF
R2	122.210.30.184/29	188.244.7.190/31	1024 :65535	514 :514	0x06/0xFF
R3	238.0.0.0/7	128.0.0.0/1	0 :65535	1024 :65535	0x11/0xFF
R4	239.235.252.28/32	201.217.36.173/32	0 :65535	5190 :5190	0x06/0xFF
R5	88.8.166.232/29	81.111.231.128/27	123 :123	0 :65535	0x06/0xFF
R6	128.0.0.0/1	56.13.197.53/32	69 :69	80 :80	0x2f/0xFF
R7	0.0.0.0/0	187.72.88.0/22	0 :65535	80 :80	0x01/0xFF
R8	0.0.0.0/1	128.71.176.0/21	0 :65535	0 :65535	0x00/0x00
…	…	…	…	…	…

Improved packet classification algorithm based on multidimensional space dynamic division and RFC

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 1

Related Articles 2

Metrics

Recommended 0

[1]	Qianxin CHEN, Renwan BI, Jie LIN, Biao JIN, Jinbo XIONG. Privacy-preserving federated learning framework with irregular-majority users [J]. Chinese Journal of Network and Information Security, 2022, 8(1): 139-150.
[2]	Xinyu ZHANG, Bingsheng ZHANG, Quanrun MENG, Kui REN. Study on privacy preserving encrypted traffic detection [J]. Chinese Journal of Network and Information Security, 2021, 7(4): 101-113.