基于独立规则集位提取的包分类压缩方法

doi:10.11772/j.issn.1001-9081.2018010069

计算机应用 ›› 2018, Vol. 38 ›› Issue (8): 2375-2380.DOI: 10.11772/j.issn.1001-9081.2018010069

基于独立规则集位提取的包分类压缩方法

王孝龙, 刘勤让, 林森杰, 黄雅静

国家数字交换系统工程技术研究中心, 郑州 450002

收稿日期:2018-01-11 修回日期:2018-04-09 出版日期:2018-08-10 发布日期:2018-08-11
通讯作者: 王孝龙
作者简介:王孝龙(1993-),男,河南民权人,硕士研究生,主要研究方向:协议解析、数据包处理;刘勤让(1975-),男,河南睢县人,研究员,博士,主要研究方向:宽带信息网络、芯片系统设计;林森杰(1993-),男,广东汕头人,硕士研究生,主要研究方向:拟态安全;黄雅静(1984-),女,湖南长沙人,博士,助理研究员,主要研究方向:信号处理。
基金资助:
国家科技重大专项资助项目（2016ZX01012101）；国家自然科学基金资助项目（61572520，61521003）。

Compression method based on bit extraction of independent rule sets for packet classification

WANG Xiaolong, LIU Qinrang, LIN Senjie, Huang Yajing

National Digital Switching System Engineering & Technological Research Center, Zhengzhou Henan 450002, China

Received:2018-01-11 Revised:2018-04-09 Online:2018-08-10 Published:2018-08-11
Supported by:
This work is partially supported by the National Science and Technology Major Project (2016ZX01012101), the National Natural Science Foundation of China (61572520, 61521003).

摘要/Abstract

摘要： 针对当前互联网中多匹配域流表规模不断膨胀、匹配宽度不断增大，导致硬件存储压力过大的问题，提出了一种基于独立规则子集位提取（BEIS）的压缩方案。首先，根据多匹配域之间的逻辑关系进行匹配域合并，从而减少匹配域个数、减小流表位宽；其次，对合并后的规则集进行独立规则子集分割，将分割后的子集进行可区分的位提取，从而使用部分位完成匹配查找功能，进一步缩减所用的三态内容寻址寄存器（TCAM）空间；最后，提出了实现该方案的硬件查找架构。仿真结果表明，对于OpenFlow流表，该方案在一定的时间复杂度下，比匹配域裁剪（FT）方案减少了20%的存储空间；另外，对于实际应用中常见的访问控制列表、防火墙等包分类规则集，可实现20%到40%的压缩比率。

关键词: 包分类, OpenFlow, 多匹配域条目, 独立规则集, 位提取

Abstract: The continuous expansion in scale of multi-field entries and the growing increase in bit-width bring heavy storage pressure in hardware on the Internet. In order to solve this problem, a compression method based on Bit Extraction of Independent rule Subsets (BEIS) was proposed. Firstly, some fields were merged based on the logical relationships among multiple match fields, thus reducing the number of match fields and the width of flow tables. Secondly, with the division of independent rule subsets for the merged rule set, some differentiate bits in the divided subsets were extracted to achieve the matching and searching function, further reducing the used Ternary Content Addressable Memory (TCAM) space. Finally, the lookup hardware architecture of this method was put forward. Simulation results show that, with certain time complexity, the storage space of the proposed method can be reduced by 20% compared with Field Trimmer (FT) in OpenFlow flow table; in addition, for common packet classification rule sets such as access control list and firewall in practical application, the compression ratio of 20%-40% can be achieved.

Key words: packet classification, OpenFlow, multi-field entry, independent rule set, bit extraction

中图分类号:

TP393

王孝龙, 刘勤让, 林森杰, 黄雅静. 基于独立规则集位提取的包分类压缩方法[J]. 计算机应用, 2018, 38(8): 2375-2380.

WANG Xiaolong, LIU Qinrang, LIN Senjie, Huang Yajing. Compression method based on bit extraction of independent rule sets for packet classification[J]. Journal of Computer Applications, 2018, 38(8): 2375-2380.

参考文献

