Fast update filter

• US 8,352,391 B1
• Filed: 08/20/2008
• Issued: 01/08/2013
• Est. Priority Date: 08/20/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kapadia, Shamit
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): PELLETT, DANIEL T
• Application Number:
  US12/194,968
• Time in Patent Office: 1,602 Days
• Field of Search: 706/14
• US Class Current: 706/14
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

A method may include defining a filter for a network device, the filter including a rule and a particular number of prioritized fields, where at least one of the prioritized fields is formatted to accept input as a range of values. The method may also include receiving a rule modification for the filter, the rule modification including at least one input as a range of values, and performing a check for conflicts of the rule modification with the rule in the filter. The method may further include expanding the input range of values to form multiple rules equivalent to the rule modification with the input range of values, establishing backtracking links to integrate the multiple rules with the existing rule, and adding the multiple rules to the filter.

Claims

1. A method performed by a network device, the method comprising:

receiving a rule modification for a filter, the filter including an existing rule and a particular number of prioritized fields;

determining that at least one of the prioritized fields does not include a value;

normalizing the rule modification to include a dummy value for each of the at least one of the prioritized fields that does not include a value;

determining that at least one of the particular number of prioritized fields includes a range of values;

resolving the range of values by converting the range of values to a plurality of different values to create a plurality of rules associated with the received rule modification,

each of the plurality of rules including the particular number of prioritized fields, the particular number of prioritized fields each including a same value except for the at least one of the particular number of prioritized fields that includes the range of values, each of the at least one of the particular number of prioritized fields that includes the range of values including a different value, and each of the different values being associated with a value of the range of values;

performing a check for conflicts between the plurality of rules and the existing rule in the filter;

establishing one or more backtracking links to integrate the plurality of rules with the existing rule; and

adding the plurality of rules to the filter.

2. The method of claim 1, where the filter includes a structure of multiple radix trees.

3. The method of claim 2, where establishing the one or more backtracking links comprises:

setting a default route in a first radix tree to point to a next most specific radix tree that is parallel with the first radix tree.

4. The method of claim 2, where establishing the one or more backtracking links comprises:

setting a default route in a first radix tree, of the multiple radix trees, to point to a default action.

5. The method of claim 1, further comprising:

assigning a priority level to the rule modification.

6. The method of claim 1, where the rule modification includes one of a rule addition or a rule deletion.

7. The method of claim 1, where the rule modification includes an update to the existing rule.

8. The method of claim 1,

where each of the plurality of different values are prefix matches corresponding to the plurality of different values.

9. A method, comprising:

defining a filter for a network device, the filter including a rule and a particular number of prioritized fields, at least one of the prioritized fields being formatted to accept an input that includes a range of values;

receiving a rule modification for the filter, the rule modification including at least one input that includes a range of values;

resolving the range of values by converting the range of values to a plurality of different values to create a plurality of rules associated with the received rule modification,

each of the plurality of rules including the particular number of prioritized fields, the particular number of prioritized fields each including a same value except for the at least one of the particular number of prioritized fields that includes the range of values, each of the at least one of the particular number of prioritized fields that includes the range of values including a different value, and each of the different values being associated with a value of the range of values;

performing a check for conflicts of the rule modification with the rule in the filter;

establishing backtracking links to integrate the plurality of rules with the existing rule; and

adding the plurality of rules to the filter.

10. The method of claim 9, further comprising:

normalizing the rule modification to include a value for each of the prioritized fields.

11. The method of claim 9, further comprising:

resolving a conflict of the rule modification with the rule in the filter based on a priority value assigned to the rule and a priority value assigned to the rule modification.

12. The method of claim 9, further comprising:

resolving a conflict of the rule modification with the rule in the filter based on the priority of a specific value over a range value.

13. The method of claim 9, further comprising:

resolving a conflict of the rule modification with the rule in the filter by modifying the input range of one of the rule modification or the rule in the filter to eliminate overlap between the rule modification and the rule in the filter.

