Packet classification

Patent metadata

Field	Value
Publication number	US-8937952-B2
Application number	US-201213565784-A
Country	US
Kind code	B2
Filing date	Aug 2, 2012
Priority date	Aug 2, 2011
Publication date	Jan 20, 2015
Grant date	Jan 20, 2015

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.

First claim

What is claimed is:

1. A method comprising:
in a processor, 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 in a memory.

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 12 further wherein the two or more field sizes defined includes small and large.

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

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

16. The method of claim 15 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.

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

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

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

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

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

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

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

Assignees

• Goyal Rajan
• Bullis Kenneth A
• Billa Satyanarayana Lakshmipathi
• Cavium Inc

Inventors

• Goyal Rajan
• Bullis Kenneth A
• Billa Satyanarayana Lakshmipathi

Classifications

• H04L45/7452

  Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) · CPC title

• H04L43/18 Primary

  Protocol analysers · CPC title

• H04L47/2441

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title