Packet Classification

• US 20130039366A1
• Filed: 08/02/2012
• Published: 02/14/2013
• Est. Priority Date: 08/02/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Bullis, Kenneth A., Billa, Satyanarayana Lakshmipathi
• Granted Patent: US 8,937,952 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/742 : Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 : Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/39 : Credit based
• CPC Class Codes: H04L 63/0227 : Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 : Rule management
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/02 : Protocol performance
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: Y02B 70/30 : Systems integrating technologies related to power network operation and communication or information technologies for improving the carbon footprint of the management of residential or tertiary loads, i.e. smart grids as climate change mitigation technology in the buildings sector, including also the last stages of power distribution and the control, monitoring or operating management systems at local level
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A packet classification system, methods, and corresponding apparatus are provided for enabling packet classification. A processor of a security appliance coupled to a network uses a classifier table having a plurality of rules, the plurality of rules having at least one field, to build a decision tree structure including a plurality of nodes, the plurality of nodes including a subset of the plurality of rules. The methods may produce wider, shallower trees that result in shorter search times and reduced memory requirements for storing the trees.

Claims

1. A method comprising:

using a classifier table having a plurality of rules, the plurality of rules having at least one field, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules;

for each node of the decision tree, (a) determining a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts;

(b) selecting a field on which to cut the node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field;

(c) cutting the node into a number of child nodes on the selected field; and

storing the decision tree structure.

2. The method of claim 1 wherein determining the number of cuts is based on a maximum number of cuts for a given storage capacity.

3. The method of claim 1 wherein selecting includes selecting the field on which to cut the node into a number of child nodes based on the field being a field of the at least one field with the smallest average of the difference between an average number of rules per child node and an actual number of rules per child node.

4. The method of claim 1 wherein cutting includes cutting the node only if the node has greater than a predetermined number of the subset of the plurality of rules.

5. The method of claim 4 wherein the predetermined number is an adjustable number, the method further comprising controlling a depth of the decision tree structure by iteratively adjusting the predetermined number.

6. The method of claim 5 wherein adjusting the predetermined number includes incrementing the predetermined number with increasing levels of the tree.

7. The method of claim 1 wherein if cutting creates a plurality of child nodes and only one child node has a subset of the plurality of rules, storing at the node an identifier of a field of the at least one field and a number of bits of the field of the at least one field to skip upon traversing the node to obtain a rule match.

8. The method of claim 7 wherein the number of bits of the field of the at least one field to skip is the same number as a number of bits used to cut the node.

9. The method of claim 1 further comprising:

while building the decision tree structure, for each level of the decision tree, comparing a subset of rules represented by child nodes having a same parent node;

identifying a set of duplicate child nodes, the set of duplicate child nodes having a duplicate subset of the plurality of rules;

selecting one child node of the set of duplicate child nodes identified as a unique child node;

linking the other child nodes of the set of duplicate child nodes identified to a same subtree as the unique child node;

using the unique child node for subsequent building of the decision tree structure; and

refraining from using the other child nodes of the set of duplicate child nodes identified for subsequent building of the decision tree structure.

10. The method of claim 1 further including grouping the plurality of rules in the classifier table into a plurality of categories of rules and building a decision tree structure including a plurality of nodes for each of the plurality of categories of rules.

11. The method of claim 10 wherein the plurality of categories of rules are based on one or more field functions, or combinations of the one or more field functions, applied to the plurality of rules.

12. The method of claim 11 wherein the one or more field functions includes:

defining two or more field sizes;

selecting one or more fields of the plurality of rules, each rule of the plurality of rules including the one or more fields selected;

for each of the one or more fields selected, defining a respective field scope range for each of the two or more field sizes defined; and

for each rule of the plurality of rules;

computing a respective field scope value for each of the one or more fields selected; and

assigning a respective field size, of the two or more field sizes defined, to each of the one or more fields selected, the respective field size being assigned based on comparing the respective field scope value computed to the respective field scope range defined for each of the two or more field sizes defined.

13. The method of claim 10 further comprising walking a received packet through each decision tree built and comparing the resulting rules from each tree to select a final match.

14. The method of claim 13 wherein the final match selected is the rule with a highest priority.

15. The method of claim 1 further comprising:

converting each child node having a number of rules less than or equal to a given number of rules to a leaf node;

creating a corresponding bucket for each child node converted, the corresponding bucket including rules of the child node converted;

linking each leaf node to the corresponding bucket created;

identifying a set of duplicate buckets, duplicate buckets each including a same set of rules;

selecting one bucket of the set of duplicate buckets and removing other buckets of the set of duplicated buckets; and

changing links to removed buckets to links to the one bucket selected.

16. The method of claim 1 further comprising:

converting each child node having a number of rules less than or equal to a given number of rules to a leaf node;

creating a corresponding bucket for each child node converted, the corresponding bucket including rules of the child node converted;

linking each leaf node to the corresponding bucket created;

identifying a set of partial duplicate buckets, partial duplicate buckets each including a duplicate partial set of rules;

separating rules in each bucket in the set of partial duplicate buckets into a first and second set of rules for each bucket, the first set of rules for each bucket including the duplicate partial set of rules and the second set of rules for each bucket including any remaining rules for each bucket; and

creating a link in each partial duplicate bucket to the first set of rules and creating a link in each partial duplicate bucket to the second set of rules.

17. The method of claim 16 wherein each partial duplicate bucket includes a linked list of pointers to the first and second set of rules.

18. The method of claim 1 wherein the decision tree structure is a binary data structure.

19. The method of claim 1 wherein the decision tree structure is compiled from the classifier table.

20. The method of claim 1 wherein a priority corresponding to each rule is stored in the decision tree structure.

21. The method of claim 1 including determining whether or not a rule is covered by one or more other higher priority rules and omitting the rule from the decision tree structure if the rule is covered.

22. The method of claim 21 wherein determining includes determining for each node that includes a subset of the subset of the plurality of rules represented by a higher level node.

74. The method of claim 12 further wherein the two or more field sizes defined includes small and large.

75. The method of claim 12 further wherein the respective field scope range defined for each of the two or more field sizes selected is defined as a ratio of a range of a given field value to its total space.

76. The method of claim 12 further wherein the respective field scope value computed is computed as a ratio of a total value of the respective field to its total field space.

77. The method of claim 76 further wherein the total value of the respective field is based on a number of relevant bits defined by a mask associated with the respective field or a given range associated with the respective field.

78. The method of claim 12 further wherein the one or more fields selected includes one or more fields of an Internet Protocol (IP) header.

79. The method of claim 12 further wherein a total number of the plurality of categories of rules is based on a first quantity, the first quantity being a first number of the one or more fields selected, and a second quantity, the second quantity being a second number of the two or more field sizes defined.

80. The method of claim 12 further wherein grouping includes grouping rules in a same category of the plurality of categories based on rules having common field sizes assigned to each of the one or more fields selected.

81. The method of claim 21 wherein the rule is covered by the one or more other higher priority rules if respective fields of the rule overlap with all respective fields of the one or more other higher priority rules.

23-27. -27. (canceled)

28. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to use a classifier table having a plurality of rules stored in the memory, the plurality of rules having at least one field, the processor further configured to build a decision tree structure including a plurality of nodes, the plurality of nodes representing a subset of the plurality of rules;

the processor further configured to determine, for each node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts;

upon determining the number of cuts that may be made on each at one least field, the processor further configured to select a field on which to cut the node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least field; and

the processor further configured to cut the node into a number of child nodes on the selected field and to store the decision tree structure in the memory.

29. The apparatus of claim 28 wherein the processor is further configured to determine the number of cuts based on a maximum number of cuts for a given storage capacity.

30. The apparatus of claim 28 wherein the processor is further configured to select the field on which to cut the node into a number of child nodes based on the field being a field of the at least one field with the smallest average of the difference between an average number of rules per child node and an actual number of rules per child node.

31. The apparatus of claim 28 wherein the processor is further configured to cut the node only if the node has greater than a predetermined number of the subset of the plurality of rules.

32. The apparatus of claim 31 wherein the predetermined number is an adjustable number, wherein the processor is further configured to control a depth of the decision tree structure by iteratively adjusting the predetermined number.

33. The apparatus of claim 32 wherein adjusting the predetermined number includes incrementing the predetermined number with increasing levels of the tree.

34. The apparatus of claim 28 wherein if cutting creates a plurality of child nodes and only one child node has a subset of the plurality of rules, the processor is further configured to store at the node an identifier of a field of the at least one field and a number of bits of the field of the at least one field to skip upon traversing the node to obtain a rule match.

35. The apparatus of claim 34 wherein the number of bits of the field of the at least one field to skip is the same number as a number of bits used to cut the node.

36. The apparatus of claim 28 wherein the processor is further configured to:

while building the decision tree structure, for each level of the decision tree, compare a subset of rules represented by child nodes having a same parent node;

identify a set of duplicate child nodes, the set of duplicate child nodes having a duplicate subset of the plurality of rules;

select one child node of the set of duplicate child nodes identified as a unique child node;

link the other child nodes of the set of duplicate child nodes identified to a same subtree as the unique child node;

use the unique child node for subsequent building of the decision tree structure; and

refrain from using the other child nodes of the set of duplicate child nodes identified for subsequent building of the decision tree structure.