14. The method of claim 9, where the filter includes a structure of multiple radix trees.

15. A network device, comprising:

a memory to store a filter, the filter including a rule and a particular number of prioritized fields; and

a processor to;

receive a rule modification to the filter,

determine that at least one of the particular number of prioritized fields is empty,

alter the rule modification to include a dummy value, based on a field size of the at least one of the particular number of prioritized fields that is empty, in the at least one of the particular number of prioritized fields that is empty to ensure a match occurs,

determine that at least one of the particular number of prioritized fields includes a range of values;

resolve the range of values by converting the range of values to a plurality of different values to create a plurality of rules associated with the received rule modification,

each of the plurality of rules including the particular number of prioritized fields, the particular number of prioritized fields each including a same value except for the at least one of the particular number of prioritized fields that includes the range of values, each of the at least one of the particular number of prioritized fields that includes the range of values including a different value, and each of the different values being associated with a value of the range of values;

establish backtracking links to integrate the plurality of rules with the existing rule, and

add the plurality of rules to the filter.

16. The network device of claim 15, where the network device comprises at least one of:

a router;

a switch;

a firewall device;

or

a server device.

17. The network device of claim 15, where the processor is further to:

receive a packet,

filter the packet through the filter, and

forward the packet in accordance with an action identified in the filter.

18. The network device of claim 15, where the processor is further to:

perform a check for conflicts between the rule modification and the existing rule in the filter.

19. A non-transitory computer-readable medium comprising instructions, the instructions comprising:

one or more instructions, executable by a processor, to define a filter for a network device, the filter including a rule and a particular number of prioritized fields;

one or more instructions, executable by the processor, to receive a rule modification for the filter;

one or more instructions, executable by the processor, to determine that at least one of the prioritized fields does not include a value;

one or more instructions, executable by the processor, to normalize the rule modification to include a dummy value for each of the at least one of the prioritized fields in the filter that does not include a value;

one or more instructions, executable by the processor, to determine that at least one of the particular number of prioritized fields includes a range of values;

one or more instructions, executable by the processor, to resolve the range of values by converting the range of values to a plurality of different values to create a plurality of rules associated with the received rule modification,

each of the plurality of rules including the particular number of prioritized fields, the particular number of prioritized fields each including a same value except for the at least one of the particular number of prioritized fields that includes the range of values, each of the at least one of the particular number of prioritized fields that includes the range of values including a different value, and each of the different values being associated with a value of the range of values;

one or more instructions, executable by the processor, to insert backtracking links into the filter; and

one or more instructions, executable by the processor, to add the plurality of rules to the filter.

20. The computer-readable medium of claim 19, where the instructions further comprise:

one or more instructions to perform a check for conflicts between the rule modification and the existing rule in the filter.

21. A non-transitory computer-readable medium comprising instructions, the instructions comprising:

one or more instructions, executable by a processor, to store a filter for a network device, the filter including a rule and a particular number of prioritized fields;

one or more instructions, executable by the processor, to receive a rule modification for the filter, the rule modification including a field with a range of values;

one or more instructions, executable by the processor, to resolve the range of values by converting the range of values to a plurality of different values to create a plurality of rules associated with the received rule modification,

each of the plurality of rules including the particular number of prioritized fields, the particular number of prioritized fields each including a same value except for the at least one of the particular number of prioritized fields that includes the range of values, each of the at least one of the particular number of prioritized fields that includes the range of values including a different value, and each of the different values being associated with a value of the range of values;

one or more instructions, executable by the processor, to perform a check for conflicts of the plurality of rules with the rule in the filter; and

one or more instructions, executable by the processor, to backtrack one or more links to integrate the plurality of rules with the existing rule.

22. The computer-readable medium of claim 21, where the instructions further comprise:

one or more instructions to resolve a conflict between the multiple rules and the rule in the filter.