Apparatus and method for event correlation and problem reporting

• US 20030204370A1
• Filed: 03/27/2003
• Published: 10/30/2003
• Est. Priority Date: 05/25/1994
• Status: Active Grant

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Kliger, Shmuel, Yemini, Yechiam, Yemini, Shaula
• Granted Patent: US 6,868,367 B2
• Time in Patent Office: Days
• US Class Current: 702/183
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: G06F 11/2273 Test methods
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/86 Event-based monitoring

Abstract

An apparatus and method is provided for efficiently determining the source of problems in a complex system based on observable events. By splitting the problem identification process into two separate activities of (1) generating efficient codes for problem identification and (2) decoding the problems at runtime, the efficiency of the problem identification process is significantly increased. Various embodiments of the invention contemplate creating a causality matrix which relates observable symptoms to likely problems in the system, reducing the causality matrix into a minimal codebook by eliminating redundant or unnecessary information, monitoring the observable symptoms, and decoding problems by comparing the observable symptoms against the minimal codebook using various best-fit approaches. The minimal codebook also identifies those observable symptoms for which the greatest benefit will be gained if they were monitored as compared to others.

By defining a distance measure between symptoms and codes in the codebook, the invention can tolerate a loss of symptoms or spurious symptoms without failure. Changing the radius of the codebook allows the ambiguity of problem identification to be adjusted easily. The invention also allows probabilistic and temporal correlations to be monitored. Due to the degree of data reduction prior to runtime, extremely large and complex systems involving many observable events can be efficiently monitored with much smaller computing resources than would otherwise be possible.

Claims

1. A method for detecting problems in a system which generates a plurality of symptoms, the method comprising the steps of:

(1) providing a computer-accessible codebook comprising a matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

(2) monitoring said plurality of symptoms generated by said system over time;

(3) decoding, through the use of a computer, said monitored symptoms into one or more of said likely problems by determining a mismatch measure between one or more of said values in said codebook and one or more of said monitored symptoms; and

(4) generating a report comprising said one or more likely problems decoded from said codebook.

2. The method of claim 1, wherein step (3) comprises the step of determining a Hamming distance between said one or more values and said one or more monitored symptoms.

3. The method of claim 1, wherein step (3) comprises the step of finding a best fit match between said one or more values and said one or more monitored symptoms.

4. The method of claim 3, wherein step (3) comprises the step of using a mismatch measure which gives a different weight to absence of a monitored symptom than to presence of a monitored symptom.

5. The method of claim 3, wherein step (3) comprises the step of outputting as likely problems all those problems in said codebook which fall within a predeterimined tolerance from said best fit match.

9. The method of claim 1, wherein said system comprises a network of computer nodes, and wherein step (2) comprises the step of receiving messages from said computer nodes, said messages comprising data indicating one or more of said symptoms.

10. The method of claim 1, wherein said system comprises a telecommunication network, and wherein step (2) comprises the step of receiving signals from equipment in said telecommunication network, said signals comprising data indicating one or more of said symptoms.

11. The method of claim 1, wherein said system comprises a computer having peripherals, and wherein step (2) comprises the step of receiving signals from said peripherals, said signals comprising data indicating one or more of said symptoms.

12. The method of claim 1, wherein said system comprises a plurality of satellites, and wherein step (2) comprises the step of receiving signals from said satellites, said signals comprising data indicating one or more of said symptoms.

13. The method of claim 1, wherein said system comprises a human patient and wherein step (2) comprises the step of receiving signals from sensors coupled to said human patient, said signals comprising data indicating one or more of said symptoms.

14. The method of claim 1, wherein step (3) comprises the step of determining said mismatch measure by looking up a predetermined measure from a pre-computed table.

15. The method of claim 1, further comprising the step of, prior to step (1), providing a causality matrix comprising a larger set of values than said codebook, said larger set of values also corresponding to mappings between said symptoms generated by said system and likely problems corresponding thereto;

and

wherein step (1) comprises the step of generating said codebook by reducing said larger set of values contained in said causality matrix into said codebook.

16. The method of claim 15, wherein step (1) comprises the step of eliminating redundant rows and columns from said causality matrix.

17. The method of claim 15, wherein step (1) comprises the step of reducing the number of rows in said causality matrix in accordance with a predetermined radius.

18. The method of claim 1, further comprising the step of, prior to step (1), providing a causality graph comprising a plurality of nodes each corresponding to an event, a plurality of directed edges each corresponding to a causal relation between two or more of said events, wherein certain of said nodes are marked as problem nodes and others are marked as symptom nodes;

and wherein step (1) comprises the step of generating said codebook by traversing said directed edges leading from problem nodes to symptom nodes.

