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 optimal 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.   
     
     
         2 . (canceled) 
     
     
         3 . The method as set forth in  claim 1 , wherein partitioning the relation graph into a set of computational domains comprises solving a graph-partitioning algorithm which obtains a partition of the relation graph into a specified number of computational domains, with approximately the same number of nodes per domain, while minimizing the sum of the weights of all the cross-domain links. 
     
     
         4 . The method as set forth in  claim 1 , wherein the step of determining a combination of optimal local solutions, one solution from each domain comprises solving a maximum set cover problem in which a set of local solutions, one from each domain, is selected to maximize the number of cross-domain symptoms that are explained by the selection. 
     
     
         5 . The method as set forth in  claim 1 , wherein the relation graph is partitioned in an adaptive fashion by defining the relational links to correspond to the symptoms that are actually observed in each realization of the fault propagation model, and limiting the nodes to those that correspond to possible causes of the symptoms actually observed in the said realization of the fault propagation model. 
     
     
         6 . The method as set forth in  claim 1 , wherein the step of finding an optimal solution is finding a set with the smallest number of faults that accounts for all the symptoms to be explained in the case when all faults are assumed to be equally probable. 
     
     
         7 . (canceled) 
     
     
         8 . A 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 optimal 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.   
     
     
         9 . (canceled) 
     
     
         10 . A computer readable memory as set forth in  claim 8 , wherein partitioning the relation graph into a set of computational domains comprises solving a graph-partitioning algorithm which obtains a partition of the relation graph into a specified number of computational domains, with approximately the same number of nodes per domain, while minimizing the sum of the weights of all the cross-domain links. 
     
     
         11 . A computer readable memory as set forth in  claim 8 , wherein the step of determining a combination of optimal local solutions, one solution from each domain comprises solving a maximum set cover problem in which a set of local solutions, one from each domain, is selected to maximize the number of cross-domain symptoms that are explained by the selection. 
     
     
         12 . A computer readable memory as set forth in  claim 8 , wherein the relation graph is partitioned in an adaptive fashion by defining the relational links to correspond to the symptoms that are actually observed in each realization of the fault propagation model, and limiting the nodes to those that correspond to possible causes of the symptoms actually observed in the said realization of the fault propagation model. 
     
     
         13 . A computer readable memory as set forth in  claim 8 , wherein the step of finding an optimal solution is finding a set with the smallest number of faults that accounts for all the symptoms to be explained in the case when all faults are assumed to be equally probable. 
     
     
         14 . (canceled) 
     
     
         15 . A system for 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:
 means for 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;   means for 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;   means for 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;   means for 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;   wherein 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;   wherein 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   means for computing a bound on the possible deviation of the optimal 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.   
     
     
         16 . The system as set forth in  claim 15 , wherein said means for translating the fault-to-symptom correlation map into an abstract relation graph includes means for 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. 
     
     
         17 . The system as set forth in  claim 15 , wherein said means for partitioning the relation graph into a set of computational domains comprises means for solving a graph-partitioning algorithm which obtains a partition of the relation graph into a specified number of computational domains, with approximately the same number of nodes per domain, while minimizing the sum of the weights of all the cross-domain links. 
     
     
         18 . The system as set forth in  claim 15 , wherein said means for determining a combination of optimal local solutions, one solution from each domain comprises means for solving a maximum set cover problem in which a set of local solutions, one from each domain, is selected to maximize the number of cross-domain symptoms that are explained by the selection. 
     
     
         19 . The system as set forth in  claim 15 , wherein said means for partitioning partitions the relation graph in an adaptive fashion by defining the relational links to correspond to the symptoms that are actually observed in each realization of the fault propagation model, and limiting the nodes to those that correspond to possible causes of the symptoms actually observed in the said realization of the fault propagation model. 
     
     
         20 . The system as set forth in  claim 15 , wherein said means for determining all optimal solutions finds a set with the smallest number of faults that accounts for all the symptoms to be explained in the case when all faults are assumed to be equally probable. 
     
     
         21 . The system as set forth in  claim 15 , wherein said means for determining all optimal solutions finds 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.