Fast update filter

• US 9,363,234 B2
• Filed: 12/21/2012
• Issued: 06/07/2016
• 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): Masur, Paul H
• Application Number:
  US13/724,720
• Publication Number:
  US 20130117837A1
• Time in Patent Office: 1,264 Days
• US Class Current: 1/1
• 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 comprising:

receiving, by a device, a rule modification for a filter,

the filter including an existing rule and a plurality of fields;

determining, by the device, that at least one of the plurality of fields includes a range of values;

converting, by the device, 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 plurality of fields,

the plurality of fields each including a same value except for the at least one of the plurality of fields that includes the range of values,

each of the at least one of the plurality of fields that includes the range of values including a respective, different value, and

each of the different values being associated with a value in the range of values;

establishing, by the device, one or more backtracking links to search for a best match in the plurality of rules; and

adding, by the device and with out recompiling entirety of the filter, the plurality of rules to the filter.

2. The method of claim 1, further comprising:

determining that a conflict exists between a rule, of the plurality of rules, and the existing rule in the filter; and

resolving the conflict.

3. The method of claim 2, where, when determining that the conflict exists, the method includes:

determining that a packet could be processed using the rule and using the existing rule.

4. The method of claim 2, where, when resolving the conflict, the method includes:

determining a first priority assigned to the rule;

determining a second priority assigned to the existing rule;

determining that the first priority and the second priority are the same; and

rejecting the rule modification.

5. The method of claim 1,

where the one or more backtracking links integrate the plurality of rules with the existing rule,

where the filter includes a plurality of trees, and

where, when establishing the one or more backtracking links, the method includes:

setting a route in a first tree, of the plurality of trees, to point to one of;

a next tree, of the plurality of trees, or

a default action.

6. The method of claim 1, further comprising:

determining that the rule modification does not include a value for at least one of the plurality of fields; and

normalizing the rule modification to include a default value for the at least one of the plurality of fields.

7. The method of claim 6, where the default value is a dummy value.

8. A device comprising:

a memory; and

a processor, connected to the memory, to;

receive a rule modification for a filter,

the filter including an existing rule and a plurality of fields;

determine that at least one of the plurality of fields includes a range of values;

convert 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 plurality of fields,

the plurality of fields each including a same value except for the at least one of the plurality of fields that includes the range of values,

each of the at least one of the plurality of fields that includes the range of values including a respective, different value, and

each of the different values being associated with a value in the range of values;

establish one or more backtracking links to search for a best match in the plurality of rules; and

add the plurality of rules to the filter without recompiling entirety of the filter.

9. The device of claim 8, where the processor is further to:

determine that a conflict exists between a rule, of the plurality of rules, and the existing rule in the filter; and

resolve the conflict.

10. The device of claim 9, where, when determining that the conflict exists, the processor is to:

determine that a packet could be processed using the rule and using the existing rule.

11. The device of claim 9, where, when resolving the conflict, the processor is to:

determine a first priority assigned to the rule;

determine a second priority assigned to the existing rule;

determine that the first priority and the second priority are the same; and

reject the rule modification.

12. The device of claim 8,

where the one or more backtracking links integrate the plurality of rules with the existing rule,

where the filter includes a plurality of trees, and

where, when establishing the one or more backtracking links, the processor is to:

set a route in a first tree, of the plurality of trees, to point to one of;

a next tree, of the plurality of trees, or

a default action.

13. The device of claim 8, where the processor is further to:

determine that the rule modification does not include a value for at least one of the plurality of fields; and

normalize the rule modification to include a default value for the at least one of the plurality of fields.

14. The device of claim 13, where the default value is a dummy value.

15. A non-transitory computer-readable medium containing instruction, the instructions comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to;

receive a rule modification for a filter,

the filter including an existing rule and a plurality of fields;

determine that at least one of the plurality of fields includes a range of values;

convert 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 plurality of fields,

the plurality of fields each including a same value except for the at least one of the plurality of fields that includes the range of values,

each of the at least one of the plurality of fields that includes the range of values including a respective, different value, and

each of the different values being associated with a value in the range of values;

establish one or more backtracking links to search for a best match in the plurality of rules; and

add the plurality of rules to the filter without recompiling entirety of the filter.

16. The medium of claim 15, where the instructions further comprise:

one or more instructions to determine that a conflict exists between a rule, of the plurality of rules, and the existing rule in the filter; and

one or more instructions to resolve the conflict.

17. The medium of claim 16, where one or more instructions to determine that the conflict exists include:

one or more instructions to determine that a packet could be processed using the rule and using the existing rule.

18. The medium of claim 16, where one or more instructions to resolve the conflict include:

one or more instructions to determine a first priority assigned to the rule;

one or more instructions to determine a second priority assigned to the existing rule;

one or more instructions to determine that the first priority and the second priority are the same; and

one or more instructions to reject the rule modification.

19. The medium of claim 15,

where the one or more backtracking links integrate the plurality of rules with the existing rule,

where the filter includes a plurality of trees, and

where the one or more instructions to establish the one or more backtracking links include:

one or more instructions to set a route in a first tree, of the plurality of trees, to point to one of;

a next tree, of the plurality of trees, or

a default action.

20. The medium of claim 15, where the instructions further comprise:

one or more instructions to determine that the rule modification does not include a value for at least one of the plurality of fields; and

one or more instructions to normalize the rule modification to include a dummy value for the at least one of the plurality of fields.