19. The method of claim 18, wherein step (1) comprises the steps of:

eliminating from said causality graph redundant symptom nodes that may be reached via directed edges from the same set of problem nodes; and

eliminating indistinguishable problem nodes that lead via directed edges to the same set of symptoms nodes.

20. The method of claim 18, wherein step (1) comprises the step of eliminating from said causality graph symptom nodes in accordance with a predetermined radius.

6. The method of claim wherein step (1) comprises the step of specifying each of said value as a probability, said probability reflecting a likelihood that a corresponding symptom was caused by a corresponding problem.

7. The method of claim 6, wherein step (1) comprises the step of specifying each of said values as a pair of data, said pair comprising a first datum designating said probability and a second datum designating a temporal indicator corresponding to a time frame within which said probability holds.

8. The method of claim 6, wherein step (1) comprises the step of specifying each said probability as a discrete value.

21. A method for detecting problems in a system which generates a plurality of symptoms, the method comprising the steps of:

(1) generating a causality matrix comprising a first matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

(2) reducing said causality matrix into a codebook comprising a second matrix of values fewer in number than said first matrix of values by eliminating duplicative sets of values from said first matrix;

(3) monitoring said plurality of symptoms generated by said system over time;

(4) decoding, through the use of a computer, said monitored symptoms into one or more of said likely problems by determining a mismatch measure between one or more of said values in said codebook and one or more of said monitored symptoms, and

(5) reporting said one or more likely problems decoded from said codebook.

22. The method of claim 21, wherein step (2) comprises the step of eliminating redundant rows and columns from said first matrix.

23. The method of claim 21, further comprising the step of selecting a radius for said codebook corresponding to a desired level of problem identification, and wherein step (2) comprises the step of deleting values from said first matrix which do not satisfy said desired level, said deletions made on the basis of comparisons between one or more of said values from said first matrix with said radius.

24. The method of claim 23, wherein said comparisons are made with respect to a Hamming distance determined with respect to one or more of said values from said first matrix.

25. The method of claim 23, further comprising the step of specifying each of said values in said first matrix as a probability, said probability reflecting a likelihood that a corresponding symptom was caused by a corresponding problem.

26. The method of claim 25, wherein said specifying step comprises the step of specifying each of said values as a discrete probability value.

27. The method of claim 23, further comprising the step of making said comparisons by using a mismatch measure which gives a different weight to absence of a symptom than to presence of a symptom.

28. A method of generating a codebook for use in a process of detecting problems in a system which generates a plurality of symptoms, the method comprising the steps of:

(1) preparing a causality matrix comprising a matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

(2) making said causality matrix well-formed by deleting redundant sets of values from said matrix of values;

(3) selecting a radius corresponding to a desired level of problem identification;

(4) generating, through the use of a computer, an optimal codebook from said well-formed causality matrix by selecting values from said well-formed causality matrix based on comparisons with said radius; and

(5) storing said optimal codebook in a computer storage device.

29. The method of claim 28, wherein step (1) comprises the step of preparing a formal specification of an even model which defines relationships between events in said system and causes thereof.

30. The method of claim 29, wherein said preparing step comprises the step of inputting to a compiler compilable statements which use probabilities to define said relationships.

31. The method of claim 30, further comprising the steps of:

compiling said compilable statements into methods and data structures; and

using said methods and data structures to generate said causality matrix by determining a causality closure of problems contained in a configuration specification.

32. The method of claim 28, wherein step (1) comprises the steps of:

(a) logging events occurring in said system over a period of time to a computer storage device;

(b) analyzing said logged events for statistical correlations;

(c) filtering said analyzed events based on a correlation threshold and producing a filtered set of data comprising symptoms and likely problems; and

(d) generating said causality matrix using said filtered set of data.

33. A method of generating a codebook for use in a process of detecting problems in a system which generates a plurality of symptoms, the method comprising steps of:

(1) preparing a causality graph comprising a plurality of nodes each corresponding to a problem, or a symptom, and a plurality of dined edges each corresponding to a causal relation between two or more of said nodes;

(2) making said causality graph well-formed by deleting redundant nodes;

(3) selecting a radius corresponding to a desired level of problem identification;

(4) generating, through the use of a computer, an optimal codebook from said well-formed causality graph by selecting symptom nodes based on comparisons with said radius; and

(5) storing said optimal codebook, in a computer storage device.

34. The method of claim 33, wherein step (1) comprises the step of inputting a formal specification of an event model into a computer, said formal specification defining relationships between events in said system and causes thereof.

35. The method of claim 34, wherein step (1) comprises the step of inputting compilable statements into a compiler, said compilable statements comprising probabilities to define said relationships.

