Low-Power TCAMs For Regular Expression Matching

Deep packet inspection(DPI)is a key function of network intrusion detection and prevention systems(NIDPS).DPI monitors real-time network traffic,which scans both headers and payloads of each packet.Due to their powerful and flexible expressiveness,regular expressions are typically applied to DPI.Nowadays,regular expression matching algorithms are mainly performed using deterministic finite automata(DFA).In the case of giving state and input character,the state transition of DFA is unique.TCAM-based regular expression matching algorithms have been proposed as a promising approach to improve processing speed,which is an important research direction of DPI.TCAM has the character of high searching speed and small storage space,as well as the TCAM power consumption is proportionate to its storage space.DFA requires large storage space and the storage space of multi-stride DFA grows exponentially with the stride of DFA,which leading to high TCAM power consumption of DFA,especially for multi-stride DFA.Firstly,this thesis presents character-indexed single-stride DFA(CIDFA)algorithm.This algorithm uses the idea of separating the alphabet table from the state transition table of single-stride DFA and builds character index,in order to reduce the activated TCAM blocks when matching,which in turn translates low TCAM power.Experimental results show that this 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 single-stride DFA.To address the high power consumption of multi-stride DFA,this thesis presents parallel character-indexed multi-stride DFA(PCIDFA)algorithm.This algorithm uses the idea of building parallel character indexes according to the stride of DFA,and activates the corresponding TCAM blocks by using bitmap intersection,which reduces TCAM power significantly.Experimental results show that our algorithm reduces the TCAM power by more than three orders of magnitude as well as the TCAM space usage by 57.4%on average,and improves the matching throughput by 2.3 times on average compared to previous solutions based on multi-stride DFA.