Apparatus and accompanying methods, using a trie-indexed hierarchy forest, for storing wildcard-based patterns and, given an input key, retrieving, from the forest, a stored pattern that is identical to or more general than the key

• US 5,995,971 A
• Filed: 09/18/1997
• Issued: 11/30/1999
• Est. Priority Date: 09/18/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Bernet, Yoram, Bar, Ofer
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/933,477
• Time in Patent Office: 803 Days
• Field of Search: 707/3, 707/100, 707/102, 707/536, 326/39, 326/41, 326/105, 395/892, 395/200.75, 395/200.48, 382/187, 382/225, 382/228, 704/8, 704/257, 370/408
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A technique, specifically apparatus and accompanying methods, which utilizes a trie-indexed hierarchy forest ("rhizome") that accommodates wildcards for retrieving, given a specific input key, a pattern stored in the forest that is identical to or subsumes the key. The rhizome contains a binary search trie and a hierarchy forest. The search trie provides an indexed path to each unique, most specific, pattern stored in a lowest level of the hierarchy forest and also possibly to increasingly general patterns at higher levels in the pattern hierarchy. The hierarchy forest organizes the patterns into nodal hierarchies of strictly increasing generality. For use as a packet classifier, the rhizome stores wildcard-based packet classification patterns at separate corresponding pattern nodes, along with, corresponding "reference" fields associated therewith. Operationally, as each different queue is established or removed, a corresponding classification pattern is either inserted into or removed from the rhizome. A search key is formed for each packet, typically by concatenating classification fields, e.g., source and destination addresses and source and destination port designations, appearing in a header of the packet. The search key is then applied to the rhizome to determine whether that key exists therein, by virtue of either matching an identical classification pattern or being completely subsumed within a more general pattern stored therein. When such a classification is found, the classifier returns the contents of the associated reference field, which for scheduling, is a designation of a transmission queue to which the packet is to be directed.

Claims

1. A memory containing a stored trie-indexed forest having hierarchically-related pattern values stored therein and for access therefrom by a program executing on a computer, said pattern values having at least one wildcard therein, the memory comprising:

search and pattern structures formed of branch and pattern nodes, respectively, each of said branch and pattern nodes being defined by a memory structure for each such node;

said search structure having a plurality of linked branch nodes collectively defining a binary search trie which indexes into a subset of the pattern nodes, wherein the memory structure for each of said branch nodes, along a search path containing said node, has an address stored therein to a next one of said nodes situated on said path, said next one node being either a different one of the branch nodes or a given one of the subset of the pattern nodes; and

said pattern structure having a set of pattern nodes, wherein the memory structure for each of said pattern nodes stores a corresponding one of the pattern values and at least one of said pattern values has said wildcard therein.

2. The memory in claim 1 wherein the memory structure for each of said nodes comprises a plurality of different memory locations.

3. The memory in claim 2 wherein each of the branch nodes has a pivot bit associated therewith and first and second linkages to first and second other ones, respectively, of said nodes, said first and second nodes being child one and child zero nodes, respectively, of said each branch node;

said pivot bit being a bit index that specifies a particular bit in an input search key; and

wherein said pivot bit and addresses, representing said linkages and as child one and child zero pointers, are stored within corresponding ones of the memory locations in the memory structure for said each branch node.

4. The memory in claim 3 wherein the pivot bit in each of said branch nodes specifies a corresponding disagreement between individual bits, at a bit position specified by the pivot bit, in a pair of said pattern values.

5. The memory in claim 4 wherein the branch nodes that form the search structure are organized, by virtue of linkages thereamong, in ascending order of their corresponding pivot bits from a root node, having a lowest bit index, in said trie to said pattern structure.

6. The memory in claim 5 wherein the memory structure for each of the branch nodes further comprises, parameters for specifying presence and location of a wildcard in a stored pattern value associated with a pattern node reachable through a series of linkages extending from said each branch node.

7. The memory in claim 6 wherein, for each of the branch nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the branch nodes, the VALUE parameter is a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said one branch node, the MASK parameter is a second predefined function of MASK parameters of the child one and child zero nodes emanating from said one branch node, and the IMASK parameter is a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said one branch node.

8. The memory in claim 7 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

9. The memory in claim 8 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

10. The memory in claim 3 wherein the memory structure for the pattern node stores, in separate memory locations, a corresponding one of the pattern values.

11. The memory in claim 10 wherein the memory structure for each of the pattern nodes further comprises parameters for specifying presence and location of a wildcard in a stored pattern value associated with one of said pattern nodes in an associated hierarchy containing and upwardly extending from said each pattern node.

12. The memory in claim 11 wherein, for each of the pattern nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the pattern nodes, the VALUE parameter is a corresponding one of the stored pattern values, the MASK parameter specifies a wildcard in any bit position in said VALUE parameter for said one pattern node;

