Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2008-12-17
2011-12-27
Le, Uyen (Department: 2157)
Data processing: database and file management or data structures
Database design
Data structure types
C707S706000
Reexamination Certificate
active
08086641
ABSTRACT:
An integrated search engine device evaluates span prefix masks for keys residing at leaf parent levels of a search tree to identify a longest prefix match to an applied search key. This longest prefix match resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key. The search engine device is also configured to read a bitmap associated with the leaf node to identify a pointer to associated data for the longest prefix match. The pointer has a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the longest prefix match.
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: 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: 7110407 (2006-09-01), Khanna
patent: 7162572 (2007-01-01), Somasundaram
patent: 7231383 (2007-06-01), Andreev et al.
patent: 7246198 (2007-07-01), Nataraj 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), Panigrahy et al.
patent: 7571156 (2009-08-01), Gupta et al.
patent: RE40932 (2009-10-01), Diede 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: 7805427 (2010-09-01), Depelteau
patent: 7831626 (2010-11-01), Depelteau
patent: 7953721 (2011-05-01), Depelteau et al.
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), 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/0095439 (2006-05-01), Buchmann 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: WO 2004088548 (2004-10-01), None
Final Office Action dated Dec. 30, 2010 for U.S. Appl. No. 11/963,142.
Final Office Action dated Feb. 4, 2011 for U.S. Appl. No. 11/934,240.
Final Office Action dated Jan. 13, 2011 for U.S. Appl. No. 11/768,646.
Non-Final Office Action dated Dec. 30, 2010 for U.S. Appl. No. 11/963,041.
Non-Final Office Action dated Oct. 22, 2010 for U.S. Appl. No. 11/934,240.
Non-Final Office Action mailed Jul. 21, 2010 for U.S. Appl. No. 11/963,142.
Non-Final Office Action mailed Jun. 21, 2010 for U.S. Appl. No. 11/858,441.
Notice of Allowance mailed Jul. 13, 2010 for U.S. Appl. No. 11/864,290.
Answers.com, http://www.answers.com/topic/b-tree, B˜tree: Information From Answers.com, Admitted prior art. 6 pages. printed Aug. 1, 2006.
B*-tree, http://en.wikipedia.org/wiki/B%2A-tree, Admitted prior art. 1 page. printed Sep. 15, 2006.
Canonical form http://en.wikipedia.org/wiki/Canonical—form, Admitted prior art, 1 page. printed Jul. 29, 2006.
Henry Hong-yi Tzeng, “Longest Prefix Search Using Compressed Trees”, In Proceedings of IEEE Globe.com, 1998, 6 pages.
Kobayashi et al. “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing”, C&C Media Research Laboratories, NEC Corporation 2000 IEEE. 13 pages.
Nasser Yazdani et al., “Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths”, IEEE, 2001, p. 76-85.
Network address processor makes embedded DRAM a virtue, http://www.electronicproducts.com/printasp?ArticleURL=oct12.oct2000, Printed Aug. 14, 2006, Admitted Prior Art, 1 page.
Srinivasan et al. “Fast Address Lookups Using Controlled Prefix Expansion” Washington University in St. Louis, ACM
Le Uyen
Mahamedi Paradice Kreisman LLP
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
Integrated search engine devices that utilize SPM-linked bit... 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 SPM-linked bit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated search engine devices that utilize SPM-linked bit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4264124