Identification of conflict rules in a network intent formal equivalence failure

• US 10,439,875 B2
• Filed: 08/31/2017
• Issued: 10/08/2019
• Est. Priority Date: 05/31/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mohanram, Kartik
• Primary Examiner(s): Won, Michael
• Application Number:
  US15/693,220
• Publication Number:
  US 20180351804A1
• Time in Patent Office: 768 Days
• CPC Class Codes: H04L 41/0866 Checking the configuration
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 67/00 Network arrangements or protocols for supporting network services or applications user-to-user messaging H04L51/00; network arrangements, protocols or services for supporting real-time applications in data packet communications networks H04L65/00

Abstract

Systems, methods, and computer-readable media for identifying conflict rules between models of network intents. A first and second model of network intents are obtained, the models describing the operation and communication between one or more network devices in a network. A logical exclusive disjunction between the first and second models is calculated over the space of possible packet conditions and network actions defined by models, without enumerating all possible packet conditions and network actions. It is detected whether the models are in conflict with respect to at least a first network device. If the models are in conflict, it is determined whether a given rule of a plurality of rules associated with the first model is a conflict rule. The determining comprises calculating the intersection between the given rule and the logical exclusive disjunction, wherein the given rule is a conflict rule if the calculated intersection is non-zero.

Claims

1. A method comprising:

obtaining, via one or more processors and from one or more network controllers, at least a first model of network intents and a second model of network intents, the first model and the second model describing an operation and communication between one or more network devices in a network based on one or more network policies configured at the one or more network controllers;

calculating, via the one or more processors, a logical exclusive disjunction between the first model of network intents and the second model of network intents, wherein the logical exclusive disjunction is calculated over a space of possible packet conditions and network actions defined by the first and second models, the calculating performed without enumerating all possible packet conditions and network actions;

based on the logical exclusive disjunction, detecting, via the one or more processors, whether the first model and second model are in conflict with respect to at least a first network device of the one or more network devices; and

in response to detecting that the first and second model are in conflict, determining, for one or more given rules of a plurality of rules associated with the first model of network intents, whether the given rule is a conflict rule, wherein the determining comprises calculating the intersection between the given rule and the logical exclusive disjunction such that the given rule is a conflict rule if the calculated intersection is non-zero.

2. The method of claim 1, further comprising determining for one or more given rules of a plurality of rules associated with the second model of network intents whether the given rule is a conflict rule, wherein the determining comprises calculating the intersection between the given rule and the logical exclusive disjunction, such that the given rule is a conflict rule if the calculated intersection is non-zero.

3. The method of claim 1, wherein the second model is a reference model and the first model is a model under test.

4. The method of claim 1, further comprising performing back annotation for one or more of the conflict rules in order to identify a contract or fabric-wide user intent from which a given one of the one or more conflict rules was derived.

5. The method of claim 1, wherein one or more of the first and second models is a Reduced Ordered Binary Decision Diagram (ROBDD).

6. The method of claim 1, wherein the logical exclusive disjunction is a Reduced Ordered Binary Decision Diagram (ROBDD).

7. The method of claim 5, wherein one or more of the first and second models is specific to network intents corresponding to a Permit, Permit_Log, Deny, or Deny_Log action.

8. A system comprising:

one or more processors; and

at least one computer-readable storage medium having stored therein instructions which, when executed by the one or more processors, cause the system to;

obtain, from one or more network controllers, at least a first model of network intents and a second model of network intents, the first model and the second model describing an operation and communication between one or more network devices in a network based on one or more network policies configured at the one or more network controllers;

calculate a logical exclusive disjunction between the first model of network intents and the second model of network intents, wherein the logical exclusive disjunction is calculated over a space of possible packet conditions and network actions defined by the first and second models, the calculating performed without enumerating all possible packet conditions and network actions;

based on the logical exclusive disjunction, detect whether the first model and second model are in conflict with respect to at least a first network device of the one or more network devices; and

in response to detecting that the first and second model are in conflict, determine for one or more given rules of a plurality of rules associated with the first model of network intents whether the given rule is a conflict rule, wherein the determining comprises calculating the intersection between the given rule and the logical exclusive disjunction such that the given rule is a conflict rule if the calculated intersection is non-zero.

9. The system of claim 8, wherein the instructions further cause the system to determine for one or more given rules of a plurality of rules associated with the second model of network intents whether the given rule is a conflict rule, wherein the determining comprises calculating the intersection between the given rule and the logical exclusive disjunction, such that the given rule is a conflict rule if the calculated intersection is non-zero.

10. The system of claim 8, wherein the second model is a reference model and the first model is a model under test.

11. The system of claim 8, wherein the instructions further cause the system to perform back annotation for one or more of the conflict rules in order to identify a contract or fabric-wide user intent from which a given one of the one or more conflict rules was derived.

12. The system of claim 8, wherein one or more of the first model, the second model, and the logical exclusive disjunction is a Reduced Ordered Binary Decision Diagram (ROBDD).

13. The system of claim 8, wherein one or more of the first and second models is specific to network intents corresponding to a Permit, Permit_Log, Deny, or Deny_Log action.

14. A non-transitory computer-readable storage medium comprising:

instructions stored therein which, when executed by one or more processors, cause the one or more processors to;

obtain, from one or more network controllers, at least a first model of network intents and a second model of network intents, the first model and the second model describing an operation and communication between one or more network devices in a network based on one or more network policies configured at the one or more network controllers;

calculate a logical exclusive disjunction between the first model of network intents and the second model of network intents, wherein the logical exclusive disjunction is calculated over a space of possible packet conditions and network actions defined by the first and second models, the calculating performed without enumerating all possible packet conditions and network actions;

based on the logical exclusive disjunction, detect whether the first model and second model are in conflict with respect to at least a first network device of the one or more network devices; and

in response to detecting that the first and second model are in conflict, determine for one or more given rules of a plurality of rules associated with the first model of network intents whether the given rule is a conflict rule, by calculating an intersection between the given rule and the logical exclusive disjunction such that the given rule is a conflict rule if the calculated intersection is non-zero.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further cause the one or more processors to determine for one or more given rules of a plurality of rules associated with the second model of network intents whether the given rule is a conflict rule, by calculating an intersection between the given rule and the logical exclusive disjunction, such that the given rule is a conflict rule if the calculated intersection is non-zero.

16. The non-transitory computer-readable storage medium of claim 14, wherein the second model is a reference model and the first model is a model under test.

17. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further cause the system to perform back annotation for one or more of the conflict rules in order to identify a contract or fabric-wide user intent from which a given one of the one or more conflict rules was derived.

18. The non-transitory computer-readable storage medium of claim 14, wherein one or more of the first model and the second model is a Reduced Ordered Binary Decision Diagram (ROBDD).

19. The non-transitory computer-readable storage medium of claim 14, wherein the logical exclusive disjunction is a Reduced Ordered Binary Decision Diagram (ROBDD).

20. The non-transitory computer-readable storage medium of claim 14, wherein one or more of the first and second models is specific to network intents corresponding to a Permit, Permit_Log, Deny, or Deny_Log action.