运用差分演化算法实现包匹配多层核心基的提取

doi:10.11772/j.issn.1001-9081.2017.03.777

计算机应用 ›› 2017, Vol. 37 ›› Issue (3): 777-781.DOI: 10.11772/j.issn.1001-9081.2017.03.777

运用差分演化算法实现包匹配多层核心基的提取

王则林^1,2, 郝水侠³

1. 南通大学杏林学院, 江苏南通 226000;
2. 南通大学计算机科学与技术学院, 江苏南通 226000;
3. 江苏师范大学数学与统计学院, 江苏徐州 221116

收稿日期:2016-08-11 修回日期:2016-10-24 出版日期:2017-03-10 发布日期:2017-03-22
通讯作者: 郝水侠
作者简介:王则林(1973-),男,江苏南通人,副教授,博士,主要研究方向:网络安全、智能计算;郝水侠(1973-),女,江苏徐州人,副教授,博士,主要研究方向:并行算法、智能算法。
基金资助:
国家自然科学基金资助项目（61070008）；南通市科技局应用研究项目（BK2014057）。

Extracting kernel basis using differential evolution algorithm for packet matching

WANG Zelin^1,2, HAO Shuixia³

1. Xinglin College, Nantong University, Nantong Jiangsu 226000, China;
2. School of Computer Science and Technology, Nantong University, Nantong Jiangsu 226000, China;
3. School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou Jiangsu 221116, China

Received:2016-08-11 Revised:2016-10-24 Online:2017-03-10 Published:2017-03-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61070008), the Application Research Project of Nantong Science and Technology Bureau (BK2014057).

摘要/Abstract

摘要： 针对网络防火墙、路由器等设备中包匹配的速度问题，提出运用差分演化算法实现包匹配多层核心基的提取。该算法运用多层基础基描述包的多层特征，在每层中分别运用差分演化算法进行比特基和实体基的提取，运用平均自信息和平均互信息量衡量基础基选择的优劣。这种方法可以根据规则库实际规模选择提取比特实体基的层数，非常适应规则库的增长。实验结果表明，所提算法在时间效率、空间效率方面相对于已有的递归数据流匹配算法和基于实数编码的差分演化的包匹配算法，综合性能最优。

关键词: 包匹配, 差分演化算法, 平均自信息, 平均互信息

Abstract: Aiming at the speed of packet matching in network firewall, router and other equipment, a differential evolution algorithm was proposed to extract the multi-layer core base of package matching. The multi-layer foundation was used to describe the multi-layer characteristics of the packet. In each layer, the bit basics and entitative basics were extracted using differential evolution algorithm and average self-information and the average mutual information were used to evaluate the quality of kernel basis. This method was adapt to select the number of layers of the extracted entity base according to the actual size of rule base, which is very suitable for the growth of rule base. The experimental results show that The proposed algorithm is the first known algorithm to be applied to packet matching efficiently. Compared with RFC (Recursive Flow Classification) algorithm and RDEPM (Real-based Differential Evolution Packet Matching) algorithm, the performance of the proposed algorithm is superior in terms of time efficiency and space efficiency.

Key words: packet matching, differential evolution algorithm, average self-information, average mutual information

中图分类号:

TP393

王则林, 郝水侠. 运用差分演化算法实现包匹配多层核心基的提取[J]. 计算机应用, 2017, 37(3): 777-781.

WANG Zelin, HAO Shuixia. Extracting kernel basis using differential evolution algorithm for packet matching[J]. Journal of Computer Applications, 2017, 37(3): 777-781.

参考文献

