Interval symbol architecture for programmable intelligent...

Details Interval symbol architecture for programmable intelligent... Interval symbol architecture for programmable intelligent...

2007-12-06

2010-11-09

Wong, Leslie (Department: 2164)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C707S737000, C707SE17046, C711S100000, C711S103000, C711S108000

Reexamination Certificate

active

07831607

ABSTRACT:
Memory architecture provides capabilities for high performance content search using regular expressions and patterns of strings. 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 include of regular expressions which are converted to finite state automata and then programmed in PRISM for evaluating content with the search rules. The PRISM memory provides features for complex regular expression symbols like interval symbol, range detection, complement control, bit masking and the like and enables complex symbols and compact regular expression representation.

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: 7464254 (2008-12-01), Sharangpani 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/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.
Alfred V. Aho et al., “Compilers: Principles, Techniques, and Tools”, Pearson Education Inc., 2007.
File History of U.S. Appl. No. 11/952,028, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,043, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,103, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,108, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,110, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,111, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,112, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,114, electronically captured from PAIR on Jun. 16, 2010.
File History of U.S. Appl. No. 11/952,117, electronically captured from PAIR on Jun. 16, 2010.
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,103, mailed Jun. 28, 2010.
Notice of Allowance issued in U.S. Appl. No. 11/952,112, mailed Jun. 30, 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,110.
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.

Affiliated with

Also associated with

Rating

Interval symbol 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 Interval symbol architecture for programmable intelligent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval symbol architecture for programmable intelligent... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4239420