36. The method of claim 34, further comprising the steps of:

compiling said formal specification into methods and data structures; and

using said methods and data structures to generate said causality graph by determining a causality closure of problems in a configuration specification.

37. Apparatus for detecting problems in a system which generates a plurality of symptoms, the apparatus comprising:

a storage device for storing a codebook comprising a matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

monitoring means for monitoring said plurality of symptoms generated by said system over time;

decoding means for reading said values from said codebook and decoding said monitored symptoms into one or more of said likely problems by determining a mismatch measure between one or more of said values read from said codebook and one or more of said monitored symptoms; and

generating means for generating a report comprising said one or more likely problems decoded from said codebook.

38. The apparatus of claim 37, wherein said decoding means comprises means for determining a Hamming distance between said one or more values and said one or more monitored symptoms.

39. The apparatus of claim 37, wherein said decoding means comprises means for determining a best fit match between said one or more values and said one or more monitored symptoms.

40. The apparatus of claim 39, wherein said best fit match determination uses a mismatch measure which gives a different weight to absence of a monitored symptom than to presence of a monitored symptom.

41. The apparatus of claim 39, wherein said decoding means outputs as likely problems all those problems in said codebook which fall within a predetermined tolerance from said best fit match.

42. The apparatus of claim 37, wherein each of said values comprises a probability reflecting a likelihood that a corresponding symptom was caused by a corresponding problem.

43. The apparatus of claim 42, wherein each of said values comprises a pair of data, said pair comprising a first datum designating said probability and a second datum designating a temporal indicator corresponding to a time frame within which said probability holds.

44. The apparatus of claim 42, wherein each of said probability values is specified as a discrete value.

45. The apparatus of claim 37, wherein said system comprises a network of computer nodes, and wherein said monitoring means comprises means for receiving messages from said computer nodes, said messages comprising data indicating one or more of said symptoms.

46. The apparatus of claim 37, wherein said system comprises a telecommunication network, and wherein said monitoring means comprises means for receiving signals from equipment in said network, said signals comprising data indicating one or more of said symptoms.

47. The apparatus of claim 37, wherein said system comprises a computer having peripherals, and wherein said monitoring means comprises means for receiving signals from said peripherals, said signals comprising data indicating one or more of said symptoms.

48. The apparatus of claim 37, wherein said system comprises a plurality of satellites, and wherein said monitoring means comprises means for receiving signals from said satellites, said signals comprising data indicating one or more of said symptoms.

49. The apparatus of claim 37, wherein said system comprises a human patient, and wherein said monitoring means comprises means for receiving signals from sensors coupled to said human patient, said signals comprising data indicating one or more of said symptoms.

50. The apparatus of claim 37, wherein said mismatch measure is determined by looking up a predetermined measure from a pre-computed table.

51. The apparatus of claim 37, further comprising:

means for storing a causality matrix comprising a larger set of values than said codebook, said values also corresponding to mappings between said symptoms generated by said system and likely problems corresponding thereto; and

means for generating said codebook by reducing said larger set of values contained in said causality matrix into values for said codebook.

52. The apparatus of claim 51, wherein said codebook is generated by eliminating redundant rows and columns from said causality matrix.

53. The apparatus of claim 51, wherein said codebook is generated by reducing the number of rows in said causality matrix in accordance with a predetermined radius.

54. The apparatus of claim 37, further comprising means for storing a causality graph comprising a plurality of nodes each corresponding to an event, and a plurality of directed edges each corresponding to a causal relation between two of said events, wherein certain nodes are marked as problems and certain nodes are marked as symptoms;

and

wherein said codebook is generated by traversing said directed edges in said causality graph leading from nodes marked as problems to nodes marked as symptoms.

55. The apparatus of claim 54, wherein said codebook is generated by eliminating from said causality graph redundant symptom nodes that may be reached via directed edges from the same set of problem nodes, and by eliminating indistinguishable problem nodes that lead via directed edges to the same set of symptom nodes.

56. The apparatus of claim 54, wherein said codebook is generated by eliminating from said causality graph symptom nodes in accordance with a predetermined radius.

57. Apparatus for detecting problems in a system which generates a plurality of symptoms, the apparatus comprising:

generating means for generating a causality matrix comprising a first matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

reducing means for reducing said causality matrix into a computer-accessible codebook comprising a second matrix of values fewer in number than said first matrix of values by eliminating duplicative sets of values from said first matrix;

monitoring means for monitoring said plurality of symptoms generated by said system over time through the use of a computer;

decoding means for decoding said monitored symptoms into one or more of said likely problems by determining a mismatch measure between one or more of said values in said codebook and one or more of said monitored symptoms; and

