Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-11-03
2009-12-15
Mofiz, Apu M (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C711S108000, C365S049100, C365S189060, C365S189070, C365S230060
Reexamination Certificate
active
07634500
ABSTRACT:
A method and apparatus for multiple string searching using a ternary content addressable memory. For one embodiment, the method includes receiving a text string having a plurality of characters and performing an unanchored search of a database of a 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 various embodiments, 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), Melchior
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: 7440304 (2008-10-01), Raj
patent: 2003/0005146 (2003-01-01), Miller et al.
patent: 2003/0041163 (2003-02-01), Rhoades
patent: 2003/0048785 (2003-03-01), Calvignac et al.
patent: 2003/0065774 (2003-04-01), Steiner et al.
patent: 2004/0054848 (2004-03-01), Folsom
patent: 2004/0133565 (2004-07-01), Hinshaw et al.
patent: 2004/0177319 (2004-09-01), Horn
patent: 2006/0221658 (2006-10-01), Gould 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/0282835 (2007-12-01), Duxbury
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: 2009/0012958 (2009-01-01), Raj
patent: 0408188 (1991-01-01), None
Masaki Hirata et al.; “A Versatile Data String-Search VLSI”; Apr. 1988, IEEE vol. 23, No. 2.; pp. 329-335.
Anthony J. McAuley et al.; “Fast Routing Table Lookup Using CAMs”, 1993, IEEE; pp. 1382-1391.
Alfred V. Aho, Margaret J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM, Jun. 1975, vol. 18, No. 6.
Tong-Bi Pei, Charles Zukowski, “Putting Routing Tables in Silicon”, IEEE Network Magazine, Jan. 1992.
Tong-Bi Pei, Charles Zukowski, “VLSI Implementation of Routing Tables: Tries and CAMs.”, 1991 IEEE.
Keith Sklower, “A Tree-Based Packet Routing Table for Berkeley Unix”, Berkeley Technical Report, UC Berkeley, CA, USA, 1991.
Paul Francis Tsuchiya, “A Search Algorithm for Table Entries with Non-contiguous Wildcarding”, Bellcore, 1991, available from the author francis@aciri.org.
Anthony J. McAuley and Paul Francis, “Fast Routing Table Lookup Using CAMs”, 1993, pp. 1382-1391, IEEE.
International Searching Authority, International Search Report for PCT/US03/26486, Feb. 4, 2004.
“Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers”, document dated Nov. 21, 2003, 6 pages.
“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.
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.
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.
Mahamede Paradice Kreisman LLP
Mofiz Apu M
NetLogic Microsystems, Inc.
Paradice III William L.
Pyo Monica M
LandOfFree
Multiple string searching using content addressable memory 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 content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple string searching using content addressable memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4081612