and the IMASK parameter is set to the MASK parameter of said one pattern node.

13. A computer readable storage medium containing a stored trie-indexed forest having hierarchically-related pattern values stored therein, said pattern values having at least one wildcard therein, the medium comprising:

search and pattern structures formed of branch and pattern nodes, respectively, each of said branch and pattern nodes being defined by a memory structure for each such node;

said search structure having a plurality of linked branch nodes collectively defining a binary search trie which indexes into a subset of the pattern nodes, wherein the memory structure for each of said branch nodes, along a search path containing said node, has an address stored therein to a next one of said nodes situated on said path, said next one node being either a different one of the branch nodes or a given one of the subset of the pattern nodes; and

said pattern structure comprising a set of pattern nodes, wherein the memory structure for each of said pattern nodes stores a corresponding one of the pattern values and at least one of said pattern values has said wildcard therein.

14. The storage medium in claim 13 wherein the memory structure for each of said nodes comprises a plurality of different memory locations.

15. The storage medium in claim 14 wherein each of the branch nodes has a pivot bit associated therewith and first and second linkages to first and second other ones, respectively, of said nodes, said first and second nodes being child one and child zero nodes, respectively, of said each branch node;

said pivot bit being a bit index that specifies a particular bit in an input search key; and

wherein said pivot bit and addresses, representing said linkages and as child one and child zero pointers, are stored within corresponding ones of the memory locations in the memory structure for said each branch node.

16. The storage medium in claim 15 wherein the pivot bit in each of said branch nodes specifies a corresponding disagreement between individual bits, at a bit position specified by the pivot bit, in a pair of said pattern values.

17. The storage medium in claim 16 wherein the branch nodes that form the search structure are organized, by virtue of linkages thereamong, in ascending order of their corresponding pivot bits from a root node, having a lowest bit index, in said trie to said pattern structure.

18. The storage medium in claim 17 wherein the memory structure for each of the branch nodes further comprises, parameters for specifying presence and location of a wildcard in a stored pattern value associated with a pattern node reachable through a series of linkages extending from said each branch node.

19. The storage medium in claim 18 wherein, for each of the branch nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the branch nodes, the VALUE parameter is a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said one branch node, the MASK parameter is a second predefined function of MASK parameters of the child one and child zero nodes emanating from said one branch node, and the IMASK parameter is a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said one branch node.

20. The storage medium in claim 19 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

21. The storage medium in claim 20 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

22. The storage medium in claim 15 wherein the memory structure for the pattern node stores, in separate memory locations, a corresponding one of the pattern values.

23. The storage medium in claim 22 wherein the memory structure for each of the pattern nodes further comprises parameters for specifying presence and location of a wildcard in a stored pattern value associated with one of said pattern nodes in an associated hierarchy containing and upwardly extending from said each pattern node.

24. The storage medium in claim 23 wherein, for each of the pattern nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the pattern nodes, the VALUE parameter is a corresponding one of the stored pattern values, the MASK parameter specifies a wildcard in any bit position in said VALUE parameter for said one pattern node;

and the IMASK parameter is set to the MASK parameter of said one pattern node.

25. A method responsive to an input key, for use with a data structure having pattern values stored therein, said pattern values having at least one wildcard therein, in retrieving one of said pattern values from said data structure which identically matches or subsumes the key,

wherein said data structure has a search trie and a pattern set, said search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said pattern set, said pattern set having a plurality of pattern nodes, each of the pattern nodes having a different corresponding one of the pattern values associated therewith and at least one of said pattern values has said wildcard therein;

the method comprises the steps of;

traversing along a path through the search trie in order to reach one of the pattern nodes in said pattern set, the path being defined by the input key and pivot bit values associated with ones of said branch nodes; and

determining whether the input key either matches or is subsumed by a pattern value associated with said one pattern node.

26. The method in claim 25 wherein said traversing step comprises the step of tracing along the path by branching from each successive branch node encountered along said path, starting at the root node, in a direction therefrom as specified by a bit of the input key indexed by the pivot bit of said each branch node until said one pattern node is encountered.

27. The method in claim 26 wherein the tracing step comprises the steps of:

examining, when the path reaches said successive branch node, a particular bit in the input key indexed by a value of the pivot bit associated with said successive branch node; and

branching, as specified by a value of the particular bit along either a child zero branch or a child one branch, both branches emanating from the successive branch node, to reach a child one or child zero node as a next node along said path, said next node being either a different one of the branch nodes, having a higher pivot bit associated therewith than that of the successive branch node, or the one pattern node.

28. The method in claim 27 further comprising the steps of, if the key identically matches or is subsumed by the desired one pattern value:

accessing a reference value associated with said desired one pattern value; and

