Integrated search engine devices having pipelined search and...

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

2007-02-13

2009-10-13

LeRoux, Etienne P (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C711S117000, C712S001000, C712S220000, C712S300000

Reexamination Certificate

active

07603346

ABSTRACT:
A pipelined search engine device, such as a longest prefix match (LPM) search engine device, includes a hierarchical memory and a pipelined tree maintenance engine therein. The hierarchical memory is configured to store a b−tree of search prefixes (and possibly span prefix masks) at multiple levels therein. The pipelined tree maintenance engine, which is embedded within the search engine device, includes a plurality of node maintenance sub-engines that are distributed with the multiple levels of the hierarchical memory. The search engine device may also include pipeline control and search logic that is distributed with the multiple levels of the hierarchical memory.

REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
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: 5758356 (1998-05-01), Hara et al.
patent: 5787430 (1998-07-01), Doeringer 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), Malick
patent: 5918245 (1999-06-01), Yung
patent: 5924115 (1999-07-01), Von Herzen et al.
patent: 6098150 (2000-08-01), Brethour et al.
patent: 6115792 (2000-09-01), Tran
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: 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: 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: 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: 6757779 (2004-06-01), Nataraj et al.
patent: 6768739 (2004-07-01), Kobayashi et al.
patent: 6778530 (2004-08-01), Greene
patent: 6831850 (2004-12-01), Pereira et al.
patent: 6839800 (2005-01-01), Stark
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: 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: 7076602 (2006-07-01), Stark et al.
patent: 7107263 (2006-09-01), Yianilos et al.
patent: 7162572 (2007-01-01), Somasunaram
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: 2002/0089937 (2002-07-01), Venkatachary et al.
patent: 2002/0146009 (2002-10-01), Gupta et al.
patent: 2002/0152413 (2002-10-01), Waters 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: 2004/0030686 (2004-02-01), Cardno 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/0163122 (2005-07-01), Sahni et al.
patent: 2006/0259682 (2006-11-01), Somasundaram
patent: WO2004088548 (2004-10-01), None
Michael A. 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.
Henry Hong-yi Tzeng, “Longest Prefix Search Using Compressed Trees”, In Proceedings of IEEE Globe.com, 1998.
Nasser Yazdani et al, “Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths”, IEEE, 2001, p. 76-85.
Chang at al., “Dynamic Routing Tables using Augmented Balanced Search Tree,” National Cheng Kung University and I-Shou University, Admitted Prior Art, 35 pages.
O'Connor et al., “The iFlow Address Processor,” 2001 IEEE, pp. 16-23.
Lu et al., “A B-Tree Dynamic Router-Table Design,” IEEE Transactions on Computers, vol. 54, Issue 7, Jul. 2005, pp. 1-27.
Aggarwal et al. “A Model for Hierarchical Memory”Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing STOCpp. 305-314 (1987).
Choudhury et al. “A New Buffer Management Scheme for Hierarchical Shared Memory Switches”IEEE/ACM Transactions on Networking(TON) 5(5):728-738 (1997).
Djordjevic et al. “A Hierarchical Memory System Environment”Proceedings of the 1988 Workshop on Computer Architecture Education WCAE(6 pages)(1998).
Suri et al. “Multiway Range Trees: Scalable IP Lookup with Fast Updates” http://www.cs.edu/˜varghese/PAPERS/globecome2001.pdf Admitted Prior Art, 5 pages.
“B-Trees: Balanced Tree Data Structures,” http://www.bluerwhite.org/btree/, Admitted Prior Art, Printed, 8 pages (believed prior to Jul. 23, 2004).

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4086431