Batch incremental update
AssigneeCavium, Inc.
InventorsRajan Goyal, Kenneth A. Bullis, Satyanarayana Lakshmipathi Billa
Life of this patent
Estimating the term…
Abstract
A system, apparatus, and method are provided for adding, deleting, and modifying rules in one update from the perspective of an active search process for packet classification. While a search processor searches for one or more rules that match keys generated from received packets, there is a need to add, delete, or modify rules. By organizing a plurality incremental updates for adding, deleting, or modifying rules into a batch update, several operations for incorporating the incremental updates may be made more efficient by minimizing a number of updates required.
Claims48
A method comprising:
- receiving a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;
- updating the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS;
- updating the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;
- and
- applying the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.
An apparatus comprising:
- a memory;
- a processor coupled to the memory, the processor configured to:
- receive a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;
- update the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS;
- update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;
- and
- apply the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.
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 a batch update including a plurality of incremental updates for a Rule Compiled Data Structure (RCDS) representing a decision tree for a set of rules used for packet classification, the RCDS being utilized for packet classification by an active search process;
- update the set of rules and one or more rule lists based on the batch update received, each of the one or more rule lists being a subset of the set of rules associated with a category subtree of a housekeeping tree, the housekeeping tree being an augmented representation of the RCDS;
- update the housekeeping tree associated with each category subtree associated with the one or more rule lists updated and building a changeset specifying one or more modifications to the RCDS based on the housekeeping tree updated;
- and
- apply the changeset built to the RCDS in a manner enabling the RCDS to atomically incorporate the plurality of incremental updates from the perspective of the active search process utilizing the RCDS.
Dependencies are inferred from the claim text.