BATCH INCREMENTAL UPDATE

摘要

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.

主权项

1. 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.