Source: http://www.google.com/patents/US7805427?dq=5,815,794
Timestamp: 2016-10-25 09:27:28
Document Index: 673627262

Matched Legal Cases: ['art. 6', 'art. 6', 'art. 1', 'art, 1', 'art, 1', 'Art, 1', 'art. 2', 'art. 2']

Patent US7805427 - Integrated search engine devices that support multi-way search trees having ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsAn integrated circuit search engine device supports a multi-way tree of search keys therein. The search engine device includes at least one multi-node sub-engine. The multi-node sub-engine includes a node processor and a plurality of columns of sub-nodes containing search keys. The node processor is...http://www.google.com/patents/US7805427?utm_source=gb-gplus-sharePatent US7805427 - Integrated search engine devices that support multi-way search trees having multi-column nodesAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7805427 B1Publication typeGrantApplication numberUS 11/864,290Publication dateSep 28, 2010Filing dateSep 28, 2007Priority dateNov 27, 2006Fee statusLapsedAlso published asUS7831626Publication number11864290, 864290, US 7805427 B1, US 7805427B1, US-B1-7805427, US7805427 B1, US7805427B1InventorsGary DepelteauOriginal AssigneeNetlogic Microsystems, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (115), Non-Patent Citations (42), Referenced by (8), Classifications (4), Legal Events (8) External Links: USPTO, USPTO Assignment, EspacenetIntegrated search engine devices that support multi-way search trees having multi-column nodes
US 7805427 B1Abstract
An integrated circuit search engine device supports a multi-way tree of search keys therein. The search engine device includes at least one multi-node sub-engine. The multi-node sub-engine includes a node processor and a plurality of columns of sub-nodes containing search keys. The node processor is configured to distribute an applied search key in parallel to each of the plurality of columns of sub-nodes in response to a search request. The node processor is also configured to receive and resolve corresponding sub-node search results from the plurality of columns of sub-nodes.
This application claims priority to U.S. Provisional Application Ser. No. 60/2867,277, filed Nov. 27, 2006, the disclosure of which is hereby incorporated herein by reference.
This application is related to U.S. application Ser. No. 11/2858,441, filed Sep. 20, 2007, entitled “Integrated Search Engine Devices Having a Plurality of Multi-Way Trees of Search Keys Therein that Share a Common Root Node,” the disclosure of which is hereby incorporated herein by reference.
Referring now to FIG. 7, an integrated circuit search engine 60 according to additional embodiments of the present invention includes a pipelined arrangement of search and tree maintenance sub-engines 70 a-70 d and a final stage handle memory lookup engine 80 therein. Each of these sub-engines 70 a-70 d includes a corresponding level of a hierarchical memory therein. Thus, the first search and tree maintenance sub-engine 70 a contains the highest level of the hierarchical memory and the fourth search and tree maintenance sub-engine 70 d contains the lowest level of the hierarchical memory. The second and third search and tree maintenance sub-engines 70 b and 70 c contain respective intermediate levels of the hierarchical memory. The number of intermediate levels of the hierarchical memory may vary depending on the application to which the search engine 60 is applied. The search and tree maintenance sub-engines 70 a-70 d are also identified by the reference labels LEVEL_1, LEVEL_2, LEVEL_3, . . . , LEVEL_L, which identify the memory level supported therein. Alternatively, the reference labels LEVEL_0, LEVEL_1, . . . , LEVEL_L-1 could also be used to reflect the same relative levels, as show by FIGS. 3-6. The reference character “L” represents a positive integer equal to a maximum height of the tree that can be supported by the search engine 60. The hierarchical memory is configured to store a multi-way tree (e.g., b-tree, b*tree, b+tree) of search prefixes that spans the plurality of memory levels. The hierarchical memory is also preferably configured to support increases in a height of the multi-way tree relative to a leaf node level of the multi-way tree, which can be fixed in location at a lowest one of the plurality of memory levels (i.e., LEVEL_L) within the fourth search and tree maintenance sub-engine 70 d. These increases in the height of the multi-way tree typically occur as a capacity of the multi-way tree increases in response to search prefix insertions.
Some methods of operating the search engine 60 of FIG. 7 will now be described more fully with reference to FIGS. 8A-8B and 9A-9H for the simplified case where L (i.e., maximum tree height) equals 3. These methods reflect operations performed within the search engine 60, in response to an insert instruction. In particular, FIG. 8A illustrates a “before” snapshot of a three-level b-tree data structure containing search prefixes and span prefix masks (SPMs) according to embodiments of the present invention and FIG. 8B illustrates an “after” snapshot of the three-level b-tree data structure, which has been updated by the insertion of search prefix X:112/5 therein. The three-level b-tree in FIG. 8A includes a root node (NODE 1-0) at LEVEL_1 with two child nodes (NODE 2-0, NODE 2-1) located at LEVEL_2. The root node (NODE 1-0) contains the search prefix J:128/2 (and corresponding 9-bit SPM) and two pointers to the two child nodes, which each have a fill count of 2. NODE 2-0 at LEVEL_2 includes two search prefixes (with corresponding SPMs), which are illustrated as D:0/3 and O:96/3. NODE 2-1 at LEVEL_2 includes two search prefixes (with corresponding SPMs), which are illustrated as R:170/8 and H:224/3. NODE 2-0 points to three leaf nodes (NODES 3-0, 3-1 and 3-2), which each have a fill count of 3. NODE 2-1 points to two leaf nodes (NODES 3-4 and 3-5), which each have a fill count of 3, and a third leaf node (NODE 3-6), which has a fill count of 2. The exemplary b-tree of FIG. 8A assumes that M=3 (i.e., maximum of three keys per node) at each level, with a required node utilization of ⅔ of M.
Referring now to FIG. 10A, a pipelined integrated circuit search engine 100 a according to additional embodiments of the present invention includes a pipelined arrangement of search and tree maintenance sub-engines 102 a-102 d therein. Each of these sub-engines 102 a-102 d includes a corresponding level of a hierarchical memory. Thus, the first search and tree maintenance sub-engine 102 a contains the highest level of the hierarchical memory and the fourth search and tree maintenance sub-engine 102 d contains the lowest level of the hierarchical memory. The second and third search and tree maintenance sub-engines 102 b and 102 c contain respective intermediate levels of the hierarchical memory. The number of intermediate levels of the hierarchical memory may vary depending on application. The search and tree maintenance sub-engines 102 a to 102 d are also identified by the reference labels LEVEL_1, LEVEL_2, LEVEL_3, LEVEL_L, which identify the memory level supported therein. The reference character “L” represents a positive integer equal to a maximum height of the multi-way tree that may be supported by the search engine 100 a. The hierarchical memory is configured to store a multi-way tree (e.g., b-tree, b*tree, b+tree) of search prefixes that spans the plurality of memory levels. As illustrated by FIGS. 4-5 and 8-9, this hierarchical memory may also be configured to store span prefix masks (SPMs) for search prefixes located on non-leaf nodes of the tree. Moreover, according to the search engine 100 a of FIG. 10A, the hierarchical memory is further configured to store data associated with the search prefixes, which is referred to herein as “associated data”. As will be understood by those skilled in the art, one type of associated data is typically referred to as a “handle,” which may, in some embodiments, represent an address (e.g., router address, memory address, etc.) that is provided to an output interface of the search engine 100 a. The hierarchical memory is also configured to support increases in a height of the multi-way tree relative to a leaf node level of the multi-way tree, which is fixed in location at a lowest one of the plurality of memory levels (LEVEL_L) within the fourth search and tree maintenance sub-engine 102 d. These increases in the height of the multi-way tree typically occur as a capacity of the multi-way tree increases in response to search prefix insertions.
In the event the search engine is configured as an exact match search engine requiring fully specified search prefixes within the b-tree and the first level search results in an exact match search result, thereby indicating a match between a search prefix residing at the root node and the applied search key (i.e., SEARCH_KEY[(W−1):0]), then the output NEXT_LEVEL[(J−1):0] may be set to a default value that precludes all downstream search and tree maintenance sub-engines from participating in the search and corrupting the search results associated with the first level search. The output NEXT_PTR[(P−1):0] may also be set to a default value or a “don't care” value. For example, the output NEXT_LEVEL[(J−1):0] may be set to a default value greater than the numeric value of the last memory level within the pipeline (i.e., greater than the value of integer L), so that none of the downstream search and tree maintenance sub-engines consider a match with the value NEXT_LEVEL[(J−1):0] generated by a preceding sub-engine. The output MATCH_VALID will also be asserted by the first control module 103 a to reflect the presence of a match with the search prefix located at the root node. Furthermore, the output BEST_MATCH_HNDL[(A−1):0] will be set to the value of the locally stored handle (or possibly other associated data) that corresponds to the matching search prefix within the LEVEL_1 memory. In alternative embodiments of the present invention, the assertion of the MATCH_VALID signal at the output of a sub-engine can be used to block downstream sub-engines from participating in any search operations. The use of an asserted MATCH_VALID signal to block subsequent search operations can be used to eliminate a need to set the NEXT_LEVEL [(J−1):0] signal to the default value.
In particular, the multi-node sub-engine 160 illustrated by FIG. 16 is configured to efficiently support a plurality of nodes having a large number of keys (and sub-tree “child” pointers) associated with each node. The multi-node sub-engine 160 is illustrated as including a node processor 162 and a plurality of columns of sub-nodes 164_0-164_3, which are operatively coupled to the node processor 162 by corresponding data/control interfaces Li_A. The plurality of columns of sub-nodes 164_0-164_3 include corresponding sub-node memories 166_0-166_3, which provide, among other things, key storage. Each of the sub-node memories 166_0-166_3 is illustrated as supporting as many as “m” keys (K0-K(m−1)) for as many as “n+1” nodes at a corresponding level of the tree. Thus, in the illustrated embodiment of FIG. 16, which contains four (4) columns of sub-nodes, the multi-node sub-engine 160 is configured to support as many as 4 m keys for each of “n+1” nodes located at level “i” of a multi-way tree. The node processor 162 is also configured to store child pointers associated with the search keys stored in the plurality of columns of sub-nodes 164_0-164_3.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4464650Aug 10, 1981Aug 7, 1984Sperry CorporationApparatus and method for compressing data signals and restoring the compressed data signalsUS4606002Aug 17, 1983Aug 12, 1986Wang Laboratories, Inc.B-tree structured data base using sparse array bit maps to store inverted listsUS5430869May 29, 1991Jul 4, 1995Hewlett-Packard CompanySystem and method for restructuring a B-TreeUS5446887Sep 17, 1993Aug 29, 1995Microsoft CorporationOptimal reorganization of a B-treeUS5475837Jan 17, 1995Dec 12, 1995Hewlett-Packard CompanyMethod and system for restructuring a B-Tree for managing data during a node splitting operationUS5560007Oct 18, 1995Sep 24, 1996Borland International, Inc.B-tree key-range bit map index optimization of database queriesUS5644763Jun 28, 1995Jul 1, 1997Sybase, Inc.Database system with improved methods for B-tree maintenanceUS5666494Mar 31, 1995Sep 9, 1997Samsung Electronics Co., Ltd.Queue management mechanism which allows entries to be processed in any orderUS5758024Jun 25, 1996May 26, 1998Microsoft CorporationMethod and system for encoding pronunciation prefix treesUS5758356Sep 12, 1995May 26, 1998Hitachi, Ltd.High concurrency and recoverable B-tree index management method and systemUS5787430Jun 30, 1994Jul 28, 1998International Business Machines CorporationVariable length data sequence backtracking a trie structureUS5812853Apr 11, 1994Sep 22, 1998Lucent Technologies Inc.Method and apparatus for parsing source code using prefix analysisUS5812996Nov 6, 1995Sep 22, 1998Sybase, Inc.Database system with methods for optimizing query performance with a buffer managerUS5813000Mar 14, 1996Sep 22, 1998Sun Micro SystemsB tree structure and methodUS5822749Feb 28, 1997Oct 13, 1998Sybase, Inc.Database system with methods for improving query performance with cache optimization strategiesUS5897655Dec 10, 1996Apr 27, 1999International Business Machines CorporationSystem and method for cache replacement within a cache set based on valid, modified or least recently used status in order of preferenceUS5918245Mar 13, 1996Jun 29, 1999Sun Microsystems, Inc.Microprocessor having a cache memory system using multi-level cache set predictionUS5924115Mar 29, 1996Jul 13, 1999Interval Research CorporationHierarchical memory architecture for a programmable integrated circuit having an interconnect structure connected in a tree configurationUS6035326 *Sep 8, 1997Mar 7, 2000International Business Machines CorporationMapping table lookup optimization systemUS6041053 *Sep 18, 1997Mar 21, 2000Microsfot CorporationTechnique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcardsUS6098150Nov 17, 1995Aug 1, 2000Sun Microsystems, Inc.Method and apparatus for fetching information from a cache memoryUS6115792Nov 9, 1999Sep 5, 2000Advanced Micro Devices, Inc.Way prediction logic for cache arrayUS6138123Jul 15, 1997Oct 24, 2000Rathbun; Kyle R.Method for creating and using parallel data structuresUS6219662Jul 9, 1998Apr 17, 2001International Business Machines CorporationSupporting database indexes based on a generalized B-tree indexUS6389507Jan 14, 2000May 14, 2002Gigabus, Inc.Memory device search system and methodUS6401117Mar 31, 1999Jun 4, 2002Intel CorporationPlatform permitting execution of multiple network infrastructure applicationsUS6404752Aug 27, 1999Jun 11, 2002International Business Machines CorporationNetwork switch using network processor and methodsUS6421730Apr 1, 1999Jul 16, 2002Intel CorporationProgrammable system for processing a partitioned network infrastructureUS6430527Aug 26, 1998Aug 6, 2002Avici SystemsPrefix search circuitry and methodUS6441053Jun 8, 1999Aug 27, 2002The Trustees Of The University Of PennsylvaniaInhibitors of glycogen synthase kinase-3 and methods for identifying and using the sameUS6460112Jun 22, 1999Oct 1, 2002Netlogic Microsystems, LlcMethod and apparatus for determining a longest prefix match in a content addressable memory deviceUS6460120Aug 27, 1999Oct 1, 2002International Business Machines CorporationNetwork processor, memory organization and methodsUS6480839Jul 18, 2000Nov 12, 2002Go2Market.ComSystem and method for improving database data manipulation using direct indexing within a B*tree index having a tunable index organizationUS6490592 *Dec 30, 1999Dec 3, 2002Nortel Networks LimitedMethod of and apparatus for generating a tree data structure supporting longest match lookupUS6522632 *Jun 25, 1998Feb 18, 2003Avici SystemsApparatus and method for efficient prefix searchUS6526055Oct 20, 1998Feb 25, 2003Sun Microsystems, Inc.Method and apparatus for longest prefix address lookupUS6532457Jul 14, 2000Mar 11, 2003Ezchip Technologies Ltd.Look-ahead tree structureUS6535491Nov 29, 1999Mar 18, 2003Cisco Technology, Inc.Method and apparatus for rapidly reconfiguring computer networks using a spanning tree algorithmUS6539369 *Dec 8, 2000Mar 25, 2003Mosaid Technologies, Inc.Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup tableUS6553370Oct 4, 2000Apr 22, 2003Lsi Logic CorporationFlexible search engine having sorted binary search tree for perfect matchUS6564211Oct 4, 2000May 13, 2003Lsi Logic CorporationFast flexible search engine for longest prefix matchUS6611832Oct 9, 2001Aug 26, 2003International Business Machines Corp.Data structure for longest-matching prefix searching and updating method for search table data structuresUS6614789Dec 29, 1999Sep 2, 2003Nasser YazdaniMethod of and apparatus for matching strings of different lengthsUS6633865Dec 23, 1999Oct 14, 2003Pmc-Sierra LimitedMultithreaded address resolution systemUS6636849Nov 22, 2000Oct 21, 2003Genmetrics, Inc.Data search employing metric spaces, multigrid indexes, and B-grid treesUS6636956Jul 6, 2001Oct 21, 2003Cypress Semiconductor Corp.Memory management of striped pipelined data structuresUS6662287Oct 18, 2001Dec 9, 2003Lsi Logic CorporationFast free memory address controllerUS6691124Apr 4, 2001Feb 10, 2004Cypress Semiconductor Corp.Compact data structures for pipelined message forwarding lookupsUS6694323Jan 27, 2003Feb 17, 2004Sybase, Inc.System and methodology for providing compact B-TreeUS6697276Feb 1, 2002Feb 24, 2004Netlogic Microsystems, Inc.Content addressable memory deviceUS6707693Jun 5, 2002Mar 16, 2004Netlogic Microsystems, Inc.Content addressable memory with simultaneous write and compare functionUS6757779Oct 31, 2001Jun 29, 2004Netlogic Microsystems, Inc.Content addressable memory with selectable mask write modeUS6768739Feb 9, 2000Jul 27, 2004Nec CorporationRouter with a cache having a high hit probabilityUS6778530Nov 8, 1999Aug 17, 2004Juniper Networks, Inc.Method and apparatus for multiple field matching in network deviceUS6782382 *Mar 7, 2001Aug 24, 2004International Business Machines CorporationPrefix search method and data structure using compressed search tablesUS6831850Nov 18, 2003Dec 14, 2004Netlogic Microsystems, Inc.Content addressable memory with configurable class-based storage partitionUS6839800Aug 28, 2002Jan 4, 2005Hywire Ltd.RAM-based range content addressable memoryUS6859455Nov 10, 2000Feb 22, 2005Nasser YazdaniMethod and apparatus for building and using multi-dimensional index trees for multi-dimensional data objectsUS6928430 *Apr 23, 2002Aug 9, 2005Integrated Silicon Solution, Inc.Prefix match search schemeUS6934795Oct 31, 2001Aug 23, 2005Netlogic Microsystems, Inc.Content addressable memory with programmable word width and programmable priorityUS6941314Apr 15, 2002Sep 6, 2005Lsi Logic CorporationUser selectable editing protocol for fast flexible search engineUS6944709Oct 31, 2001Sep 13, 2005Netlogic Microsystems, Inc.Content addressable memory with block-programmable mask write mode, word width and priorityUS7007027Dec 2, 2002Feb 28, 2006Microsoft CorporationAlgorithm for tree traversals using left linksUS7016904Apr 25, 2001Mar 21, 2006Altera CorporationMethod and system for rapid insertion of various data streams into sorted tree structuresUS7017021Apr 4, 2001Mar 21, 2006Cypress Semiconductor Corp.High-speed message forwarding lookups for arbitrary length strings using pipelined memoriesUS7023807Nov 12, 2002Apr 4, 2006Timothy Scott MichelsNetwork switching device with pipelined search enginesUS7035844Feb 25, 2002Apr 25, 2006Lsi Logic CorporationFFS search and edit pipeline separationUS7047317Jun 14, 2000May 16, 2006Altera CorporationHigh performance network address processor systemUS7062499 *Jan 8, 2002Jun 13, 2006Intel CorporationEnhanced multiway radix tree and related methodsUS7076602Oct 21, 2003Jul 11, 2006Hywire Ltd.Multi-dimensional associative search engine having an external memoryUS7107263Dec 8, 2000Sep 12, 2006Netrics.Com, Inc.Multistage intelligent database search methodUS7162572Oct 12, 2004Jan 9, 2007Spans Logic Inc.Memory and power efficient mechanism for fast table lookupUS7231383May 1, 2002Jun 12, 2007Lsi CorporationSearch engine for large-width dataUS7257530Feb 12, 2003Aug 14, 2007Hongfeng YinMethod and system of knowledge based search engine using text miningUS7289979 *Dec 10, 2003Oct 30, 2007Alcatel LucentParallel asymmetric binary search on lengthsUS7292162Jul 12, 2006Nov 6, 2007Madian SomasundaramData coding system and methodUS7383276Jan 30, 2004Jun 3, 2008Microsoft CorporationConcurrency control for B-trees with node deletionUS7426518Mar 28, 2003Sep 16, 2008Netlogic Microsystems, Inc.System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded sizeUS7437354May 7, 2004Oct 14, 2008Netlogic Microsystems, Inc.Architecture for network search engines with fixed latency, high capacity, and high throughputUS7478109 *Mar 15, 2004Jan 13, 2009Cisco Technology, Inc.Identification of a longest matching prefix based on a search of intervals corresponding to the prefixesUS7571156Mar 25, 2004Aug 4, 2009Netlogic Microsystems, Inc.Network device, storage medium and methods for incrementally updating a forwarding databaseUS7603346Feb 13, 2007Oct 13, 2009Netlogic Microsystems, Inc.Integrated search engine devices having pipelined search and b-tree maintenance sub-engines thereinUS7653619Feb 13, 2007Jan 26, 2010Netlogic Microsystems, Inc.Integrated search engine devices having pipelined search and tree maintenance sub-engines therein that support variable tree heightUS20020089937Nov 14, 2001Jul 11, 2002Srinivasan VenkatacharyPacket matching method and systemUS20020116526 *Dec 8, 2000Aug 22, 2002Mosaid Technologies, Inc.Method and apparatus for longest match address lookupUS20020146009Apr 4, 2001Oct 10, 2002Pankaj GuptaHigh-speed message forwarding lookups for arbitrary length strings using pipelined memoriesUS20020147721 *Apr 4, 2001Oct 10, 2002Pankaj GuptaCompact data structures for pipelined message forwarding lookupsUS20020152413Jun 11, 2002Oct 17, 2002Waters Gregory M.Prefix search circuitry and methodUS20030009453Jul 3, 2001Jan 9, 2003International Business Machines CorporationMethod and system for performing a pattern match search for text stringsUS20030009466Jun 21, 2001Jan 9, 2003Ta John D. C.Search engine with pipeline structureUS20030093613Aug 9, 2002May 15, 2003David ShermanCompressed ternary mask system and methodUS20030093646Aug 28, 2002May 15, 2003Hywire Ltd.RAM-based range content addressable memoryUS20030123397Dec 31, 2001Jul 3, 2003Kang-Bok LeeMethod for generating nodes in multiway search tree and search method using the sameUS20030123459Sep 17, 2001Jul 3, 2003Heng LiaoEfficiency masked matchingUS20030163302Feb 12, 2003Aug 28, 2003Hongfeng YinMethod and system of knowledge based search engine using text miningUS20030182272 *Mar 22, 2002Sep 25, 2003International Business Machines CorporationEfficient implementation of an index structure for multi-column bi-directional searchesUS20040030686Jun 6, 2003Feb 12, 2004Cardno Andrew JohnMethod and system of searching a database of recordsUS20040059731Dec 8, 2000Mar 25, 2004Yianilos Peter N.Multistage intelligent database search methodUS20040062208 *Sep 30, 2002Apr 1, 2004Mosaid Technologies Inc.Dense mode coding schemeUS20040083336Oct 21, 2003Apr 29, 2004Hywire Ltd.Multi-dimensional associative search engine having an external memoryUS20040109451Dec 6, 2002Jun 10, 2004Stmicroelectronics, Inc.Apparatus and method of using fully configurable memory, multi-stage pipeline logic and an embedded processor to implement multi-bit trie algorithmic network search engineUS20040139274Oct 20, 2003Jul 15, 2004Hui Ronald Chi-ChunVirtual content addressable memory with high speed key insertion and deletion and pipelined key searchUS20040170379Feb 18, 2004Sep 2, 2004Kabushiki Kaisha TohsibaHierarchical storage scheme and data playback scheme for enabling random access to realtime stream dataUS20040193619Mar 28, 2003Sep 30, 2004Srinivasan VenkatacharySystem and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded sizeUS20040205229Oct 23, 2003Oct 14, 2004Isic CorporationMethod and apparatus for longest prefix matching in processing a forwarding information databaseUS20040249803May 7, 2004Dec 9, 2004Srinivasan VankatacharyArchitecture for network search engines with fixed latency, high capacity, and high throughputUS20050091443Oct 23, 2003Apr 28, 2005Hywire Ltd.Search method using coded keysUS20050131867Dec 10, 2003Jun 16, 2005AlcatelParallel asymmetric binary search on lengthsUS20050163122Dec 30, 2004Jul 28, 2005University Of Florida Research Foundation, Inc.System and methods for packet filteringUS20050195832 *Feb 9, 2005Sep 8, 2005Washington UniversityMethod and system for performing longest prefix matching for network address lookup using bloom filtersUS20060167843 *Jan 24, 2005Jul 27, 20063Com CorporationTire search engines and ternary CAM used as pre-classifierUS20060259682Jul 12, 2006Nov 16, 2006Madian SomasundaramData coding system and methodUS20070038626 *Oct 18, 2006Feb 15, 2007Waters Gregory MPrefix search circuitry and methodUS20070276648Feb 13, 2007Nov 29, 2007Lsi Logic CorporationSequential tester for longest prefix search enginesWO2004088548A1Mar 26, 2004Oct 14, 2004Cypress SemiconductorSystem and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size* Cited by examinerNon-Patent CitationsReference1"B-Trees: Balanced Tree Data Structures" pp. 1-8 (believed prior to Nov. 27, 2006) .2"B-Trees: Balanced Tree Data Structures" pp. 1-8 (believed prior to Nov. 27, 2006) <http://www.bluerwhite.org/btree/>.3Aggarwal et al. "A Model for Hierarchical Memory" Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing STOC pp. 305-314 (1987).4Answers.com, http://www.answers.com/topic/b-tree, B~tree: Information From Answers.com, Admitted prior art. 6 pages.5Answers.com, http://www.answers.com/topic/b-tree, B˜tree: Information From Answers.com, Admitted prior art. 6 pages.6B*-tree, http://en.wikipedia.org/wiki/B%2A-tree, Admitted prior art. 1 page.7Bayer, R. et al., "Prefix B-Trees," ACM Trans. On Database Systems, vol. 2, No. 1, Mar. 1977, pp. 11-26.8Bender et al. "Cache-oblivious B-trees", Siam J. Comput, 2000, pp. 1-18.9Canonical form http://en.wikipedia.org/wiki/Canonical-form, Admitted prior art, 1 page.10Canonical form http://en.wikipedia.org/wiki/Canonical—form, Admitted prior art, 1 page.11Chang et al. "Dynamic Routing Tables using Augmented Balanced Search Tree" National Cheng Kung University and I-Shou University (35 pages)(believed prior to Jul. 23, 2004).12Choudhury et al. "A New Buffer Management Scheme for Hierarchical Shared Memory Switches" IEEE/ACM Transactions on Networking (TON) 5(5):728-738 (1997).13Djordjevic et al. "A Hierarchical Memory System Environment" Proceedings of the 1988 Workshop on Computer Architecture Education WCAE (6 pages)(1998).14Final Office Action dated Aug. 4, 2009 for U.S. Appl. No. 11/674,487, 22 Pages.15Final Office Action dated Dec. 8, 2009 for U.S. Appl. No. 11/768,646, 13 Pages.16Final Office Action dated Nov. 24, 2009 for U.S. Appl. No. 11/685,982, 20 Pages.17Final Office Action dated Sep. 10, 2008 for U.S. Appl. No. 11/184,243, 15 Pages.18Henry Hong-yi Tzeng, "Longest Prefix Search Using Compressed Trees", In Proceedings of IEEE Globe.com, 1998.19Kobayashi et al. "A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing", C&C Media Research Laboratories, NEC Corporation 2000 IEEE.20Lu et al. "A B-Tree Dynamic Router-Table Design" pp. 1-27 (believed prior to Nov. 27, 2006).21Nasser Yazdani et al., "Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths", IEEE, 2001, p. 76-85.22Network address processor makes embedded DRAM a virtue, http://www.electronicproducts.com/print.asp?ArticleURL=oct12.oct2000, Printed Aug. 14, 2006, Admitted Prior Art, 1 page.23Non-final Office Action dated Apr. 1, 2009 for U.S. Appl. No. 11/532,225, 8 Pages.24Non-final Office Action dated Dec. 11, 2008 for U.S. Appl. No. 11/674,474, now Issued Patent 7,603,346 , 22 Pages.25Non-final Office Action dated Dec. 11, 2008 for U.S. Appl. No. 11/674,487, 23 Pages.26Non-final Office Action dated Dec. 17, 2009 for U.S. Appl. No. 11/184,843, 18 Pages.27Non-final Office Action dated Jul. 21, 2009 for U.S. Appl. No. 11/685,982, 20 Pages.28Non-final Office Action dated Jun. 25, 2009 for U.S. Appl. No. 11/184,243, 15 Pages.29Non-final Office Action dated Jun. 25, 2009 for U.S. Appl. No. 11/768,646, 12 Pages.30Non-final Office Action dated Mar. 18, 2009 for U.S. Appl. No. 11/184,243, 15 Pages.31Non-final Office Action dated Nov. 15, 2007 for U.S. Appl. No. 11/184,243, 18 Pages.32Non-final Office Action dated Sep. 10, 2009 for U.S. Appl. No. 11/532,225, 8 Pages.33Notice of Allowance dated Aug. 7, 2009 for U.S. Appl. No. 11/674,474, now Issued Patent 7,603,346 , 13 Pages.34Notice of Allowance dated Dec. 2, 2009 for U.S. Appl. No. 11/674,487, 11 Pages.35Notice of Allowance dated Jan. 12, 2010 for U.S. Appl. No. 11/532,225, 6 Pages.36O'Connor et al. "The iFlow Address Processor" 2001 IEEE Micro pp. 16-23 (2001).37Srinivasan 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.38Suri et al. "Multiway Range Trees: Scalable IP Lookup with Fast Updates" (5 pages)(believed prior to Nov. 27, 2006) http://www.cs.edu/~Varghese/PAPERS/globecome2001.pdf.39Suri et al. "Multiway Range Trees: Scalable IP Lookup with Fast Updates" (5 pages)(believed prior to Nov. 27, 2006) http://www.cs.edu/˜Varghese/PAPERS/globecome2001.pdf.40Tree (data structure), http://en.wikipedia.org/wiki/Tree-data-structure, (Redirected from Tree data structure, Admitted prior art. 2 pages.41Tree (data structure), http://en.wikipedia.org/wiki/Tree—data—structure, (Redirected from Tree data structure, Admitted prior art. 2 pages.42Uga 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.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7953721May 31, 2011Netlogic Microsystems, Inc.Integrated search engine devices that support database key dumping and methods of operating sameUS8086641Dec 17, 2008Dec 27, 2011Netlogic Microsystems, Inc.Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating sameUS8886677Jun 26, 2007Nov 11, 2014Netlogic Microsystems, Inc.Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix lengthUS9043757 *Dec 13, 2012May 26, 2015Oracle International CorporationIdentifying differences between source codes of different versions of a software when each source code is organized using incorporated filesUS9245626Oct 26, 2012Jan 26, 2016Cisco Technology, Inc.System and method for packet classification and internet protocol lookup in a network environmentUS20100228716 *Mar 4, 2010Sep 9, 2010Canon Kabushiki KaishaProtocol processing apparatus and methodUS20140173559 *Dec 13, 2012Jun 19, 2014Oracle International CorporationIdentifying differences between source codes of different versions of a software when each source code is organized using incorporated filesUS20150098470 *Oct 4, 2013Apr 9, 2015Broadcom CorporationHierarchical hashing for longest prefix matching* Cited by examinerClassifications U.S. Classification707/706International ClassificationG06F17/30Cooperative ClassificationG06F17/30327European ClassificationG06F17/30S2P3Legal EventsDateCodeEventDescriptionSep 28, 2007ASAssignmentOwner name: INTEGRATED DEVICE TECHNOLOGY, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:DEPELTEAU, GARY;REEL/FRAME:019897/0255Effective date: 20070928Jul 17, 2009ASAssignmentOwner name: SILICON VALLEY BANK, CALIFORNIAFree format text: SECURITY AGREEMENT;ASSIGNORS:NETLOGIC MICROSYSTEMS, INC.;NETLOGIC MICROSYSTEMS INTERNATIONAL LIMITED;NETLOGIC MICROSYSTEMS CAYMANS LIMITED;REEL/FRAME:022973/0710Effective date: 20090717Jul 23, 2009ASAssignmentOwner name: NETLOGIC MICROSYSTEMS, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:INTEGRATED DEVICE TECHNOLOGY, INC.;REEL/FRAME:022996/0609Effective date: 20090717Aug 30, 2011ASAssignmentOwner name: NETLOGIC MICROSYSTEMS INTERNATIONAL LIMITED, CALIFFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:SILICON VALLEY BANK;REEL/FRAME:026830/0141Effective date: 20110826Owner name: NETLOGIC MICROSYSTEMS, INC., CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:SILICON VALLEY BANK;REEL/FRAME:026830/0141Effective date: 20110826Owner name: NETLOGIC MICROSYSTEMS CAYMANS LIMITED, CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:SILICON VALLEY BANK;REEL/FRAME:026830/0141Effective date: 20110826May 9, 2014REMIMaintenance fee reminder mailedSep 28, 2014LAPSLapse for failure to pay maintenance feesNov 18, 2014FPExpired due to failure to pay maintenance feeEffective date: 20140928Apr 16, 2015ASAssignmentOwner name: BROADCOM CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:NETLOGIC I LLC;REEL/FRAME:035443/0763Effective date: 20150327Owner name: NETLOGIC I LLC, DELAWAREFree format text: CHANGE OF NAME;ASSIGNOR:NETLOGIC MICROSYSTEMS, INC.;REEL/FRAME:035443/0824Effective date: 20130123RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services