Method and apparatus for component association inference, failure diagnosis and misconfiguration detection based on historical failure data

• US 7,937,347 B2
• Filed: 06/13/2007
• Issued: 05/03/2011
• Est. Priority Date: 06/13/2007
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Tao, Shu, Mao, Yun, Anerousis, Nikolaos, Jamjoom, Hani T.
• Primary Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US11/762,229
• Publication Number:
  US 20080313118A1
• Time in Patent Office: 1,420 Days
• Field of Search: None
• US Class Current: 706/45
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: 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

Abstract

A method (which can be computer implemented) for inferring component associations among a plurality of components in a distributed computing system includes the steps of obtaining status information for each pertinent component of the plurality of components, forming an N by D matrix, X, based on the status information, and factorizing the matrix X to obtain a first matrix indicative of the component associations to be inferred and a second matrix indicative of failure explanations for corresponding ones of the probe instances. N is a number of probe instances associated with a given time frame. D is a number of the plurality of components for which the associations are to be inferred. Techniques are also presented for forming a database with the status information.

Claims

1. A method for inferring component associations among a plurality of components in a distributed computing system, said method comprising the steps of:

obtaining status information for each pertinent component of said plurality of components;

forming an N by D matrix, X, based on said status information, where;

N comprises a number of probe instances associated with a given time frame; and

D comprises a number of said plurality of components for which said associations are to be inferred; and

factorizing said matrix X to obtain a first matrix indicative of said component associations to be inferred and a second matrix indicative of failure explanations for corresponding ones of said probe instances, wherein one or more steps are performed by a hardware device.

2. The method of claim 1, wherein:

said first matrix indicative of said component associations to be inferred comprises a matrix W having dimensions N by R, where R is a number of failure groups representing said component associations to be inferred; and

said second matrix indicative of said failure explanations for said corresponding ones of said probe instances comprises a matrix H having dimensions R by D.

3. The method of claim 2, further comprising the additional step of setting initial values of said matrix W and said matrix H to random numbers within a range between zero and one.

4. The method of claim 3, wherein said factorizing comprises non-negative matrix factorization.

5. The method of claim 4, wherein said matrices W and H each have a plurality of column vectors and each of said column vectors has a maximal element, further comprising the additional steps of:

normalizing said matrix W such that said maximal element of each of said column vectors of said matrix W is one; and

normalizing said matrix H such that said maximal element of each of said column vectors of said matrix H is one.

6. The method of claim 5, further comprising the additional steps of:

generating a binary matrix U based on said matrix W; and

generating a binary matrix V based on said matrix H.

7. The method of claim 6, wherein:

said matrix V has a plurality of row vectors;

said matrix U has a plurality of row vectors;

each of said row vectors of said matrix V represents a given one of said component associations to be inferred; and

each of said row vectors of said matrix U represents a given one of said failure explanations for said corresponding ones of said probe instances.

8. The method of claim 7, wherein:

said step of generating said binary matrix U comprises applying the relationships;

U_ij=1 if W_ij>

Threshold;

otherwise, U_ij=0; and

said step of generating said binary matrix V comprises applying the relationships;

V_ij=1 if H_ij=max(H_kj) and H_ij>

Threshold and H₁>

Threshold×

