基于TCAM的低能耗正则表达式匹配算法

doi:10.3969/j.issn.1000-436x.2014.08.020

Abstract

Abstract:

A character-indexed regular expression matching algorithm was presented to address the limitations of TCAM power consumption. This algorithm used the idea of separating the alphabet table from the states in deterministic finite automaton (DFA) for building a character index, in order to reduce the number of activated TCAM blocks, which in turn translated low TCAM power. Experimental results showed that proposed algorithm reduces the TCAM power by 92.7% on average as well as the TCAM space usage by 32.0% on average, and improves the matching throughput by 57.9% on average compared to previous solutions based on DFA.

Key words: regular expression matching, character index, block-based storage, low power

Lin-xuan DING,Kun HUANG,Da-fang ZHANG. Low-power TCAM for regular expression matching[J]. Journal on Communications, 2014, 35(8): 162-168.

Figures/Tables 7

References 27

[1]	PAXSON V , ASANOVIC K , DHARMAPURIKAR S , et al. Rethink-ing hardware support for network analysis and intrusion prevention[A]. Proceeding of USENIX Workshop on Hot Topics in Security[C] Van-couver, Canada, 2006.
[2]	SOMMER R , PAXSON V . Enhancing byteleve network intrusion detection signatures with context[A]. Proceeding of ACM Conference on Computer and Communications security[C] Washington, DC, USA, 2003. 262-271.
[3]	Snort::rules[EB/OL]. , 2013- 12-01.
[4]	The bro network security monitor[EB/OL]. , 2013.
[5]	HP TippingPoint S1200N IPS A7500 module[EB/OL]. , 2013-12-01.
[6]	Intrusion prevention system(IPS)-Cisco systems[EB/OL]. , 2013-12-05.
[7]	YU F , KATZ R , LAKSHMAN T V . Gigabit rate packet pattern-matching using TCAM[A]. Proceeding of IEEE International Confer-ence on Network Protocols[C]. Berlin, Germany, 2004.
[8]	MEINERS C R , PATEL J , NORIGE E , et al. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems[A]. Proceeding of the 19th USENIX Security Symposium[C]. Washington, DC, USA, 2010, 8.
[9]	PENG K , TANG S , CHEN M , et al. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM[A]. Pro-ceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. Brooklyn, NY, USA, 2011.
[10]	MA Y , BANERJEE S . A smart pre-classifier to reduce power con-sumption of TCAMS for multi-dimensional packet classification[A]. Proceeding of ACM Conference of the Special Interest Group on Data Communication[C] Helsinki, Finland, 2012.
[11]	SIDHU R , PRASANNA V K . Fast regular expression matching using FPGA[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C] Rohnert Park, CA,USA, 2001.
[12]	CLARK C R , SCHIMMEL D E . Scalable pattern matching onhigh-speed networks[A]. Proceeding of IEEE International Sympo-sium on Field-Programmable Custom Computing Machines[C]. BNapa Valley, CA, USA, 2004.
[13]	SOURDIS I , PNEVMATIKATOS D . Pre-decoded CAMs for efficient and high-speed NIDS pattern matching[A]. Proceeding of IEEE Inter-national Symposium on Field-Programmable Custom Computing Ma-chines[C] Napa Valley, CA, USA, 2004.
[14]	MOSCOLA J , LOCKWOOD J , LOUI R P , et al. Implementation of a content-scanning module for an internet firewall[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C] Napa Valley, CA, USA, 2003.
[15]	KUMAR S , DHARMAPURIKAR S , YU F , et al. Algorithms to accel-erate multiple regular expressions matching for deep packet inspec-tion[A]. Proceeding of ACM Conference of the Special Interest Group on Data Communication[C] Pisa, Italy, 2006.
[16]	KUMAR S , TURNER J , WILLIAMS J . Advanced algorithms for fast and scalable deep packet inspection[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C] San Jose, CA, USA, 2006.
[17]	BECCHI M , CADAMI S . Memory-efficient regular expression search using stae merging[A]. Proceeding of IEEE International Conference on Computer Communications[C] Anchorage, Alaska, USA, 2007.
[18]	BECCHI M , CROWLEY P . An improved algorithm to accelerate regular expression evaluation[A]. Proceeding of ACM/IEEE Sympo-sium on Architectures for Networking and Communications Sys-tems[C]. San Jose, CA, USA, 2008.
[19]	SMITH R , ESTAN C , JHA S . XFA: faster signature matching with extended automata[A]. Proceeding of IEEE Symposium on Security and Privacy[C]. Oakland, CA, USA, 2008.
[20]	SMITH R , ESTAN C , JHA S , et al. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata[A]. Proceeding of ACM Conference of the Special Interest Group on Data Communication[C] Seattle, WA, USA, 2008.
[21]	MEINERS C R , LIU A X , TORNG E . TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs[A]. Pro-ceeding of IEEE International Conference on Network Protocols[C]. Beijing, China, 2007.
[22]	LIU A X , MEINERS C R , ZHOU Y . All-match based complete redun-dancy removal for packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Computer Communications[C] Phoenix, AZ, USA, 2008.
[23]	MEINERS C R , LIU A X , TORNG E . Bit weaving: a non-prefix ap-proach to compressing packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C] Princeton, NJ, USA, 2009.
[24]	ZANE F , NARLIKAR G , BASU A . CoolCAMs: power-efficient TCAMs for forwarding engines[A]. Proceeding of IEEE Interna-tional Conference on Computer Communications[C]. San Francisco, USA, 2003.
[25]	SPITZNAGEL E , TAYLOR D , TURNER J . Packet classification using extended TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C] Atlanta, Georgia, USA, 2003.
[26]	Regular expression processor[EB/OL]. , 2013-12-01.
[27]	AGRAWAL B , SHERWOOD T . Modeling TCAM power for next generation network devices[A]. Proceeding of IEEE International Symposium on Performance Analysis of Systems and Software[C] Austin, TX, USA, 2006.