returning the stored reference associated with said desired one pattern value.

29. The method in claim 28 further comprising the step of:

returning a message, indicative of a no match condition, in the event said input key did not match nor was subsumed by the pattern value stored in said one pattern node.

30. The method in claim 29 further comprising the step of inserting a new pattern node, into said pattern set, for storing a new pattern value in the data structure.

31. The method in claim 30 wherein said inserting step further comprises the steps of:

inserting said new pattern node at a proper location within said pattern set, said inserting comprises updating stored parameter values associated with existing ones of the nodes in the data structure such that said new pattern node is situated properly and is fully reachable therethrough; and

if said pattern set contains a wildcard-based pattern, replicating sufficient structure in said search trie, where necessary, based on bit positions where bit disagreements occur among bits in corresponding bit positions in said new pattern and existing pattern values stored in the data structure, such that the new pattern node is reachable over all different paths that, as a result of a wildcard, can be extended through the search trie to the new pattern node.

32. The method in claim 31 wherein each of said branch nodes in said search trie has a corresponding data structure associated therewith, the replicating step comprises the step of defining a data structure for each new branch node formed in said search trie, wherein the defining step comprises the step of:

storing, in corresponding memory locations in said data structure for said new branch node;

a corresponding one of the pivot bits associated with said new branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters.

33. The method in claim 32 wherein said storing step further comprises the steps of:

forming the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said new branch node;

forming the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said new branch node; and

forming the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said new branch node.

34. The method in claim 33 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

35. The method in claim 34 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

36. The method in claim 31 wherein each of said pattern nodes in said pattern set has a corresponding data structure associated therewith, the inserting step comprises the step of defining a data structure for each new pattern node formed in said pattern set, wherein the defining step comprises the step of storing, in corresponding memory locations in said data structure:

a reference value; and

values for VALUE, MASK and IMASK parameters.

37. The method in claim 36 wherein said storing step further comprises the steps of:

setting the VALUE parameter equal to a new pattern value to be stored in said each new pattern node;

forming the MASK parameter to specify a wildcard in any bit position in said VALUE parameter for said each new pattern node; and

forming the IMASK parameter as the MASK parameter of said each new pattern node.

38. The method in claim 29 further comprising the step of removing an existing pattern node, from said pattern set, so as to remove a pattern value associated therewith from said data structure.

39. The method in claim 38 wherein the removing step comprises the steps of:

eliminating structure from the search trie solely needed to previously support said existing pattern node; and

updating stored parameter values associated with remaining ones of the nodes in the data structure such that the existing pattern node is fully removed from the data structure and is not reachable therein.

40. The method in claim 39 wherein each branch node in the search trie has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a corresponding one of the pivot bits associated with said each branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters; and

wherein said updating step for, a remaining one of the branch nodes in the forest, comprises the steps of;

forming the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said remaining one branch node;

forming the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said remaining one branch node; and

forming the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said remaining one branch node.

41. The method in claim 40 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

42. The method in claim 41 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said remaining one branch node, and the third function is the conjunction function taken up to the pivot bit position for said remaining one branch node.

43. A computer readable medium having computer executable instructions stored therein for performing the steps recited in claim 25.

44. Apparatus, responsive to an input key, for use in a computer system, having a processor, for retrieving a pattern value from a data structure having at least one stored wildcard-based pattern value therein such that the retrieved pattern identically matches or subsumes the key, wherein the apparatus comprises:

the processor, and

a memory having executable instructions and a data structure stored therein;

the data structure having a search trie and a pattern set, said search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said pattern set, said pattern set having a plurality of pattern nodes, each of the pattern nodes having a different corresponding one of the pattern values associated therewith and at least one of pattern values has a wildcard therein; and

wherein the processor, in response to the stored instructions;

traverses along a path through the search trie in order to reach one of the pattern nodes in said pattern set, the path being defined by the input key and pivot bit values associated with ones of said branch nodes; and

determines whether the input key either matches or is subsumed by a pattern value associated with said one pattern node.

45. The apparatus in claim 44 wherein the processor, in response to the stored instructions, traces along the path by branching from each successive branch node encountered along said path, starting at the root node, in a direction therefrom as specified by a bit of the input key indexed by the pivot bit of said each branch node until said one pattern node is encountered.

46. The apparatus in claim 45 wherein the processor, in response to the stored instructions:

examines, when the path reaches said successive branch node, a particular bit in the input key indexed by a value of the pivot bit associated with said successive branch node; and

branches, as specified by a value of the particular bit along either a child zero branch or a child one branch, both child branches emanating from the successive branch node, to reach a child one or child zero node as a next node along said path, said next node being either a different one of the branch nodes, having a higher pivot bit associated therewith than that of the successive branch node, or the one pattern node.

