Granted Patent B2

US 8,934,488 · App. 13/664,015 · Granted Jan 13, 2015

Abstract

Claims (113)

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;

grouping rules, by the processor, based on whether or not rules overlap;

assigning, by the processor, priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and

storing, by the processor, the decision tree structure, including storing the plurality of rules and the priority value assigned, in a memory.

2. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured 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, each node representing a subset of the plurality of rules;

group rules based on whether or not rules overlap;

assign priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and

store the decision tree structure in the memory including storing the plurality of rules and the priority value assigned.

3. A non-transitory 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, each node representing a subset of the plurality of rules;

group rules based on whether or not rules overlap;

assign priority values to the plurality of rules including assigning unique priority values within each group of overlapping rules and enabling non-overlapping rules to have a same priority value; and

store the decision tree structure including storing the plurality of rules and the priority value assigned.

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

identifying, by the processor, duplication in the decision tree structure;

modifying, by the processor, the decision tree structure based on the identified duplication; and

storing, by the processor, the modified decision tree structure in a memory.

5. The method of claim 4 further wherein the plurality of nodes includes parent nodes and child nodes, wherein identifying includes:

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

identifying a set of duplicate child nodes, the set of duplicate child nodes having a duplicate subset of the plurality of rules; and wherein modifying includes:

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

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

6. The method of claim 4 wherein the plurality of nodes includes parent nodes and child nodes, the method 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 duplicate buckets; and

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

7. The method of claim 4 wherein the plurality of nodes includes parent nodes and child nodes, the method 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.

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

9. The method of claim 4 wherein the plurality of nodes includes parent nodes and child nodes, the method 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 bucket entries linked to rules of the child node converted;

linking each leaf node to the corresponding bucket created;

identifying a duplicate one or more rules included in at least two buckets; and

replacing at least one bucket entry of the at least two buckets identified with at least one same bucket entry, the same bucket entry being linked to the one or more duplicate rules.

10. An apparatus comprising:

a memory;

a processor coupled to the memory, the processor configured to:

use 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;

identify duplication in the decision tree structure;

modify the decision tree structure based on the identified duplication; and

store the modified decision tree structure in the memory.

11. The apparatus of claim 10 further wherein the plurality of nodes includes parent nodes and child nodes, wherein to identify duplication the processor is further configured to:

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

identify a set of duplicate child nodes, the set of duplicate child nodes having a duplicate subset of the plurality of rules; and wherein to modify the processor is further configured to include:

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

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

12. The apparatus of claim 10 wherein the plurality of nodes includes parent nodes and child nodes, 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 duplicate buckets; and

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

13. The apparatus of claim 10 wherein the plurality of nodes includes parent nodes and child nodes, 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.

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

15. The apparatus of claim 10 wherein the plurality of nodes includes parent nodes and child nodes, 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 bucket entries linked to rules of the child node converted;

link each leaf node to the corresponding bucket created;

identify a duplicate one or more rules included in at least two buckets;

replace at least one bucket entry of the at least two buckets indcntificd identified with at least one same bucket entry, the same bucket entry being linked to the one or more duplicate rules.

16. A non-transitory 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, building a decision tree structure including a plurality of nodes, each node representing a subset of the plurality of rules;

identify duplication in the decision tree structure;

modify the decision tree structure based on the identified duplication; and

store the modified decision tree structure in a memory.

17. The non-transitory computer-readable medium of claim 16 wherein the plurality of nodes includes parent nodes and child nodes, wherein the sequence of instructions which, when executed by a processor, further causes the processor to:

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

identify a set of duplicate child nodes, the set of duplicate child nodes having a duplicate subset of the plurality of rules; and wherein to modify includes the processor further caused to:

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

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

18. The non-transitory computer-readable medium of claim 16 wherein the plurality of nodes includes parent nodes and child nodes, wherein the sequence of instructions which, when executed by a processor, further causes the processor 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 duplicate buckets; and

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

19. The non-transitory computer-readable medium of claim 16 wherein the plurality of nodes includes parent nodes and child nodes, wherein the sequence of instructions which, when executed by a processor, further causes the processor 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.

20. The non-transitory computer-readable medium of claim 19 wherein each partial duplicate bucket includes a linked list of pointers to the first and second set of rules.

21. The non-transitory computer-readable medium of claim 16 wherein the plurality of nodes includes parent nodes and child nodes, wherein the sequence of instructions which, when executed by a processor, further causes the processor 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 bucket entries linked to rules of the child node converted;

link each leaf node to the corresponding bucket created;

identify a duplicate one or more rules included in at least two buckets; and replace at least one bucket entry of the at least two buckets identified with at least one same bucket entry, the same bucket entry being linked to the one or more duplicate rules.

Assignments (6)