A compression approach to reducing power consumption of TCAMs in regular expression matching

doi:10.1016/j.comcom.2015.08.003

	A compression approach to reducing power consumption of TCAMs in regular expression matching
	Yang, Jinmin 1; Yang, Jie 1; Huang, Kun 2; Rong, Huigui 1; Li, Kin Fun 3
	2015-10-01
发表期刊	COMPUTER COMMUNICATIONS
ISSN	0140-3664
卷号	70 页码:86-94
摘要	Ternary content addressable memory (TCAM) is a popular device for fast regular expression (Regex) matching in networking and security applications. The rapid growth of Regexes necessitates large TCAM memory consumption, which in turn impacts power consumption. Compressing the transition table can cut down TCAM memory consumption, thereby reducing its power consumption. This work identifies the compressibility of transition entries and then proposes a compression scheme. In our scheme, the compression ratio is improved by skillfully assigning identifiers to states in a deterministic finite automaton (DFA). Furthermore, our scheme utilizes the wildcard function and the priority matching mechanism provided in TCAM to exploit the minimum differentiation among a set of source states. A complete implementation of the identifier assignment and transition table compression is presented. Experimental results on real-world Regex sets show that our scheme is significantly more effective, reducing power consumption by 87.4% and memory space by 93.2%, and improving throughput up to 114.7% on average compared to prior work. (C) 2015 Elsevier B.V. All rights reserved.
关键词	Regular expression matching Ternary content addressable memory Power consumption Compressibility identification Source state differentiation
DOI	10.1016/j.comcom.2015.08.003
收录类别	SCI
语种	英语
资助项目	national natural science foundation of China[61272401] ; key science & technology plan of Hunan province[2013GK2003] ; prospective research project on future networks of Jiangsu future networks innovation institute[2013095-1-05]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000364268000008
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：4[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9154
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Yang, Jinmin
作者单位	1.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100864, Peoples R China 3.Univ Victoria, Dept Elect & Comp Engn, Victoria, BC V8W 2Y2, Canada
推荐引用方式 GB/T 7714	Yang, Jinmin,Yang, Jie,Huang, Kun,et al. A compression approach to reducing power consumption of TCAMs in regular expression matching[J]. COMPUTER COMMUNICATIONS,2015,70:86-94.
APA	Yang, Jinmin,Yang, Jie,Huang, Kun,Rong, Huigui,&Li, Kin Fun.(2015).A compression approach to reducing power consumption of TCAMs in regular expression matching.COMPUTER COMMUNICATIONS,70,86-94.
MLA	Yang, Jinmin,et al."A compression approach to reducing power consumption of TCAMs in regular expression matching".COMPUTER COMMUNICATIONS 70(2015):86-94.