47. The apparatus in claim 46 wherein the processor, in response to the stored instructions, if the key identically or is subsumed by the desired one pattern value:

accesses a reference value associated with said desired one pattern value; and

returns the stored reference associated with said desired one pattern value.

48. The apparatus in claim 47 wherein the processor, in response to the stored instructions, returns a message, indicative of a no match condition, in the event said input key did not match nor was subsumed by the pattern value stored in said one pattern node.

49. The apparatus in claim 48 wherein the processor, in response to the stored instructions, inserts a new pattern node, into said pattern set, for storing a new pattern value in the data structure.

50. The apparatus in claim 49 wherein the processor, in response to the stored instructions:

inserts said new pattern node at a proper location within said pattern set, and, through so doing, updates stored parameter values associated with existing ones of the nodes in the data structure such that said new pattern node is situated properly and is fully reachable therethrough; and

if said pattern set contains a wildcard-based pattern, replicates sufficient structure in said search trie, where necessary, based on bit positions where bit disagreements occur among bits in corresponding bit positions in said new pattern and existing pattern values stored in the data structure, such that the new pattern node is reachable over all different paths that, as a result of a wildcard, can be extended through the search trie to the new pattern node.

51. The apparatus in claim 50 wherein each of said branch nodes in said search trie has a corresponding data structure associated therewith, and the processor, in response to the stored instructions, defines a data structure for each new branch node formed in said search trie, and through so doing stores, in corresponding memory locations in said data structure for said new branch node:

a corresponding one of the pivot bits associated with said new branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters.

52. The apparatus in claim 51 wherein the processor, in response to the stored instructions:

forms the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said new branch node;

forms the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said new branch node; and

forms the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said new branch node.

53. The apparatus in claim 52 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

54. The apparatus in claim 53 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

55. The apparatus in claim 50 wherein each of said pattern nodes in said pattern set has a corresponding data structure associated therewith, and the processor, in response to the stored instructions, defines a data structure for each new pattern node formed in said pattern set, and through so doing stores, in corresponding memory locations in said data structure:

a reference value; and

values for VALUE, MASK and IMASK parameters.

56. The apparatus in claim 55 wherein the processor, in response to the stored instructions:

sets the VALUE parameter equal to a new pattern value to be stored in said each new pattern node;

forms the MASK parameter to specify a wildcard in any bit position in said VALUE parameter for said each new pattern node; and

forms the IMASK parameter as the MASK parameter of said each new pattern node.

57. The apparatus in claim 48 wherein the processor, in response to the stored instructions, removes an existing pattern node, from said pattern set, so as to remove a pattern value associated therewith from said data structure.

58. The apparatus in claim 57 wherein the processor, in response to the stored instructions:

eliminates structure from the search trie solely needed to previously support said existing pattern node; and

updates stored parameter values associated with remaining ones of the nodes in the data structure such that the existing pattern node is fully removed from the data structure and is not reachable therein.

59. The apparatus in claim 58 wherein each branch node in the search trie has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a corresponding one of the pivot bits associated with said each branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters; and

wherein the processor, in response to the stored instructions for, a remaining one of the branch nodes in the forest;

forms the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said remaining one branch node;

forms the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said remaining one branch node; and

forms the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said remaining one branch node.

60. The apparatus in claim 59 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

61. The apparatus in claim 60 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said remaining one branch node, and the third function is the conjunction function taken up to the pivot bit position for said remaining one branch node.

62. A memory containing a stored trie-indexed forest having hierarchically-related pattern values stored therein and for access therefrom by a program executing on a computer, said pattern values having wildcards therein, the memory comprising:

search and hierarchy structures formed of branch and pattern nodes, respectively, each of said branch and pattern nodes being defined by a memory structure for each such node;

said search structure having a plurality of linked branch nodes collectively defining a binary search trie which indexes into a subset of the pattern nodes, wherein the memory structure for each of said branch nodes, along a search path containing said node, has an address stored therein to a next one of said nodes situated on said path, said next one node being either a different one of the branch nodes or a given one of the subset of the pattern nodes; and

said hierarchy structure having linkages amongst said pattern nodes so as to define hierarchical nodal relationships occurring among the pattern values associated therewith, wherein the memory structure for each of said pattern nodes stores a corresponding one of the pattern values and an address to the memory structure, for another one of the pattern nodes, which stores a differing one of the pattern values having a wildcard therein and situated at a next higher level of an associated hierarchy.

63. The memory in claim 62 wherein the memory structure for each of said nodes comprises a plurality of different memory locations.

64. The memory in claim 63 wherein each of the branch nodes has a pivot bit associated therewith and first and second linkages to first and second other ones, respectively, of said nodes, said first and second nodes being child one and child zero nodes, respectively, of said each branch node;