a report generator for reporting said one or more likely problems decoded from said codebook.

58. The apparatus of claim 57, wherein said reducing means eliminates redundant rows and columns from said first matrix.

59. The apparatus of claim 57, wherein said reducing means comprises means for inputting a radius for said codebook corresponding to a desired level of problem identification, and wherein said reducing means deletes values from said first matrix which do not satisfy said desired level, said deletions made on the basis of comparisons between one or more of said values from said first matrix with said radius.

60. The apparatus of claim 59, wherein said comparisons are made with respect to a Hamming distance determined with respect to one or more of said values from said first matrix.

61. The apparatus of claim 59, wherein each of said values in said first matrix comprises a probability reflecting a likelihood that a corresponding symptom was caused by a corresponding problem.

62. The apparatus of claim 61, wherein said probabilities comprise a discrete value.

63. The apparatus of claim 59, wherein said mismatch measure gives a different weight to absence of a symptom than to presence of a symptom.

64. Apparatus for generating a codebook for use in detecting problems in a system which generates a plurality of symptoms, the apparatus comprising:

preparing means for preparing a causality matrix comprising a matrix of values each corresponding to a mapping between one of said plurality of symptoms and a likely problem in said system;

means for making said causality matrix well-formed by deleting redundant sets of values from said matrix of values;

inputting means for inputting a radius corresponding to a desired level of problem identification;

generating means for generating a computer-accessible optimal codebook from said well-formed causality matrix by selecting values from said well-formed causality matrix based on comparisons with said radius; and

a storage device for storing said computer-accessible optimal codebook.

65. The apparatus of claim 64, wherein said preparing means comprises:

means for inputting a specification of an event model defining relationships between events in said system and causes thereof; and

a compiler for compiling said specification into data structures.

66. The apparatus of claim 65, wherein said specification comprises statements which define said relationships using probability values.

67. The apparatus of claim 65, further comprising a matrix generator for transforming said data structures into said causality matrix by determining a causality closure of problems contained in a configuration specification.

68. The apparatus of claim 64, wherein said preparing means comprises:

means for logging events occurring in said system over a period of time to a computer storage device;

means for analyzing said logged events for statistical correlations;

means for filtering said analyzed events based on a correlation threshold and producing a filtered set of data comprising symptoms and likely problems; and

means for generating said causality matrix using said filtered set of data.

69. Apparatus for generating a codebook for use in detecting problems in a system which generates a plurality of symptoms, the apparatus comprising:

preparing means for preparing a causality graph comprising a plurality of nodes each corresponding to a problem or a symptom, and a plurality of directed edges each corresponding to a causal relation between two or more of said nodes;

means for making said causality graph well-formed by deleting redundant nodes;

specifying means for specifying a radius corresponding to a desired level of problem identification in said system;

generating means for generating, through the use of a computer, an optimal codebook from said well-formed causality graph by selecting symptom nodes based on comparisons with said radius; and

a computer storage device for storing said optimal codebook.

70. The apparatus of claim 69, wherein said preparing means comprises means for inputting a specification of an event model which defines relationships between events in said system and causes thereof.

71. The apparatus of claim 70, wherein said specification comprises compilable statements which use probabilities to define said relationships.

72. The apparatus of claim 70, wherein said preparing means comprises means for compiling said specification into methods and data structures, and wherein said methods and data structures are used to generate said causality graph by determining a causality closure of problems contained in a configuration specification.

73. The apparatus of claim 69, wherein said preparing means comprises:

means for logging events occurring in said system over a period of time to a computer storage device;

means for analyzing said logged events for statistical correlations;

means for filtering said analyzed events based on a correlation threshold and producing a filtered set of data comprising symptoms and likely problems; and

means for generating said causality graph using said filtered set of data.

74. A method of preparing a data structure for use in identifying problems in a system having a plurality of components, said system generating a plurality of observable events, the method comprising the steps of:

(1) preparing first compilable statements which define causal relationships between said observable events and likely problems in said system;

(2) preparing second compilable statements which define propagation properties of said observable events among said components of said system;

(3) preparing a configuration specification which defines relationships among said components of said system;

(4) translating, through the use of a computer, said first and second compilable statements into said data structure by determining a causality closure of said observable events based on said relationships among components of said system and said propagation properties; and

(5) storing said data structure in a computer storage device.

75. The method according to claim 74, wherein step (1) comprises the step of preparing said first compilable statements for each class of components in said system, and wherein step (2) comprises the step of preparing said second compilable statements for each class of components in said system.

76. The method according to claim 75, wherein steps (1) and (2) are performed once for a generic configuration of components, and wherein step (3) is performed once for each unique configuration of system components.