Metrics

Recommended 0

No Suggested Reading articles found!

特征规则集	规则条数	字母表大小	通配符表达式条数
R1	31	88	7
R2	23	81	2
R3	33	78	1
R4	33	78	14
R5	33	78	33
R6	31	88	15
R7	23	81	11
R8	23	81	23
R9	31	88	31
R10	217	110	18

特征规则集	DFA/MB	CIDFA/MB
R1	10.32	7.02
R2	16.30	11.09
R3	18.38	12.50
R4	31.34	21.32
R5	50.05	34.03
R6	83.83	57.00
R7	85.77	58.33
R8	96.05	65.32
R9	191.84	130.45
R10	17.29	11.76

特征规则集	DFA/(Gbit·s^?1)	CIDFA/(Gbit·s^?1)
特征规则集	DFA/(Gbit·s^?1)	最小	最大
R1	1.98	3.11	3.63
R2	1.82	2.72	3.11
R3	1.82	2.72	3.11
R4	1.68	2.42	2.72
R5	1.56	2.42	2.72
R6	1.56	2.18	2.42
R7	1.56	2.18	2.42
R8	1.56	2.18	2.42
R9	1.45	1.98	2.18
R10	1.82	3.11	3.63

Low-power TCAM for regular expression matching

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 27

Related Articles 4

Metrics

Recommended 0

[1]	Xiaorong ZHU,Yao SHEN. RPMA low-power wide-area network planning method based on data mining [J]. Journal on Communications, 2019, 40(3): 28-35.
[2]	. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 20-168.
[3]	Si-quan HU,Jun-feng WANG. Smart low power listening for wireless sensor networks [J]. Journal on Communications, 2009, 30(9): 95-101.
[4]	Qin WANG,Chong LI,Ya-dong WAN,Lei LI. Low power data fusion for sensor node constrained by real time management in WSN [J]. Journal on Communications, 2008, 29(11): 220-226.