Incremental update
First Claim
Patent Images
1. A method comprising:
- receiving an incremental update for a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS utilized for packet classification by an active search process;
maintaining a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS for determining updates for the RCDS;
using the housekeeping tree to create a change list; and
atomically updating the RCDS based on the incremental update received, the change list created for atomically updating the RCDS from the perspective of the active search process utilizing the RCDS.
6 Assignments
0 Petitions
Accused Products
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 adding, deleting, and modifying rules in one update from the perspective of an active search process for packet classification, performance and functionality of the active search process may be maintained, thereby preventing packet loss and preserving throughput.
-
Citations
65 Claims
-
1. A method comprising:
-
receiving an incremental update for a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS utilized for packet classification by an active search process; maintaining a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS for determining updates for the RCDS; using the housekeeping tree to create a change list; and atomically updating the RCDS based on the incremental update received, the change list created for atomically updating the RCDS from the perspective of the active search process utilizing the RCDS. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. An apparatus comprising:
-
a first memory configured to store a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification; a second memory for maintaining a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS for determining updates for the RCDS, the housekeeping tree used to create a change list; and a processor coupled to the first memory, the processor receiving the change list, the change list including an incremental update for the RCDS; the processor performing an active search of the RCDS to classify received packets; and the processor updating the RCDS atomically from the perspective of the active search being performed based on the incremental update for the RCDS. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57)
-
-
58. An apparatus comprising:
-
a memory; a processor coupled to the memory, the processor including an incremental update module; the incremental update module receiving an incremental update; and the incremental update module creating a change list in the memory, the change list created to update a Rule Compiled Data Structure (RCDS), atomically, from the perspective of an active search process utilizing the RCDS, wherein the processor maintains a housekeeping tree, an augmented representation of the RCDS including additional information of the RCDS to enable the incremental update module to determine updates for the RCDS, the incremental update module using the housekeeping tree for creating the change list, the processor atomically updating the RCDS based on the incremental update received. - View Dependent Claims (59, 60, 61, 62, 63, 64)
-
-
65. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by a processor, causes the processor to:
-
receive an incremental update for a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS utilized for packet classification by an active search process; maintain a housekeeping tree, an augmented representation of the RCDS; use the housekeeping tree to create a change list; and atomically update the RCDS based on the incremental update received, the change list created for atomically updating the RCDS from the perspective of the active search process utilizing the RCDS.
-
Specification