Improved L7-Filter's pattern matching algorithm based on multi-core processors

doi:10.3724/SP.J.1087.2012.00609

Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (03): 609-613.DOI: 10.3724/SP.J.1087.2012.00609

• Network and distributed techno • Previous Articles Next Articles

Improved L7-Filter's pattern matching algorithm based on multi-core processors

YU Tao, WU Wei-dong

College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan Hubei 430065, China

Received:2011-08-30 Revised:2011-11-16 Online:2012-03-01 Published:2012-03-01

基于多核处理器的L7-Filter规则匹配改进算法

余涛,吴卫东

武汉科技大学计算机科学与技术学院, 武汉 430065

通讯作者: 余涛
作者简介:余涛(1985-),男,湖北郧县人,硕士研究生,主要研究方向:多核处理器应用算法、计算机网络、嵌入式系统;吴卫东(1964-),男,湖北武汉人,副教授,博士,主要研究方向:多核处理器应用算法、计算机网络。
基金资助:
湖北省教育厅科技项目(D20101105)。

Abstract

Abstract: According to the architecture of multi-core processors and the temporal local characteristics of network data flow, a division and dynamic adaptation algorithm was proposed based on multi-core processors. Classifying network data flow by the type and optimizing chain of rules dynamically by the temporal locality of network flow, the count of the multi-core's L7-Filter matching network data flow were reduced effectively and the processing efficiency was improved dramatically. The simulation result shows that given the number of packets in the same conditions, the algorithm has about 7 percent improvement of the multi-core processing performance. With the increasing number of network packets, the performance superiority becomes more obvious.

Key words: multi-core processor, network data flow, L7-Filter, temporal locality, packet classification, dynamic optimization

摘要： 针对多核处理器的体系结构和网络数据流在时间上的局部性特点,提出了一种基于多核处理器的分链动态适应算法。该算法通过对网络数据流进行类型分类并根据网络数据流的时间局部性对规则链进行动态优化,从而有效减少了多核处理器下L7-Filter对网络数据流的匹配次数,显著提升了规则匹配效率。仿真实验结果表明:在网络数据包个数相同条件下,所提算法在性能上约有7%的提高。随着网络数据包个数的增加,性能优越性更加明显。

关键词: 多核处理器, 网络数据流, L7-Filter, 时间局部性, 数据包分类, 动态优化

CLC Number:

YU Tao WU Wei-dong. Improved L7-Filter's pattern matching algorithm based on multi-core processors[J]. Journal of Computer Applications, 2012, 32(03): 609-613.

余涛吴卫东. 基于多核处理器的L7-Filter规则匹配改进算法[J]. 计算机应用, 2012, 32(03): 609-613.

References

[1]林闯,王元卓,任丰原. 新一代网络QoS研究[J]. 计算机学报,2008,31(9);1525-1535.

[2]KUMAR S, TURNER J, WILLIAMS J. Advanced algorithms for fast and scalable deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking And Communications Systems. New York: ACM Press, 2006: 81-92.

[3]曹折波,李青. 多核处理器并行编程模型的研究与设计[J].计算机工程与设计,2010,31(13);2999-3003.

[4]GUO DANHUA, LIAO GUANGDENG, BHUAN L N. A scalable multithreaded L7-Filter design for multi-core servers [C]// Proceedings of the 4th ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York: ACM Press, 2008: 60-68.

[5]Windows Hardware Development Center. Receive Side Scaling(RSS) [EB/OL].[2011-10-20].http://msdn.microsoft.com/en-us/windows/hardware/gg463253.aspx.

[6]所光,杨学军. 多核处理机系统Cache管理技术研究现状[J]. 计算机工程与科学,2010,32(7):65-68.

[7]WALDVOQEL M. Multi-dimensional prefix matching using line search [C]// Proceedings of the 25th Annual IEEE Conference on Local Computer Networks. Washington, DC: IEEE Computer Society, 2000:200-207.

[8]HAMED H, AL-SHAER E. On autonomic optimization of firewall policy organization [J]. Journal of High Speed Networks,2006,15(3):209-227.

[9]丁晶,陈晓岚,吴萍. 基于正则表达式的深度包检测算法[J]. 计算机应用,2007,27(9):2184-2193.

[10]MIT DARPA intrusion detection data sets[EB/OL]. [2010-10-10].http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.

[11]杨赞,杨林,王宝林,等. 依据流统计特性的文分类规则动态优化[J].计算机应用研究,2011,28(5):1878-1882.

[12](美)约翰逊,(美)威曾格,(美)普拉瓦提. Linux服务器性能调整[M]. 韩智文,译.北京:清华大学出版社,2004:23-24.

[13](美) LOVE R. Linux内核设计与实现[M].3版. 陈莉君,康华,译.北京:机械工业出版社,2011:143-148.

[14]Libnids[CP/OL]. [2010-10-10].http://libnids.sourceforge.net/.

[15]徐卫志,宋风龙,刘志勇,等. 众核处理器片上同步机制和评估方法研究[J].计算机学报,2010,33(10):1777-1787.

Improved L7-Filter's pattern matching algorithm based on multi-core processors

基于多核处理器的L7-Filter规则匹配改进算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended Articles

Metrics

[1]	AN Xin, XIA Jinwei, YANG Haijiao, OUYANG Yiming, REN Fuji. Discrete controller synthesis based resource management method of heterogeneous multi-core processor system [J]. Journal of Computer Applications, 2020, 40(6): 1698-1706.
[2]	AN Xin, ZHANG Ying, KANG An, CHEN Tian, LI Jianhua. Machine learning based online mapping approach for heterogeneous multi-core processor system [J]. Journal of Computer Applications, 2019, 39(6): 1753-1759.
[3]	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.
[4]	YUAN Yichuan, YANG Zhou, LUO Tingxing, QIN Jin. Multi-population-based competitive differential evolution algorithm for dynamic optimization problem [J]. Journal of Computer Applications, 2018, 38(5): 1254-1260.
[5]	MA Teng CHEN Shuqiao ZHANG Xiaaohui TIAN Le. Multiple decision-tree packet classification algorithm based on rule set partitioning [J]. Journal of Computer Applications, 2013, 33(09): 2450-2454.
[6]	FANG Juan GUO Mei DU Wenjuan LEI Ding. Low-power oriented cache design for multi-core processor [J]. Journal of Computer Applications, 2013, 33(09): 2404-2409.
[7]	WANG Wenyong REN Chunmei HUANG Lisheng. HiCuts classification algorithm based on non-uniform cutting [J]. Journal of Computer Applications, 2013, 33(02): 357-360.
[8]	JING Si-yuan SHE Kun ZHONG Yi. Power-aware algorithm for hard real-time tasks scheduling in multi-core embedded environment [J]. Journal of Computer Applications, 2011, 31(11): 2936-2939.
[9]	QU Shuang-xi ZHANG Min-xuan LIU Tao LIU Guang-hui. Temperature-aware thread scheduling algorithm for multi-core processors [J]. Journal of Computer Applications, 2011, 31(09): 2567-2570.
[10]	. Efficient packet classification algorithm based on rules compression [J]. Journal of Computer Applications, 2010, 30(11): 3053-3055.
[11]	. An algorithm of packet classification based on binary search on levels [J]. Journal of Computer Applications, 2009, 29(2): 500-502.
[12]	. New evolutionary algorithm based on girdding for dynamic optimization problems [J]. Journal of Computer Applications, 2008, 28(2): 319-321.
[13]	Lei Yu . A novel IP packet classification algorithm based on hierarchical intelligent cuttings [J]. Journal of Computer Applications, 2006, 26(7): 1557-1559.