Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2011-03-01
2011-03-01
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S108000, C711SE12002
Reexamination Certificate
active
07899976
ABSTRACT:
Memory architecture provides capabilities for high performance content search. The architecture creates an innovative memory that can be programmed with content search rules which are used by the memory to evaluate presented content for matching with the programmed rules. When the content being searched matches any of the rules programmed in the Programmable Intelligent Search Memory (PRISM) action(s) associated with the matched rule(s) are taken. Content search rules comprise of regular expressions which are converted to finite state automata (FSA) and then programmed in PRISM for evaluating content with the search rules. PRISM architecture comprises of a plurality of programmable PRISM Search Engines (PSE), each capable of supporting a predetermined size FSAs. FSA extension architecture is created to extend the predetermined size limit of an FSA supported by PSE, by coupling multiple PSEs together to behave as a composite PSE to support larger FSAs.
REFERENCES:
patent: 6778557 (2004-08-01), Yuki et al.
patent: 6892237 (2005-05-01), Gai et al.
patent: 7353332 (2008-04-01), Miller et al.
patent: 7406470 (2008-07-01), Mathur et al.
patent: 7464254 (2008-12-01), Sharangpani et al.
patent: 7472285 (2008-12-01), Graunke et al.
patent: 7660140 (2010-02-01), Joshi et al.
patent: 7685254 (2010-03-01), Pandya
patent: 2002/0161664 (2002-10-01), Shaya et al.
patent: 2004/0059443 (2004-03-01), Sharangpani
patent: 2004/0083387 (2004-04-01), Dapp et al.
patent: 2004/0215593 (2004-10-01), Sharangpani et al.
patent: 2005/0012521 (2005-01-01), Sharangpani et al.
patent: 2005/0052934 (2005-03-01), Tran
patent: 2005/0108518 (2005-05-01), Pandya
patent: 2005/0216770 (2005-09-01), Rowett et al.
patent: 2006/0085533 (2006-04-01), Hussain et al.
patent: 2006/0136570 (2006-06-01), Pandya
patent: 2006/0253816 (2006-11-01), Gould et al.
patent: 2007/0038798 (2007-02-01), Bouchard et al.
patent: 2007/0061884 (2007-03-01), Dapp et al.
patent: 2007/0255894 (2007-11-01), Hessel et al.
patent: 2008/0008202 (2008-01-01), Terrell et al.
patent: 2008/0046423 (2008-02-01), Khan Alicherry et al.
patent: 2008/0133517 (2008-06-01), Kapoor et al.
patent: 2008/0255839 (2008-10-01), Larri et al.
patent: 2009/0100055 (2009-04-01), Wang
PCT International Search Report and Written Opinion of the International Searching Authority mailed on Apr. 30, 2008 regarding PCT/US2007/86785 filed on Dec. 7, 2007, (13 pgs.).
Ville Laurikari, “NFAs with Tagged Transitions, Their Conversion to Deterministic Automata and Application to Regular Expressions”, Seventh International Symposium on String Processing Infomratino Retrieval (SPIRE'00), Sep. 27-29, 2000.
Gerard Berry et al., “From Regular Expressions to Deterministic Automata”, Theoretical Computer Science, vol. 48, pp. 117-126 (1986).
Bruce W. Watson, “A Taxonomy of Finite Automata Contruction Algorithms”, Computing Science, May 18, 1994.
Sailesh Kumar et al., “Algorithms to Accelerate Multiple Regular Expression Matching for Deep Packet Inspection”, SIGCOMM'06, Sep. 11-15, 2006, Pisa, Italy, pp. 339-350.
Reetinder Sidhu et al., “Fast Regular Expression Matching Using FPGAs”, Proceedings of the 9th Annual IEEE Symposium of Field-Programmable Custom Computing Machines, pp. 227-238 (2001).
Alfred V. Aho et al, “Efficient String Matching: An Aid to Bibliographic Search”, Communication of the ACM, vol. 18, No. 6, pp. 333-340, Jun. 1975.
James Moscola et al., “Implementation of a Content-Scanning Module for an Internet Firewall”, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 31, 2003 (9 pages).
Sarang Dhamapurikar et al., “Deep Packet Inspection Using Parallell Bloom Filters”, Hot Interconnects 11, IEEE Computer Society, pp. 52-61, Jan. 2004.
Ken Thompson, “Regular Expression Search Algorithm”, Communication of the ACM, vol. 11, No. 6, pp. 419-422, Jun. 1968.
S.C. Kleene, “Representation of Events in Nerve Nets and Finite Automata”, In Automata Studies, C.E. Shannon and J. McCarthy (eds.), Princeton, University Press, 1956, pp. 3-40.
M. O. Rabin et al., “Finite Automata and Their Decision Problems”, IBM Journal, pp. 114-125, Apr. 1959.
John E. Hopcroft et al., “Introduction to Automata Theory, Language, and Computation”, Addison-Wesley Publishing Company, 1979.
File History of U.S. Appl. No. 11/952,028.
File History of U.S. Appl. No. 11/952,043.
File History of U.S. Appl. No. 11/952,103.
File History of U.S. Appl. No. 11/952,104.
File History of U.S. Appl. No. 11/952,108.
File History of U.S. Appl. No. 11/952,111.
File History of U.S. Appl. No. 11/952,112.
File History of U.S. Appl. No. 11/952,114.
File History of U.S. Appl. No. 11/952,117.
Notice of Allowance issued in U.S. Appl. No. 11/952,103, mailed Jun. 28, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,104, mailed Jun. 30, 2010.
Notice of Aliowance issued in U.S. Appl. No. 11/952,112, mailed Jun. 28, 2010.
Amendment filed Aug. 12, 2010 in U.S. Appl. No. 11/952,108.
Amendment filed Aug. 12, 2010 in U.S. Appl. No. 11/952,114.
Amendment filed Aug. 12, 2010 in U.S. Appl. No. 11/952,117.
Alfred V. Aho et al., “Compilers: Principles, Techniques, and Tools”, Pearson Education Inc., Aug. 31, 2006.
Office Action issued in U.S. Appl. No. 11/952,111, mailed Sep. 20, 2010.
Office Action issued in U.S. Appl. No. 11/952,028, mailed Sep. 22, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,108, mailed Sep. 24, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,117, mailed Oct. 28, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,114, mailed Oct. 22, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,043, mailed Nov. 22, 2010.
File History of U.S. Appl. No. 12/899,336, electronically captured on Dec. 16, 2010.
File History of U.S. Appl. No. 121902,485, electronically captured on Dec. 16, 2010.
File History of U.S. Appl. No. 12/902,500, electronically captured on Dec. 16, 2010.
Bataille Pierre-Michel
DLA Piper (LLP) US
Dudek, Jr. Edward J
LandOfFree
FSA extension architecture for programmable intelligent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with FSA extension architecture for programmable intelligent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FSA extension architecture for programmable intelligent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2711456