To search, Click below search items.


All Published Papers Search Service


A Novel Efficient Pattern Matching Packet Inspection by using δnFA


N.Kannaiya Raja, K.Arulanandam, G. Ambika M.E


Vol. 13  No. 1  pp. 79-88


Deep packet Inspection is an advanced method of packet filtering that functions at the Application layer of the OSI reference model. Deep Packet Inspection is a form of computer network packet filtering that examines the data part of a packet as it passes an inspection point, searching for protocol ,viruses ,spam, intrusions or predefined criteria to decide if the packet can pass or it needs to be routed to a different destination, or for the purpose of collecting statistical information. Deterministic finite automata (DFAs), use large set of rules need a memory amount that turns out to be too large for practical implementation we have presented a new compressed representation for deterministic finite automata, called Delta Finite Automata. The algorithm considerably reduces the number of states and transitions, and it is based on the observation that most adjacent states share several common transitions, so it is convenient to store only the differences between them. In this paper we have presented an improvement to δFA that exploits the Nth-order dependence between states and further reduces the number of transitions by adopting the concept of temporary transition. This schema named as δnFA. Both the schemes are orthogonal to most of the previous solutions, thus allowing for higher compression rates. A new encoding scheme for states has been also proposed(which we refer to as char state), which exploits the association of many states with a few input chars. Such a compression scheme can be efficiently integrated into δFA and δnFA, allowing a further memory reduction with a negligible increase in the state lookup time. The experimental runs have shown remarkable results in terms of lookup speed as well as the issue of excessive memory consumption.


Deep packet inspection, differential encoding, finite automata (FAs), pattern matching, regular expressions.