said pivot bit being a bit index that specifies a particular bit in an input search key; and

wherein said pivot bit and addresses, representing said linkages and as child one and child zero pointers, are stored within corresponding ones of the memory locations in the memory structure for said each branch node.

65. The memory in claim 64 wherein the pivot bit in each of said branch nodes specifies a corresponding disagreement between individual bits, at a bit position specified by the pivot bit, in a pair of said pattern values.

66. The memory in claim 65 wherein the branch nodes that form the search structure are organized, by virtue of linkages thereamong, in ascending order of their corresponding pivot bits from a root node, having a lowest bit index, in said trie to said hierarchy structure.

67. The memory in claim 66 wherein the memory structure for each of the branch nodes further comprises, parameters for specifying presence and location of a wildcard in a stored pattern value associated with a pattern node reachable through a series of linkages extending from said each branch node.

68. The memory in claim 67 wherein, for each of the branch nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the branch nodes, the VALUE parameter is a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said one branch node, the MASK parameter is a second predefined function of MASK parameters of the child one and child zero nodes emanating from said one branch node, and the IMASK parameter is a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said one branch node.

69. The memory in claim 68 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

70. The memory in claim 69 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

71. The memory in claim 64 wherein the memory structure for the pattern node stores, in separate memory locations, a corresponding one of the pattern values and, as a godparent pointer, the address to a next higher node in the hierarchy associated therewith.

72. The memory in claim 71 wherein the memory structure for each of the pattern nodes further comprises parameters for specifying presence and location of a wildcard in a stored pattern value associated with one of said pattern nodes in an associated hierarchy containing and upwardly extending from said each pattern node.

73. The memory in claim 72 wherein, for each of the pattern nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the pattern nodes, the VALUE parameter is a corresponding one of the stored pattern values, the MASK parameter specifies a wildcard in any bit position in said VALUE parameter for said one pattern node;

and the IMASK parameter, if said one pattern node has a hierarchy associated therewith, is a fourth predefined function of the MASK parameter of said one pattern node and the IMASK parameter of a godparent to said one pattern node or, if said one pattern node does not have a hierarchy associated therewith, is set to the MASK parameter of said one pattern node.

74. The memory in claim 73 wherein said fourth function is a conjunction function.

75. A computer readable storage medium containing a stored trie-indexed forest having hierarchically-related pattern values stored therein, said pattern values having wildcards therein, the medium comprising:

search and hierarchy structures formed of branch and pattern nodes, respectively, each of said branch and pattern nodes being defined by a memory structure for each such node;

said search structure having a plurality of linked branch nodes collectively defining a binary search trie which indexes into a subset of the pattern nodes, wherein the memory structure for each of said branch nodes, along a search path containing said node, has an address stored therein to a next one of said nodes situated on said path, said next one node being either a different one of the branch nodes or a given one of the subset of the pattern nodes; and

said hierarchy structure having linkages amongst said pattern nodes so as to define hierarchical nodal relationships occurring among the pattern values associated therewith, wherein the memory structure for each of said pattern nodes stores a corresponding one of the pattern values and an address to the memory structure, for another one of the pattern nodes, which stores a differing one of the pattern values having a wildcard therein and situated at a next higher level of an associated hierarchy.

76. The storage medium in claim 75 wherein the memory structure for each of said nodes comprises a plurality of different memory locations.

77. The storage medium in claim 76 wherein each of the branch nodes has a pivot bit associated therewith and first and second linkages to first and second other ones, respectively, of said nodes, said first and second nodes being child one and child zero nodes, respectively, of said each branch node;

said pivot bit being a bit index that specifies a particular bit in an input search key; and

wherein said pivot bit and addresses, representing said linkages and as child one and child zero pointers, are stored within corresponding ones of the memory locations in the memory structure for said each branch node.

78. The storage medium in claim 77 wherein the pivot bit in each of said branch nodes specifies a corresponding disagreement between individual bits, at a bit position specified by the pivot bit, in a pair of said pattern values.

79. The storage medium in claim 78 wherein the branch nodes that form the search structure are organized, by virtue of linkages thereamong, in ascending order of their corresponding pivot bits from a root node, having a lowest bit index, in said trie to said hierarchy structure.

80. The storage medium in claim 79 wherein the memory structure for each of the branch nodes further comprises, parameters for specifying presence and location of a wildcard in a stored pattern value associated with a pattern node reachable through a series of linkages extending from said each branch node.

81. The storage medium in claim 80 wherein, for each of the branch nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the branch nodes, the VALUE parameter is a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said one branch node, the MASK parameter is a second predefined function of MASK parameters of the child one and child zero nodes emanating from said one branch node, and the IMASK parameter is a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said one branch node.

82. The storage medium in claim 81 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

