Multi-field classification dynamic rule updates

• US 20060020600A1
• Filed: 07/20/2004
• Published: 01/26/2006
• Est. Priority Date: 07/20/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Davis, Gordon T., Jeffries, Clark D., Corl, Everett A. Jr.
• Granted Patent: US 7,478,426 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

The present invention relates to a method and computer system device for applying a plurality of rules to data packets within a network computer system. A filter rule decision tree is updated by adding or deleting a rule. If deleting a filter rule then the decision tree is provided to a network data plane processor with an incremental delete of the filter rule. If adding a filter rule then either providing an incremental insertion of the filter rule to the decision tree or rebuilding the first decision tree into a second decision tree responsive to comparing a parameter to a threshold. In one embodiment the parameter and thresholds relate to depth values of the tree filter rule chained branches. In another the parameter and thresholds relate to a total count of rule additions since a building of the relevant tree.

Claims

1. A method for applying a plurality of rules organized into a first decision tree to data packets within a network computer system, comprising the steps of:

(a) deleting one of the plurality of filter rules or adding a new rule;

(b) if deleting one filter rule in step (a), then providing an incremental delete of the one filter rule from the first decision tree to a network data plane processor for application to network data packets;

(c) if adding a new rule in step (a), then;

(c1) determining a parameter responsive to the new rule addition;

(c2) comparing the parameter to a first threshold; and

(c3) responsive to the comparison of the parameter to the first threshold either;

(c3i) providing an incremental insertion of the one filter rule to the first decision tree to a network data plane processor;

or

(c3ii)(1) rebuilding the plurality of rules and new rule into a second decision tree; and

(c3ii)(2) providing the second decision tree to the network data plane processor.

2. The method of claim 1 further comprising the step (c3ii)(3) of updating the first threshold to a second threshold responsive to the second decision tree.

3. The method of claim 2, wherein the first and second decision trees have a plurality of chained branches of filter rules, each branch having a depth value defined by a number of linked pointers leading from a root of the tree to a tip of the branch, and the first threshold is a first maximum branch depth of the first tree;

wherein step (c1) comprises the steps of;

adding the new rule to a branch of the first decision tree to form an enlarged branch; and

determining a total rule depth of the enlarged branch as the parameter;

step (c2) comprises comparing the enlarged branch total rule depth parameter to the first maximum branch depth threshold;

step (c3i) occurs if the enlarged branch total rule depth parameter is less than or equal to the first maximum branch depth threshold, step (c3i) comprising providing a definition of the decision node added to the enlarged branch of the first decision tree to the network data plane processor, where the new decision node is inserted into the copy of the decision tree local to the network data plane processor;

step (c3ii) occurs if the enlarged branch total rule depth is greater than the first maximum branch depth; and

the second threshold is a second maximum branch depth of the second tree.

4. The method of claim 3, further comprising the steps of:

determining the first maximum branch depth responsive to a total of the plurality of rules in a longest branch in the first tree plus a value N; and

determining the second maximum branch depth responsive to a total of the plurality of rules in a longest branch in the second tree plus a value N.

5. The method of claim 4, further comprising the steps of:

determining a tree total rule size; and

setting the value N responsive to the tree total rule size.

6. The method of claim 5, wherein the value N is reduced in inverse proportion to an increase in tree total rule size.

7. The method of claim 2, wherein the parameter is a total count of rule additions since a building of the first tree, the first threshold is a first tree total rule addition threshold M1 and the second threshold is a second tree total rule addition threshold M2;

wherein step (c1) comprises incrementing the rule addition total count responsive to the new rule;

step (c2) comprises comparing the incremented rule addition total count parameter to M1;

step (c3i) occurs if the incremented rule addition total count parameter is less than or equal to M1; and

step (c3ii) occurs if the incremented rule addition total count parameter is greater than M1.

8. The method of claim 7, further comprising the steps of:

determining a first tree total rule size;

setting M1 responsive to the first tree total rule size;

determining a second tree total rule size; and

setting M2 responsive to the second tree total rule size.

9. A computer system device in communication with a network computer system control point configured to apply a plurality of rules to data packets organized in a first decision tree, the device comprising:

a processor; and

a memory coupled to the processor, the memory containing one or more sequences of instructions for controlling a network device, wherein execution of the one or more sequences of instructions by the processor causes the processor to perform the steps of;

(a) deleting one of the plurality of filter rules or adding a new rule;

(b) if deleting one filter rule in step (a), then providing an incremental delete of the one filter rule from the first decision tree to a network data plane processor for application to network data packets;

(c) if adding a new rule in step (a), then;

(c2) determining a parameter responsive to the new rule addition;

(c2) comparing the parameter to a first threshold; and

(c3) responsive to the comparison of the parameter to the first threshold either;

(c3i) providing an incremental insertion of the one filter rule to the first decision tree to a network data plane processor;

or

