# US 8,280,835 B2 · Method for automated distributed diagnostics for networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,835 B2
- Document ID: US8280835B2
- Status: Granted
- Kind: B2
- Application number: 12/362,298
- Filed: 2009-01-29
- Published: 2010-07-29
- Granted: 2012-10-02
- Earliest claimed: 2009-01-29
- Assignees: Telcordia Technologies, Inc.
- Inventors: Komandur R. Krishnan; Hanan Luss; David F. Shallcross; Arnold L. Neidhardt
- Web page: https://patentgrep.com/patent/US8280835B2

## CPC

- G06F 11/079: {Root cause analysis, i.e. error or fault diagnosis (in a hardware test environment G06F11/22; in a software test environment G06F11/36)}
- G05B 23/0248: {Causal models, e.g. fault tree; digraphs; qualitative physics}
- G06F 11/0706: {the processing taking place on a specific hardware platform or in a specific software environment}
- H04L 41/065: {involving logical or physical relationship, e.g. grouping and hierarchies}
- H04L 41/0677: Localisation of faults
- Y04S 40/00: Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y04S: SYSTEMS INTEGRATING TECHNOLOGIES RELATED TO POWER NETWORK OPERATION, COMMUNICATION OR INFORMATION TECHNOLOGIES FOR IMPROVING THE ELECTRICAL POWER GENERATION, TRANSMISSION, DISTRIBUTION, MANAGEMENT OR USAGE, i.e. SMART GRIDS

## 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.

## Claims

### Claim 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.

### Claim 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 (k1, k2, . . . , km) that accounts for all the symptoms to be explained and has the smallest metric H (k1, k2, . . . , km), where
H
⁡
(
k
1
,
k
2
,
…
⁢
,
k
m
)
⁢
=
Δ
⁢
∏
j
=
1
m
⁢
⁢
p
k
j
1
-
p
k
j
,
and where pkj=the prior probability of occurrence of fault kj, j=1,2, . . . , m.

### Claim 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.

### Claim 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 (k1, k2, . . . , km) that accounts for all the symptoms to be explained and has the smallest metric H (k1, k2, . . . , km), where
H
⁡
(
k
1
,
k
2
,
…
⁢
,
k
m
)
⁢
=
Δ
⁢
∏
j
=
1
m
⁢
⁢
p
k
j
1
-
p
k
j
,
and where pkj=the prior probability of occurrence of fault kj, j =1,2, . . . , m.