83. The storage medium in claim 82 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

84. The storage medium in claim 77 wherein the memory structure for the pattern node stores, in separate memory locations, a corresponding one of the pattern values and, as a godparent pointer, the address to a next higher node in the hierarchy associated therewith.

85. The storage medium in claim 84 wherein the memory structure for each of the pattern nodes further comprises parameters for specifying presence and location of a wildcard in a stored pattern value associated with one of said pattern nodes in an associated hierarchy containing and upwardly extending from said each pattern node.

86. The storage medium in claim 85 wherein, for each of the pattern nodes, said parameters comprise values for VALUE, MASK and IMASK parameters stored in corresponding locations in the memory structure, wherein for any one of the pattern nodes, the VALUE parameter is a corresponding one of the stored pattern values, the MASK parameter specifies a wildcard in any bit position in said VALUE parameter for said one pattern node;

and the IMASK parameter, if said one pattern node has a hierarchy associated therewith, is a fourth predefined function of the MASK parameter of said one pattern node and the IMASK parameter of a godparent to said one pattern node or, if said one pattern node does not have a hierarchy associated therewith, is set to the MASK parameter of said one pattern node.

87. The storage medium in claim 86 wherein said fourth function is a conjunction function.

88. A method responsive to an input key, for use with a data structure having hierarchically-related pattern values stored therein, said pattern values having wildcards therein, in retrieving one of said pattern values from said data structure which identically matches or subsumes the key,

wherein said data structure has a search trie and a hierarchy forest, said search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, said hierarchy forest having a plurality of pattern nodes, each having a different corresponding one of the pattern values associated therewith, and at least one hierarchy of pattern nodes with associated pattern values of increasing generality;

the method comprises the steps of;

traversing along a path through the search trie in order to reach one of the pattern nodes in said hierarchy forest, the path being defined by the input key and pivot bit values associated with ones of said branch nodes; and

determining whether the input key either matches a pattern value associated with said one pattern node or is subsumed by a different pattern value associated with a different one of pattern nodes situated at an increasingly higher level of a hierarchy containing said one pattern node, so as to locate a desired one of the pattern values, stored in the hierarchy, that either identically matches or most specifically subsumes the input key.

89. The method in claim 88 wherein said traversing step comprises the step of tracing along the path by branching from each successive branch node encountered along said path, starting at the root node, in a direction therefrom as specified by a bit of the input key indexed by the pivot bit of said each branch node until said one pattern node is encountered.

90. The method in claim 89 wherein the tracing step comprises the steps of:

examining, when the path reaches said successive branch node, a particular bit in the input key indexed by a value of the pivot bit associated with said successive branch node; and

branching, as specified by a value of the particular bit along either a child zero branch or a child one branch, both branches emanating from the successive branch node, to reach a child one or child zero node as a next node along said path, said next node being either a different one of the branch nodes, having a higher pivot bit associated therewith than that of the successive branch node, or the one pattern node.

91. The method in claim 90 further comprising the steps of, if the key identically matches or is subsumed by the desired one pattern value:

accessing a reference value associated with said desired one pattern value; and

returning the stored reference associated with said desired one pattern value.

92. The method in claim 91 further comprising the steps of:

returning a message, indicative of a no match condition, in the event said input key did not match the pattern value stored in said one pattern node;

or

if said one pattern node does have a hierarchy associated therewith, returning a message, indicative of the no match condition, in the event said input key did not match nor was subsumed by the pattern value stored in said one pattern node nor any of the pattern values stored at all increasingly higher levels of the hierarchy.

93. The method in claim 92 further comprising the step of inserting a new pattern node, into said hierarchy forest, for storing a new pattern value in the data structure.

94. The method in claim 93 wherein said inserting step further comprises the steps of:

inserting said new pattern node at a proper hierarchical location within said hierarchy forest, said inserting comprises updating stored parameter values associated with existing ones of the nodes in the data structure such that said new pattern node is situated properly and is fully reachable therethrough; and

if said hierarchy forest contains a wildcard-based pattern, replicating sufficient structure in said search trie, where necessary, based on bit positions where bit disagreements occur among bits in corresponding bit positions in said new pattern and existing pattern values stored in the data structure, such that the new pattern node is reachable over all different paths that, as a result of a wildcard, can be extended through the search trie to the new pattern node.

95. The method in claim 94 wherein each of said branch nodes in said search trie has a corresponding data structure associated therewith, the replicating step comprises the step of defining a data structure for each new branch node formed in said search trie, wherein the defining step comprises the step of:

storing, in corresponding memory locations in said data structure for said new branch node;

a corresponding one of the pivot bits associated with said new branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters.

96. The method in claim 95 wherein said storing step further comprises the steps of:

forming the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said new branch node;

forming the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said new branch node; and

