System and method for locating a route in a route table using hashing and compressed radix tree searching

Claim 2

An adaptive information search method for information referenced by keys, the method comprising: (a) performing a reverse-hashing search in response to said keys having a first characteristic; (b) performing a hierarchical-hashing search in response to said keys not having said first characteristic; and (c) performing a compressed radix tree search in response to (a) and (b) not providing results according to a specified criterion.

Claim 3

An adaptive information search method as in claim 1, wherein the information is a table, the keys correspond to addresses, and the first characteristic corresponds to said keys not having more than a given number of different lengths.

Claim 4

An adaptive information search method as in claim 1, wherein the specified criterion corresponds to a period of time.

Claim 5

An adaptive information search method as in claim 1, wherein the information is a table, the keys correspond to addresses, the first characteristic corresponds to said keys not having more than a given number of different lengths, and the specified criterion corresponds to a period of time.

Claim 6

An adaptive information search method as in claim 1, wherein the reverse-hashing search, the hierarchical-hashing search, and the compressed radix tree search are longest prefix match searches.

Claim 7

An adaptive information search method for information referenced by keys, the method comprising: performing a hashing search; and, performing a compressed radix tree search in response to the hashing search not providing results according to a specified criterion.

Claim 8

An adaptive information search method for information referenced by keys, the method comprising: performing a hashing search; and, performing a compressed radix tree search in response to the hashing search not providing results according to a specified criterion.

Claim 9

An adaptive information search method as in claim 6, wherein the information is a table and the keys correspond to addresses.

Claim 10

An adaptive information search method as in claim 6, wherein the specified criterion corresponds to a period of time.

Claim 11

An adaptive information search method as in claim 6, wherein the information is a table, the keys correspond to addresses, and the specified criterion corresponds to a period of time.

Claim 12

An adaptive information search method as in claim 6, wherein the hashing search and the compressed radix tree search are longest prefix match searches.

Claim 13

A hierarchical hashing search method for information referenced by keys, comprising: (a) hashing an initial portion of a target key to obtain an initial hash entry; (b) determining, in response to the initial hash entry, a set of mask lengths; and (c) iteratively searching for subsequent hash entries using the set of mask lengths and further mask lengths determined as a result of said searching.

Claim 14

A hierarchical hashing search method for information referenced by keys, comprising: (a) hashing an initial portion of a target key to obtain an initial hash entry; (b) determining, in response to the initial hash entry, a set of mask lengths; and (c) iteratively searching for subsequent hash entries using the set of mask lengths and further mask lengths determined as a result of said searching.

Claim 15

A method as in claim 11, further comprising performing a compressed radix tree search in response to (a)-(c) not providing results according to a specified criterion.

Claim 16

A method as in claim 12, wherein the specified criterion corresponds to a period of time.

Claim 17

A reverse hashing search method for information referenced by keys, comprising: (a) searching using a target key in its entirety; and (b) in response to no match resulting from (a), iteratively hashing portions of the target key using a set of mask lengths, said mask lengths being selected in decreasing size order.

Claim 18

A reverse hashing search method for information referenced by keys, comprising: (a) searching using a target key in its entirety; and (b) in response to no match resulting from (a), iteratively hashing portions of the target key using a set of mask lengths, said mask lengths being selected in decreasing size order.

Claim 19

A method as in claim 14, further comprising performing a compressed radix tree search in response to (a)-(b) not providing results according to a specified criterion.

Claim 20

A method as in claim 15, wherein the specified criterion corresponds to a period of time.

Claim 21

A compressed radix tree search method for information referenced by keys, the keys corresponding to nodes of a tree, the method comprising: (a) selecting an initial node as a current node, the current node having a plurality of entries; (b) selecting an initial length as a current index length; (c) forming an intermediate key in response to a most significant portion of a target key, the most significant portion corresponding to the current index length; (d) selecting one of said entries of the current node using the intermediate key and determining the skip length contained in said entry; (e) comparing a next most significant portion of the target key equal in length to the skip length with a skip value; (f) in response to the next most significant portion of the target key matching the skip value, accessing a node field; (g) in response to the node field containing a null value, selecting the information in an information field; (h) in response to the node field not containing a null value, selecting the node corresponding to the node field as the current node, removing the most significant portion and the next most significant portion from the target key, determining an index length from an index field, and iterating (c)-(h).

Claim 22

