Data processing: database and file management or data structures – Database and file access
Reexamination Certificate
2007-03-21
2010-12-28
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database and file access
C707S758000, C707S797000
Reexamination Certificate
active
07860849
ABSTRACT:
A search tree embodying a plurality of signatures and a number of states each having a failure transition to a fail state and one or more success transitions to next states is optimized by selecting a success size parameter that indicates a maximum number of input characters to be traversed on the success transitions and compressing the search tree to create a compressed search tree characterized by the selected success size parameter.
REFERENCES:
patent: 5051886 (1991-09-01), Kawaguchi et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5278981 (1994-01-01), Kawaguchi et al.
patent: 5299206 (1994-03-01), Beaverson 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: 6011795 (2000-01-01), Varghese et al.
patent: 6012057 (2000-01-01), Mayer 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: 6856981 (2005-02-01), Wyschogrod et al.
patent: 6980992 (2005-12-01), Hursey et al.
patent: 7058821 (2006-06-01), Parekh 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: 7529746 (2009-05-01), Ichiriu et al.
patent: 7636717 (2009-12-01), Gupta et al.
patent: 7676444 (2010-03-01), Venkatachary et al.
patent: 2003/0041163 (2003-02-01), Rhoades et al.
patent: 2003/0048785 (2003-03-01), Calvignac et al.
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0065774 (2003-04-01), Steiner et al.
patent: 2003/0065800 (2003-04-01), Wyschogrod et al.
patent: 2004/0015498 (2004-01-01), Rabaioli
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
patent: 2004/0177319 (2004-09-01), Horn
patent: 2004/0267732 (2004-12-01), Luk et al.
patent: 2005/0050260 (2005-03-01), Schacham et al.
patent: 2005/0114306 (2005-05-01), Shu et al.
patent: 2006/0059196 (2006-03-01), Sato et al.
patent: 2006/0259508 (2006-11-01), Sikdar et al.
patent: 2007/0011734 (2007-01-01), Balakrishnan et al.
patent: 2007/0027867 (2007-02-01), Ichino
patent: 2007/0055662 (2007-03-01), Edelman et al.
patent: 2007/0130140 (2007-06-01), Cytron et al.
patent: 2008/0046423 (2008-02-01), Khan Alicherry et al.
patent: 2008/0071781 (2008-03-01), Ninan et al.
patent: 0408188 (1991-01-01), None
Dharmapurikar, et al. Fast and Scalable Pattern Matching for Content Filtering; Oct. 26-28, 2005; Proceedings of the 2005 ACM Symposium on Architecture for Networking and Communications Systems, pp. 183-192.
Final Office Action mailed Aug. 26, 2009 for U.S. Appl. No. 11/689,421 24 pgs.
Final Office Action mailed Oct. 29, 2009 for U.S. Appl. No. 11/689,446.
Hierons, “Optimizing the Length of Checking Sequences,” May 2006, IEEE transactions on Computers, vol. 55, Issue 5, pp. 618-629 (Abstract only).
Non-Final Office Action mailed May 14, 2009 for U.S. Appl. No. 11/689,421 22 pgs.
Non-Final Office Action mailed May 29, 2009 for U.S. Appl. No. 11/689,446.
Notice of Allowance mailed Oct. 26, 2009 for U.S. Appl. No. 11/689,421 8 pgs.
Notice of Allowance mailed Dec. 31, 2009 for U.S. Appl. No. 11/689,446 10 pgs.
Pao et al., Efficient packet classification using TCAMs, Computer Networks, vol. 50, pp. 3523-3535 (2006).
Song et al., “Efficient packet Classification for Network Intrusion Detection using FGPA,” FPGA '05, Feb. 20-22, 2005, Monterey, CA, pp. 238-245.
Darmapurikar et al., “Fast and Scalable Pattern Matching for Content Filtering”, Proc. 2005 ACM Symp. Archit. For Networking Communications Systems, held Oct. 26-28, 2005, pp. 183-192.
Non-Final Office Action mailed Jul. 22, 2010 for U.S. Appl. No. 11/689,429.
Non-Final Office Action mailed Mar. 17, 2010 for U.S. Appl. No. 11/689,429 26 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.
Fast Routing Table Lookup Using CAMs, Anthony J. McAuley and Paul Francis, 1993, pp. 1382-1391, IEEE.
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.
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.
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.
Gupta Pankaj
Venkatachary Srinivasan
Adams Charles D
Mahamedi Paradice Kreisman LLP
NetLogic Microsystems, Inc.
Paradice III William L.
Rones Charles
LandOfFree
Optimizing search trees by increasing success size parameter does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimizing search trees by increasing success size parameter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing search trees by increasing success size parameter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4192548