Representing and verifying network management policies using collective constraints

• US 6,393,473 B1
• Filed: 12/18/1998
• Issued: 05/21/2002
• Est. Priority Date: 12/18/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chu, Clare
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US09/215,393
• Time in Patent Office: 1,250 Days
• Field of Search: 709/223, 709/222, 709/224
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management

Abstract

A method and apparatus are provided for representing abstract network management policies and processing such policies to resolve conflicts. In one aspect, the invention provides a method of managing a network according to a plurality of network management policies, comprising the steps of storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take; storing one or more collective constraints, in which at least one of the constraints is that none of the variables may interfere with one another; applying a constraint satisfaction algorithm to the stored variables, values, restrictions, to create zero or more solutions and checking the solution set against the collective constraints; identifying a conflict in the policies when zero solutions are created and when one or more of the instance or collective constraints is violated; and resolving the conflict by modifying one or more of the variables, values or restrictions. Using a collective constraint representation, policy conflicts are rapidly identified and resolved. Resolution may be accomplished simply by adding a constraint that defines a change in a variable, value, or restriction or redefining the collective constraints.

Claims

1. A method of managing a network according to a plurality of network management policies, comprising the computer-implemented steps of:

storing each of the policies as a first constraint;

storing at least one collective constraint in association with the first constraint;

applying a constraint satisfaction algorithm to the first constraint to determine a solution or a set of solutions;

checking whether addition of a solution or the set of solutions taken together violates any of the collective constraints;

identifying a conflict in the policies when one or more of the first constraint or collective constraints is violated; and

resolving the conflict by modifying one or more of the variables, values or restrictions.

2. The method recited in claim 1, wherein storing each of the policies as a first constraint comprises the steps of storing each of the policies as a first constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

3. The method recited in claim 2, wherein storing at least one collective constraint comprises the steps of storing one or more collective constraints in which at least one of the collective constraints is that none of the variables may interfere with one another.

4. The method recited in claim 2, wherein applying a constraint satisfaction algorithm comprises the steps of:

applying a constraint satisfaction algorithm to the stored variables, values, restrictions, to the first constraints to create zero or more solutions; and

checking the collective constraints to test whether the new proposed solution does not conflict with any solutions already in the system.

5. The method recited in claim 1, wherein resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new constraint that defines the modified variable, value or restriction.

6. The method recited in claim 1, wherein storing each of the policies as a first constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

7. The method recited in claim 1, wherein storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.

8. A method of managing a network according to a plurality of network management policies, comprising the computer-implemented steps of:

storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take;

storing one or more collective constraints, in which at least one of the collective constraints is that none of the variables may interfere with one another;

applying a constraint satisfaction algorithm to the stored variables, values, restrictions to create zero or more solutions;

checking the collective constraints for any conflicts;

identifying a conflict in the policies when zero solutions are created and when one or more of the constraints or collective constraints is violated; and

resolving the conflict by modifying one or more of the variables, values or restrictions or collective constraints.

9. The method recited in claim 8, wherein resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new constraint that defines the modified variable, value or restriction.

10. The method recited in claim 8, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

11. The method recited in claim 8, wherein storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.

12. In a policy-based network management system that comprises at least one computer program for managing a network according to a plurality of network management policies, a method of resolving conflicts in the policies, the method comprising the computer-implemented steps of:

storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take, wherein the constraints are stored in a database associated with the system;

storing one or more collective constraints in the database, in which at least one of the collective constraints is that none of the variables may interfere with one another;

applying a constraint satisfaction algorithm to the stored variables, values, restrictions to create zero or more solutions;

checking the collective constraints for any conflicts;

identifying a conflict in the policies when zero solutions are created and when one or more of the constraints or collective constraints is violated; and

resolving the conflict by modifying one or more of the variables, values or restrictions.

13. The method recited in claim 12, wherein resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new constraint that defines the modified variable, value or restriction.

14. The method recited in claim 12, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

15. The method recited in claim 12, wherein storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.

16. A computer-readable medium carrying one or more sequences of instructions for managing a network according to a plurality of network management policies, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

storing each of the policies as a first constraint;

storing at least one collective constraint in association with the first constraint;

applying a constraint satisfaction algorithm to the first constraint;

checking the solutions against the collective constraint;

identifying a conflict in the policies when one or more of the first constraints or collective constraints is violated; and

resolving the conflict by modifying one or more of the variables, values or restrictions.

17. The computer-readable medium recited in claim 16, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

18. The computer-readable medium recited in claim 17, wherein storing at least one collective constraint comprises the steps of storing one or more collective constraints in which at least one of the collective constraints is that none of the variables may interfere with one another.

19. The computer-readable medium recited in claim 17, wherein applying a constraint satisfaction algorithm comprises the steps of applying a constraint satisfaction

algorithm to the stored variables, values, restrictions, and to the collective constraint to create zero or more solutions.

20. The computer-readable medium recited in claim 16, wherein resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new constraint that defines the modified variable, value or restriction.

21. The computer-readable medium recited in claim 16, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

22. The computer-readable medium recited in claim 16, wherein storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.

23. A policy-based networking system, comprising:

a network that comprises at least one network device under management;

a first computer program that manages the network and the network device according to a plurality of network management policies; and

a second computer program that resolves conflicts in the policies and carrying one or more sequences of instructions for managing a network according to a plurality of network management policies, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the computer-implemented steps of;

storing each of the policies as a first constraint;

storing at least one collective constraint in association with the first constraint;

applying a constraint satisfaction algorithm to the first constraint and checking against the collective constraint;

identifying a conflict in the policies when one or more of the first constraints or collective constraints is violated; and

resolving the conflict by modifying one or more of the variables, values or restrictions.

24. The system recited in claim 23, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as a constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

25. The system recited in claim 24, wherein storing at least one collective constraint comprises the steps of storing one or more collective constraints in which at least one of the collective constraints is that none of the variables may interfere with one another.

26. The system recited in claim 24, wherein applying a constraint satisfaction algorithm comprises the steps of:

applying a constraint satisfaction algorithm to the stored variables, values,

restrictions, to create zero or more solutions;

checking the solutions against the collective constraint to ensure that all the solutions

are valid.

27. The system recited in claim 23, wherein resolving the conflict by modifying one or more of the variables, values or restrictions further comprises the step of adding a new first constraint that defines the modified variable, value or restriction.

28. The system recited in claim 23, wherein storing each of the policies as a constraint comprises the steps of storing each of the policies as an instance constraint that comprises one or more variables, a set of possible values, and a set of restrictions on the values that the variables can simultaneously take.

29. The system recited in claim 23, wherein storing one or more collective constraints comprises the steps of storing one or more group constraints, in which at least one of the group constraints is that none of the variables may interfere with one another.