Source: http://www.google.com/patents/US7953721?dq=456322
Timestamp: 2017-09-22 12:04:31
Document Index: 97770812

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

Patent US7953721 - Integrated search engine devices that support database key dumping and ... - Google Patents
Methods of operating a search engine device include repeatedly reading next keys (and associated handles) from a database within the search engine device in order to identify and transfer some or possibly all of the contents of the database to another device (e.g., command host) requesting the database...http://www.google.com/patents/US7953721?utm_source=gb-gplus-sharePatent US7953721 - Integrated search engine devices that support database key dumping and methods of operating same
Publication number US7953721 B1
Application number US 11/963,041
Publication number 11963041, 963041, US 7953721 B1, US 7953721B1, US-B1-7953721, US7953721 B1, US7953721B1
Inventors Gary Depelteau, David Walter Carr
Patent Citations (126), Non-Patent Citations (59), Referenced by (2), Classifications (5), Legal Events (9)
Integrated search engine devices that support database key dumping and methods of operating same
US 7953721 B1
Methods of operating a search engine device include repeatedly reading next keys (and associated handles) from a database within the search engine device in order to identify and transfer some or possibly all of the contents of the database to another device (e.g., command host) requesting the database contents. An operation to read a next key includes: (i) searching a pipelined database within the search engine device with a first key to identify at least one key therein that is greater than the first key and then (ii) executing a next key fetch operation in the pipelined database to identify the next key from the at least one key. The next key and a handle associated with the next key are then retrieved from the search engine device (e.g., transferred to a command host).
reading a next key from the search engine device by:
searching a pipelined database within the search engine device with a first key to identify at least one key therein that is greater than the first key;
executing a next key fetch operation in the pipelined database to identify the next key from the at least one key; and then
retrieving the next key and a handle associated with the next key from the search engine device,
wherein the pipelined database comprises multiple levels of hierarchical processing logic, wherein each level of the multiple levels of hierarchical processing logic include (a) control and search logic, (b) storage for data structures for a level of a b-tree associated therewith, and (c) a node maintenance sub-engine, and
wherein searching a pipelined database within the search engine device comprises replacing an idle cycle detected at a highest level of the pipelined database with a next key search operation.
2. The method of claim 1, wherein searching a pipelined database within the search engine device comprises searching the pipelined database within the search engine device with a first key to identify a respective next key candidate that is greater than the first key at each of a plurality of levels of the pipelined database; and wherein executing a next key fetch operation comprises identifying the next key as the next key candidate located at a lowest level of the pipelined database containing a next key candidate.
3. The method of claim 1, wherein executing a next key fetch operation comprises replacing an idle cycle detected a highest level of the pipelined database with the next key fetch operation.
4. The method of claim 1, wherein executing a next key fetch operation comprises replacing an idle cycle detected a highest level of the pipelined database with the next key fetch operation.
5. The method of claim 1, wherein executing the next key fetch operation is preceded by generating a ready message that passes from a second level of the pipelined database to an immediately next higher first level of the pipelined database in response to storing a next key candidate at the second level of the pipelined database.
6. The method of claim 5, wherein executing the next key fetch operation comprises passing a first next key candidate from the first level of the pipelined database to the second level of the pipelined database.
7. The method of claim 6, wherein executing the next key fetch operation comprises passing a second next key candidate stored at the second level of the pipelined database from the second level of the pipelined database to an immediately next lower third level of the pipelined database.
8. The method of claim 1, wherein executing the next key fetch operation is preceded by generating a ready message that passes from a second level of the pipelined database to an immediately next higher first level of the pipelined database.
9. The method of claim 8, wherein executing the next key fetch operation comprises passing a first next key candidate from the first level of the pipelined database to the second level of the pipelined database.
10. The method of claim 9, wherein executing the next key fetch operation comprises passing the first next key candidate from the second level of the pipelined database to an immediately next lower third level of the pipelined database; and wherein retrieving the next key comprises retrieving the first next key candidate and handle associated with the first next key candidate from the search engine device.
11. An integrated search engine device, comprising:
a storage device including a pipelined database for storing a plurality of search keys; and
a search engine configured to perform the steps of:
(a) search the pipelined database with a first key to identify at least one key therein that is greater than the first key,
(b) execute a next key fetch operation in the pipelined database to identify a next key from the at least one key, and
(c) output the next key and a handle associated with the next key,
12. The integrated search engine device of claim 11, wherein the search engine is further configured to search the database with a first key to identify a respective next key candidate that is greater than the first key at each of a plurality of levels of the database, and wherein the next key corresponds to the next key candidate located at a lowest level of the database containing a next key candidate.
a hierarchical memory configured to store a plurality of databases of search keys therein arranged as a corresponding plurality of multi-way trees that span multiple levels of the hierarchical memory; and
a plurality of search and tree maintenance sub-engines for dumping keys from a first one of the plurality of databases to a second one of the plurality of databases, the plurality of search and tree maintenance sub-engines being configured to:
search the first one of the plurality of databases for a first key stored therein to obtain a handle associated with the first key;
store the first key and the handle associated with the first key in the second one of the plurality of databases;
search the first one of the plurality of databases using the first key identified therein as a search key to obtain a second key and a handle associated with the second key; and
store the second key and the handle associated with the second key in the second one of the plurality of databases,
wherein the plurality of search and tree maintenance sub-engines comprises multiple levels of hierarchical processing logic, wherein each level of the multiple levels of hierarchical processing logic include (a) control and search logic, (b) storage for data structures for a level of a b-tree associated therewith, and (c) a node maintenance sub-engine, and
wherein searching the hierarchical memory within the search engine device comprises replacing an idle cycle with a search operation.
This application is a continuation-in-part of U.S. application Ser. No. 11/934,240, filed Nov. 2, 2007, which claims priority to U.S. Provisional Application Ser. No. 60/867,277, filed Nov. 27, 2006, the disclosures of which are hereby incorporated herein by reference.
This application is related to U.S. application Ser. No. 11/858,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; U.S. application Ser. No. 11/768,646, filed Jun. 26, 2007, entitled Integrated Search Engine Devices that Support LPM Search Operations Using Span Prefix Masks that Encode Key Prefix Length, and U.S. application Ser. No. 11/864,290, filed Sep. 28, 2007, entitled Integrated Search Engine Devices that Support Multi-Way Search Trees Having Multi-Column Nodes, the disclosures of which are hereby incorporated herein by reference.
B 0/1
C 0/2
D 0/3
E 0/4
F 144/4
G 192/3
H 224/3
I 240/4
J 128/2
K 208/5
M 248/5
N 160/4
O 96/3
P 112/4
Q 168/6
R 170/8
S 120/5
T 0/5
U 192/2
V 64/2
As illustrated by the highlighted search path, a search of the b-tree using 171 as an applied search key begins at Node 0-0. The search prefix J at Node 0-0 represents a match with the search key 171 because 171 (i.e., 10101011b) is a match with 128/2 (i.e., 10XXXXXX), where X represents a “don't-care” value. The search then proceeds to Node 1-1 (i.e., along a right-side branch from Node 0-0 to Node 1-1) because 171 is greater than 128. No matches are present at Node 1-1 because the search key 171 (i.e., 10101011b) does not match either the search prefix R: 170/8 (10101010b) or the search prefix H:224/3 (i.e., 111XXXXX). Because the search key 171 is greater than 170 and less than 224, the search then proceeds to and terminates at Node 2-5, which is a leaf node of the b-tree 30. None of the search prefixes U:192/2, G:192/3 or K:208/5 at Node 2-5 represent a match with the search key 171. Thus, based on the illustrated search path, which traverses Nodes 0-0, 1-1 and 2-5 of the b-tree 30, only search prefix J:128/2 represents a matching entry within the search key 171. However, as illustrated best by FIG. 2, the search prefix Q:168/6, which resides at Node 2-4 of FIG. 3, actually represents the longest prefix match with the search key 171, yet this search prefix was not within the search path and was not detected during the search operation. Moreover, the search prefixes A:0/0, L:128/1 and N:160/4 also represent matches that were not within the search path. This means that the conventional sorting of prefixes within the b-tree 30 of FIG. 3 will not yield correct results for all applied search keys.
An additional type of b-tree data structure includes a b*tree data structure, which can require non-root nodes to be at least ⅔ full at all times. To maintain this fill requirement, a sibling node is not immediately split whenever it is full. Instead, keys are first shared between sibling nodes before node splitting is performed. Only when all sibling nodes within a group are full does a node splitting operation occur upon insertion of a new search key. FIG. 12 illustrates a conventional three-level b*tree data structure. These three levels are illustrated as L0, L1 and L2, where L0 is treated as the root level and L2 is treated as a leaf level. Level L1 is an intermediate level, which is a child relative to the root level and a parent relative to the leaf level. As will be understood by those skilled in the art, a b*tree of type N:(N+1) (i.e., 2:3, 3:4, 4:5, . . . ) requires all non-root nodes to be between N/(N+1) and 100% capacity (i.e, 67%, 75%, 80%, . . . up to 100%) before and after an insert or delete operation has been fully performed. The b*tree of FIG. 12 is a 3:4 tree, with four key locations per node (i.e., M=4).
FIG. 13A illustrates a portion of a b*tree with excess capacity having three sibling nodes at a leaf level and a parent node (at the root level) containing the search keys A-K, which represent numeric search key values. The leftmost sibling node contains the search keys A, B and C, the middle sibling node contains the search keys E, F and G and the rightmost sibling node contains the search keys I, J and K. The parent node contains the search keys D and H. These sibling nodes are at 75% capacity, which meets the requirement that all non-root nodes be between N/(N+1) and 100% capacity for a 3:4 type b*tree, where N=3. As illustrated by FIG. 13B, an insertion of the key L into the b*tree of FIG. 13A increases the rightmost sibling node to full capacity without affecting the other two sibling nodes. The additional insertion of key M into the rightmost sibling node in the b*tree of FIG. 13B causes the transfer of key Ito the parent node and the transfer of key H from the parent node to the middle sibling node, as illustrated by FIG. 13C.
SPM SEARCH “AND” SHORTER PREFIX WITHIN SPM
LENGTH VECTOR PREFIX RESULT LEFT SUB-TREE? VALUE
/0 00000000 128 = 10000000 0/0 = A YES SPM[0] = 1
/1 10000000 128 = 10000000 128/1 = L  YES SPM[1] = 1
/2 11000000 128 = 10000000 128/2 = J  YES SPM[2] = 1
/3 11100000 128 = 10000000 128/3 NO SPM[3] = 0
/4 11110000 128 = 10000000 128/4 NO SPM[4] = 0
/5 11111000 128 = 10000000 128/5 NO SPM[5] = 0
/6 11111100 128 = 10000000 128/6 NO SPM[6] = 0
/7 11111110 128 = 10000000 128/7 NO SPM[7] = 0
/8 11111111 128 = 10000000 128/8 NO SPM[8] = 0
/0 00000000 0 = 00000000 0/0 = A YES SPM[0] = 1
/1 10000000 0 = 00000000 0/1 = B YES SPM[1] = 1
/2 11000000 0 = 00000000 0/2 = C YES SPM[2] = 1
/3 11100000 0 = 00000000 0/3 = D YES SPM[3] = 1
/4 11110000 0 = 00000000 0/4 NO SPM[4] = 0
/5 11111000 0 = 00000000 0/5 NO SPM[5] = 0
/6 11111100 0 = 00000000 0/6 NO SPM[6] = 0
/7 11111110 0 = 00000000 0/7 NO SPM[7] = 0
/8 11111111 0 = 00000000 0/8 NO SPM[8] = 0
/0 00000000 96 = 01100000 0/0 NO SPM[0] = 0
/1 10000000 96 = 01100000 0/1 NO SPM[1] = 0
/2 11000000 96 = 01100000 64/2 = V YES SPM[2] = 1
/3 11100000 96 = 01100000 96/3 = O YES SPM[3] = 1
/4 11110000 96 = 01100000 96/4 NO SPM[4] = 0
/5 11111000 96 = 01100000 96/5 NO SPM[5] = 0
/6 11111100 96 = 01100000 96/6 NO SPM[6] = 0
/7 11111110 96 = 01100000 96/7 NO SPM[7] = 0
/8 11111111 96 = 01100000 96/8 NO SPM[8] = 0
/0 00000000 170 = 10101010 0/0 NO SPM[0] = 0
/1 10000000 170 = 10101010 128/1 NO SPM[1] = 0
/2 11000000 170 = 10101010 128/2 NO SPM[2] = 0
/3 11100000 170 = 10101010 160/3 NO SPM[3] = 0
/4 11110000 170 = 10101010 160/4 = N YES SPM[4] = 1
/5 11111000 170 = 10101010 168/5 NO SPM[5] = 0
/6 11111100 170 = 10101010 168/6 = Q YES SPM[6] = 1
/7 11111110 170 = 10101010 170/7 NO SPM[7] = 0
/8 11111111 170 = 10101010 170/8 = R YES SPM[8] = 1
/0 00000000 224 = 11100000 0/0 NO SPM[0] = 0
/1 10000000 224 = 11100000 128/1 NO SPM[1] = 0
/2 11000000 224 = 11100000 192/2 = U YES SPM[2] = 1
/3 11100000 224 = 11100000 224/3 = H YES SPM[3] = 1
/4 11110000 224 = 11100000 224/4 NO SPM[4] = 0
/5 11111000 224 = 11100000 224/5 NO SPM[5] = 0
/6 11111100 224 = 11100000 224/6 NO SPM[6] = 0
/7 11111110 224 = 11100000 224/7 NO SPM[7] = 0
/8 11111111 224 = 11100000 224/8 NO SPM[8] = 0
Because the search key 171 is greater than 128, the next stage of the search at Level 1 passes down and to the right of node 0-0 to node 1-1. At node 1-1, it is apparent that the search key 171 is greater than the search prefix R:170/8 and less than the search prefix H:224/3, which means the next stage of the search operation at Level 2 passes to node 2-5, which contains no matching search prefixes. Here, the breakout box to the right of node 1-1 shows that the span prefix mask associated with the search prefix R:170/8 identifies three search prefixes (N:160/4, Q:168/6 and R:170/8) as being within the b-tree 40 even though the search path passes to the right of the search prefix R and does not encounter leaf node 2-4 of the b-tree 40, which contains the additional matching search prefixes of N:160/4 and Q:168/6. These three search prefixes are identified by ANDing the vectors 11110000 (corresponding to SPM /4), 11111100 (corresponding to SPM /6) and 11111111 (corresponding to SPM /8) with 170, which is represented in binary format as 10101010b. This ANDing operation is illustrated more fully by TABLE 5. Of the identified search prefixes N:160/4, Q:168/6 and R:170/8 within the breakout box to the right of node 1-1, search prefix Q:168/6 represents a longest prefix match to the applied search key 171. Thus, even though the search prefix Q:168/6 is not within the search path that extends from node 0-0 to node 1-1 and then terminates at node 2-5, it is properly identified as a longest prefix match with the aid of the SPMs. In this manner, the SPM associated with search prefix R:170/8 supports a “lookahead” search operation to node 2-4, which is outside the search path associated with the applied search key 171.
A search engine device according to additional embodiments of the present invention is configured as a pipelined search engine having a multiple levels of hierarchical processing logic. As described and illustrated more fully hereinbelow with respect to FIGS. 7-11, each (LEVEL_i) includes: (i) control and search logic, (ii) storage for that level's node data-structures, and (iii) a node maintenance sub-engine. The node maintenance sub-engine locally handles node modifications for that level's nodes, communicates with its child level (i.e., next lowest level the hierarchy) to assist in handling node overflows and underflows at that level (does not apply to leaf level) and communicates with its parent level to get support in handling its own node overflows and underflows (does not apply to LEVEL—1). Each level (LEVEL_i) also communicates with a handle memory lookup engine (HANDLE_MEMORY) to delegate and coordinate handle memory updates that must be kept in sync with node data structure updates.
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.
The first node maintenance sub-engine 75 a is illustrated as being communicatively coupled to a maintenance request interface E and a maintenance acknowledgment interface L. The maintenance request interface E may be used to pass maintenance instructions (e.g., insert, delete, age, learn, search and learn (SNL)) to the search engine 60 for processing therein and the maintenance acknowledgment interface L may be used to communicate maintenance results and status information back to an issuing host processor (not shown). Interfaces G, H, I, J and K extend between the node maintenance sub-engines 75 a-75 d, as illustrated. Interface G is a maintenance information interface, which can communicate maintenance information downstream (for inserts and deletes), and a bidirectional interface H is “key drop” interface, which supports upstream requests (for prefixes) and downstream transfers of search prefixes between the plurality of levels (LEVEL—1, LEVEL_L) of the search engine 60. Interface I is a child modification interface, which supports upstream transfers of information relating to child nodes associated with a lower memory level. Interface J is a bidirectional “key raise” interface, which supports upstream transfers of search prefixes between the plurality of levels of the search engine 60 and downstream transfers of parent acknowledgment information. Interface K is a maintenance “ready” interface, which indicates a ready/non-ready status (done or error). Finally, interface P is a handle update interface, which supports handle memory updates within the handle memory lookup engine 80. As illustrated, this interface is coupled to each of the search and tree maintenance sub-engines 70 a-70 d in the pipeline. In some embodiments of the present invention, the handle memory lookup engine 80 may have the same general configuration illustrated by FIGS. 4C-4D and 11A-11B.
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 2/3 of M.
The first node maintenance sub-engine 75 a within the first search and tree maintenance sub-engine 70 a at LEVEL—1 also recommends (via its G interface) to LEVEL—2 a redistribution between NODES 2-0 and 2-1 if NODE 2-0 incurs an overflow in response to the insert command. The second node maintenance sub-engine 75 b at LEVEL—2 recommends (via its G interface) to LEVEL—3 a 2→3 split starting with NODES 3-1 and 3-2, if NODE 3-2 incurs an overflow. In response to this recommendation, the third node maintenance sub-engine 75 c at LEVEL—3 recognizes that the node to be inserted into, NODE 3-2, is already full and will overflow if the insert is to proceed as illustrated by FIG. 9A. Thus, the third node maintenance sub-engine 75 c at LEVEL—3 must undergo an insert overflow operation by performing the 2→3 node split involving NODES 3-1 and 3-2.
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.
Referring still to FIG. 10A, the first search and tree maintenance sub-engine 102 a is illustrated as including a first pipeline control and search logic module 103 a, also referred to herein more generally as a first control module, a first node/handle memory 105 a, which operates as a highest memory level within the hierarchical memory, and a node/handle maintenance sub-engine 107 a. This node/handle maintenance sub-engine 107 a performs operations similar to those described above with respect to the node maintenance sub-engines 75 a-75 d and handle maintenance sub-engine 85 illustrated by FIG. 7. Upon commencement of a search operation, the first control module 103 a receives a search valid signal SEARCH_VALID, which initiates a search operation within the search engine 100 a when asserted, and a corresponding applied search key SEARCH_KEY[(W−1):0]. In response, the first control module 103 a may generate a plurality of signals that are passed downstream to the next control module within the pipeline. This next control module is illustrated as the second control module 103 b.
The plurality of signals that are passed downstream from the first control module 103 a are illustrated as: SEARCH_VALID, SEARCH_KEY[(W−1):0], NEXT_LEVEL[(J−1):0], NEXT_PTR[(P−1):0], MATCH_VALID and BEST_MATCH_HNDL[(A−1):0]. This passing of the plurality of signals need not occur during the same clock cycle(s). In particular, whenever a search and tree maintenance sub-engine completes its role in a search operation, the search request and search key are passed, along with the search results, to the next control module (in the pipeline) via the SEARCH_VALID and SEARCH_KEY[(W−1):0] signals so that the search operands propagate downstream from sub-engine to sub-engine.
Upon commencement of a search operation, the first search and tree maintenance sub-engine 102 a evaluates a locally stored root level indicator (ROOT_LEVEL) and a locally stored root pointer (ROOT_PTR) to determine whether the highest one of the plurality of memory levels residing therein contains a root node of the multi-way tree and, if so, the location (e.g., memory address) of the root node designated by the root pointer ROOT_PTR. The presence of the root node within the highest memory level (LEVEL—1) indicates that the multi-way tree is at a maximum height and spans all memory levels within the hierarchical memory. When this is the case, the first search and tree maintenance sub-engine 102 a participates in the requested search operation, beginning at the memory location identified by the root pointer ROOT_PTR. According to some embodiments of the invention, the root level indicator ROOT_LEVEL and root pointer ROOT_PTR may be stored within the logic (e.g., registers) associated with the first control module 103 a.
In the event the root level indicator ROOT_LEVEL specifies that the root node of the multi-way tree resides within the highest memory level (LEVEL—1), then upon completion of a first level search and generation of a non-match result, the first search and tree maintenance sub-engine 102 a will: (i) set its output NEXT_LEVEL[(J−1):0] to a value that specifies LEVEL—2 as the next memory level to continue the search operation; and (ii) set its output NEXT_PTR[(P−1):0] to a value that identifies the location of the next node of the multi-way tree in LEVEL—2 to be evaluated during the pipelined search operation. The value of NEXT_PTR[(P−1):0] issued by the first control module 103 a is based on a node branching decision made during the search of the root node within LEVEL—1 of the hierarchical memory.
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.
As a further alternative, if the root level indicator ROOT_LEVEL designates that the root node of the multi-way tree resides within a lower memory level (e.g., LEVEL—2 through LEVEL_L), then the first search and tree maintenance sub-engine 102 a will set its output NEXT_LEVEL[(J−1):0] to a value that specifies the memory level containing the root node of the multi-way tree and set its output NEXT_PTR[(P−1):0] to the value of the root pointer ROOT_PTR that is locally stored within the first control module 103 a.
The continuation of the search operation to the next highest memory level causes the second highest search and tree maintenance sub-engine 102 b (LEVEL—2) to evaluate its input NEXT_LEVEL [(J−1):0], which specifies whether it is to participate in the search operation (either as a root note or as a branch node stemming from the root node residing in LEVEL—1). If the second search and tree maintenance sub-engine 102 b is to participate in the search operation, then the value of the input NEXT_PTR[(P−1):0] will specify the location of the node within the LEVEL—2 memory to continue the search by comparing the applied search prefix SEARCH_KEY[(W−1):0] against the search prefixes stored within the designated node. This continuation of the search may result in the generation of a branching pointer to the LEVEL—3 memory. This means the signals NEXT_LEVEL[(J−1):0] and NEXT_PTR[(P−1):0] generated by the second control module 103 b will reflect LEVEL—3 as the next level to participate in the search and also designate the corresponding node within LEVEL—3 to evaluate as the search operation continues. If the search within the second search and tree maintenance sub-engine 102 b is successful at identifying a match with the applied search prefix (SEARCH_KEY[(W−1):0], then output MATCH_VALID will be asserted by the second control module 103 b to reflect the presence of a match with the applied search prefix. The output BEST_MATCH_HNDL[(A−1):0] will also be set to the value of the handle (or possibly other associated data) that corresponds to the matching search prefix within the LEVEL—2 memory.
On the other hand, if the received NEXT_LEVEL[(J−1):0] signal specifies a value other than LEVEL—2 (e.g., LEVEL—3), then the second search and tree maintenance sub-engine 102 b will not participate in the search operation, but will merely pass all its inputs: SEARCH_VALID, SEARCH_KEY[(W−1):0] NEXT_LEVEL [(J−1):0], NEXT_PTR[(P−1):0], MATCH_VALID and BEST_MATCH_HNDL[(A−1):0] downstream to the third search and tree maintenance sub-engine 102 c for further processing.
Referring now to FIG. 10B, a pipelined integrated circuit search engine 100 b according to an additional embodiment of the present invention is illustrated. In this search engine 100 b, the first, second, third and fourth search and tree maintenance engines 102 a′-102 d′ are each illustrated as including respective control modules 103 a′-103 d′, node memories 105 a′-105 d′ and node maintenance sub-engines 107 a′-107 d′.
This search engine 100 b is similar to the search engine 100 a of FIG. 10A, however, the associated data (e.g., prefix handles), which was stored locally in each of the plurality of memory levels (LEVEL—1-LEVEL_L) illustrated in FIG. 10A, is now aggregated together within a dedicated handle memory lookup engine 110. This handle memory lookup engine 110 includes a pipeline control and handle lookup module 113, handle memory 115 and a handle maintenance sub-engine 117, which is communicatively coupled by an interface P (not shown) to the node maintenance sub-engines 107 a′-107 d′. The handle memory lookup engine 110 is configured as a last stage to the pipelined search engine 100 b. To support the transfer of the prefix handles to a dedicated handle memory lookup engine 110, the output signal lines associated with the BEST_MATCH_HANDLE[(A−1):0] in FIG. 10A are replaced by the following signal lines: BEST_MATCH_LEVEL[(J−1):0], BEST_MATCH_PTR[(P−1):0] and BEST_MATCH_KEY_POS[(K−1):0]. The signal BEST_MATCH_LEVEL[(J−1):0] identifies the level within the multi-way tree that contains the matching search prefix and the signal BEST_MATCH_PTR[(P−1):0] identifies the “matching” node. The signal BEST_MATCH_KEY_POS[(K−1):0] identifies the location of the search prefix within the “matching” node. These three signals are referred to herein collectively as the BEST_MATCH_* signals.
Referring now to FIG. 10C, a pipelined integrated circuit search engine 100 c according to another embodiment of the invention may be configured to have LPM capability, which is the capability to identify a search prefix that represents a longest prefix match with an applied search prefix. In this case, the hierarchical memory within the search engine 100 c is configured to store an SPM with each search prefix located above the lowest memory level (LEVEL_L) (i.e., for all search prefixes that do not reside at a leaf level of the multi-way tree). Operations to derive SPMs for search prefixes within a multi-way tree are described more fully hereinabove with respect to FIGS. 4A-4D and TABLES 2-6. In this search engine 100 c, the first, second, third and fourth search and tree maintenance engines 102 a″-102 d″ are each illustrated as including respective control modules 103 a″-103 d″, node memories 105 a″-105 d″ and node maintenance sub-engines 107 a″-107 d″. In addition, the handle memory lookup engine 110′ includes a pipeline control and handle lookup module 113′, handle memory 115′ and a handle maintenance sub-engine 117′, which is communicatively coupled by an interface P (not shown) to the node maintenance sub-engines 107 a″-107 d″.
In particular, the search engine 100 c of FIG. 10C is similar to the search engine 100 b of FIG. 10B, however, an additional signal BEST_MATCH_KEY_OFFSET[(F−1):0] is generated by each of the sub-engines 102 a″-102 d″ within the pipeline. This additional signal identifies the location of an asserted bit (or set bit position) within an SPM associated with a search prefix that is evaluated during a corresponding search operation. Thus, using the b-tree 40 of FIG. 4B as an example of a multi-way tree supported by the search engine 100 c, the identity of the seventh bit of the SPM associated with the search prefix R:170/8 at node 1-1 of the b-tree 40 would be specified by the signal BEST_MATCH_KEY_OFFSET[(F−1):0] for the case of an applied search prefix equal to 171. Referring now to FIGS. 11B and 4C.2, the handle memory 115′ used within the search engine 100 c may be allocated so that all handles are grouped hierarchically (i) by level within the multi-way tree (selected by BEST_MATCH_LEVEL[(J−1):0]), (ii) by node within a respective level (selected by BEST_MATCH_PTR[(P−1):0]); (iii) by position within a respective node (selected by BEST_MATCH_KEY_POS[(K−1):0]); and (iv) by an offset within a respective position (selected by BEST_MATCH_KEY_OFFSET[(F−1):0]). Alternatively, the handle memory 115′ may be configured as illustrated by FIG. 4D.2.
The root node for Key Size=54, DB#1 stores key size, database number and validity information in L1_KEY_CNTXT_STORE and two keys (Key 0, Key 1) in L1_KEY_STORE. These two keys occupy Key 1 and Key 2 storage within the combined root node. Storage is also provided for a left child pointer, ptr_e, associated with Key 1, a left child pointer, ptr_f, associated with Key 2 and a right child pointer, prt_g, associated with the corresponding logical database (i.e., the database for key size Key Size=54, DB#1). These three pointers, ptr_e, ptr_f and ptr_g, point to three nodes at L2 of the hierarchical memory, which have respective fill counts specified as: Key 1 LCH_FCNT, Key 2 LCH_FCNT and DB 54, 1 RCH_FCNT.
Referring now to FIG. 16, the pipelined arrangement of search and tree maintenance sub-engines within the search engines illustrated by FIGS. 7, 10A-10C and 11A-11B, may be configured to support a combined multi-node sub-engine 160 located at a non-leaf level of a multi-way tree, such as a b*tree or other b-tree variant. In the illustrated embodiment of FIG. 16, the multi-node sub-engine 160 may be located at an intermediate level (Li) of a pipelined search engine, where 1≦i≦L for the case where L1 includes the root node of the tree and the integer L designates the leaf level of the tree. Variants of the node sub-engine 160 illustrated by FIG. 16 may also be used to store search keys at the root node of the tree at LEVEL—1 (see, e.g., FIG. 15) or store search keys (w/o child pointers) for nodes located at the leaf level (i.e., LEVEL_L) of the tree, according to further embodiments of the present invention.
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.
To compensate for the removal of the zero-length prefix (a/k/a default route prefix) from the search path of the hierarchical b-tree, a database index table is provided to store a zero prefix length indicator for each of the b-tree databases supported by the search engine along with any corresponding handle associated with a zero-length prefix. This database index table of FIG. 17A is similar to the table illustrated on the left side of FIG. 15A, however, two additional columns are provided to store a zero prefix length indicator (PREF_LEN—0<20>) and a corresponding 20-bit handle (PREF_LEN_HNDL<19:0>), if the indicator has been set. The columns associated with a selected database may be accessed in advance of or concurrently with operations to search a corresponding b-tree of search prefixes, to thereby identify whether the database contains a zero-length prefix that matches all applied search keys and, if so, retrieve a corresponding handle. A zero-length prefix may be indicated when the indicator has been set to a logic 1 value (i.e., PREF_LEN—0<20>=1) and, if so, the corresponding handle read from the database index table is returned as the best match handle in the event the search of the b-tree fails to detect a match.
Then, as illustrated by Block 180 e, a “next key fetch” operation may be performed to identify a next key from the next key candidate(s) identified in Block 180 d. A check is made at Block 180 f to see whether a next key has been identified from the next key candidate(s). If the check at Block 180 f results in a “no” answer, then all remaining keys have been retrieved from the pipelined database and the read next key operations associated with a database key dump operation are completed. However, if the answer is “yes”, then the identified next key (including prefix length indicator) and its associated handle are transferred to another device (e.g., command host). The steps illustrated by Blocks 180 d-180 g are then repeated, using the identified next key as the “previously retrieved key” in the subsequent cycle of operations. The steps illustrated by Blocks 180 d-180 g may be performed using first and second passes through the stages of a pipelined search engine device 100 d, as described hereinbelow with respect to FIG. 10D. However, according to alternative embodiments of the present invention, the search engine device 100 d may also be configured so that the operations illustrated by Blocks 180 d-180 g may be performed by making only a single pass through the pipelined stages (e.g., 102 a″, 102 b″, 102 c″ and 102d″). According to these embodiments of the invention, the passing of the previously retrieved key through each stage of the pipelined search engine may be performed concurrently with operations to pass a next key candidate, if any, to each lower stage and then resolve the next key at the final stage of the pipeline (e.g., LEVEL_L in FIG. 10D).
KEY NO. KEY HANDLE LEVEL NODE
1 0/0 A — —
2 12/6 B 2 2-0
3 17/8 C 1 1-0
4 22/7 D 2 2-1
5 24/5 E 2 2-1
6 30/7 F 1 1-0
7 32/3 G 2 2-2
8 32/4 H 2 2-2
9 38/8 I 0 0-0
10 40/5 J 2 2-3
11 42/7 K 1 1-1
12 60/6 L 2 2-4
13 65/8 M 2 2-4
14 98/8 N 1 1-1
15 128/1  O 2 2-5
16 128/8  P 2 2-5
The maintenance engine controller 122 may then perform a read next key operation by issuing a read next key request and associated key (e.g., previously retrieved key) to the LEVEL—1 search and tree maintenance sub-engine 102 a″ via interface E. The pipeline control and search logic 103 a″ at LEVEL—1 waits for a necessary idle cycle(s) and then inserts a “first pass” command as a next key search command into the forward pipeline along with the search key received from the maintenance engine controller 122. In response to this first pass command, each level (LEVEL—1-LEVEL_L) of the search engine 100 d does a search to identify a smallest key at each level that is just larger than the search key. Completion of the “first pass” operations is communicated back to the LEVEL—1 sub-engine 102 a″ via the lookup core maintenance ready interface K. In particular, the LEVEL_L sub-engine 102 d″ may store the results of its search for the next larger key relative to the search key (i.e., a level L next key candidate), if any, in corresponding flip-flops and then pass a maintenance ready message upstream through the pipeline on interface K. Likewise, the LEVEL—3 sub-engine 102 c″ may store the results of its search for the next larger key relative to the search key (i.e., a level 3 next key candidate), if any, in corresponding flip-flops and then pass a maintenance ready message upstream on interface K only after receiving a ready message from the immediately next lower sub-engine. The LEVEL—2 sub-engine 102 b″ may store the results of its search for the next larger key relative to the search key (i.e., a level 2 next key candidate), if any, in corresponding flip-flops and then pass a maintenance ready message upstream on interface K to the LEVEL—1 sub-engine 102 a″ only after receiving a ready message from the LEVEL—3 sub-engine 102 c″.
Upon receipt of a maintenance ready message associated with the first pass operations on interface K, the LEVEL—1 sub-engine 102 a″ again waits for a necessary idle cycle(s) to commence “second pass” operations by inserting a “next key fetch” command into the pipeline. In response to this command, each sub-engine outputs (e.g., on interface F) it's smallest key candidate stored in flip-flops and passes this candidate key to the next lower level sub-engine. Accordingly, if the LEVEL—1 sub-engine 102 a″ has a valid next key candidate stored within its flip-flops, then the sub-engine 102 a″ passes this “first level” candidate to the LEVEL—2 sub-engine 102 b″. This “first level” candidate will then be passed from the LEVEL—2 sub-engine 102 b″ to the LEVEL—3 sub-engine 102 c″ only if the LEVEL—2 sub-engine 102 b″ does not have a valid next key candidate stored within its flip-flops. If the LEVEL—2 sub-engine 102 b″ has a valid next key candidate, then the LEVEL—2 sub-engine 102 b″ will update the “first level” candidate by dropping it and passing its “second level” candidate to the LEVEL—3 sub-engine 102 c″. This sequence of operations continues through the pipeline until the LEVEL_L sub-engine 102 d″ checks its flip-flops for the presence of a valid next key candidate. Thus, as described herein, the lowest level sub-engine to update the next key candidate is the level that had the next larger key in the database during the “first pass” operations. Accordingly, at the end of the second pass operations, the LEVEL_L sub-engine 102 d″ passes the next key on interface F to the handle memory lookup engine 110′. In response, the handle memory lookup engine 110′ outputs the next key (including prefix length indicator) and associated handle to the maintenance engine controller 122 on interface S. The maintenance engine controller 122 may then report the results (next key and handle) to the external device (e.g., command host) responsible for issuing the database dump command(s) and then seek the next key in the database by issuing another “read next key” request on interface E. According to alternative embodiments of the invention, the operations described above may be performed in a reverse-order sequence by repeatedly seeking the next smaller key within the database instead of repeatedly seeking the next larger key within the database as described herein. In such alternative embodiments, the first key specified during a “read this key” operation may be a fully-specified key containing all logic 1 bits.
The pipelined integrated circuit search engine 100 d of FIG. 10D is also configured to perform database flush operations in response to a database flush command. In particular, the maintenance engine controller 122 may receive a register write instruction from an external device (e.g., command host) to its flush control register (FCR) 124, which operates as a request to flush all keys from a logical database specified in the FCR 124. In response to this register write instruction, the controller 122 clears a corresponding DONE bit within a flush status register (FSR) 123 and issues the database flush command (DB_FLUSH) and the specified logical database over the lookup core maintenance request interface E to the LEVEL—1 sub-engine 102 a″. Among other things, the LEVEL—1 sub-engine 102 a″ waits for an idle cycle(s) and then forwards the database flush command and the specified logical database to the LEVEL—2 sub-engine 102 b″ via the internal pipeline interface F. Similarly, the LEVEL—2 sub-engine 102 b″ forwards the database flush command and the specified logical database to the LEVEL—3 sub-engine 102 c″ and these forwarding operations continue until the LEVEL_L sub-engine 102 d″ receives the database flush command and the specified logical database. Moreover, as illustrated by FIGS. 15A and 17A, the LEVEL—1 sub-engine 102 a″ will update its database index table (associated with a combined root node) by resetting the DB_VALID entry (and the other entries in the same row) associated with the specified database to thereby reflect the removal of the specified database from the search engine 100 d.
Furthermore, the pipeline control and search logic 103 d″ within the LEVEL_L sub-engine 102 d″ receives the database flush command for the specified logical database and forwards the flush command to its node maintenance sub-engine 107 d″, which passes the flush command on the LLM_B interface to a node access list manager 108 d. The node access list manager 108 d processes the flush command by reading through all node locations in a node access list 109 d (accessed via interface LLM_A) and for those assigned to the specified logical database it returns the node to the free list by updating the node access list 109 d accordingly. These operations, which effectively flush all keys stored for the specified logical database from LEVEL_L and makes all resources assigned to the logical database available for future use, are performed essentially as background operations which do not further limit a search bandwidth of the search engine device 100 d by utilizing additional cycles and resources associated with the lookup core internal pipeline interface F. Upon updating the node access list 109 d, the node access list manager 108 d gives a done indication to the node maintenance sub-engine 107 d″ via the interface LLM_B. In response, the LEVEL_L node maintenance sub-engine 107 d″ sends a maintenance ready message on interface K to the next higher level sub-engine in the pipeline.
The pipeline control and search logic 103 c″ within the LEVEL—3 sub-engine 102 c″, which previously received the database flush command for the specified logical database, forwards the flush command to its node maintenance sub-engine 107 c″, which passes the flush command on the L3M_B interface to a node access list manager 108 c. The node access list manager 108 c processes the flush command by reading through all node locations in a node access list 109 c (accessed via interface L3M_A) and for those assigned to the specified logical database it returns the node to the free list by updating the node access list 109 c accordingly. These operations, which effectively flush all keys stored for the specified logical database from LEVEL—3 and makes all resources assigned to the logical database available for future use, are performed essentially as background operations which do not further limit a search bandwidth of the search engine device 100 d by utilizing additional cycles and resources associated with the lookup core internal pipeline interface F. Upon updating the node access list 109 c, the node access list manager 108 c gives a done indication to the node maintenance sub-engine 107 c″ via the interface LL3_B. In response to this done indication and a receipt of a maintenance ready message received from the next lower level in the pipeline, the LEVEL—3 node maintenance sub-engine 107 c″ sends a maintenance ready message on interface K to the LEVEL—2 sub-engine 102 b″.
The pipeline control and search logic 103 b″ within the LEVEL—2 sub-engine 102 b″, which previously received the database flush command for the specified logical database, forwards the flush command to its node maintenance sub-engine 107 b″, which passes the flush command on the L2M_B interface to a node access list manager 108 b. The node access list manager 108 b processes the flush command by reading through all node locations in a node access list 109 b (accessed via interface L2M_A) and for those assigned to the specified logical database it returns the node to the free list by updating the node access list 108 b accordingly. These operations, which effectively flush all keys stored for the specified logical database from LEVEL—2 and makes all resources assigned to the logical database available for future use, are performed essentially as background operations which do not further limit a search bandwidth of the search engine device 100 d by utilizing additional cycles and resources associated with the lookup core internal pipeline interface F. Upon updating the node access list 108 b, the node access list manager 109 b gives a done indication to the node maintenance sub-engine 107 b″ via the interface LL2_B. In response to this done indication and a receipt of a maintenance ready message received from the next lower LEVEL—3 sub-engine 102 c″, the LEVEL—2 node maintenance sub-engine 107 b″ sends a maintenance ready message on interface K to the LEVEL—1 sub-engine 102 a″.
The pipeline control and search logic 103 a″ within the LEVEL—1 sub-engine 102 a″, which previously received the database flush command for the specified logical database, forwards the flush command to its node maintenance sub-engine 107 a″, which passes the flush command on the L1M_B interface to a node access list manager 108 a. The node access list manager 108 a processes the flush command by reading through all node locations in a node access list 109 a (accessed via interface L1M_A) and for those assigned to the specified logical database it returns the node to the free list by updating the node access list 109 a accordingly. These operations, which effectively flush all keys stored for the specified logical database from LEVEL—1 and makes all resources assigned to the logical database available for future use, are performed essentially as background operations which do not further limit a search bandwidth of the search engine device 100 d by utilizing additional cycles and resources associated with the lookup core internal pipeline interface F.
Upon updating the node access list 109 a, the node access list manager 108 a gives a done indication to the node maintenance sub-engine 107 a″ via the interface LL1_B. In response to this done indication and a receipt of a maintenance ready message received from the next lower LEVEL—2 sub-engine 102 b″, the LEVEL—1 sub-engine 102 a″ issues a done message to the maintenance engine controller 122 on the lookup core maintenance acknowledgment interface L. This done message indicates that the database flush operations have been completed across all levels of the pipeline. In response to the done message, the maintenance engine controller 122 sets the corresponding done bit in the flush status register 123. The contents of this flush status register 123 may be communicated to the external device that issued the original request to perform a database flush operation in order to confirm deletion of the selected database from the search engine 100 d.
These database flush operations described above with respect to FIG. 10D contrast with alternative flush operations that may not require the use of additional node access list storage 109 a-109 d. In particular, alternative database flush operations may eliminate the need to manage separate node access list storage by relatively heavily utilizing the resources of the lookup core internal pipeline interface F to perform recursive “tree-walk” operations that sequentially remove pointers to nodes of a selected database at each of the levels (LEVEL—1 to LEVEL_L) of the search engine using downstream and upstream communications. These operations may include initially visiting the root node of a selected database at LEVEL—1 to identify a first child pointer to a lower level node at LEVEL—2. The corresponding lower level node at LEVEL—2 is then visited to identify a second child pointer to yet another node at LEVEL—3 and the first child pointer is deleted. Similarly, the corresponding node at LEVEL—3 is visited to identify a third child pointer to a lower level node and the second child pointer is deleted. These downstream operations continue until a first leaf node is identified. The child pointer associated with this first leaf node is deleted and an upstream operation is then performed to revisit the node containing the now deleted pointer to the first leaf node. Another child pointer associated with this node, if any, is then identified and followed in a downstream direction to the next lower level in the pipeline. These downstream operations continue until a next leaf node is encountered. At this time, a repeating sequence of alternating upstream and downstream operations are performed until all lower level nodes containing pointers are visited and the root node is revisited. Upon revisiting the root node, another child pointer, if any, is identified and the recursive “walk” through the nodes of the selected database continues until all child pointers associate with the selected database to be flushed have been deleted and the root node freed.
US4464650 Aug 10, 1981 Aug 7, 1984 Sperry Corporation Apparatus and method for compressing data signals and restoring the compressed data signals
US4606002 Aug 17, 1983 Aug 12, 1986 Wang Laboratories, Inc. B-tree structured data base using sparse array bit maps to store inverted lists
US5228115 Feb 12, 1992 Jul 13, 1993 International Business Machines Corporation Hybrid backtrack/lookahead search technique for constraint-satisfaction problems
US5430869 May 29, 1991 Jul 4, 1995 Hewlett-Packard Company System and method for restructuring a B-Tree
US5446887 Sep 17, 1993 Aug 29, 1995 Microsoft Corporation Optimal reorganization of a B-tree
US5475837 Jan 17, 1995 Dec 12, 1995 Hewlett-Packard Company Method and system for restructuring a B-Tree for managing data during a node splitting operation
US5666494 Mar 31, 1995 Sep 9, 1997 Samsung Electronics Co., Ltd. Queue management mechanism which allows entries to be processed in any order
US5758024 Jun 25, 1996 May 26, 1998 Microsoft Corporation Method and system for encoding pronunciation prefix trees
US5758356 Sep 12, 1995 May 26, 1998 Hitachi, Ltd. High concurrency and recoverable B-tree index management method and system
US5787430 Jun 30, 1994 Jul 28, 1998 International Business Machines Corporation Variable length data sequence backtracking a trie structure
US5812996 Nov 6, 1995 Sep 22, 1998 Sybase, Inc. Database system with methods for optimizing query performance with a buffer manager
US5813000 Mar 14, 1996 Sep 22, 1998 Sun Micro Systems B tree structure and method
US5897655 Dec 10, 1996 Apr 27, 1999 International Business Machines Corporation System and method for cache replacement within a cache set based on valid, modified or least recently used status in order of preference
US5918245 Mar 13, 1996 Jun 29, 1999 Sun Microsystems, Inc. Microprocessor having a cache memory system using multi-level cache set prediction
US5924115 Mar 29, 1996 Jul 13, 1999 Interval Research Corporation Hierarchical memory architecture for a programmable integrated circuit having an interconnect structure connected in a tree configuration
US6035326 Sep 8, 1997 Mar 7, 2000 International Business Machines Corporation Mapping table lookup optimization system
US6115792 Nov 9, 1999 Sep 5, 2000 Advanced Micro Devices, Inc. Way prediction logic for cache array
US6138123 Jul 15, 1997 Oct 24, 2000 Rathbun; Kyle R. Method for creating and using parallel data structures
US6389507 Jan 14, 2000 May 14, 2002 Gigabus, Inc. Memory device search system and method
US6421730 Apr 1, 1999 Jul 16, 2002 Intel Corporation Programmable system for processing a partitioned network infrastructure
US6430527 Aug 26, 1998 Aug 6, 2002 Avici Systems Prefix search circuitry and method
US6441053 Jun 8, 1999 Aug 27, 2002 The Trustees Of The University Of Pennsylvania Inhibitors of glycogen synthase kinase-3 and methods for identifying and using the same
US6480839 Jul 18, 2000 Nov 12, 2002 Go2Market.Com System and method for improving database data manipulation using direct indexing within a B*tree index having a tunable index organization
US6490592 Dec 30, 1999 Dec 3, 2002 Nortel Networks Limited Method of and apparatus for generating a tree data structure supporting longest match lookup
US6532457 Jul 14, 2000 Mar 11, 2003 Ezchip Technologies Ltd. Look-ahead tree structure
US6539369 Dec 8, 2000 Mar 25, 2003 Mosaid Technologies, Inc. Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table
US6564211 Oct 4, 2000 May 13, 2003 Lsi Logic Corporation Fast flexible search engine for longest prefix match
US6611832 Oct 9, 2001 Aug 26, 2003 International Business Machines Corp. Data structure for longest-matching prefix searching and updating method for search table data structures
US6633865 Dec 23, 1999 Oct 14, 2003 Pmc-Sierra Limited Multithreaded address resolution system
US6636956 Jul 6, 2001 Oct 21, 2003 Cypress Semiconductor Corp. Memory management of striped pipelined data structures
US6662287 Oct 18, 2001 Dec 9, 2003 Lsi Logic Corporation Fast free memory address controller
US6691124 Apr 4, 2001 Feb 10, 2004 Cypress Semiconductor Corp. Compact data structures for pipelined message forwarding lookups
US6694323 Jan 27, 2003 Feb 17, 2004 Sybase, Inc. System and methodology for providing compact B-Tree
US6697276 Feb 1, 2002 Feb 24, 2004 Netlogic Microsystems, Inc. Content addressable memory device
US6768739 Feb 9, 2000 Jul 27, 2004 Nec Corporation Router with a cache having a high hit probability
US6782382 Mar 7, 2001 Aug 24, 2004 International Business Machines Corporation Prefix search method and data structure using compressed search tables
US6859455 Nov 10, 2000 Feb 22, 2005 Nasser Yazdani Method and apparatus for building and using multi-dimensional index trees for multi-dimensional data objects
US6928430 Apr 23, 2002 Aug 9, 2005 Integrated Silicon Solution, Inc. Prefix match search scheme
US6941314 Apr 15, 2002 Sep 6, 2005 Lsi Logic Corporation User selectable editing protocol for fast flexible search engine
US7007027 Dec 2, 2002 Feb 28, 2006 Microsoft Corporation Algorithm for tree traversals using left links
US7016904 Apr 25, 2001 Mar 21, 2006 Altera Corporation Method and system for rapid insertion of various data streams into sorted tree structures
US7017021 Apr 4, 2001 Mar 21, 2006 Cypress Semiconductor Corp. High-speed message forwarding lookups for arbitrary length strings using pipelined memories
US7035844 Feb 25, 2002 Apr 25, 2006 Lsi Logic Corporation FFS search and edit pipeline separation
US7047317 Jun 14, 2000 May 16, 2006 Altera Corporation High performance network address processor system
US7062499 Jan 8, 2002 Jun 13, 2006 Intel Corporation Enhanced multiway radix tree and related methods
US7076602 Oct 21, 2003 Jul 11, 2006 Hywire Ltd. Multi-dimensional associative search engine having an external memory
US7107263 Dec 8, 2000 Sep 12, 2006 Netrics.Com, Inc. Multistage intelligent database search method
US7162572 Oct 12, 2004 Jan 9, 2007 Spans Logic Inc. Memory and power efficient mechanism for fast table lookup
US7231383 May 1, 2002 Jun 12, 2007 Lsi Corporation Search engine for large-width data
US7257530 Feb 12, 2003 Aug 14, 2007 Hongfeng Yin Method and system of knowledge based search engine using text mining
US7289979 Dec 10, 2003 Oct 30, 2007 Alcatel Lucent Parallel asymmetric binary search on lengths
US7383276 Jan 30, 2004 Jun 3, 2008 Microsoft Corporation Concurrency control for B-trees with node deletion
US7697518 * Sep 15, 2006 Apr 13, 2010 Netlogic Microsystems, Inc. Integrated search engine devices and methods of updating same using node splitting and merging operations
US20020116526 Dec 8, 2000 Aug 22, 2002 Mosaid Technologies, Inc. Method and apparatus for longest match address lookup
US20020146009 Apr 4, 2001 Oct 10, 2002 Pankaj Gupta High-speed message forwarding lookups for arbitrary length strings using pipelined memories
US20020147721 Apr 4, 2001 Oct 10, 2002 Pankaj Gupta Compact data structures for pipelined message forwarding lookups
US20020152413 Jun 11, 2002 Oct 17, 2002 Waters Gregory M. Prefix search circuitry and method
US20020161969 Oct 31, 2001 Oct 31, 2002 Nataraj Bindiganavale S. Content addressable memory with programmable word width and programmable priority
US20030009453 Jul 3, 2001 Jan 9, 2003 International Business Machines Corporation Method and system for performing a pattern match search for text strings
US20030093613 Aug 9, 2002 May 15, 2003 David Sherman Compressed ternary mask system and method
US20030093646 Aug 28, 2002 May 15, 2003 Hywire Ltd. RAM-based range content addressable memory
US20030123397 Dec 31, 2001 Jul 3, 2003 Kang-Bok Lee Method for generating nodes in multiway search tree and search method using the same
US20030123459 Sep 17, 2001 Jul 3, 2003 Heng Liao Efficiency masked matching
US20030163302 Feb 12, 2003 Aug 28, 2003 Hongfeng Yin Method and system of knowledge based search engine using text mining
US20030182272 Mar 22, 2002 Sep 25, 2003 International Business Machines Corporation Efficient implementation of an index structure for multi-column bi-directional searches
US20040030686 Jun 6, 2003 Feb 12, 2004 Cardno Andrew John Method and system of searching a database of records
US20040059731 Dec 8, 2000 Mar 25, 2004 Yianilos Peter N. Multistage intelligent database search method
US20040062208 Sep 30, 2002 Apr 1, 2004 Mosaid Technologies Inc. Dense mode coding scheme
US20040083336 Oct 21, 2003 Apr 29, 2004 Hywire Ltd. Multi-dimensional associative search engine having an external memory
US20040109451 Dec 6, 2002 Jun 10, 2004 Stmicroelectronics, 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 engine
US20040139274 Oct 20, 2003 Jul 15, 2004 Hui Ronald Chi-Chun Virtual content addressable memory with high speed key insertion and deletion and pipelined key search
US20040170379 Feb 18, 2004 Sep 2, 2004 Kabushiki Kaisha Tohsiba Hierarchical storage scheme and data playback scheme for enabling random access to realtime stream data
US20040193619 Mar 28, 2003 Sep 30, 2004 Srinivasan Venkatachary System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size
US20040205229 Oct 23, 2003 Oct 14, 2004 Isic Corporation Method and apparatus for longest prefix matching in processing a forwarding information database
US20040249803 May 7, 2004 Dec 9, 2004 Srinivasan Vankatachary Architecture for network search engines with fixed latency, high capacity, and high throughput
US20050131867 Dec 10, 2003 Jun 16, 2005 Alcatel Parallel asymmetric binary search on lengths
US20050163122 Dec 30, 2004 Jul 28, 2005 University Of Florida Research Foundation, Inc. System and methods for packet filtering
US20050195832 Feb 9, 2005 Sep 8, 2005 Washington University Method and system for performing longest prefix matching for network address lookup using bloom filters
US20060167843 Jan 24, 2005 Jul 27, 2006 3Com Corporation Tire search engines and ternary CAM used as pre-classifier
US20060259682 Jul 12, 2006 Nov 16, 2006 Madian Somasundaram Data coding system and method
US20070038626 Oct 18, 2006 Feb 15, 2007 Waters Gregory M Prefix search circuitry and method
US20070276648 Feb 13, 2007 Nov 29, 2007 Lsi Logic Corporation Sequential tester for longest prefix search engines
WO2004088548A1 Mar 26, 2004 Oct 14, 2004 Cypress Semiconductor System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size
1 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.
2 Answers.com, http://www.answers.com/topic/b-tree, B~tree: Information From Answers.com, Admitted prior art. 6 pages.
3 Answers.com, http://www.answers.com/topic/b-tree, B˜tree: Information From Answers.com, Admitted prior art. 6 pages.
4 Bayer, R. et al., "Prefix B-Trees," ACM Trans. On Database Systems, vol. 2, No. 1, Mar. 1977, pp. 11-26.
5 Bender et al. "Cache-oblivious B-trees", SIAM J. Comput, 2000, pp. 1-18.
6 B-tree, http://en.wikipedia.org/wiki/B%2A-tree, Admitted prior art. 1 page.
7 B-Trees: Balanced Tree Data Structures, http://www.bluerwhite.org/btree/, Admitted Prior Art, Printed, 8 pages.
8 Canonical form http://en.wikipedia.org/wiki/Canonical-form, Admitted prior art, 1 page.
9 Canonical form http://en.wikipedia.org/wiki/Canonical—form, Admitted prior art, 1 page.
10 Chang et al., "Dynamic Routing Tables using Augmented Balanced Search Tree," National Cheng Kung University and I-Shou University, Admitted Prior Art, 35 pages.
11 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.
12 Djordjevic et al. "A Hierarchical memory system environment" Jun. 1998 Proceedings of the 1998 workshop on Computer architecture education WCAE '98 Publisher: ACM Press.
13 Final Office Action dated Aug. 4, 2009 for U.S. Appl. No. 11/674,487, 22 Pages.
14 Final Office Action dated Dec. 30, 2010 for U.S. Appl. No. 11/963,142.
15 Final Office Action dated Dec. 8, 2009 for U.S. Appl. No. 11/768,646, 13 Pages.
16 Final Office Action dated Feb. 4, 2011 for U.S. Appl. No. 11/934,240.
17 Final Office Action dated Jan. 13, 2011 for U.S. Appl. No. 11/768,646.
18 Final Office Action dated Mar. 26, 2010 for U.S. Appl. No. 11/864,290.
19 Final Office Action dated Nov. 24, 2009 for U.S. Appl. No. 11/685,982, 20 Pages.
20 Final Office Action dated Sep. 10, 2008 for U.S. Appl. No. 11/184,243, 15 Pages.
21 Henry Hong-yi Tzeng, "Longest Prefix Search Using Compressed Trees", In Proceedings of IEEE Globe.com, 1998.
22 Kobayashi et al. "A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing", C&C Media Research Laboratories, NEC Corporation 2000 IEEE.
23 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).
24 Microsoft Computer Dictionary, 2002, Microsoft Press, Fifth Edition, p. 329.
25 Nasser Yazdani et al., "Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths", IEEE, 2001, p. 76-85.
26 Network 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.
27 Non-final Office Action dated Apr. 1, 2009 for U.S. Appl. No. 11/532,225, 8 Pages.
28 Non-final Office Action dated Dec. 11, 2008 for U.S. Appl. No. 11/674,474, now Issued Patent 7,603,346 , 22 Pages.
29 Non-final Office Action dated Dec. 11, 2008 for U.S. Appl. No. 11/674,487, 23 Pages.
30 Non-final Office Action dated Dec. 17, 2009 for U.S. Appl. No. 11/184,843, 18 Pages.
31 Non-final Office Action dated Jul. 21, 2009 for U.S. Appl. No. 11/685,982, 20 Pages.
32 Non-final Office Action dated Jun. 25, 2009 for U.S. Appl. No. 11/184,243, 15 Pages.
33 Non-final Office Action dated Jun. 25, 2009 for U.S. Appl. No. 11/768,646, 12 Pages.
34 Non-final Office Action dated Mar. 18, 2009 for U.S. Appl. No. 11/184,243, 15 Pages.
35 Non-final Office Action dated Nov. 15, 2007 for U.S. Appl. No. 11/184,243, 18 Pages.
36 Non-final Office Action dated Oct. 15, 2009 for U.S. Appl. No. 11/864,290, 15 Pages.
37 Non-Final Office Action dated Oct. 22, 2010 for U.S. Appl. No. 11/934,240.
38 Non-final Office Action dated Sep. 10, 2009 for U.S. Appl. No. 11/532,225, 8 Pages.
39 Non-Final Office Action dated Sep. 30, 2010 for U.S. Appl. No. 11/768,646.
40 Non-Final Office Action mailed Jul. 21, 2010 for U.S. Appl. No. 11/963,142.
41 Non-Final Office Action mailed Jun. 21, 2010 for U.S. Appl. No. 11/858,441.
42 Notice of Allowance dated Apr. 2, 2010 for U.S. Appl. No. 11/184,243.
43 Notice of Allowance dated Aug. 7, 2009 for U.S. Appl. No. 11/674,474, now Issued Patent 7,603,346 , 13 Pages.
44 Notice of Allowance dated Dec. 2, 2009 for U.S. Appl. No. 11/674,487, 11 Pages.
45 Notice of Allowance dated Jan. 12, 2010 for U.S. Appl. No. 11/532,225, 6 Pages.
46 Notice of Allowance dated Mar. 31, 2010 for U.S. Appl. No. 11/685,982.
47 Notice of Allowance mailed Jul. 13, 2010 for U.S. Appl. No. 11/864,290.
48 Notice of Allowance mailed Sep. 22, 2010 for U.S. Appl. No. 11/858,441.
49 O'Connor et al., "The iFlow Address Processor," 2001 IEEE, pp. 16-23.
50 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.
51 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.
52 Tree (data structure), http://en.wikipedia.org/wiki/Tree-data-structure, (Redirected from Tree data structure, Admitted prior art. 2 pages.
53 Tree (data structure), http://en.wikipedia.org/wiki/Tree—data—structure, (Redirected from Tree data structure, Admitted prior art. 2 pages.
54 U.S. Appl. No. 11/184,243, filed Jul. 9, 2005, Depelteau, Gary.
55 U.S. Appl. No. 11/685,982, filed Mar. 14, 2007, Depelteau, Gary.
56 U.S. Appl. No. 11/934,240, filed Nov. 2, 2007, Depelteau, Gary.
57 U.S. Appl. No. 11/963,142, filed Dec. 21, 2007, Depelteau, Gary.
58 U.S. Appl. No. 12/336,565, filed Dec. 17, 2008, Carr, D. W.
59 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.
US9245626 Oct 26, 2012 Jan 26, 2016 Cisco Technology, Inc. System and method for packet classification and internet protocol lookup in a network environment
U.S. Classification 707/706, 707/778
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:DEPELTEAU, GARY;CARR, DAVID WALTER;REEL/FRAME:020464/0507
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:INTEGRATED DEVICE TECHNOLOGY, INC.;REEL/FRAME:022997/0250