max(H_id{, where k=1 . . . R and d=1 . . . D;

otherwise, V_ij=0.

9. The method of claim 1, wherein a priori information pertaining to said component associations is one of incomplete and non-existent.

10. The method of claim 1, wherein said step of obtaining status information for each pertinent component of said plurality of components further comprises obtaining geographic location information for at least some of said plurality of components.

11. The method of claim 10, wherein:

said first matrix indicative of said component associations to be inferred comprises a matrix W having dimensions N by R, where R is a number of failure groups representing said component associations to be inferred; and

said second matrix indicative of said failure explanations for said corresponding ones of said probe instances comprises a matrix H having dimensions R by D;

further comprising the additional steps of;

clustering said D components into R clusters; and

setting initial values of said matrix W and said matrix H in accordance with an assumption that said R clusters comprise said R failure groups.

12. The method of claim 10, wherein said geographic location information comprises longitude and latitude information.

13. The method of claim 12, wherein said latitude and longitude information is obtained directly.

14. The method of claim 12, further comprising the additional steps of:

obtaining physical address information; and

converting said address information to said latitude and longitude information.

15. The method of claim 10, further comprising the additional steps of:

inferring said component associations based on said first matrix indicative of said component associations to be inferred; and

checking said geographic location information against said inferred component associations to identify at least one mis-configuration.

16. The method of claim 15 wherein said component associations to be inferred are represented by a plurality of failure groups and wherein said checking comprises examining said failure groups for geographic outliers.

17. The method of claim 1, wherein in said step of obtaining status information for each pertinent component of said plurality of components, said pertinent components comprises end-point components.

18. The method of claim 1, further comprising the additional steps of:

inferring said component associations based on said first matrix indicative of said component associations to be inferred;

obtaining health status of select ones of said components of said distributed system, based on said second matrix indicative of failure explanations for corresponding ones of said probe instances; and

facilitating presentation of (i) topology information, based on said component associations, and (ii) said health status of said select ones of said components, to an operator of said system.

19. The method of claim 1, wherein said status information is obtained from a database.

20. The method of claim 1, wherein said first matrix indicates multiple topological levels, further comprising the additional step of repeating said forming and factorizing steps for at least one sub-association group corresponding to at least one additional one of said multiple topological levels.

21. The method of claim 1, wherein:

said step of obtaining status information for each pertinent component of said plurality of components further comprises obtaining geographic location information for at least some of said plurality of components; and

said forming and factorizing steps are based on;

assuming associated ones of said components are more likely to fail simultaneously due to shared risk; and

assuming that physically close ones of said components are more likely to be associated together.

22. A method for forming a database useful in inferring component associations among a plurality of components in a distributed computing system, said method comprising the steps of:

obtaining a location of each of at least two of said plurality of components;

determining a topology of said at least two of said plurality of components based on said location;

monitoring status information for each pertinent component of said plurality of components, said monitoring comprising probing in a series of probe instances, each of said instances pertaining to a substantially contemporaneous time stamp; and

recording said status information in said database when predetermined conditions are present, wherein said status information is based on said determined topology and wherein one or more steps are performed by a hardware device.

23. The method of claim 22, wherein said predetermined conditions comprise performance of a given one of said probe instances.

24. The method of claim 22, wherein said predetermined conditions comprise performance of a given one of said probe instances which yields failure information.

25. The method of claim 22, wherein said probe instances are conducted periodically.

26. The method of claim 22, wherein said probe instances are conducted based on occurrence of a pre-determined threshold.

27. The method of claim 26, wherein said pre-determined threshold comprises a ratio of failed components to total components.

28. The method of claim 22, wherein said status information is binary, with one comprising failure and zero comprising success.

29. A computer program product comprising a tangible computer useable readable storage medium including computer usable program code for inferring component associations among a plurality of components in a distributed computing system, said computer program product including:

computer usable program code for obtaining status information for each pertinent component of said plurality of components;

computer usable program code for forming an N by D matrix, X, based on said status information, where;

N comprises a number of probe instances associated with a given time frame; and

D comprises a number of said plurality of components for which said associations are to be inferred; and

computer usable program code for factorizing said matrix X to obtain a first matrix indicative of said component associations to be inferred and a second matrix indicative of failure explanations for corresponding ones of said probe instances.

30. The computer program product of claim 29, wherein:

said first matrix indicative of said component associations to be inferred comprises a matrix W having dimensions N by R, where R is a number of failure groups representing said component associations to be inferred; and

said second matrix indicative of said failure explanations for said corresponding ones of said probe instances comprises a matrix H having dimensions R by D.

31. The computer program product of claim 30, wherein:

said factorizing comprises non-negative matrix factorization;

said matrices W and H each have a plurality of column vectors and each of said column vectors has a maximal element; and

said computer program product further comprises;

computer usable program code for normalizing said matrix W such that said maximal element of each of said column vectors of said matrix W is one;

computer usable program code for normalizing said matrix H such that said maximal element of each of said column vectors of said matrix H is one;

computer usable program code for setting initial values of said matrix W and said matrix H to random numbers within a range between zero and one;

computer usable program code for generating a binary matrix U based on said matrix W; and

computer usable program code for generating a binary matrix V based on said matrix H.

32. An apparatus for inferring component associations among a plurality of components in a distributed computing system, the apparatus comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

obtain status information for each pertinent component of said plurality of components;

form an N by D matrix, X, based on said status information, where;

N comprises a number of probe instances associated with a given time frame; and

D comprises a number of said plurality of components for which said associations are to be inferred; and

factorize said matrix X to obtain a first matrix indicative of said component associations to be inferred and a second matrix indicative of failure explanations for corresponding ones of said probe instances.

33. The apparatus of claim 32, wherein:

said first matrix indicative of said component associations to be inferred comprises a matrix W having dimensions N by R, where R is a number of failure groups representing said component associations to be inferred; and

said second matrix indicative of said failure explanations for said corresponding ones of said probe instances comprises a matrix H having dimensions R by D.

34. The apparatus of claim 33, wherein:

said factorizing comprises non-negative matrix factorization;

said matrices W and H each have a plurality of column vectors and each of said column vectors has a maximal element; and

said processor is further operative to;

normalize said matrix W such that said maximal element of each of said column vectors of said matrix W is one;

normalize said matrix H such that said maximal element of each of said column vectors of said matrix H is one;

set initial values of said matrix W and said matrix H to random numbers within a range between zero and one;

generate a binary matrix U based on said matrix W; and

generate a binary matrix V based on said matrix H.

35. A computer program product comprising a tangible computer useable readable storage medium including computer usable program code for forming a database useful in inferring component associations among a plurality of components in a distributed computing system, said computer program product including:

computer usable program code for obtaining a location of each of at least two of said plurality of components;

computer usable program code for determining a topology of said at least two of said plurality of components based on said location;

computer usable program code for monitoring status information based on said determined topology for each pertinent component of said plurality of components, said monitoring comprising probing in a series of probe instances, each of said instances pertaining to a substantially contemporaneous time stamp; and

computer usable program code for recording said status information in said database when predetermined conditions are present, wherein said status information is based on said determined topology.