Data processing: database and file management or data structures – Database and file access – Search engines
Reexamination Certificate
2005-07-19
2010-06-29
Vital, Pierre M (Department: 2156)
Data processing: database and file management or data structures
Database and file access
Search engines
C707S791000, C707S797000, C711S117000
Reexamination Certificate
active
07747599
ABSTRACT:
A search engine device includes a hierarchical memory that is configured to store a b-tree of search prefixes and span prefix masks (SPMs). These SPMs are evaluated during each search operation to identify search prefixes that match an applied search key yet reside at nodes of the b-tree that are not traversed during the search operation. The search engine device also includes handle memory. This handle memory is configured to support a respective handle memory block for each search prefix within each of a plurality of nodes of the b-tree that reside at a leaf parent level within the b-tree. Each of these handle memory blocks may have sufficient capacity to support one result handle per bit within a span prefix mask associated with a corresponding search prefix. In other cases, each of these handle memory blocks may have sufficient capacity to support only M+1 handles, where M is a positive integer corresponding to a quantity of search prefixes supported by each of a plurality of leaf nodes within the b-tree.
REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4606002 (1986-08-01), Waisman et al.
patent: 5228115 (1993-07-01), Natarajan
patent: 5430869 (1995-07-01), Ishak et al.
patent: 5446887 (1995-08-01), Berkowitz
patent: 5475837 (1995-12-01), Ishak et al.
patent: 5560007 (1996-09-01), Thai
patent: 5644763 (1997-07-01), Roy
patent: 5666494 (1997-09-01), Mote, Jr.
patent: 5758024 (1998-05-01), Alleva
patent: 5758356 (1998-05-01), Hara et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5812853 (1998-09-01), Carroll et al.
patent: 5812996 (1998-09-01), Rubin et al.
patent: 5813000 (1998-09-01), Furlani
patent: 5822749 (1998-10-01), Agarwal
patent: 5897655 (1999-04-01), Mallick
patent: 5918245 (1999-06-01), Yung
patent: 5924115 (1999-07-01), Von Herzen et al.
patent: 6035326 (2000-03-01), Miles et al.
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6098150 (2000-08-01), Brethour et al.
patent: 6115792 (2000-09-01), Tran
patent: 6138123 (2000-10-01), Rathbun
patent: 6219662 (2001-04-01), Fuh et al.
patent: 6389507 (2002-05-01), Sherman
patent: 6401117 (2002-06-01), Narad et al.
patent: 6404752 (2002-06-01), Allen, Jr. et al.
patent: 6421730 (2002-07-01), Harad et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6441053 (2002-08-01), Klein et al.
patent: 6460112 (2002-10-01), Srinivasan et al.
patent: 6460120 (2002-10-01), Bass et al.
patent: 6480839 (2002-11-01), Whittington et al.
patent: 6490592 (2002-12-01), St. Denis et al.
patent: 6522632 (2003-02-01), Waters et al.
patent: 6526055 (2003-02-01), Perlman et al.
patent: 6532457 (2003-03-01), Tal et al.
patent: 6535491 (2003-03-01), Gai et al.
patent: 6539369 (2003-03-01), Brown
patent: 6553370 (2003-04-01), Andreev et al.
patent: 6564211 (2003-05-01), Andreev et al.
patent: 6611832 (2003-08-01), van Lunteren
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 6633865 (2003-10-01), Liao
patent: 6636849 (2003-10-01), Tang et al.
patent: 6636956 (2003-10-01), Venkatachary et al.
patent: 6662287 (2003-12-01), Andreev et al.
patent: 6691124 (2004-02-01), Gupta et al.
patent: 6694323 (2004-02-01), Bumbulis
patent: 6697276 (2004-02-01), Pereira et al.
patent: 6707693 (2004-03-01), Ichiriu
patent: 6757779 (2004-06-01), Nataraj et al.
patent: 6768739 (2004-07-01), Kobayashi et al.
patent: 6778530 (2004-08-01), Greene
patent: 6782382 (2004-08-01), Lunteren
patent: 6831850 (2004-12-01), Pereira et al.
patent: 6839800 (2005-01-01), Stark
patent: 6859455 (2005-02-01), Yazdani et al.
patent: 6928430 (2005-08-01), Chien et al.
patent: 6934795 (2005-08-01), Nataraj et al.
patent: 6941314 (2005-09-01), Andreev et al.
patent: 6944709 (2005-09-01), Nataraj et al.
patent: 7007027 (2006-02-01), Najork et al.
patent: 7016904 (2006-03-01), Grove et al.
patent: 7017021 (2006-03-01), Gupta et al.
patent: 7023807 (2006-04-01), Michels et al.
patent: 7035844 (2006-04-01), Andreev et al.
patent: 7047317 (2006-05-01), Huie et al.
patent: 7062499 (2006-06-01), Nehru et al.
patent: 7076602 (2006-07-01), Stark et al.
patent: 7107263 (2006-09-01), Yianilos et al.
patent: 7162572 (2007-01-01), Somasundaram
patent: 7231383 (2007-06-01), Andreev et al.
patent: 7257530 (2007-08-01), Yin
patent: 7289979 (2007-10-01), Wilson
patent: 7292162 (2007-11-01), Samasundaram
patent: 7383276 (2008-06-01), Lomet
patent: 7426518 (2008-09-01), Venkatachary et al.
patent: 7437354 (2008-10-01), Venkatachary et al.
patent: 7478109 (2009-01-01), Panigraphy et al.
patent: 7571156 (2009-08-01), Gupta et al.
patent: 7603346 (2009-10-01), Depelteau et al.
patent: 7653619 (2010-01-01), Depelteau et al.
patent: 2002/0089937 (2002-07-01), Venkatachary et al.
patent: 2002/0116526 (2002-08-01), Brown
patent: 2002/0146009 (2002-10-01), Gupta et al.
patent: 2002/0147721 (2002-10-01), Gupta et al.
patent: 2002/0152413 (2002-10-01), Waters et al.
patent: 2002/0161969 (2002-10-01), Nataraj et al.
patent: 2003/0009453 (2003-01-01), Basso et al.
patent: 2003/0009466 (2003-01-01), Ta et al.
patent: 2003/0093613 (2003-05-01), Sherman
patent: 2003/0093646 (2003-05-01), Stark
patent: 2003/0123397 (2003-07-01), Lee et al.
patent: 2003/0123459 (2003-07-01), Liao
patent: 2003/0163302 (2003-08-01), Yin
patent: 2003/0182272 (2003-09-01), Leung et al.
patent: 2004/0030686 (2004-02-01), Cardno et al.
patent: 2004/0059731 (2004-03-01), Yianilos et al.
patent: 2004/0062208 (2004-04-01), Brown et al.
patent: 2004/0082416 (2004-04-01), Stark et al.
patent: 2004/0083336 (2004-04-01), Stark et al.
patent: 2004/0109451 (2004-06-01), Huang et al.
patent: 2004/0139274 (2004-07-01), Hui
patent: 2004/0170379 (2004-09-01), Yao et al.
patent: 2004/0193619 (2004-09-01), Venkatachary et al.
patent: 2004/0205229 (2004-10-01), Stojancic
patent: 2004/0249803 (2004-12-01), Vankatachary et al.
patent: 2005/0091443 (2005-04-01), Hershkovich et al.
patent: 2005/0131867 (2005-06-01), Wilson
patent: 2005/0163122 (2005-07-01), Sahni et al.
patent: 2005/0195832 (2005-09-01), Dharmapurikar et al.
patent: 2006/0167843 (2006-07-01), Allwright et al.
patent: 2006/0259682 (2006-11-01), Somasundaram
patent: 2007/0038626 (2007-02-01), Waters et al.
patent: 2007/0276648 (2007-11-01), Andreev et al.
patent: WO2004088548 (2004-10-01), None
patent: WO2004088548 (2004-10-01), None
Choudhury et al. “A New Buffer Management Scheme forHierarchical Shared Memory Switches” Oct. 1997 IEEE/ACM Transactions on Networking (TON), vol. 5 Issue 5 Publisher: IEEE Press.
Djordjevic et al.“A hierarchical memory system environment” Jun. 1998 Proceedings of the 1998 workshop Computer architecture education WCAE '98 Publisher: ACM Press.
Aggarwal et al. “A Model for Hierarchical Memory” Jan. 1987 Proceedings of the nineteenth annual ACM conference on Theory of computing STOC '87 Publisher: ACM Press.
Choudhury et al. “A New Buffer Management Scheme for Hierarchical Shared Memory Switches” Oct. 1997 IEEE/ACM Transactions on Networking (TON), vol. 5 Issue 5 Publisher: IEEE Press.
Uga et al. “A fast and compact longest match prefix look-up method using pointer cache for very long network address”, IT Network Service Systems Laboratories Midori 3-9-1 1, Musashino, Tokyo 180-8585, Japan, 1999 IEEE.
Srinivasan et al. “Fast Address Lookups Using Controlled Prefix Expansion” Washington University in St. Louis, ACM Sigmetrics '98/ Performance '98 Joint International Conference on Measurement and Modeling of Computer Systems.
Kobayashi et al. “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing”, C&C Media Research Laboratories, NEC Corporation 2000 IEEE.
Bender et al. “Cache-Oblivious B-Trees”, SIAM J. Comput, 2000, pp. 1-18.
Bender et al., “Cache-oblivious B-trees,” SIAM J. Comput. 2000, pp. 1-18.
R. Bayer et al., “Prefix B-Trees,” ACM Trans. On Database Systems, vol. 2, No. 1, Mar. 1977, pp. 11-26.
Lu et al., “A B-Tree Dynamic Router-Table Design,” http://www.cise.ufl.edu/˜sahn/papers/btree.pdf, Admitted Prior Art, 27 pages.
Suri, et al., “Multi
Carr David Walter
Depelteau Gary Michael
Mahamedi Paradice Kreisman LLP
Mitiku Berhanu
NetLogic Microsystems, Inc.
Vital Pierre M
LandOfFree
Integrated search engine devices that utilize hierarchical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Integrated search engine devices that utilize hierarchical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated search engine devices that utilize hierarchical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4225942