A Compression Approach To Reducing Power Consumption Of TCAMs In Regular Expression Matching

Deep packet inspection(DPI)is one of the core components for network instrusion detection/prevention systems(NIDS/NIPS).The function of DPI is to real-time detect malicious instrusions and identify some specific applications by examining both the header and the payload of network data packets.The regular expression(Regex)is expressive and flexible,so it is widely used in DPI.Currently,a given Regex is exactly recognized by an equivalent deterministic finite automaton(DFA).DFA is a finite state machine in which a source accepts an input character and then migrates to an unique destination state.But DFA suffers from the state explosion problem,where the number of DFA states grows exponentially with the size of Regex signatures.Ternary Content Addressable Memory(TCAM)is a type of popular device for fast regular expression(Regex)matching.With the rapid development fo network applications,the Regex set is becoming more and more complex and its size is large.A large and complex Regex set indicates large TCAM momery consumption.The TCAM power consumption is proportional to its memory consumption,so a large TCAM momery consumption in turn leads to the high TCAM power consumption problem.This paper proposes a compression approach to reducing power consumption of TCAMs in Regex matching,and it is called as power-efficient DFA(PEDFA).PEDFA consists of two type tables:character-index table and transition table.The size of character-index table is associated with the input character encoding,but the size of transition table is associate with the scale and complexity of Regex.Therefore,the more the transition table is compressed,the more TCAM momery consumption is reduced.The small TCAM momery consumption indicates low TCAM power consumption.PEDFA sufficiently exploits the two TCAM characteristics:the TCAM wildcard'*' function and the priority matching mechanism.PEDFA consists of three parts:pre-processing,reconverable compression,and feasible compression.The goal of pre-processing is to obtain higher compression ration of recoverable compression by assigning reasonable identification number to the DFA states.If some entries have the same destination and binary prefix code,recoverable compression uses only one entry to displace them,exploiting the TCAM wildcard fuction.Feasible compression continues to compress the redundant entries into one default entry by exploiting the priority matching mechanism.In order to ensure the correctness of feasible compression,the default entry must be placed behind those uncompressed remaining entries.Experimental results on real-world Regex sets show that our scheme is significantly effective,reducing 87.4%power consumption and 93.2%memory space,and improving throughput up to 114.7%on average compared to the prior work.