[1] WARKHEDE P, SURI S, VARGHESE G. Fast packet classification for two-dimensional conflict-free filters[C]//Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ:IEEE, 2001:1434-1443.
[2] GUPTA P, MCKEOWN N. Algorithms for packet classification[J]. IEEE Network, 2001, 15(2):24-32.
[3] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching[J]. ACM SIGCOMM Computer Communication Review, 1998, 28(4):191-202.
[4] FELDMAN A, MUTHUKRISHNAN S. Tradeoffs for packet classification[C]//Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ:IEEE, 2000:1193-1202.
[5] GUPTA P, MCKEOWN N. Packet classification with hierarchical intelligent cuttings[J]. IEEE Micro, 2000, 20(1):34-41.
[6] SINGH S, BABOESCU F, VARGHESE G, et al. Packet classification using multidimensional cutting[C]//Proceedings of the 2003 conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York:ACM, 2003:213-224.
[7] GUPTA P, MCKEOWN N. Packet classification on multiple fields[C]//Proceedings of the 1999 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York:ACM, 1999:147-160.
[8] TSAI C-H, CHU H-M, WANG P-C. Packet classification using multi-iteration RFC[C]//Proceedings of the 2013 IEEE 37th Annual Computer Software and Application Conference Workshops. Washington, DC:IEEE Computer Society, 2013:748-753.
[9] VAN LUNTEREN J, ENGBERSEN APJ. Multi-field packet classification using ternary CAM[J]. Electronics Letters, 2002, 38(1):21-23.
[10] SREELAJA N K, VIJAYALAKSHMI PAI G A. Ant colony optimization based approach for efficient packet filtering in firewall[J]. Applied Soft Computing, 2010, 10(4):1222-1236.
[11] WANG Z, WU Z, ZHANG B. Packet matching algorithm based on improving differential evolution[J]. Wuhan University Journal of Natural Sciences, 2012, 17(5):447-453.
[12] 王则林,吴志健,尹兰.IPV6环境下的高维大规模包匹配算法[J].电子学报,2013,41(11):2181-2186.(WANG Z L, WU Z J, YIN L. High dimension large scale packet matching algorithm in IPV6[J]. Acta Eletronica Sinica, 2013, 41(11):2181-2186.)
[13] RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1):64-79.
[14] QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2):398-417.
[15] 汪慎文,丁立新,谢承旺,等.应用精英反向学习策略的混合差分演化算法[J].武汉大学学报(理学版),2013,59(2):111-116.(WANG S W, DING L X, XIE C W, et al. A hybrid differential evolution with elite opposition-based learning[J]. Journal of Wuhan University (Natural Science Edition), 2013, 59(2):111-116.)
[16] ZHANG J, SANDERSON A C. JADE:adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5):945-958.
[17] BREST J, GREINER S, BOSKOVIC B, et al. Self-adapting control parameters in differential evolution:a comparative study on numerical benchmark problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6):646-657.
[18] WANG Y, CAI Z, ZHANG Q. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1):55-66.

运用差分演化算法实现包匹配多层核心基的提取

Extracting kernel basis using differential evolution algorithm for packet matching

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	李康顺, 左磊, 李伟. 基于单形正交实验设计的差分演化算法[J]. 计算机应用, 2016, 36(1): 143-149.
[2]	周靖. 平均互信息和类别区分性修剪规则的KNN算法[J]. 计算机应用, 2013, 33(02): 558-562.
[3]	田心记宋成. 数字网络编码的正交协作方案[J]. 计算机应用, 2012, 32(08): 2116-2122.
[4]	张震胡学钢. 基于互信息量的分类模型[J]. 计算机应用, 2011, 31(06): 1678-1680.
[5]	拓守恒汪文勇. 求解高维多模优化问题的正交小生境自适应差分演化算法[J]. 计算机应用, 2011, 31(04): 1094-1098.
[6]	高意颜宏文. 基于差分演化算法的粗糙集属性约简[J]. 计算机应用, 2010, 30(9): 2329-2331.
[7]	鄢靖丰张泊平龚文引谭水木. 一种新型的差分演化算法及其应用研究[J]. 计算机应用, 2008, 28(3): 719-722.
[8]	贺毅朝寇应展陈致明. 求解旅行商问题的位置-次序编码差分演化算法[J]. 计算机应用, 2007, 27(3): 630-632.