37. The apparatus of claim 28 wherein the processor is further configured to group the plurality of rules in the classifier table into a plurality of categories of rules and build a decision tree structure including a plurality of nodes for each of the plurality of categories of rules.

38. The apparatus of claim 37 wherein the plurality of categories of rules are based on one or more field functions, or combinations of the one or more field functions, applied to the plurality of rules.

39. The apparatus of claim 38 wherein one or more field functions includes:

applying a no Internet Protocol (IP) address wildcard, source IP but not

defining two or more field sizes;

selecting one or more fields of the plurality of rules, each rule of the plurality of rules including the one or more fields selected;

for each of the one or more fields selected, defining a respective field scope range for each of the two or more field sizes defined; and

for each rule of the plurality of rules;

computing a respective field scope value for each of the one or more fields selected; and

assigning a respective field size, of the two or more field sizes defined, to each of the one or more fields selected, the respective field size being assigned based on comparing the respective field scope value computed to the respective field scope range defined for each of the two or more field sizes defined.

40. The apparatus of claim 28 wherein the processor is further configured to:

convert each child node having a number of rules less than or equal to a given number of rules to a leaf node;

create a corresponding bucket for each child node converted, the corresponding bucket including rules of the child node converted;

link each leaf node to the corresponding bucket created;

identify a set of duplicate buckets, duplicate buckets each including a same set of rules;

select one bucket of the set of duplicate buckets and removing other buckets of the set of duplicated buckets; and

change links to removed buckets to links to the one bucket selected.

41. The apparatus of claim 28 wherein the processor is further configured to:

convert each child node having a number of rules less than or equal to a given number of rules to a leaf node;

create a corresponding bucket for each child node converted, the corresponding bucket including rules of the child node converted;

link each leaf node to the corresponding bucket created;

identify a set of partial duplicate buckets, partial duplicate buckets each including a duplicate partial set of rules;

separate rules in each bucket in the set of partial duplicate buckets into a first and second set of rules for each bucket, the first set of rules for each bucket including the duplicate partial set of rules and the second set of rules for each bucket including any remaining rules for each bucket; and

create a link in each partial duplicate bucket to the first set of rules and creating a link in each partial duplicate bucket to the second set of rules.

42. The apparatus of claim 41 wherein each partial duplicate bucket includes a linked list of pointers to the first and second set of rules.

43. The apparatus of claim 28 wherein the decision tree structure is a binary data structure.

44. The apparatus of claim 28 wherein the decision tree structure is compiled from the classifier table.

45. The apparatus of claim 28 wherein a priority corresponding to each rule is stored in the decision tree structure.

46. The apparatus of claim 28 including determining whether or not a rule is covered by one or more other higher priority rules and omitting the rule from the decision tree structure if the rule is covered.

82. The apparatus of claim 39 wherein the two or more field sizes defined includes small and large.

83. The apparatus of claim 39 further wherein the respective field scope range defined for each of the two or more field sizes selected is defined as a ratio of a given range of a field value to its total space.

84. The apparatus of claim 39 further wherein the respective field scope value computed is computed as a ratio of a total value of the respective field to its total field space.

85. The apparatus of claim 84 further wherein the total value of the respective field is based on a number of relevant bits defined by a mask associated with the respective field or a given range associated with the respective field.

86. The apparatus of claim 39 further wherein the one or more fields selected includes one or more fields of an Internet Protocol (IP) header.

87. The apparatus of claim 39 further wherein a total number of the plurality of categories of rules is based on a first quantity, the first quantity being a first number of the one or more fields selected, and a second quantity, the second quantity being a second number of the two or more field sizes defined.

88. The apparatus of claim 39 further wherein the processor is further configured to group rules in a same category of the plurality of categories based on rules having common field sizes assigned to each of the one or more fields selected.

89. The apparatus of claim 46 wherein the rule is covered by the one or more other higher priority rules if respective fields of the rule overlap with all respective fields of the one or more other higher priority rules

47. A non-transient computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:

use a classifier table having a plurality of rules, the plurality of rules having at least one field;

build a decision tree structure including a plurality of nodes, the plurality of nodes including a subset of the plurality of rules;

determine, for each node of the decision tree, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts;

select, upon determining the number of cuts that may be made on each at one least field, a field on which to cut the node based on a comparison of an average of a difference between an average number of rules per child node created and an actual number of rules per child node created per each at least one field;

cut the node into a number of child nodes on the selected at least field; and

store the decision tree structure.

48. The non-transient computer-readable medium of claim 47, wherein the processor selects the field on which to cut the node into a number of child nodes based on the at least one field with the smallest average of the difference between an average number of rules per child node and an actual number of rules per child node.

49-73. -73. (canceled)