Semantic analysis to detect shadowing of rules in a model of network intents

• US 10,505,816 B2
• Filed: 08/31/2017
• Issued: 12/10/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, Iyer, Sundar, Kompella, Ramana Rao, Yadav, Navneet
• Primary Examiner(s): Henderson, Esther B.
• Assistant Examiner(s): Naoreen, Nazia
• Application Number:
  US15/693,242
• Publication Number:
  US 20180351819A1
• Time in Patent Office: 831 Days
• CPC Class Codes: H04L 41/0636 based on a decision tree analysis
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• 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 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV

Abstract

Systems, methods, and computer-readable media for performing semantic analysis to identify shadowing events. One or more models of network intents, based at least in part on a priority-ordered listing of rules representing network intents, is received. Each rule comprises a Boolean function of one or more packet characteristics and network fabric conditions, and a corresponding network action. For each given rule of the priority-ordered listing of rules, partial and complete shadowing events are detected based on semantic analysis. The semantic analysis comprises calculating an inverse set that comprises the inverse of the set comprising all rules with a higher or equal priority to the given rule, and then calculating a shadowing parameter that comprises the intersection between the inverse set and the given rule. If the shadowing parameter is equal to zero, a complete shadowing event is detected. If the shadowing parameter is not equal to zero and is not equal to the given rule, a partial shadowing event is detected.

Claims

1. A method comprising:

obtaining one or more models of network intents, each model based at least in part on a priority-ordered listing of rules representing network intents, wherein each rule comprises a Boolean function of one or more packet characteristics and network fabric conditions, and a corresponding network action; and

for each given rule of the priority-ordered listing of rules, detecting partial and complete shadowing events, the detecting based at least in part on a semantic analysis comprising;

calculating an inverse set, the inverse set comprising the inverse of the set comprising all rules with a higher or equal priority to the given rule; and

calculating a shadowing parameter, the shadowing parameter comprising the intersection between the inverse set and the given rule, wherein;

a complete shadowing event is detected if the shadowing parameter is equal to zero; and

a partial shadowing event is detected if the shadowing parameter is not equal to zero and the shadowing parameter is not equal to the given rule.

2. The method of claim 1, further comprising calculating one or more suggested fixes for the detected partial and complete shadowing events.

3. The method of claim 1, further comprising determining for each detected partial and complete shadowing events whether the event is a conflict event or a non-conflict event.

4. The method of claim 3, wherein the ROBDD is generated, at least in part, based on a flat-listing of rules normalized by a shim layer.

5. The method of claim 1, wherein the network intent model comprises a flat-listing of rules normalized by a shim layer.

6. The method of claim 1, wherein the network intent model comprises a Reduced Ordered Binary Decision Diagram (ROBDD) that encodes a realized impact of each rule of the priority-ordered listing of rules representing network intents.

7. The method of claim 1, wherein the one or more models of network intent describe the operation and communication between one or more network devices in a network or a software-defined network (SDN).

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;

receive one or more models of network intents, each model based at least in part on a priority-ordered listing of rules representing network intents, wherein each rule comprises a Boolean function of one or more packet characteristics and network fabric conditions, and a corresponding network action; and

for each given rule of the priority-ordered listing of rules, detect partial and complete shadowing events, the detecting based at least in part on a semantic analysis causing the system to;

calculate an inverse set, the inverse set comprising the inverse of the set comprising all rules with a higher or equal priority to the given rule; and

calculate an shadowing parameter, the shadowing parameter comprising the intersection between the inverse set and the given rule, wherein;

a complete shadowing event is detected if the shadowing parameter is equal to zero; and

a partial shadowing event is detected if the shadowing parameter is not equal to zero and the shadowing parameter is not equal to the given rule.

9. The system of claim 8, wherein the instructions further cause the system to calculate one or more suggested fixes for the detected partial and complete shadowing events.

10. The system of claim 8, wherein the instructions further cause the system to determine for each detected partial and complete shadowing events whether the event is a conflict event or a non-conflict event.

11. The system of claim 8, wherein the network intent model comprises a flat-listing of rules normalized by a shim layer.

12. The system of claim 8, wherein the network intent model comprises a Reduced Ordered Binary Decision Diagram (ROBDD) that encodes a realized impact of each rule of the priority-ordered listing of rules representing network intents.

13. The system of claim 12, wherein the ROBDD is generated, at least in part, based on a flat-listing of rules normalized by a shim layer.

14. The system of claim 8, wherein the one or more models of network intent describe the operation and communication between one or more network devices in a network or a software-defined network (SDN).

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

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

receive one or more models of network intents, each model based at least in part on a priority-ordered listing of rules representing network intents, wherein each rule comprises a Boolean function of one or more packet characteristics and network fabric conditions, and a corresponding network action; and

for each given rule of the priority-ordered listing of rules, detect partial and complete shadowing events, the detecting based at least in part on a semantic analysis causing the system to;

calculate an inverse set, the inverse set comprising the inverse of the set comprising all rules with a higher or equal priority to the given rule; and

calculate an shadowing parameter, the shadowing parameter comprising the intersection between the inverse set and the given rule, wherein;

a complete shadowing event is detected if the shadowing parameter is equal to zero; and

a partial shadowing event is detected if the shadowing parameter is not equal to zero and the shadowing parameter is not equal to the given rule.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the system to calculate one or more suggested fixes for the detected partial and complete shadowing events.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further cause the system to determine for each detected partial and complete shadowing events whether the event is a conflict event or a non-conflict event.

18. The non-transitory computer-readable storage medium of claim 15, wherein the network intent model comprises a flat-listing of rules normalized by a shim layer.

19. The non-transitory computer-readable storage medium of claim 15, wherein the network intent model comprises a Reduced Ordered Binary Decision Diagram (ROBDD) that encodes a realized impact of each rule of the priority-ordered listing of rules representing network intents.

20. A method comprising:

obtaining a listing of shadowed rules, where the shadowed rules are associated with a priority-ordered listing of rules representing network intents of a network intent model, wherein each rule comprises a Boolean function of one or more packet characteristics or network fabric conditions, and a corresponding network action; and

for each given rule of the listing of shadowed rules, determining whether a given shadowed rule is partially shadowed or completely shadowed, the determining based at least in part on a semantic analysis comprising calculating the intersection between the given shadowed rule and each individual higher priority rule of the priority-ordered listing of rules, wherein;

the given shadowed rule is completely shadowed by the higher priority rule if the intersection is equal to the given shadowed rule, such that the higher priority rule is flagged as a complete shadower and the analysis exits; and

the given shadowed rule is partially shadowed by the higher priority rule if the intersection is not equal to zero, such that the higher priority rule is flagged as a partial shadower and the analysis proceeds to the next of the higher priority rules;

for each given rule of the listing of shadowed rules, determining whether a given shadowed rule and its complete shadower or partial shadowers form a conflict pair, such that the shadowed rule stipulates a first action for a given set of conditions and the complete shadower or partial shadowers stipulate a second action for a given set of conditions, where the second action is different from the first action.