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

• US 5,946,679 A
• Filed: 07/31/1997
• Issued: 08/31/1999
• Est. Priority Date: 07/31/1997
• Status: Expired due to Term

• Current Assignee: Ericsson IP Infrastructure Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Torrent Networking Technologies Corp. (Telefonaktiebolaget LM Ericsson)
• Inventors: Shah, Bakul, Kanakia, Hemant, Illingworth, Roy, Ahuja, Ritesh
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US08/904,287
• Time in Patent Office: 761 Days
• Field of Search: 707/3, 707/7, 395/200.68, 395/200.69, 395/200.7, 395/200.71, 395/200.72
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus searches table information using keys of varying lengths. Based on criteria, the method selects one of three processes for performing the search. The first routine is a reverse hash search process which is useful for searching information with few key lengths. The second process is a hierarchical search routine which is useful for searching information with many key lengths. The third process is a compressed radix tree search which is useful for searching information that presents significant time barriers to the first two routines.

Claims

1. 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.

2. 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.

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

4. 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.

5. 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.

6. 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.

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

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

9. 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.

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

11. 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.

12. 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.

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

14. 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.

15. 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.

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

17. 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).

18. 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.

19. A method of organizing information into a compressed radix tree, the method comprising:

(a) forming a node corresponding to a partial key having a selected length;

(b) in response to said partial key corresponding to at least one child key, storing in said node a sub-tree indicator and sub-tree index length indicator corresponding thereto; and

(c) iterating (a) and (b) until the information is fully organized.

20. 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.

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

22. 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.

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

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

25. 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.

26. 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.

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

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

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

30. 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.

31. 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.