We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Reseach Article

Efficient String Matching Using Deterministic Finite Automation Hardware: Speed vs Area Tradeoff

by Aakanksha Pandey, Nilay Khare
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 44 - Number 18
Year of Publication: 2012
Authors: Aakanksha Pandey, Nilay Khare
10.5120/6366-8750

Aakanksha Pandey, Nilay Khare . Efficient String Matching Using Deterministic Finite Automation Hardware: Speed vs Area Tradeoff. International Journal of Computer Applications. 44, 18 ( April 2012), 37-42. DOI=10.5120/6366-8750

@article{ 10.5120/6366-8750,
author = { Aakanksha Pandey, Nilay Khare },
title = { Efficient String Matching Using Deterministic Finite Automation Hardware: Speed vs Area Tradeoff },
journal = { International Journal of Computer Applications },
issue_date = { April 2012 },
volume = { 44 },
number = { 18 },
month = { April },
year = { 2012 },
issn = { 0975-8887 },
pages = { 37-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume44/number18/6366-8750/ },
doi = { 10.5120/6366-8750 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:35:54.617183+05:30
%A Aakanksha Pandey
%A Nilay Khare
%T Efficient String Matching Using Deterministic Finite Automation Hardware: Speed vs Area Tradeoff
%J International Journal of Computer Applications
%@ 0975-8887
%V 44
%N 18
%P 37-42
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Pattern matching is a crucial task in several critical network services such as intrusion detection and matching of the IP address during packet forwarding by the router. In this paper we present an speed vs area tradeoff of the the original DFA and the DFA called delayed input DFA(D2FA) with optimized area by eliminating the redundant transition edges. In delayed input DFA the area required to store transition table reduces to 60% of the original DFA but the clock pulse required to execute the process increases almost 40% of the original DFA. The comparison of area and speed is presented. This area optimized architecture of DFA is simulated and synthesized using VHDL on the Xilinx ISE 12. 4.

References
  1. A. BabuKaruppiah, Dr. S Rajaram "Deterministic Finite Automata for Pattern Matching in FPGA for intrusion Detection" in International Conference on Computer and Electrical Technoogy-ICCCET 2011,18th& 19th March,2011. "
  2. Jan Kastil, Jan Korenek Hardware Accelerated Pattern Matching Based onDeterministic Finite Automata with Perfect Hashing,IEEE 2010,p-149-152.
  3. Kai Wang, Yaxuan Q, YiboXue, Jun LReorganized and Compact DFA for EfficientRegular Expression Matching,IEEE communication society
  4. Hiroki Nakahara,TsutomuSasao and Munehiromatsuura "A Regular Expression Matching Using Non-Deterministic Finite Automata" in IEEE 2010.
  5. IvanoBonesana,MarcoPaolieri,Marco D. Santambrogio "An adaptable FPGA based system for regular expression Matching" in IEEE 2008.
  6. Mother Aldwairi,ThomasConte,PaulFranzon "Configurable string Matching Hardware for Speeding up Intrusion detection" inACM SIGARCH Computer Architecture News in,Vol. 33,No. 1, March 2005.
  7. Ashok kumarTummala and ParimalPatel"Distributed IDS using Reconfigurable Hardware" in IEEE 2007.
  8. Hoang Le and Viktor K. Prasanna Ming Hsieh Department of Electrical Engineering University of Southern California Los Angeles, CA 90089, USA A Memory-Efficient and Modular Approach for String Matching on FPGAs ,2010
  9. M. Dhanapriya,C. Vasanthanayaki "Hardware Based Pattern Matching Technique for Packet Inspection of High Speed Network" International Conference on "Control,Automation,Communication and energy Consevation-2009 4th -6thjune 2009.
  10. IoannisSourdis, DionisiosN. Pnevmatikatos, and StamatisVassiladis," Scalable Multigigabit Pattern Matching for Packet Inspection," in Proc. IEEE Symp. Field program. Custom Comput. Feb. 2008.
  11. B. L. Hutchings and R. Franklin and D. Carver "Scalable hardware implementation usonf Finite Automata"Department of Electrical and Computer Engineering.
  12. J. Hasan, S. Cadambi, V. Jakkula and S. Chakradhar, "Chisel: A Storage-efficient, Collision-free Hash-based Network Processing Architecture," 33rd International Symposium on Computer Architecture,p. 203-215.
  13. ReetinderSidhu,Vikot K. Prasanna "Fast Regular Expression Matching using FPGAs"9th Annual Symposium IEEE2001.
  14. Sailesh Kumar, SarangDharmapurikar, Fang Yu, Patrick Crowley, Jonathan Turner "Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection", SIGCOMM'06, September 11-15, 2006, Pisa, Italy, 2006 ACM.
Index Terms

Computer Science
Information Sciences

Keywords

String Matching dfa Vhdl