forming the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said new branch node.

97. The method in claim 96 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

98. The method in claim 97 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

99. The method in claim 94 wherein each of said pattern nodes in said hierarchy forest has a corresponding data structure associated therewith, the inserting step comprises the step of defining a data structure for each new pattern node formed in said hierarchy forest, wherein the defining step comprises the step of storing, in corresponding memory locations in said data structure:

a reference value;

a pointer to a next higher pattern node in a hierarchy containing said new pattern node; and

values for VALUE, MASK and IMASK parameters.

100. The method in claim 99 wherein said storing step further comprises the steps of:

setting the VALUE parameter equal to a new pattern value to be stored in said each new pattern node;

forming the MASK parameter to specify a wildcard in any bit position in said VALUE parameter for said each new pattern node; and

forming the IMASK parameter as a fourth predefined function of the MASK parameter of said each new pattern node and the IMASK parameter of a godparent to said each new pattern node does not have a hierarchy associated therewith, as the MASK parameter of said each new pattern node.

101. The method in claim 100 wherein said fourth function is a conjunction function.

102. The method in claim 101 further comprising the step of removing an existing pattern node, from said hierarchy forest, so as to remove a pattern value associated therewith from said data structure.

103. The method in claim 102 wherein the removing step comprises the steps of:

eliminating structure from the search trie solely needed to previously support said existing pattern node; and

updating stored parameter values associated with remaining ones of the nodes in the data structure such that the existing pattern node is fully removed from the data structure and is not reachable therein.

104. The method in claim 103 wherein each branch node in the search trie has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a corresponding one of the pivot bits associated with said each branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters; and

wherein said updating step for, a remaining one of the branch nodes in the forest, comprises the steps of;

forming the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said remaining one branch node;

forming the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said remaining one branch node; and

forming the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said remaining one branch node.

105. The method in claim 104 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

106. The method in claim 105 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said remaining one branch node, and the third function is the conjunction function taken up to the pivot bit position for said remaining one branch node.

107. The method in claim 103 wherein each pattern node in the hierarchy forest has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a reference value;

a pointer to a next higher pattern node in a hierarchy containing said new pattern node; and

values for VALUE, MASK and IMASK parameters, wherein said updating step for, a remaining one of the pattern nodes in the data structure, comprises the step of;

forming the IMASK parameter as a fourth predefined function of the MASK parameter of said remaining one pattern node and the IMASK parameter of a godparent to said remaining one pattern node does not have a hierarchy associated therewith, as the MASK parameter of said remaining one pattern node.

108. The method in claim 107 wherein said fourth function is a conjunction function.

109. A computer readable medium having computer executable instructions stored therein for performing the steps recited in claim 88.

110. Apparatus, responsive to an input key, for use in a computer system, having a processor, for retrieving a pattern value from a data structure having stored wildcard-based pattern values therein such that the retrieved pattern identically matches or subsumes the key, wherein the apparatus comprises:

the processor, and

a memory having executable instructions and a data structure stored therein;

the data structure having a search trie and a hierarchy forest, said search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, said hierarchy forest having a plurality of pattern nodes, each having a different corresponding one of the pattern values associated therewith, organized into at least one hierarchy of pattern nodes with associated pattern values of increasing generality wherein at least one of the pattern values in the hierarchy contains a wildcard; and

wherein the processor, in response to the stored instructions;

traverses along a path through the search trie in order to reach one of the pattern nodes in said hierarchy forest, the path being defined by the input key and pivot bit values associated with ones of said branch nodes; and

determines whether the input key either matches a pattern value associated with said one pattern node or is subsumed by a different pattern value associated with a different one of pattern nodes situated at an increasingly higher level of a hierarchy containing said one pattern node, so as to locate a desired one of the pattern values, stored in the hierarchy, that either identically matches or most specifically subsumes the input key.

111. The apparatus in claim 110 wherein the processor, in response to the stored instructions, traces along the path by branching from each successive branch node encountered along said path, starting at the root node, in a direction therefrom as specified by a bit of the input key indexed by the pivot bit of said each branch node until said one pattern node is encountered.

112. The apparatus in claim 111 wherein the processor, in response to the stored instructions:

examines, when the path reaches said successive branch node, a particular bit in the input key indexed by a value of the pivot bit associated with said successive branch node; and

branches, as specified by a value of the particular bit along either a child zero branch or a child one branch, both child branches emanating from the successive branch node, to reach a child one or child zero node as a next node along said path, said next node being either a different one of the branch nodes, having a higher pivot bit associated therewith than that of the successive branch node, or the one pattern node.

113. The apparatus in claim 112 wherein the processor, in response to the stored instructions, if the key identically or is subsumed by the desired one pattern value:

accesses a reference value associated with said desired one pattern value; and

