Technique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcards

• US 6,041,053 A
• Filed: 09/18/1997
• Issued: 03/21/2000
• 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): Bocure, Tesfaldet
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/933,476
• Time in Patent Office: 915 Days
• Field of Search: 370/389, 370/254, 370/255, 370/256, 370/408, 370/400, 370/252, 370/411, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 707/3, 707/6, 707/100, 707/5, 709/102, 709/103, 709/245, 709/252
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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

2. The method in claim 1 wherein the classification is a designation of a transmission queue.

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

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

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

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

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

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

9. The method in claim 8 wherein the classification is a designation of a transmission queue.

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

11. The method in claim 10 wherein the portion of the packet is a packet header and the information comprises source and destination addresses.

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

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

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

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

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

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

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

19. The method in claim 18 wherein said fourth function is a conjunction function.

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

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

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

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

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

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

26. The method in claim 25 wherein said fourth function is a conjunction function.

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

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

29. The apparatus in claim 28 wherein the classification is a designation of a transmission queue.

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

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

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

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

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

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

36. The apparatus in claim 35 wherein the classification is a designation of a transmission queue.

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

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

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

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

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

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

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

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

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

46. The apparatus in claim 45 wherein said fourth function is a conjunction function.

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

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

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

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

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

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

53. The apparatus in claim 52 wherein said fourth function is a conjunction function.