Method for automated distributed diagnostics for networks

Abstract

A method for distributed computations for fault-diagnosis in a system whose fault propagation model has deterministic couplings between faults and symptoms includes creating a ‘relation graph’ in which the nodes correspond to the potential faults, with two nodes connected by a ‘relational link’ if their corresponding faults have an observed symptom in common. Each relational link is assigned a weight equal to the sum, taken over the symptoms represented by the relational link, of the reciprocal of the number of distinct fault-pairs that produce each such symptom. The relation graph is then partitioned into several domains, while minimizing the number of cross-domain relational links, which correspond to cross-domain symptoms. In each domain, all the optimal local solutions to the domain's sub-problem are first determined, and then a combination is selected of the local solutions, one from each domain, that explains the maximum number of cross-domain symptoms, where the optimal solution is supplemented, if necessary, with additional faults to explain any remaining unexplained cross-domain symptoms, determining also a bound on the deviation from optimality of the global solution.

1. A method of distributed computations for diagnosing faults in a system for which a fault-to-symptom correlation map is specified by a fault propagation model including a specification, for each potential fault, of a set of symptoms that will be observed if a fault occurs, comprising the steps of:
 translating the fault-to-symptom correlation map into an abstract relation graph in which nodes represent potential faults and a link between two nodes indicates that the corresponding faults produce one or more symptoms in common; 
 partitioning the relation graph into a set of computational domains, thus obtaining a partition of the nodes among the domains, each domain including a set of nodes assigned to a respective domain and a set of local symptoms that either have both their end-nodes in the same domain or cross-domain symptoms that have only one end-node in a domain; 
 determining all optimal solutions to the local diagnosis problem in each domain by finding the most probable set of faults in each domain that can explain all the local symptoms of each domain, disregarding the presence of cross-domain symptoms; 
 determining a combination of the optimal local solutions of the domains, composed of one solution from each domain, that maximizes the number of cross-domain symptoms explained by the faults chosen in the combination; 
 if all cross-domain symptoms are explained by the combination of optimal local solutions, the union of the faults in all the local solutions in the combination represents an optimal global solution; 
 if there remain unexplained cross-domain symptoms, determining an optimal solution to the residual diagnosis problem by finding additional faults to explain the remaining cross-domain symptoms, and completing the global solution by adding the additional faults to the faults in all the selected combinations of optimal local solutions, and 
 computing a bound on the possible deviation of the selected solution from optimality given by the difference between the number of faults in the solution and the total number of faults in all the optimal local solutions determined for each individual domain; 
 wherein translating the fault-to-symptom correlation map into an abstract relation graph includes the step of assigning to each relational link a weight equal to the sum, taken over the symptoms represented by the relational link, of the reciprocal of the number of distinct fault-pairs that produce each such symptom. 
 
     
     
       2. A method of distributed computations for diagnosing faults in a system for which a fault-to-symptom correlation map is specified by a fault propagation model including a specification, for each potential fault, of a set of symptoms that will be observed if a fault occurs, comprising the steps of:
 translating the fault-to-symptom correlation map into an abstract relation graph in which nodes represent potential faults and a link between two nodes indicates that the corresponding faults produce one or more symptoms in common; 
 partitioning the relation graph into a set of computational domains, thus obtaining a partition of the nodes among the domains, each domain including a set of nodes assigned to a respective domain and a set of local symptoms that either have both their end-nodes in the same domain or cross-domain symptoms that have only one end-node in a domain; 
 determining all optimal solutions to the local diagnosis problem in each domain by finding the most probable set of faults in each domain that can explain all the local symptoms of each domain, disregarding the presence of cross-domain symptoms; 
 determining a combination of the optimal local solutions of the domains, composed of one solution from each domain, that maximizes the number of cross-domain symptoms explained by the faults chosen in the combination; 
 if all cross-domain symptoms are explained by the combination of optimal local solutions, the union of the faults in all the local solutions in the combination represents an optimal global solution; 
 if there remain unexplained cross-domain symptoms, determining an optimal solution to the residual diagnosis problem by finding additional faults to explain the remaining cross-domain symptoms, and completing the global solution by adding the additional faults to the faults in all the selected combinations of optimal local solutions, and 
 computing a bound on the possible deviation of the selected solution from optimality given by the difference between the number of faults in the solution and the total number of faults in all the optimal local solutions determined for each individual domain; 
 wherein the step of finding an optimal solution is finding a set of faults (k 1 , k 2 , . . . , k m ) that accounts for all the symptoms to be explained and has the smallest metric H (k 1 , k 2 , . . . , k m ), where 
 
       
         
           
             
               
                 
                   H 
                   ⁡ 
                   
                     ( 
                     
                       
                         k 
                         1 
                       
                       , 
                       
                         k 
                         2 
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         k 
                         m 
                       
                     
                     ) 
                   
                 
                 ⁢ 
                 
                   = 
                   Δ 
                 
                 ⁢ 
                 
                   
                     ∏ 
                     
                       j 
                       = 
                       1 
                     
                     m 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       p 
                       
                         k 
                         j 
                       
                     
                     
                       1 
                       - 
                       
                         p 
                         
                           k 
                           j 
                         
                       
                     
                   
                 
               
               , 
             
           
         
         
           and where p k     j   =the prior probability of occurrence of fault k j , j=1,2, . . . , m. 
         
       
     
     
       3. A non-transitory computer readable medium having computer readable program for operating on a computer for diagnosing faults in a system for which a fault-to-symptoms correlation map is specified by a fault propagation model including a specification, for each potential fault, of a set of symptoms that will be observed if a fault occurs, said program comprising instructions that cause the computer to perform the steps of:
 translating the fault-to-symptom correlation map into an abstract relation graph in which nodes represent potential faults and a link between two nodes indicates that the corresponding faults produce one or more symptoms in common; 
 partitioning the relation graph into a set of computational domains, thus obtaining a partition of the nodes among the domains, each domain including a set of nodes assigned to a respective domain and a set of local symptoms that either have both their end-nodes in the same domain or cross-domain symptoms that have only one end-node in a domain; 
 determining all optimal solutions to the local diagnosis problem in each domain by finding the most probable set of faults in each domain that can explain all the local symptoms of each domain, disregarding the presence of cross-domain symptoms; 
 determining a combination of the optimal local solutions of the domains, composed of one solution from each domain, that maximizes the number of cross-domain symptoms explained by the faults chosen in the combination; 
 if all cross-domain symptoms are explained by the combination of optimal local solutions, the union of the faults in all the local solutions in the combination represents an optimal global solution; 
 if there remain unexplained cross-domain symptoms, determining an optimal solution to the residual diagnosis problem by finding additional faults to explain the remaining cross-domain symptoms, and completing the global solution by adding the additional faults to the faults in all the selected combinations of optimal local solutions, and 
 computing a bound on the possible deviation of the selected solution from optimality given by the difference between the number of faults in the solution and the total number of faults in all the optimal local solutions determined for each individual domain; 
 wherein translating the fault-to-symptom correlation map into an abstract relation graph includes the step of assigning to each relational link a weight equal to the sum, taken over the symptoms represented by the relational link, of the reciprocal of the number of distinct fault-pairs that produce each such symptom. 
 
     
     
       4. A non-transitory computer readable medium having computer readable program for operating on a computer for diagnosing faults in a system for which a fault-to-symptoms correlation map is specified by a fault propagation model including a specification, for each potential fault, of a set of symptoms that will be observed if a fault occurs, said program comprising instructions that cause the computer to perform the steps of:
 translating the fault-to-symptom correlation map into an abstract relation graph in which nodes represent potential faults and a link between two nodes indicates that the corresponding faults produce one or more symptoms in common; 
 partitioning the relation graph into a set of computational domains, thus obtaining a partition of the nodes among the domains, each domain including a set of nodes assigned to a respective domain and a set of local symptoms that either have both their end-nodes in the same domain or cross-domain symptoms that have only one end-node in a domain; 
 determining all optimal solutions to the local diagnosis problem in each domain by finding the most probable set of faults in each domain that can explain ill the local symptoms of each domain, disregarding the presence of cross-domain symptoms: 
 determining a combination of the optimal local solutions of the domains, composed of one solution from each domain, that maximizes the number of cross-domain symptoms explained by the faults chosen in the combination; 
 if all cross-domain symptoms are explained by the combination of optimal local solutions, the union of the faults in all the local solutions in the combination represents an optimal global solution; 
 if there remain unexplained cross-domain symptoms, determining an optimal solution to the residual diagnosis problem by finding additional faults to explain the remaining cross-domain symptoms, and completing the global solution by adding the additional faults to the faults in all the selected combinations of optimal local solutions, and 
 computing a bound on the possible deviation of the selected solution from optimality given by the difference between the number of faults in the solution and the total number of faults in all the optimal local solutions determined for each individual domain; 
 wherein the step of finding an optimal solution is finding a set of faults (k 1 , k 2 , . . . , k m ) that accounts for all the symptoms to be explained and has the smallest metric H (k 1 , k 2 , . . . , k m ), where 
 
       
         
           
             
               
                 
                   H 
                   ⁡ 
                   
                     ( 
                     
                       
                         k 
                         1 
                       
                       , 
                       
                         k 
                         2 
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         k 
                         m 
                       
                     
                     ) 
                   
                 
                 ⁢ 
                 
                   = 
                   Δ 
                 
                 ⁢ 
                 
                   
                     ∏ 
                     
                       j 
                       = 
                       1 
                     
                     m 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       p 
                       
                         k 
                         j 
                       
                     
                     
                       1 
                       - 
                       
                         p 
                         
                           k 
                           j 
                         
                       
                     
                   
                 
               
               , 
             
           
         
         and where p k     j   =the prior probability of occurrence of fault k j , j =1,2, . . . , m.