Static information storage and retrieval – Associative memories
Reexamination Certificate
2011-06-28
2011-06-28
Luu, Pho M (Department: 2824)
Static information storage and retrieval
Associative memories
C365S049160, C365S049170, C365S049180
Reexamination Certificate
active
07969758
ABSTRACT:
Disclosed herein is a method and apparatus for multiple string searching using a ternary content addressable memory. The method includes receiving a text string having a plurality of characters and performing an unanchored search of a database of stored patterns matching one or more characters of the text string using a state machine, wherein the state machine comprises a ternary content addressable memory (CAM) and wherein the performing comprises comparing a state and one of the plurality of characters with contents of a state field and a character field, respectively, stored in the ternary CAM. In the method and apparatus described herein, one or more of the following search features may be supported: exact string matching, inexact string matching, single character wildcard matching, multiple character wildcard matching, case insensitive matching, parallel matching and rollback.
REFERENCES:
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5051886 (1991-09-01), Kawaguchi et al.
patent: 5140644 (1992-08-01), Kawaguchi et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5278981 (1994-01-01), Kawaguchi et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5440715 (1995-08-01), Wyland
patent: 5440753 (1995-08-01), Hou et al.
patent: 5452451 (1995-09-01), Akizawa et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5497488 (1996-03-01), Akizawa et al.
patent: 5525982 (1996-06-01), Cheng et al.
patent: 5615378 (1997-03-01), Nishino et al.
patent: 5712971 (1998-01-01), Stanfill et al.
patent: 5781431 (1998-07-01), Duret et al.
patent: 5963942 (1999-10-01), Igata
patent: 5995963 (1999-11-01), Nanba et al.
patent: 5999435 (1999-12-01), Henderson et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 6185524 (2001-02-01), Carus et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6311183 (2001-10-01), Cohen
patent: 6377942 (2002-04-01), Hinsley et al.
patent: 6421660 (2002-07-01), Glaise
patent: 6425099 (2002-07-01), Lattmann et al.
patent: 6473846 (2002-10-01), Melchoir
patent: 6487566 (2002-11-01), Sundaresan
patent: 6505206 (2003-01-01), Tikkanen et al.
patent: 6538911 (2003-03-01), Allan et al.
patent: 6546391 (2003-04-01), Tsuruoka
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6628660 (2003-09-01), Morse
patent: 6658524 (2003-12-01), Villaret et al.
patent: 6665297 (2003-12-01), Hariguchi et al.
patent: 6760821 (2004-07-01), Stefan et al.
patent: 6785677 (2004-08-01), Fritchman
patent: 6892237 (2005-05-01), Gai et al.
patent: 6952694 (2005-10-01), Mathur et al.
patent: 6980992 (2005-12-01), Hursey et al.
patent: 6988189 (2006-01-01), O'Connor et al.
patent: 6996662 (2006-02-01), Miller et al.
patent: 7058821 (2006-06-01), Parekh et al.
patent: 7082044 (2006-07-01), Gould et al.
patent: 7130230 (2006-10-01), Jain et al.
patent: 7134143 (2006-11-01), Stellenberg et al.
patent: 7139753 (2006-11-01), Bass et al.
patent: 7139837 (2006-11-01), Parekh et al.
patent: 7225188 (2007-05-01), Gai et al.
patent: 7305422 (2007-12-01), Wang
patent: 7330908 (2008-02-01), Jungck
patent: 7353332 (2008-04-01), Miller et al.
patent: 7366001 (2008-04-01), Hanzawa et al.
patent: 7440304 (2008-10-01), Raj
patent: 7505296 (2009-03-01), Hanzawa et al.
patent: 7634500 (2009-12-01), Raj
patent: 7685254 (2010-03-01), Pandya
patent: 7783654 (2010-08-01), Sreenath
patent: 7881088 (2011-02-01), Hanzawa et al.
patent: 2003/0005146 (2003-01-01), Miller et al.
patent: 2003/0041163 (2003-02-01), Rhoades et al.
patent: 2003/0048785 (2003-03-01), Calvignac et al.
patent: 2003/0065774 (2003-04-01), Steiner et al.
patent: 2004/0028294 (2004-02-01), Fukuda
patent: 2004/0054848 (2004-03-01), Folsom
patent: 2004/0133565 (2004-07-01), Hinshaw et al.
patent: 2004/0141510 (2004-07-01), Blanc et al.
patent: 2004/0177319 (2004-09-01), Horn
patent: 2004/0199630 (2004-10-01), Sarkissian et al.
patent: 2005/0171943 (2005-08-01), Ichino et al.
patent: 2006/0168273 (2006-07-01), Michael
patent: 2006/0221658 (2006-10-01), Gould et al.
patent: 2006/0259498 (2006-11-01), Ellison et al.
patent: 2006/0259508 (2006-11-01), Sikdar et al.
patent: 2007/0075878 (2007-04-01), Furodet et al.
patent: 2007/0088955 (2007-04-01), Lee et al.
patent: 2007/0113170 (2007-05-01), Dignum et al.
patent: 2007/0113222 (2007-05-01), Dignum et al.
patent: 2007/0220232 (2007-09-01), Rhoades et al.
patent: 2007/0282835 (2007-12-01), Duxbury
patent: 2008/0052300 (2008-02-01), Horgan
patent: 2008/0071765 (2008-03-01), Ichiriu et al.
patent: 2008/0071781 (2008-03-01), Ninan et al.
patent: 2008/0212581 (2008-09-01), Miller et al.
patent: 2010/0088756 (2010-04-01), Balakrishnan et al.
patent: 0408188 (1991-01-01), None
Non-final Office Action Mailed Mar. 16, 2009 in U.S. Appl. No. 10/700,722.
Final Office Action Mailed Mar. 2, 2010 in U.S. Appl. No. 11/533,204, 21 pages.
Non-Final Office Action Mailed Nov. 9, 2009 in U.S. Appl. No. 12/028,668, 33 pages.
Non-Final Office Action Mailed May 25, 2010 in U.S. Appl. No. 12/028,668.
“Fast Routing Table Lookup Using CAMs”, Anthony J. McAuley and Paul Francis, 1993, pp. 1382-1391, IEEE.
“Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers”, document dated Nov. 21, 2003, 6 pages.
A Search Algorithm for Table Entries with Non-Contiguous Wildcarding, Paul F. Tsuchiya, Bellcore, 1991, pp. 1-10.
A Tree-Based Packet Routing Table for Berkeley Unix, Keith Sklower, Berkeley Technical Report, UC Berkeley, CA, USA, 1991, pp. 1-14.
Efficient String Matching: An Aid to Bibliographic Search, Aho, A. V. and Corasick, M. J., Communications of the Association of Computing Machinery (ACM) Jun. 1975, vol. 18, No. 6. pp. 333-340.
Masaki Hirata et al, “A Versatile Data String-Search VLSI,” Apr. 1988, IEEE vol. 23, No. 2, pp. 329-335.
Over 10Gbps String Matching Mechanism for Multi-stream Packet Scanning Systems, Yutaka Sugawara, Mary Inaba, and Kei Hiraki, FPL 2004, LNCS 3203, pp. 484-493, 2004, J. Becker, M. Platzner, S. Vernalde, Editors.
Putting Routing Tables in Silicon, Tong-Bi Pei and Charles Zukowski, IEEE Network Magazine, Jan. 1992, vol. 6, No. 1, pp. 42-50.
VLSI Implementation of Routing Tables: Tries and CAMs, Tong-Bi Pei and Charles Zukowski, 1991 IEEE Infocom'91, Proceedings vol. 2, pp. 515-524.
Bu et al., “A Keyword Match Processor Architecture using Content Addressable Memory,” GLSVLSI '04, Apr. 26-28, 2004, 5 pages.
Gigabit Rate Packet Pattern-Matching Using TCAM, Fang Yu, Randy H. Katz, and T.V. Lakshman, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), Oct. 5-8, 2004, pp. 174-183.
High Speed Pattern Matching for Network IDS/IPS, Alicherry, Muthuprasanna and Kumar, IEEE Sep. 2006, 1-4244-0596-9/06.
Ichiriu, M., “High Performance layer 3 Forwarding, The Need for Dedicated Hardware Solutions,” White Paper, Application Note NCS05, Mar. 2001, 6 pages.
International Searching Authority, International Search Report for PCT/US03/26486, Feb. 4, 2004.
NetLogic Microsystems, “CIDR Longest Prefix Matching in Network Search Engines,” Application Note NCS05, Mar. 2001, 4 pages.
Peng et al., “Content-Addressable memory (CAM) and its network applications,” International IC—Taipei—Conference Proceedings, 3 pages.
Yu et al., “Efficient Multi-Match packet Classification with TCAM,” Technical Report UCB/CSD-4-1316, Mar. 2004, 7 pages.
Luu Pho M
Mahamedi Paradice Kreisman LLP
NetLogic Microsystems, Inc.
Paradice III William L
LandOfFree
Multiple string searching using ternary content addressable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple string searching using ternary content addressable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple string searching using ternary content addressable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2679896