Incremental update

Patent metadata

Field	Value
Publication number	US-9137340-B2
Application number	US-201213565775-A
Country	US
Kind code	B2
Filing date	Aug 2, 2012
Priority date	Aug 2, 2011
Publication date	Sep 15, 2015
Grant date	Sep 15, 2015

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.

First claim

What is claimed is:

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.

2. The method of claim 1 , wherein atomically updating the RCDS includes:
restricting a state of the RCDS to a before state and an after state, the before state being a state of the RCDS before receiving the incremental update for the RCDS, the after state being a state of the RCDS after a series of one or more modifications to the RCDS has been completed, the series of one or more modifications having been completed based on the incremental update received, the series of one or more modifications being visible to the active search process based on performing one update to the RCDS being searched.

3. The method of claim 1 , wherein updating the RCDS based on the incremental update received includes:
atomically adding a new rule to the RCDS based on the incremental update being an add rule operation;
atomically deleting a rule from the RCDS based on the incremental update being a delete rule operation; and
atomically modifying a rule in the RCDS based on the incremental update being a modify rule operation, wherein modifying the rule includes at least one of: modifying a priority of the rule or modifying at least one field of the rule.

4. The method of claim 3 , wherein modifying the priority of the rule includes:
identifying a priority fit conflict based on a change in priority of the rule being inconsistent with a current priority ordering of the rule and one or more other rules;
atomically modifying the priority of the rule based on the priority fit conflict not being identified; and
atomically modifying the priority of the rule and priority of another rule based on the conflict being identified.

5. The method of claim 3 , wherein modifying at least one field of the rule includes:
determining whether one or more rules need to be added or deleted; and
adding or deleting the one or more rules, wherein adding or deleting the one or more rules is atomic.

6. The method of claim 1 , further comprising:
atomically invalidating a specified rule in the RCDS based on the incremental update being a delete operation specifying the rule, wherein the active search process skips the specified rule invalidated.

7. The method of claim 1 , further comprising:
representing the RCDS as a tree of the set of rules, the tree being a binary data structure including one or more nodes and one or more leaves;
representing at least one of the one or more nodes as a parent node and linking the parent node to one or more children, the one or more children being a node or a leaf, wherein linking the parent node to the one or more children includes pointing the parent node to a sibling list, the sibling list including the one or more children;
linking nodes of the tree to one or more nodes and one or more leaves of the tree; and
linking leaves of the tree to one or more buckets, each bucket representing a subset of the set of rules, each bucket including one or more bucket entries corresponding to the subset of the set of rules, bucket entries being ordered by increasing or decreasing rule priority; and
storing the set of rules in a rule table, the rules within the rule table being ordered or unordered.

8. The method of claim 1 , wherein the RCDS is a performance tree,
the housekeeping tree includes field ranges of the rules and lists of the rules at each node in the performance tree, and wherein updating the performance tree atomically further includes utilizing the housekeeping tree such that a series of one or more modifications to the performance tree is made visible to the active search process based on one update to the performance tree being searched.

9. The method of claim 8 , further comprising:
creating a change list specifying the one or more modifications to the performance tree.

10. The method of claim 8 , wherein the incremental update is an add, delete, or modify operation, the method further comprising:
including a cover list of rules for each rule in the housekeeping tree;
creating the change list specifying one or more rules to add, delete, or modify based on the cover list; and
updating the cover list based on the change list determined.

11. The method of claim 8 , further comprising:
maintaining in each leaf a pointer to a bucket from among the one or more buckets and a bucket rule counter, the bucket rule counter tracking a number of rules included in the bucket, the bucket rule counter being incremented based on a rule being added to the bucket and the bucket rule counter being decremented based on a rule being deleted from the bucket.

12. The method of claim 8 , further comprising:
tracking at each node a total number of incremental updates;
determining at a given node a ratio of a number of rules represented by the given node to the total number of incremental updates tracked for the given node; and
adaptively adjusting the performance tree by recompiling a subtree based on the ratio being greater than a given threshold value.

13. The method of claim 7 , wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:
splitting a leaf of the tree into one or more new nodes and adding the rule to a bucket associated with one or more leaves of the one or more new nodes.

14. The method of claim 7 , wherein each bucket is a data structure and the one or more bucket entries is a rule, an index to a rule, a pointer to a rule, a pointer to a set of rules, or a pointer to another bucket.

15. The method of claim 7 , wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:
identifying a destination bucket from among the one or more buckets to include the new rule; and
appending the new rule to the end of the destination bucket based on determining a space fit and priority fit of the new rule in the destination bucket, wherein appending the new rule to the end of the destination bucket takes one update.

16. The method of claim 15 , wherein the space fit is based on a current number of rules in the destination bucket being less than a maximum number of rules for the destination bucket.

17. The method of claim 15 , wherein the priority fit is based on the priority associated with the new rule being consistent with a priority ordering of current rules in the destination bucket.

18. The method of claim 7 , wherein the incremental update includes atomically adding a new rule to the tree, the method further comprising:
identifying a destination bucket from among the one or more buckets to include the new rule;
creating a new bucket based on determining the priority associated with the new rule being inconsistent with a priority ordering of rules in the destination bucket, the active search process being unaffected by the new bucket created;
including the set of rules of the destination bucket in the new bucket;
including the new rule in the new bucket;
adjusting an o

Assignees

• Goyal Rajan
• Bullis Kenneth A
• Billa Satyanarayana Lakshmipathi
• Cavium Inc

Inventors

• Goyal Rajan
• Bullis Kenneth A
• Billa Satyanarayana Lakshmipathi

Classifications

• H04L45/7452

  Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) · CPC title

• H04L43/18 Primary

  Protocol analysers · CPC title

• G06F12/04

  Addressing variable-length words or parts of words · CPC title

• Y02B60/142

  Cross-Sectional Technologies · mapped topic

• G06F9/46

  Multiprogramming arrangements · CPC title