A compressed radix tree search method for information referenced by keys, the keys corresponding to nodes of a tree, the method comprising: (a) selecting an initial node as a current node, the current node having a plurality of entries; (b) selecting an initial length as a current index length; (c) forming an intermediate key in response to a most significant portion of a target key, the most significant portion corresponding to the current index length; (d) selecting one of said entries of the current node using the intermediate key and determining the skip length contained in said entry; (e) comparing a next most significant portion of the target key equal in length to the skip length with a skip value; (f) in response to the next most significant portion of the target key matching the skip value, accessing a node field; (g) in response to the node field containing a null value, selecting the information in an information field; (h) in response to the node field not containing a null value, selecting the node corresponding to the node field as the current node, removing the most significant portion and the next most significant portion from the target key, determining an index length from an index field, and iterating (c)-(h).

Claim 23

A compressed radix tree search method as in claim 17, further comprising terminating further processing in response to a complete match with the target key being determined.

Claim 26

An adaptive information search system for information referenced by keys, comprising: a hashing search subsystem adapted to perform a hashing search; and a compressed radix tree search subsystem adapted to perform a compressed radix tree search in response to said hashing search not providing results according to a specified criterion.

Claim 27

An adaptive information search system for information referenced by keys, comprising: a hashing search subsystem adapted to perform a hashing search; and a compressed radix tree search subsystem adapted to perform a compressed radix tree search in response to said hashing search not providing results according to a specified criterion.

Claim 28

A system as in claim 20, wherein the specified criterion is finding a desired correspondence within a given time period.

Claim 29

A system as in claim 20, wherein the specified criterion is finding correspondence between a target key and one of a set of stored keys.

Claim 30

A system as in claim 20, wherein said hashing search subsystem includes a hierarchical hashing search subsystem.

Claim 31

A system as in claim 20, wherein said hashing search subsystem includes a reverse hashing search subsystem.

Claim 32

A compressed radix tree search system, comprising: a register set storing a root node pointer, a root index length, a default route pointer, a current node pointer, a current node index, and a result route pointer; a plurality of tree nodes, each having a table of entries and each entry containing a skip-bits field, a skip-length field, a route-pointer field, a has-route field, a tree-pointer field, a has-subtree field, and a tree-index-length filed; and a processor operatively connected to the register set and the plurality of tree nodes, the processor comparing a target address with data corresponding to the tree nodes according to a compressed radix tree search, starting from a root node specified by the root node pointer and route index length and progressing therefrom by associating with the current node pointer and current node index select ones of the tree nodes based on the skip-bits field, the skip-length field, the tree-pointer field, the has-subtree field, and the tree-index length field, the processor producing as output in response to a match being found with the target address a route specified by the route-pointer field and the has-route field of a corresponding one of the plurality of tree nodes, the processor further producing as output in response to no match being found a route specified by the default route pointer, the processor further providing said output on the result route pointer.

Claim 33

A compressed radix tree search system, comprising: a register set storing a root node pointer, a root index length, a default route pointer, a current node pointer, a current node index, and a result route pointer; a plurality of tree nodes, each having a table of entries and each entry containing a skip-bits field, a skip-length field, a route-pointer field, a has-route field, a tree-pointer field, a has-subtree field, and a tree-index-length filed; and a processor operatively connected to the register set and the plurality of tree nodes, the processor comparing a target address with data corresponding to the tree nodes according to a compressed radix tree search, starting from a root node specified by the root node pointer and route index length and progressing therefrom by associating with the current node pointer and current node index select ones of the tree nodes based on the skip-bits field, the skip-length field, the tree-pointer field, the has-subtree field, and the tree-index length field, the processor producing as output in response to a match being found with the target address a route specified by the route-pointer field and the has-route field of a corresponding one of the plurality of tree nodes, the processor further producing as output in response to no match being found a route specified by the default route pointer, the processor further providing said output on the result route pointer.

Claim 34

A system as in claim 25, further comprising a hashing search subsystem pre-processing said target address and providing as output a result route in response to correspondence between the target address and a stored address being determined by the hashing search subsystem.

Claim 35

A system as in claim 25, wherein each of the plurality of tree nodes is of a predetermined size.

Claim 36

A system as in claim 25, wherein each of the plurality of tree nodes is of a variable size.

Claim 37

A system as in claim 25, wherein each skip-bits field has a null value.

Claim 38

An adaptive information search method for information referenced by keys, the method comprising: performing a hashing search; and performing simultaneously a compressed radix tree search.

Claim 39

An adaptive information search method for information referenced by keys, the method comprising: performing a hashing search; and performing simultaneously a compressed radix tree search.

Claim 40

An adaptive information search system for information referenced by keys, comprising: a hashing search subsystem adapted to perform a hashing search; and a compressed radix tree search subsystem adapted to perform a compressed radix tree search simultaneously to said hashing search.

Claim 41

An adaptive information search system for information referenced by keys, comprising: a hashing search subsystem adapted to perform a hashing search; and a compressed radix tree search subsystem adapted to perform a compressed radix tree search simultaneously to said hashing search.