Packet classification

• US 9,191,321 B2
• Filed: 12/15/2014
• Issued: 11/17/2015
• 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
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): HENSON, JAMAAL R
• Application Number:
  US14/570,626
• Publication Number:
  US 20150117461A1
• Time in Patent Office: 337 Days
• US Class Current: 1/1
• 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:

in a processor, building a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field;

for at least one node of the decision tree structure, determining a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and selecting a field on which to cut the at least one 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;

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

storing the decision tree structure in a memory, wherein selecting the field on which to cut the at least one node based on the comparison enables the processor to build a wider, shallower decision tree structure relative to selecting the field on which to cut not based on the comparison, reducing a search time of a search performed using the decision tree structure stored in the memory.

2. The method of claim 1 wherein the plurality of rules are stored in a classifier table.

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

4. The method of claim 1 wherein selecting includes selecting the field on which to cut the at least one 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.

5. The method of claim 1 wherein cutting includes cutting the at least one node in an event the at least one node has greater than a predetermined number of the subset of the plurality of rules.

6. The method of claim 5 wherein the predetermined number is an adjustable number, and building includes controlling a depth of the decision tree structure by iteratively adjusting the predetermined number.

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

8. The method of claim 1 wherein in an event cutting creates a plurality of child nodes and only one child node has a subset of the plurality of rules, storing at the at least one 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.

9. The method of claim 8 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 at least one node.

10. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to build a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field; and

the processor further configured to determine, for at least one node of the decision tree structure, a number of cuts that may be made on each at least one field creating child nodes equal to the number of cuts and to select a field on which to cut the at least one 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, wherein the processor is further configured to cut the at least one node into a number of child nodes on the selected field and to store the decision tree structure in the memory, wherein selecting the field on which to cut the at least one node based on the comparison enables the processor to build a wider, shallower decision tree structure relative to selecting the field on which to cut not based on the comparison, reducing a search time of a search performed using the decision tree structure stored in the memory.

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

12. The apparatus of claim 10 wherein the processor is further configured to select the field on which to cut the at least one 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.

13. The apparatus of claim 10 wherein the processor is further configured to cut the at least one node in an event the at least one node has greater than a predetermined number of the subset of the plurality of rules.

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

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

16. The apparatus of claim 11 wherein in an event 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 at least one 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 and 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.

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

build a decision tree structure including a plurality of nodes, each node representing a subset of a plurality of rules having at least one field;

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

select a field on which to cut the at least one 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 at least one node into a number of child nodes on the selected at least one field; and

store the decision tree structure in a memory, wherein selecting the field on which to cut the at least one node based on the comparison enables the processor to build a wider, shallower decision tree structure relative to selecting the field on which to cut not based on the comparison, reducing a search time of a search performed using the decision tree structure stored in the memory.