An Efficient Algorithm For TCAM-based Regular Expression Matching

A large number of high-speed network technologies such as IP technology,Asynchronous Transfer Mode(ATM),gigabit Ethernet,Fiber Distributed Data Interface(FDDI)etc have emerged in recent years.Due to the rapid development of network,the network data analysis techniques such as network intrusion detection,content filtering,network flow classification,and protocol analysis becomes more and more complex,study how to detect and analysize network data under the environment of high-speed network is very important.Regular expression matching is widely used in the analysis of network data.Regular expression matching based on ternary content addressable memory(TCAM)has advantages of three state storage and high matching speed of parallel search,becoming the core technology of deep packet inspection(DPI).This paper mainly discussed the efficient regular expression matching.The main work of this research is as follows:(1)This paper proposes a high efficiency regular expression matching algorithm based on TCAM,using TCAM multichannel parallel search characteristic.DFA's multilevel coding effectively compress the storage space,reducing the system cost and power consumption.(2)Except using our efficient algorithm to realize deterministic finite automata(DFA)based on TCAM in this paper,we extend its application to extend finite automata(XFA).The research show that XFA based on our algorithm also effectively reducing the storage space.(3)This paper propose a network-flow's classification and control system based on TCAM.This system aims at high speed backbone network.IP packers are captured from backbone network and deeply inspected.Data analysis on not only IP header but also the payload,extending the traditional analysis form network protocol and transmission protocol to application protocol.Our algorithm improves the network-flow's classification technology.