Rule modification in decision trees
First Claim
Patent Images
1. A method comprising:
- receiving an incremental update specifying a new rule definition including a modification of at least one field of a designated rule of a plurality of rules, the plurality of rules being represented by a Rule Compiled Data Structure (RCDS) as a decision tree for packet classification utilized by an active search process, the plurality of rules representing a search space for the packet classification, each rule of the plurality of rules having an original rule definition defining a subset of the search space;
determining an intersection of the new rule definition specified and the original rule definition of the designated rule;
setting the original rule definition of the designated rule to an intermediate rule definition defined by the intersection determined and incorporating a series of one or more updates determined in the RCDS, atomically from the perspective of the active search process; and
setting the intermediate rule definition of the designated rule to the new rule definition and incorporating the series of one or more updates determined in the RCDS, atomically from the perspective of the active search process.
6 Assignments
0 Petitions
Accused Products
Abstract
A system, apparatus, and method are provided for modifying rules in-place atomically from the perspective of an active search process using the rules for packet classification. A rule may be modified in-place by updating a rule'"'"'s definition to be an intersection of an original and new definition. The rule'"'"'s definition may be further updated to the rule'"'"'s new definition and a decision tree may be updated based on the rule'"'"'s new definition. While a search processor searches for one or more rules that match keys generated from received packets the in-place rule modification prevents periods of incorrect rule matching of the keys thereby preventing packet loss and preserving throughput.
76 Citations
33 Claims
-
1. A method comprising:
-
receiving an incremental update specifying a new rule definition including a modification of at least one field of a designated rule of a plurality of rules, the plurality of rules being represented by a Rule Compiled Data Structure (RCDS) as a decision tree for packet classification utilized by an active search process, the plurality of rules representing a search space for the packet classification, each rule of the plurality of rules having an original rule definition defining a subset of the search space; determining an intersection of the new rule definition specified and the original rule definition of the designated rule; setting the original rule definition of the designated rule to an intermediate rule definition defined by the intersection determined and incorporating a series of one or more updates determined in the RCDS, atomically from the perspective of the active search process; and setting the intermediate rule definition of the designated rule to the new rule definition and incorporating the series of one or more updates determined in the RCDS, atomically from the perspective of the active search process. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. An apparatus comprising:
-
a memory; a processor coupled to the memory, the processor configured to; receive an incremental update specifying a new rule definition including a modification of at least one field of a designated rule of a plurality of rules, the plurality of rules being represented by a Rule Compiled Data Structure (RCDS) as a decision tree for packet classification utilized by an active search process, the plurality of rules representing a search space for the packet classification, each rule of the plurality of rules having an original rule definition defining a subset of the search space; determine an intersection of the new rule definition specified and the original rule definition of the designated; set the original rule definition of the designated rule to an intermediate rule definition defined by the intersection determined and incorporate a series of one or more updates determined in the RCDS, atomically from the perspective of the active search process; and set the intermediate rule definition of the designated rule to the new rule definition and incorporating the series of one or more updates determined in the RCDS, atomically from the perspective of the active search process. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:
-
receive an incremental update specifying a new rule definition including a modification of at least one field of a designated rule of a plurality of rules, the plurality of rules being represented by a Rule Compiled Data Structure (RCDS) as a decision tree for packet classification utilized by an active search process, the plurality of rules representing a search space for the packet classification, each rule of the plurality of rules having an original rule definition defining a subset of the search space; determine an intersection of the new rule definition specified and the original rule definition of the designated rule; set the original rule definition of the designated rule to an intermediate rule definition defined by the intersection determined and incorporate a series of one or more updates determined in the RCDS, atomically from the perspective of the active search process; and set the intermediate rule definition of the designated rule to the new rule definition and incorporating the series of one or more updates determined in the RCDS, atomically from the perspective of the active search process. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
Specification