Layered memory architecture for deterministic finite...

Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C711S122000

Reexamination Certificate

active

07356663

ABSTRACT:
The present invention provides a method and apparatus for searching multiple strings within a packet data using deterministic finite automata. The apparatus includes means for updating memory tables stored in a layered memory architecture comprising a BRAM, an SRAM and a DRAM; a mechanism to strategically store the relevant data structure in the three memories based on the characteristics of data, size/capacity of the data structure, and frequency of access. The apparatus intelligently and efficiently places the associated data in different memories based on the observed fact that density of most rule-sets is around 10% for common data in typical network intrusion prevention systems. The methodology and layered memory architecture enable the apparatus implementing the present invention to achieve data processing line rates over 2 Gbps.

REFERENCES:
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0065800 (2003-04-01), Wyschogrod et al.
patent: 2003/0110208 (2003-06-01), Wyschogrod et al.
patent: 2003/0163803 (2003-08-01), Wyschogrod et al.
patent: 2003/0221013 (2003-11-01), Lockwood et al.
patent: 2004/0049596 (2004-03-01), Schuehler et al.
patent: 2004/0059443 (2004-03-01), Sharangpani
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
Aho, Alfred V. and Corasick, Margaret J., “Efficient String Matching: An Aid to Bibliographic Search”, 1975, Communications of the ACM, vol. 18, Issue 6, pp. 333-340.
Sidhu, R. and Prasanna, V.K. “Fast Regular Expression Matching using FPGAs”, 2001, IEEE Symposium of Field-Programmalbe Custom Computing Machines (FCCM).
Sidhu, R. et al., “Sring Matching on Multicontext FPGAs using Self-Reconfiguration”, 1999, ACM/SIGDA 7 Intl. Symposium on Field Programmable Gate Arrays, pp. 217-226.
Virtex-E Datasheet, “Virtex(TM)-E 1.8 V Field Programmable Gate Arrays”, Jul. 17, 2002, DS022-1 (v2.3), 6 pages.
M. Fisk and G. Varghese “Applying Fast String Matching to Intrusion Detection” [retrieved from the Internet <<URL: http://public.lanl.gov/mfisk/papers/setmatch-raid.pdf>> on Jul. 13, 2004], 21 pages.
R. Franklin, D. Carver, and B.L. Hutchings “Assisting Network Intrusion Detection with Reconfigurable Hardware,”Proceedings, FCCM 2002, 10 pages.
Z. K. Baker and V. K. Prasanna “Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs,” FPL 2004, pp. 311-321.
Z. K. Baker and V.K. Prasanna, “A Methodology for Synthesis of Efficient Intrusion Detection Systems on FPGAs”, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2004, 10 pages.
Y.H. Cho and W.H. Mangione-Smith “Deep Packet Filter with Dedicated Logic and Read Only Memories,” IEEE Symposium of Field Programmable Custom Computing Machines (FCCM), 2004, 10 pages.
S. Dharmapurikar, P. Krishnamurthy, T. Sproull, J. W. Lockwood “Deep Packet Inspection Using Parallel Bloom Filters,” IEEE Computer Society, Jan.-Feb. 2004, pp. 52-61.
N. Tuck, T. Sherwood, B. Calder, G. Varghese “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,”Proceedings, IEEE INFOCOM 2004, 12 pages.
A. V. Aho and M.J. Corasick “Efficient String Matching: An Aid to Bibliographic Search,” Communications of the ACM, vol. 18, Issue 6, Jun. 1975, pp. 333-340.
R. Lippmann, D. Fried, I. Graf, J. Haines, K. Kendall, D. McClung, D. Weber, S. Webster, D. Wyschogrod, R. Cunningham, M. Zissman “Evaluating Intrusion Detection Systems: The 1998 DARPA Off-line Intrusion Detection Evaluation,”Proceedings, DARPA Information Survivability Conference and Exhibition (DISCEX) 2000, IEEE Computer Society Press, Los Alamitos, CA, pp. 12-26.
E.P. Markatos, S. Antonatos, M. Polychronakis and K.G. Anagnostakis “Exclusion-based Signature Matching for Intrusion Detection,”Proceedings, IASTED International Conference on Communications and Computer Networks (CCN), Cambridge, USA, 2002, pp. 146-152.
I. Sourdis and D. Pnevmatikatos “Fast, Large-Scale String Match for a 10Gbps FPGA-based Network Intrusion Detection System,”Proceedings, 13th Intl. Conf. on Field Programmable Logic and Applications (FPL2003), Sep. 2003, Lisbon, Portugal, 10 pages.
R. Sidhu and V.K. Prasanna “Fast Regular Expression Matching using FPGAs,” IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Apr. 2001, 12 pages.
M. Gokhale, D. Dubois, A. Dubois, M. Boorman, S. Poole, V. Hogsett “Granidt: Towards Gigabit Rate Network Intrusion Detection Technology,”Proceedings, FPL 2002, 10 pages.
J. Moscola, J. Lockwood, R.P. Loui, M. Pachos “Implementation of a Content-Scanning Module for an Internet Firewall,”Proceedings, FCCM 2003, 8 pages.
I. Sourdis and D. Pnevmatikatos “Pre-decoded CAMs for Efficient and High-Speed NIDS Pattern Matching,”Proceedings, IEEE Symposium on Field Programmable Custom Computing Machines (FCCM), Apr. 2004, Napa, California, USA, 10 pages.
Y.H. Cho, S. Navab, W.H. Mangione-Smith “Specialized Hardware for Deep Network Packet Filtering,”M. Glesner, P. Zipf, and M. Renovell (Eds.), FPL 2002, LNCS 2438, pp. 452-461.
S. Golson “State Machine Design Techniques for Verilog and VHDL,” Synopsys Journal of High-Level Design, Sep. 1994, 11 pages.
R.P.S. Sidhu, A. Mei and V. K. Prasanna “String Matching on Multicontext FPGAs using Self-Reconfiguration,”Proceedings, 1999 ACM/SIGDA 7th Intl. Symposium on Field Programmable Gate Arrays, Feb. 1999, pp. 217-226.
Z.K. Baker, V.K. Prasanna “Time and Area Efficient Pattern Matching on FPGAs,”Proceedings, FPGA '04, Feb. 2004, Monterey, California, USA, 10 pages.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Layered memory architecture for deterministic finite... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Layered memory architecture for deterministic finite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered memory architecture for deterministic finite... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2769067

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.