US6041053A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcards
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-09-18
•
Granted: 2000-03-21
•
Expires: 2017-09-18
Abstract
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.
Inventors
- 👤 John R. Douceur
- 👤 Ofer Bar
- 👤 Yoram Bernet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 05:47
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/24; H04L47/2441; H04L45/00; H04L45/74; H04L45/742; H04L47/2408; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
260 words
A method for use in a packet classifier, the classifier having a data structure with hierarchically-related pattern values stored therein, said pattern values having wildcards therein; wherein the data structure has a search trie and a hierarchy forest, the 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, the 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 comprising the steps of: forming a key in response to information contained in a portion of the packet; 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 key and pivot bit values associated with ones of said branch nodes; determining whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in 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 key; and if the key identically matches or is subsumed by the desired one pattern value: accessing a stored classification associated with said desired one pattern value; and returning the stored classification for the packet.
Claim 2
Independent Claim
260 words
A method for use in a packet classifier, the classifier having a data structure with hierarchically-related pattern values stored therein, said pattern values having wildcards therein; wherein the data structure has a search trie and a hierarchy forest, the 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, the 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 comprising the steps of: forming a key in response to information contained in a portion of the packet; 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 key and pivot bit values associated with ones of said branch nodes; determining whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in 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 key; and if the key identically matches or is subsumed by the desired one pattern value: accessing a stored classification associated with said desired one pattern value; and returning the stored classification for the packet.
Claim 3
Dependent Claim
15 words
The method in claim 1 wherein the classification is a designation of a transmission queue.
Claim 4
Dependent Claim
56 words
The method in claim 2 wherein the accessing step further comprises the steps of: accessing a reference field associated with a pattern node storing said desired one pattern value so as to yield a stored designation of an associated transmission queue as the classification; and returning the designation of the associated transmission queue for the packet.
Claim 5
Dependent Claim
29 words
The method in claim 3 wherein the portion of the packet is a packet header, and the information comprises source and destination addresses and source and destination port designations.
Claim 6
Dependent Claim
62 words
The method in claim 1 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 key indexed by the pivot bit of said each branch node until said one pattern node is encountered.
Claim 7
Dependent Claim
119 words
The method in claim 5 wherein the tracing step comprises the steps of: examining, when the path reaches said successive branch node, a particular bit in the 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.
Claim 8
Dependent Claim
56 words
The method in claim 6 further comprising the step of: returning a message, indicative of the no match condition, in the event said 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.
Claim 9
Dependent Claim
51 words
The method in claim 7 further comprising the step of inserting, in response to a new transmission queue being established, a new pattern node, into said hierarchy forest, for storing a new pattern value in the data structure, said new pattern node having a designation of the new queue associated therewith.
Claim 10
Dependent Claim
15 words
The method in claim 8 wherein the classification is a designation of a transmission queue.
Claim 11
Dependent Claim
56 words
The method in claim 9 wherein the accessing step further comprises the steps of: accessing a reference field associated with a pattern node storing said desired one pattern value so as to yield a stored designation of an associated transmission queue as the classification; and returning the designation of the associated transmission queue for the packet.
Claim 12
Dependent Claim
23 words
The method in claim 10 wherein the portion of the packet is a packet header and the information comprises source and destination addresses.
Claim 13
Dependent Claim
136 words
The method in claim 8 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.
Claim 14
Dependent Claim
99 words
The method in claim 12 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.
Claim 15
Dependent Claim
93 words
The method in claim 13 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.
Claim 16
Dependent Claim
24 words
The method in claim 14 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.
Claim 17
Dependent Claim
47 words
The method in claim 15 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.
Claim 18
Dependent Claim
87 words
The method in claim 12 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.
Claim 19
Dependent Claim
88 words
The method in claim 17 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.
Claim 20
Dependent Claim
13 words
The method in claim 18 wherein said fourth function is a conjunction function.
Claim 21
Dependent Claim
35 words
The method in claim 7 further comprising the step of removing an existing pattern node, from said hierarchy forest, so as to remove a pattern value, and a flow, associated therewith from said data structure.
Claim 22
Dependent Claim
62 words
The method in claim 20 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.
Claim 23
Dependent Claim
164 words
The method in claim 21 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.
Claim 24
Dependent Claim
24 words
The method in claim 22 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.
Claim 25
Dependent Claim
49 words
The method in claim 23 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.
Claim 26
Dependent Claim
107 words
The method in claim 21 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.
Claim 27
Dependent Claim
13 words
The method in claim 25 wherein said fourth function is a conjunction function.
Claim 28
Dependent Claim
18 words
A computer readable medium having computer executable instructions stored therein for performing the steps recited in claim 1.
Claim 29
Dependent Claim
270 words
Apparatus for a packet classifier comprising: a processor; 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 of said pattern nodes having a different corresponding one of the pattern values associated therewith, organized into at least one hierarchy of pattern nodes of increasing generality wherein at least one of the pattern values in the hierarchy contains a wildcard; wherein the processor, in response to the stored instructions: forms a key in response to information contained in a portion of the packet 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 key and pivot bit values associated with ones of said branch nodes; determines whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in 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 key; and if the key identically matches or is subsumed by the desired one pattern value: accesses a stored classification associated with said desired one pattern value; and returns the stored classification for the packet.
Claim 30
Dependent Claim
270 words
Apparatus for a packet classifier comprising: a processor; 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 of said pattern nodes having a different corresponding one of the pattern values associated therewith, organized into at least one hierarchy of pattern nodes of increasing generality wherein at least one of the pattern values in the hierarchy contains a wildcard; wherein the processor, in response to the stored instructions: forms a key in response to information contained in a portion of the packet 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 key and pivot bit values associated with ones of said branch nodes; determines whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in 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 key; and if the key identically matches or is subsumed by the desired one pattern value: accesses a stored classification associated with said desired one pattern value; and returns the stored classification for the packet.
Claim 31
Dependent Claim
15 words
The apparatus in claim 28 wherein the classification is a designation of a transmission queue.
Claim 32
Dependent Claim
56 words
The apparatus in claim 29 wherein the processor, in response to the stored instructions: accesses a reference field associated with a pattern node storing said desired one pattern value so as to yield a stored designation of an associated transmission queue as the classification; and returns the designation of the associated transmission queue for the packet.
Claim 33
Dependent Claim
29 words
The apparatus in claim 30 wherein the portion of the packet is a packet header, and the information comprises source and destination addresses and source and destination port designations.
Claim 34
Dependent Claim
63 words
The apparatus in claim 28 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 key indexed by the pivot bit of said each branch node until said one pattern node is encountered.
Claim 35
Dependent Claim
120 words
The apparatus in claim 32 wherein the processor, in response to the stored instructions: examines, when the path reaches said successive branch node, a particular bit in the 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 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.
Claim 36
Dependent Claim
60 words
The apparatus in claim 33 wherein the processor, in response to the stored instructions, returns a message, indicative of the no match condition, in the event said 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.
Claim 37
Dependent Claim
56 words
The apparatus in claim 34 wherein the processor, in response to the stored instructions, inserts, in response to a new transmission queue being established, a new pattern node, into said hierarchy forest, for storing a new pattern value in the data structure, said new pattern node having a designation of the new transmission queue associated therewith.
Claim 38
Dependent Claim
15 words
The apparatus in claim 35 wherein the classification is a designation of a transmission queue.
Claim 39
Dependent Claim
56 words
The apparatus in claim 36 wherein the processor, in response to the stored instructions: accesses a reference field associated with a pattern node storing said desired one pattern value so as to yield a stored designation of an associated transmission queue as the classification; and returns the designation of the associated transmission queue for the packet.
Claim 40
Dependent Claim
29 words
The apparatus in claim 37 wherein the portion of the packet is a packet header, and the information comprises source and destination addresses and source and destination port designations.
Claim 41
Dependent Claim
136 words
The apparatus in claim 35 wherein the processor, in response to the stored instructions: inserts 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, 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.
Claim 42
Dependent Claim
98 words
The apparatus in claim 39 wherein each of said branch nodes in said search trie has a corresponding data structure associated therewith, and wherein 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.
Claim 43
Dependent Claim
93 words
The apparatus in claim 40 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.
Claim 44
Dependent Claim
24 words
The apparatus in claim 41 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.
Claim 45
Dependent Claim
47 words
The apparatus in claim 42 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.
Claim 46
Dependent Claim
85 words
The apparatus in claim 39 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.
Claim 47
Dependent Claim
88 words
The apparatus in claim 44 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.
Claim 48
Dependent Claim
13 words
The apparatus in claim 45 wherein said fourth function is a conjunction function.
Claim 49
Dependent Claim
39 words
The apparatus in claim 34 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, and a flow, associated therewith from said data structure.
Claim 50
Dependent Claim
63 words
The apparatus in claim 47 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.
Claim 51
Dependent Claim
165 words
The apparatus in claim 48 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.
Claim 52
Dependent Claim
24 words
The apparatus in claim 49 wherein said first and second functions are each a disjunction function, and said third function is a conjunction function.
Claim 53
Dependent Claim
49 words
The apparatus in claim 50 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.
Claim 54
Dependent Claim
109 words
The apparatus in claim 48 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.
Claim 55
Dependent Claim
13 words
The apparatus in claim 52 wherein said fourth function is a conjunction function.
References Cited (Backward Citations)
US5640551A
Cited
US5546390A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-21 | 2003-09-20 | 2004-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-21 | 2007-09-20 | 2008-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-21 | 2011-09-20 | 2012-03-21 | $7700.00 | Window Closed / Lapsed |