(c3ii)(1) rebuilding the plurality of rules and new rule into a second decision tree; and

(c3ii)(2) providing the second decision tree to the network data plane processor.

10. The computer system device of claim 9, further configured to perform a step (c3ii)(3) of updating the first threshold to a second threshold responsive to the second decision tree.

11. The computer system device of claim 10, wherein the first and second decision trees have a plurality of chained branches of filter rules, each branch having a depth value defined by a number of linked pointers leading from a root of the tree to a tip of the branch, and the first threshold is a first maximum branch depth of the first tree;

wherein step (c1) comprises the steps of;

adding the new rule to a branch of the first decision tree to form an enlarged branch; and

determining a total rule depth of the enlarged branch as the parameter;

step (c2) comprises comparing the enlarged branch total rule depth parameter to the first maximum branch depth threshold;

step (c3i) occurs if the enlarged branch total rule depth parameter is less than or equal to the first maximum branch depth threshold, step (c3i) comprising providing a definition of the decision node added to the enlarged branch of the first decision tree to the network data plane processor, where the new decision node is inserted into the copy of the decision tree local to the network data plane processor;

step (c3ii) occurs if the enlarged branch total rule depth is greater than the first maximum branch depth; and

the second threshold is a second maximum branch depth of the second tree.

12. The computer system device of claim 11, further configured to set the first maximum branch depth equal to the first maximum branch depth plus a value N;

and

to set the second maximum branch depth equal to the second maximum branch depth plus a value N.

13. The computer system device of claim 12, further configured to perform the steps of:

determining a tree total rule size; and

setting the value N responsive to the tree total rule size.

14. The computer system device of claim 13, wherein the value N is reduced in inverse proportion to an increase in the tree total rule size.

15. The computer system device of claim 10, wherein the parameter is a total count of rule additions since a building of the first tree, the first threshold is a first tree total rule addition threshold M1 and the second threshold is a second tree total rule addition threshold M2;

wherein step (c1) comprises incrementing the rule addition total count responsive to the new rule;

step (c2) comprises comparing the incremented rule addition total count to M1;

step (c3i) occurs if the incremented rule addition total count is less than or equal to M1; and

step (c3ii) occurs if the incremented rule addition total count is greater than M1.

16. The computer system device of claim 15, further configured to perform the steps of:

determining a first tree total rule size;

setting M1 responsive to the first tree total rule size;

determining a second tree total rule size; and

setting M2 responsive to the second tree total rule size.

17. An article of manufacture comprising a computer usable medium having a computer readable program embodied in said medium, wherein the computer readable program, when executed on a computer within a network computer system, causes the computer to:

(a) delete one of the plurality of filter rules organized into a first decision tree or adding a new rule to the plurality of rules;

(b) if deleting one filter rule in step (a), then provide an incremental delete of the one filter rule from the first decision tree to a network data plane processor for application to network data packets;

(c) if adding a new rule in step (a), then;

(c1) determine a parameter responsive to the new rule addition;

(c2) compare the parameter to a first threshold; and

(c3) responsive to the comparison of the parameter to the first threshold either;

(c3i) provide an incremental insertion of the one filter rule to the first decision tree to a network data plane processor;

or

(c3ii)(1) rebuild the plurality of rules and new rule into a second decision tree;

(c3ii)(2) provide the second decision tree to the network data plane processor; and

(c3ii)(3) update the first threshold to a second threshold responsive to the second decision tree.

18. The article of manufacture of claim 17, wherein the first and second decision trees have a plurality of chained branches of filter rules, each branch having a depth value defined by a number of linked pointers leading from a root of the tree to a tip of the branch, and the first threshold is a first maximum branch depth of the first tree;

step (c1) comprises the steps of;

adding the new rule to a branch of the first decision tree to form an enlarged branch; and

determining a total rule depth of the enlarged branch as the parameter;

step (c2) comprises comparing the enlarged branch total rule depth parameter to the first maximum branch depth threshold;

step (c3i) occurs if the enlarged branch total rule depth parameter is less than or equal to the first maximum branch depth threshold, step (c3i) comprising providing a definition of the decision node added to the enlarged branch of the first decision tree to the network data plane processor, where the new decision node is inserted into the copy of the decision tree local to the network data plane processor;

step (c3ii) occurs if the enlarged branch total rule depth is greater than the first maximum branch depth; and

the second threshold is a second maximum branch depth of the second tree.

19. The article of manufacture of claim 17, wherein the parameter is a total count of rule additions since a building of the first tree, the first threshold is a first tree total rule addition threshold M1 and the second threshold is a second tree total rule addition threshold M2;

wherein step (c1) comprises incrementing the rule addition total count responsive to the new rule;

step (c2) comprises comparing the incremented rule addition total count parameter to M1;

step (c3i) occurs if the incremented rule addition total count parameter is less than or equal to M1; and

step (c3ii) occurs if the incremented rule addition total count parameter is greater than M1.