A Pattern Partitioning Algorithm for Memory-Efficient Parallel String Matching in Deep Packet Inspection

被引：8

作者：

Kim, HyunJin ^{[1
]}

Hong, Hyejeong ^{[1
]}

Baek, Dongmyoung ^{[2
]}

Kang, Sungho ^{[1
]}

机构：

[1] Yonsei Univ, Dept Elect & Elect Engn, Seoul 120749, South Korea

[2] ETRI, Broadcasting & Telecommun Convergence Res Lab, Taejon, South Korea

来源：

IEICE TRANSACTIONS ON COMMUNICATIONS | 2010年 / E93B卷 / 06期

关键词：

computer network security; deep packet inspection; finite state machine; pattern matching; and network monitoring;

D O I：

10.1587/transcom.E93.B.1612

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

This paper proposes a pattern partitioning algorithm that maps multiple target patterns onto homogeneous memory-based string matchers. The proposed algorithm adopts the greedy search based on lexicographical sorting. By mapping as many target patterns as possible onto each string matcher, the memory requirements are greatly reduced.

引用

页码：1612 / 1614

页数：3

共 50 条

[41] Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing
Zhang, Shuzhuang
Luo, Hao
Fang, Binxing
Yun, Xiaochun
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2009, E92D (10) : 1953 - 1960
[42] Algorithms to accelerate multiple regular expressions matching for deep packet inspection
Kumar, Sailesh
Dharmapurikar, Sarang
Yu, Fang
Crowley, Patrick
Turner, Jonathan
ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2006, 36 (04) : 339 - 350
[43] Deep Packet Inspection using Ternary Content Addressable Memory
Jayashree, S.
Shivashankarappa, N.
2014 INTERNATIONAL CONFERENCE ON CIRCUITS, COMMUNICATION, CONTROL AND COMPUTING (I4C), 2014, : 441 - 447
[44] Space-Efficient String Indexing for Wildcard Pattern Matching
Lewenstein, Moshe
Nekrich, Yakov
Vitter, Jeffrey Scott
31ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2014), 2014, 25 : 506 - 517
[45] Parallel implementation of fuzzified pattern matching algorithm on GPU
Soroushnia, Shima
Daneshtalab, Masoud
Pahikkala, Tapio
Plosila, Juha
23RD EUROMICRO INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING (PDP 2015), 2015, : 341 - 344
[46] A Parallel Method of Deep Packet Inspection based on Message-Passing Interface
Qu, Jia-xing
Zhang, Guo-yin
Wang, Xi-zhong
Liu, Jia-hui
Song, Da-hua
INTERNATIONAL JOURNAL OF SECURITY AND ITS APPLICATIONS, 2015, 9 (12): : 29 - 34
[47] APFA: Asynchronous Parallel Finite Automaton for Deep Packet Inspection in Cloud Computing
Li, Yang
Li, Zheng
Yu, Nenghai
Ma, Ke
CLOUD COMPUTING, PROCEEDINGS, 2009, 5931 : 529 - 540
[48] Hierarchical multi-pattern matching algorithm for network content inspection
Sheu, Tzu-Fang
Huang, Nen-Fu
Lee, Hsiao-Ping
INFORMATION SCIENCES, 2008, 178 (14) : 2880 - 2898
[49] Efficient Pattern Matching Algorithm for Intrusion Detection Systems
Yang, Wenjun
SENSORS, MECHATRONICS AND AUTOMATION, 2014, 511-512 : 1178 - 1184
[50] An Efficient Pattern Matching Algorithm for Intrusion Detection Systems
Anithakumari, S.
Chithraprasad, D.
2009 IEEE INTERNATIONAL ADVANCE COMPUTING CONFERENCE, VOLS 1-3, 2009, : 223 - +

← 1 2 3 4 5 →