Static information storage and retrieval – Associative memories
Reexamination Certificate
2007-07-19
2008-10-21
Luu, Pho M. (Department: 2824)
Static information storage and retrieval
Associative memories
C365S189060, C365S189070, C365S230060, C365S233100
Reexamination Certificate
active
07440304
ABSTRACT:
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 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: 5051886 (1991-09-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: 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: 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: 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: 6785677 (2004-08-01), Fritchman
patent: 7134143 (2006-11-01), Stellenberg et al.
patent: 7225188 (2007-05-01), Gai 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/0177319 (2004-09-01), Horn
patent: 2006/0259508 (2006-11-01), Sikdar et al.
patent: 0408188 (1991-01-01), None
“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.
International Searching Authority, International Search Report for PCT/US03/26486, Feb. 4, 2004.
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.
Luu Pho M.
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-4013402