Integrated search engine devices having pipelined node...

Details Integrated search engine devices having pipelined node... Integrated search engine devices having pipelined node...

2011-07-26

2011-07-26

Mofiz, Apu M (Department: 2161)

Data processing: database and file management or data structures

Database design

Database and data structure management

C714S718000, C711S117000

Reexamination Certificate

active

07987205

ABSTRACT:
An integrated search engine device contains a pipelined arrangement of a plurality of search and tree maintenance sub-engines therein. This pipelined arrangement of sub-engines includes a hierarchical memory, which is configured to store a plurality of databases of search prefixes. These databases are arranged as a corresponding plurality of multi-way trees that span multiple levels of the hierarchical memory. The plurality of search and tree maintenance sub-engines are configured to respond to a database flush command by redesignating active nodes of a selected database within the hierarchical memory as free nodes using downstream and upstream communications between the plurality of search and tree maintenance sub-engines.

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), Narad 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), 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: 6868414 (2005-03-01), Khanna 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: 6963868 (2005-11-01), Basso 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), Somasundaram
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), Panigrahy 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: 7697518 (2010-04-01), De Wit
patent: 7725450 (2010-05-01), Depelteau
patent: 7747599 (2010-06-01), Depelteau
patent: 2001/0043602 (2001-11-01), Brown
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: 2003/0236793 (2003-12-01), Karlsson
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/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), Vankatacharv 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
Agarwal 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.
Answers.com, http://www.answers.com/topic/b-tree, B˜tree: Information From Answers.com, Admitted prior art. 6 pages.
B*-tree, http://en.wikipedia.org/wiki/B%2A-tree, Admitted prior art. 1 page.
Bayer, R. et al., “Prefix B-Trees,” ACM Trans. On Database Systems, vol. 2, No. 1, Mar. 1977, pp. 11-26.
Bender et al. “Cache-oblivious B-trees”, SIAM J. Comput, 2000, pp. 1-18.
B-Trees: Balanced Tree Data Structures, http://www.bluerwhite.org/btree/, Admitted Prior Art, Printed, 8 pages.
Canonical form http://en.wikipedia.org/wiki/Canonical—form, Admitted prior art, 1 page.
Chang et al., “Dynamic Routing Tables using Augmented Balanced Search Tree,” National Cheng Kung University and I-Shou University, Admitted Prior Art, 35 pages.
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.
Djordjevic et al. “A Hierarchical memory system environment” Jun. 1998 Proceedings of the 1998 workshop on Computer architecture education WCAE '98 Publisher: ACM Press.
Henry Hong-yi Tzeng, “Longest Prefix Search Using Compressed Trees”, In Proceedings of IEEE Globe.com, 1998.
Kobayashi et al. “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing”, C&C Media Research Laboratories, NEC Corporation 2000 IEEE.
Lu et al., “A B-Tree Dynamic Router-Table Design”, IEEE Transactions on Computers, 54:7, pp. 1-27, http:!/www.cise.ufl.edu/-sahn/papers/btree.odf, (Jul. 2005).
Nasser Yazdani et al., “Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths”, IEEE, 2001, p. 76-8

Affiliated with

Also associated with

Rating

Integrated search engine devices having pipelined node... 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 having pipelined node..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated search engine devices having pipelined node... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2687744