[1] McKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow:enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2):69-74.
[2] 马腾,陈庶樵,张校辉,等.基于规则集划分的多决策树报文分类算法[J].计算机应用,2013,33(9):2450-2454. (MA T, CHEN S Q, ZHANG X H, et al. Multiple decision-tree packet classification algorithm based on rule set partitioning[J]. Journal of Computer Applications, 2013, 33(9):2450-2454.)
[3] SONG H, TURNER J S. ABC:adaptive binary cuttings for multidimensional packet classification[J]. IEEE/ACM Transactions on Networking, 2013, 21(1):98-109.
[4] VAMANAN B, VOSKUILEN G, VIJAYKUMAR T N. EffiCuts:optimizing packet classification for memory and throughput[C]//Proceedings of the ACM SIGCOMM 2010 Conference. New York:ACM, 2010:207-218.
[5] 陈正虎,兰巨龙,黄万伟,等.一种基于Bloom-filter表项压缩的TCAM业务识别算法[J].电子与信息学报,2011,33(9):2212-2218. (CHEN Z H, LAN J L, HUANG W W, et al. A TCAM service identification algorithm based on access compression using bloom-filter[J]. Journal of Electronics & Information Technology, 2011, 33(9):2212-2218).
[6] SUN P, LAN J, WANG P, et al. RFC:range feature code for TCAM-based packet classification[J]. Computer Networks, 2017, 118:54-61.
[7] MEINERS C R, LIU A X, TORNG E. Bit weaving:a non-prefix approach to compressing packet classifiers in TCAMs[J]. IEEE/ACM Transactions on Networking, 2012, 20(2):488-500.
[8] KOGAN K, NIKOLENKO S I, ROTTENSTREICH O, et al. Exploiting order independence for scalable and expressive packet classification[J]. IEEE/ACM Transactions on Networking, 2016, 24(2):1251-1264.
[9] SCHIFF L, AFEK Y, BREMLER-BARR A. ORange:multi field openflow based range classifier[C]//ANCS 2015:Proceedings of the 11th ACM/IEEE Symposium on Architectures for Networking & Communications Systems. Washington, DC:IEEE Computer Society, 2015:63-73.
[10] GE J, CHEN Z, WU Y, et al. H-SOFT:a heuristic storage space optimisation algorithm for flow table of OpenFlow[J]. Concurrency & Computation Practice & Experience, 2015, 27(13):3497-3509.
[11] 孙鹏浩,兰巨龙,陆肖元,等. 一种基于匹配域裁剪的包分类规则集压缩方法[J]. 电子与信息学报, 2017, 39(5):1185-1192. (SUN P H, LAN J L, LU X Y, et al. Field-trimming compression model for rule set of packet classification[J]. Journal of Electronics & Information Technology, 2017, 39(5):1185-1192.)
[12] DEERING S, HINDEN R. Request For Comments:2460[EB/OL].[2017-12-10]. https://www.rfc-editor.org/rfc/pdfrfc/rfc2460.txt.pdf.
[13] TAYLOR D E, TURNER J S. ClassBench:a packet classification benchmark[C]//IEEE INFOCOM 2005:Proceedings of the 2005 International Conference on Computer Communications. Piscataway, NJ:IEEE, 2005:2068-2079.

基于独立规则集位提取的包分类压缩方法

Compression method based on bit extraction of independent rule sets for packet classification

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	王明芬. 软件定义无线局域网的切换接入机制[J]. 计算机应用, 2020, 40(9): 2706-2711.
[2]	黄鑫, 李芹, 杨贵, 竹之涵, 李文猛, 施玉祥. 基于软件定义网络的智能变电站网络架构设计[J]. 计算机应用, 2017, 37(9): 2512-2517.
[3]	何倩, 胡启伟, 王勇, 阳鑫磊, 刘曙铭. 基于软件定义网络的反饱和分组云负载均衡[J]. 计算机应用, 2016, 36(6): 1520-1525.
[4]	刘艺, 张红旗, 代向东, 雷程. 面向OpenFlow网络的访问控制规则自动实施方案[J]. 计算机应用, 2015, 35(11): 3270-3274.
[5]	汪文勇任春梅黄鹂声. 基于非均匀切割的HiCuts分类算法[J]. 计算机应用, 2013, 33(02): 357-360.
[6]	余涛吴卫东. 基于多核处理器的L7-Filter规则匹配改进算法[J]. 计算机应用, 2012, 32(03): 609-613.
[7]	毕夏安谢高岗张大方. 基于规则集压缩的高效包分类算法[J]. 计算机应用, 2010, 30(11): 3053-3055.
[8]	潘登张大方谢鲲张继. 一种基于折半层次搜索的包分类算法[J]. 计算机应用, 2009, 29(2): 500-502.
[9]	余磊邓亚平王江波 . 基于层次智能切割的IP分类算法[J]. 计算机应用, 2006, 26(7): 1557-1559.