Computing diagnostic explanations of network faults from monitoring data

Abstract

A system and method for network fault diagnosis in a network having network elements is presented. The method comprises creating a network causality model, generating Boolean expressions from the network causality model, converting the Boolean expressions into SAT sets, receiving network monitoring results, correlating these monitoring results with the SAT sets, and enumerating all possible diagnostic explanations of potential faults, properly annotated. Creating a network causality model can comprise creating, for each network element, an element-specific causality model, stitching together all network elements using the element-specific causality models and a network topology, retrieving monitoring state and propagation information, and generating the network causality model using the stitched together network elements and the monitoring state and propagation information. Stitching together network elements can comprise adding causes and implies dependency between appropriate network elements and/or adding and connecting reachable and not-reachable states. The network causality model can comprise network element states.

1 . A method for network fault diagnosis in a network having a plurality of network elements, comprising steps of:
 creating a network causality model;   generating Boolean expressions from said network causality model;   converting said Boolean expressions into SAT sets;   receiving network monitoring results;   correlating said network monitoring results with said SAT sets; and   enumerating all possible diagnostic explanations of potential faults and displaying a ranked fault list having said explanations with annotations on a computer.   
     
     
         2 .- 5 . (canceled) 
     
     
         6 . The method according to  claim 1 , wherein the network causality model comprises states for all of the network elements. 
     
     
         7 . A non-transitory computer readable medium having computer readable program for operating on a computer for network fault diagnosis in a network having a plurality of network elements, said program comprising instructions that cause the computer to perform steps of:
 creating a network causality model;   generating Boolean expressions from said network causality model;   converting said Boolean expressions into SAT sets;   receiving network monitoring results;   correlating said network monitoring results with said SAT sets; and   enumerating all possible diagnostic explanations of potential faults and displaying a ranked fault list having said explanations with annotations on a computer.   
     
     
         8 .- 11 . (canceled) 
     
     
         12 . The non-transitory computer readable medium according to  claim 7 , wherein the network causality model comprises states for all of the network elements. 
     
     
         13 . A system for network fault diagnosis in a network having a plurality of network elements, comprising:
 a network causality model of a network;   SAT sets of truth values of every state in the network causality model; and   network results collector receiving and collecting the states of particular devices in the network until it is determined that it is likely to have all results relating to a particular network fault event and providing network monitoring results, wherein the network causality model generates the SAT sets using Boolean expressions, the network monitoring results and the SAT sets are correlated to enumerate all possible diagnostic explanations of potential faults, and a ranked fault list having said explanations with annotations are displayed on a display device.   
     
     
         14 .- 17 . (canceled) 
     
     
         18 . The system according to  claim 13 , wherein the network causality model comprises states for all of the network elements.