An innovative approach for regular expression matching based on noc architecture

被引：0

作者：

Linhai, Cui ^{[1
]}

机构：

[1] Harbin University of Science and Technology, Harbin

来源：

International Journal of Smart Home | 2014年 / 8卷 / 01期

关键词：

Deep packet inspection; Finite state machine; Network-on-chip; Reconfigurable design; Regular expression matching; Throughput;

D O I：

10.14257/ijsh.2014.8.1.06

中图分类号：

学科分类号：

摘要：

An new regular expression (regex) matching method based on Network-on-Chip(NoC) architecture is proposed in this paper. The idea is to combine a new kind of regex matching engine implemented in hardware with NoC architecture to get a high matching rate. The Regex matching was performed by partitioning the regex into several parts to make the finite state machine (FSM) simpler. Each part of regex can be matched by an engine cell core, and each core communicates with other cores by routers on a NOC topology. This method is suitable for different rule libraries in Deep packet inspection (DPI) and is easy to change the rule library of regex stored in memory. The engine was designed and implemented based on field programming gate array (FPGA) as a prototype and a model to implement the architecture in Application-Specific Integrated Circuits (ASIC) is also discussed in this paper. The experimental results show that this method can make regex matching much faster than traditional methods. © 2014 SERSC.

引用

页码：45 / 52

页数：7

共 14 条

[1]

Yu F., Chen Z.F., Diao Y.L., Lakshman T.V., Katz R.H., Fast and memory efficient regular expression matching for deep packet inspection, Bhuyan LN, Dubois M, Eatherton W, Proc. of the 2006 ACM/IEEE Symp. On Architecture for Networking and Communications Systems, pp. 93-102, (2006)

[2]

Kumar S., Dharmapurikar S., Yu F., Crowley P., Turner J., Algorithms to accelerate multiple regular expressions matching for deep packet inspection, Rizzo L, Anderson TE, McKeown N, Proc. of the ACM SIGCOMM 2006 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 339-350, (2006)

[3]

Brodie B., Cytron R., Talor D., A scalable architecture for high-throughput regular-expression pattern matching, ISCA, (2006)

[4]

Floyd R.W., Ullman J.D., The Compilation of Regular Expressions into Integrated Circuits, 29, 3, pp. 603-622, (1982)

[5]

Sidhu R., Prasanna V.K., Fast Regular Expression Matching Using FPGAs, IEEE Symposium on Field Programmable Custom Computing Machines, (2001)

[6]

Yang Y.-H.E., Jiang W., Prasanna V.K., Compact architecture for high-throughput regular expression matching on FPGA, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, pp. 227-238, (2008)

[7]

Yu F., Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection, UCB tech. report, (2005)

[8]

Brodie B.C., Taylor D.E., Cytron R.K., A Scalable Architecture For High Throughput Regular Expression Pattern Matching, 33rd International Symposium on Computer Architecture (ISCA'06), (2006)

[9]

Goossens K., A Ethereal Network on Chip: Concepts, Architectures, and Implementations, IEEE Design & Test of Computers, 22, 5, (2005)

[10]

Pande P.P., Performance Evaluation and Design Trade-offs for Network-on chip Interconnect Architectures, IEEE Transctions on Computers, 54, 8, pp. 1025-1040, (2005)

← 1 2 →