returns the stored reference associated with said desired one pattern value.

114. The apparatus in claim 113 wherein the processor, in response to the stored instructions, returns a message, indicative of the no match condition, in the event said input key did not match nor was subsumed by the pattern value stored in said one pattern node nor in any of the pattern values stored at all increasingly higher levels of the hierarchy.

115. The apparatus in claim 114 wherein the processor, in response to the stored instructions, inserts a new pattern node, into said hierarchy forest, for storing a new pattern value in the data structure.

116. The apparatus in claim 115 wherein the processor, in response to the stored instructions:

inserts said new pattern node at a proper hierarchical location within said hierarchy forest, and, through so doing, updates stored parameter values associated with existing ones of the nodes in the data structure such that said new pattern node is situated properly and is fully reachable therethrough; and

if said hierarchy forest contains a wildcard-based pattern, replicates sufficient structure in said search trie, where necessary, based on bit positions where bit disagreements occur among bits in corresponding bit positions in said new pattern and existing pattern values stored in the data structure, such that the new pattern node is reachable over all different paths that, as a result of a wildcard, can be extended through the search trie to the new pattern node.

117. The apparatus in claim 116 wherein each of said branch nodes in said search trie has a corresponding data structure associated therewith, and the processor, in response to the stored instructions, defines a data structure for each new branch node formed in said search trie, and through so doing stores, in corresponding memory locations in said data structure for said new branch node:

a corresponding one of the pivot bits associated with said new branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters.

118. The apparatus in claim 117 wherein the processor, in response to the stored instructions:

forms the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said new branch node;

forms the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said new branch node; and

forms the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said new branch node.

119. The apparatus in claim 118 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

120. The apparatus in claim 119 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said one branch node, and the third function is the conjunction function taken up to the pivot bit position for said one branch node.

121. The apparatus in claim 116 wherein each of said pattern nodes in said hierarchy forest has a corresponding data structure associated therewith, and the processor, in response to the stored instructions, defines a data structure for each new pattern node formed in said hierarchy forest, and through so doing stores, in corresponding memory locations in said data structure:

a reference value;

a pointer to a next higher pattern node in a hierarchy containing said new pattern node; and

values for VALUE, MASK and IMASK parameters.

122. The apparatus in claim 121 wherein the processor, in response to the stored instructions:

sets the VALUE parameter equal to a new pattern value to be stored in said each new pattern node;

forms the MASK parameter to specify a wildcard in any bit position in said VALUE parameter for said each new pattern node; and

forms the IMASK parameter as a fourth predefined function of the MASK parameter of said each new pattern node and the IMASK parameter of a godparent to said each new pattern node.

123. The apparatus in claim 122 wherein said fourth function is a conjunction function.

124. The apparatus in claim 114 wherein the processor, in response to the stored instructions, removes an existing pattern node, from said hierarchy forest, so as to remove a pattern value associated therewith from said data structure.

125. The apparatus in claim 124 wherein the processor, in response to the stored instructions:

eliminates structure from the search trie solely needed to previously support said existing pattern node; and

updates stored parameter values associated with remaining ones of the nodes in the data structure such that the existing pattern node is fully removed from the data structure and is not reachable therein.

126. The apparatus in claim 125 wherein each branch node in the search trie has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a corresponding one of the pivot bits associated with said each branch node;

child zero and child one pointers to child one and child zero nodes; and

values for VALUE, MASK and IMASK parameters; and

wherein the processor, in response to the stored instructions for, a remaining one of the branch nodes in the forest;

forms the VALUE parameter as a first predefined function of the VALUE parameters of the child one and zero nodes emanating from said remaining one branch node;

forms the MASK parameter as a second predefined function of MASK parameters of the child one and child zero nodes emanating from said remaining one branch node; and

forms the IMASK parameter as a third predefined function of IMASK parameters of the child one and child zero nodes emanating from said remaining one branch node.

127. The apparatus in claim 126 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.

128. The apparatus in claim 127 wherein said first and second functions is the disjunction function taken up to the pivot bit position for said remaining one branch node, and the third function is the conjunction function taken up to the pivot bit position for said remaining one branch node.

129. The apparatus in claim 125 wherein each pattern node in the hierarchy forest has a corresponding data structure associated therewith, the data structure storing in separate fields therein:

a reference value;

a pointer to a next higher pattern node in a hierarchy containing said new pattern node; and

values for VALUE, MASK and IMASK parameters, wherein the processor, in response to the stored instructions and for a remaining one of the pattern nodes in the data structure, forms the IMASK parameter as a fourth predefined function of the MASK parameter of said remaining one pattern node and the IMASK parameter of a godparent to said remaining one pattern node.

130. The apparatus in claim 129 wherein said fourth function is a conjunction function.