System and method for inferring causal paths in a distributed computing environment

• US 20060282546A1
• Filed: 06/09/2005
• Published: 12/14/2006
• Est. Priority Date: 06/09/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Reynolds, Patrick A., Aguilera, Marcos K., Wiener, Janet L., Mogul, Jeffrey C.
• Granted Patent: US 9,178,721 B2
• Time in Patent Office: Days
• US Class Current: 709/248
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

According to one embodiment, a method comprises evaluating messages between nodes of a distributed computing environment. Based on timing relationships of the messages, probability of causal links between pairs of messages determined. Based on the determined probability, at least one causal path comprising a plurality of causal links is inferred. Further, an overall probability that the inferred causal path is accurate is determined. In certain embodiments, the overall probability is output for the corresponding causal path to provide an indication of the confidence of the accuracy of such inferred causal path.

Claims

1. A method comprising:

evaluating messages between pairs of nodes of a distributed computing environment;

based on timing relationships of said messages, determining probability of a causal link between two or more of said messages;

based on said determined probability, inferring at least one causal path comprising a plurality of causal links; and

determining an overall probability that the inferred causal path is accurate.

2. The method of claim 1 wherein said determining probability of a causal link between two or more of said messages comprises:

selecting a service time distribution for causal links through each pair of said nodes.

3. The method of claim 2 wherein said selecting a service time distribution comprises:

determining at least one parameter describing the shape or scale of said selected distribution.

4. The method of claim 3 wherein said determining said at least one parameter comprises:

creating a histogram of all possible delay values for all said causal links in said messages.

5. The method of claim 4 wherein said determining said at least one parameter further comprises:

selecting at least one parameter value that best matches the delay distribution to the histogram.

6. The method of claim 5 wherein said determining said at least one parameter further comprises:

applying said at least one parameter to create a new histogram;

determining a new value for said at least one parameter based on said new histogram; and

repeating said new histogram and said determining for said at least one parameter until a desired termination condition is met.

7. The method of claim 3 wherein said inferring comprises:

assigning a probability to each potential causal link found in said messages based on the parameterized service time distribution for nodes in said potential causal link.

8. The method of claim 7 wherein said probability is increased according to a parameterized function of length of a call-return path completed in said potential causal link.

9. The method of claim 2 wherein said service time distribution is an exponential distribution.

10. The method of claim 2 wherein said service time distribution is a Gaussian distribution.

11. The method of claim 1 wherein said determining probability of a causal link between two or more of said messages comprises:

estimating an average causal delay between receipt and transmission of said messages.

12. The method of claim 11 wherein said estimating an average causal delay comprises:

determining, for each occurrence of said causal link in said messages, an amount of delay from (a) receipt of an immediately preceding message sent by a first node in the causal link to the second node in the causal link to (b) the second node sending a message to a third node in the causal link; and

averaging the determined delays to estimate said average causal delay for said second node.

13. The method of claim 11 further comprising:

estimating respective average causal delays for each of a plurality of different pairs of said second and third nodes.

14. The method of claim 11 further comprising:

using said average causal delay to determine parameters for a service time distribution for said pairs of second and third nodes.

15. The method of claim 1 wherein said determining an overall probability comprises:

determining said overall probability as a product of probabilities of said plurality of causal links included in the inferred causal path.

16. The method of claim 1 wherein said inferring comprises:

classifying each of a plurality of causal links as probably true, probably false, or try-both.

17. The method of claim 16 wherein said classifying is based at least in part on said determined probability of said causal link.

18. The method of claim 16 wherein a plurality of said causal links classified as probably false are reclassified as try-both or probably true so that each message appears in at least one inferred causal path.

19. The method of claim 16 wherein the number of causal links classified as try-both is limited to no more than a parameterized value.

20. The method of claim 19 wherein the causal links classified as try-both are ranked based on their probabilities.

21. The method of claim 16 wherein said inferring comprises:

including said causal links classified as probably true in an inferred causal path and excluding said causal links classified as probably false in said inferred causal path.

22. The method of claim 16 wherein said inferring comprises:

for each of such causal links classified as try-both, inferring a first causal path that includes said try-both causal link and inferring a second causal path that does not include said try-both causal link.

23. The method of claim 1 further comprising:

outputting to a user the inferred at least one causal path and the corresponding overall probability of each of the at least one causal path.

24. The method of claim 1 wherein said nodes of the distributed computing environment comprise one or more selected from the group consisting of:

separate clusters of computers, separate individual computers, separate processors implemented on one or more computers, separate processes executing on a device, separate threads within a single software process and separate software objects within one or more threads.

25. The method of claim 1 wherein said distributed computing environment comprises a wide-area distributed system.

26. The method of claim 1 wherein said inferring does not require that said nodes of said distributed computing environment adhere to call-return semantics for communicating with each other.

27. The method of claim 1 wherein said messages include at least one fat message comprising a combination of a sequence of a plurality of messages from one sending node to one receiving node.

28. Computer-executable software code stored to a computer-readable medium, said computer-executable software code comprising:

code for evaluating messages between nodes of a distributed computing environment;

code for determining, based on timing relationships of said messages, probability of a causal link between one or more pairs of said messages;

code for inferring, based on said determined probability, at least one causal path comprising a plurality of causal links; and

code for presenting said at least one causal path and a corresponding indication of confidence in the accuracy of each of the at least one inferred causal path.

29. The computer-executable software code of claim 28 wherein said code for presenting an indication of confidence comprises:

code for presenting, for each of the at least one inferred causal path, a respective probability that such inferred causal path is accurate.

30. The computer-executable software code of claim 29 further comprising:

code for determining, for each of the at least one inferred causal path, said respective probability that such inferred causal path is accurate.

31. The computer-executable software code of claim 30 wherein said code for determining said respective probability comprises:

code for determining said respective probability of such inferred causal path as a product of determined probabilities of said plurality of causal links included in such inferred causal path.

32. The computer-executable software code of claim 28 wherein said code for determining probability of a causal link between one or more pairs of said messages comprises:

code for estimating an average causal delay for said causal link.

33. The computer-executable software code of claim 32 wherein said code for estimating an average causal delay comprises:

code for determining, for each occurrence of said causal link in said messages, an amount of delay between receipt of an immediately preceding message sent by a first node and received by a second node, and transmission of a message from said second node to a third node; and

code for averaging the determined delays to estimate said average causal delay for said second node.

34. The computer-executable software code of claim 33 further comprising:

code for determining parameters for a service time distribution for said pairs of second and third nodes based on said average causal delay estimated for said pairs of second and third nodes.

35. The computer-executable software code of claim 34 wherein said service time distribution is an exponential distribution.

36. The computer-executable software code of claim 34 wherein said code for inferring comprises:

code for assigning a probability a potential causal link found in said messages based on the parameterized service time distribution for said pair of second and third nodes in said potential causal link.

37. The computer-executable software code of claim 36 wherein said code for assigning probabilities increases the probability of a plurality of causal links according to a parameterized function of length of a call-return path said causal links complete.

38. The computer-executable software code of claim 28 wherein said code for inferring comprises:

code for classifying a causal link as probably true, probably false, or try-both.

39. The computer-executable software code of claim 38 wherein said code for classifying performs said classifying based at least in part on said determined probability of said causal link.

40. The computer-executable software code of claim 38 wherein said code for inferring comprises:

code for including said causal links classified as probably true in an inferred causal path; and

code, responsive to each of the said causal links classified as try-both, for inferring a first causal path that includes such try-both causal link and inferring a second causal path that does not include such try-both causal link.

41. The computer-executable software code of claim 28 wherein said code for inferring does not require that said nodes of said distributed computing environment adhere to call-return semantics for communicating with each other.

42. A method comprising:

receiving, by logic for inferring a causal path, a trace of communication messages between nodes in a distributed computing environment;

evaluating, by said logic, said trace of communication messages to infer at least one causal path, wherein said evaluating does not require that said communication messages adhere to call-return semantics;

based on timing relationship of said messages, said logic determining probability of a causal link between pairs of said messages; and

based on said determined probabilities, said logic forming at least one causal path comprising a plurality of causal links.

43. The method of claim 42 wherein said determining probability of a causal link between pairs of messages comprises:

determining probability of a causal link between a pair of messages from a first node to a second node and later from said second node to a third node, wherein said logic estimating an average causal delay for said second node.

44. The method of claim 43 wherein said estimating an average causal delay comprises:

said logic determining, for each occurrence of said message from said second node to said third node in said messages, an amount of delay from receipt of an immediately preceding message by said second node to the transmission of a message from said second node to said third node; and

said logic averaging the determined delays to estimate said average causal delay for said pair of second and third nodes.

45. The method of claim 44 further comprising:

said logic using said average causal delay to parameterize a service time distribution for said pair of second and third nodes.

46. The method of claim 45 wherein said determining probability of a causal link between said pair of messages comprises:

said logic assigning a probability to each potential causal link found in said trace of communication messages based on the parameterized service time distribution for said pair of second and third nodes in said causal links.

47. The method of claim 42 further comprising:

determining by said logic, an overall probability that said at least one causal path is accurate.

48. The method of claim 47 wherein said determining an overall probability comprises:

determining, by said logic, said overall probability as a product of probabilities of said plurality of causal links included in the at least one formed causal path.

49. The method of claim 42 wherein said forming at least one causal path comprises:

classifying by said logic, each causal link as probably true, probably false, or try-both, wherein said classifying is based at least in part on said determined probability of said causal link.

50. The method of claim 49 wherein said forming at least one causal path further comprises:

including, in a formed causal path, said causal links classified as probably true; and

for each causal link classified as try-both, forming a first causal path that includes such try-both causal link and forming a second causal path that does not include such try-both causal link.

51. A method comprising:

receiving a trace of communication messages between nodes in a distributed computing environment;

estimating an average causal delay for one or more pairs of nodes in the trace;

inferring causal relationships between messages and assigning corresponding confidence scores to each inferred causal relationship; and

forming at least one causal path from the inferred causal relationships.

52. The method of claim 51 further comprising:

assigning corresponding confidence scores to each of the at least one causal path.

53. The method of claim 52 wherein said assigning corresponding confidence scores comprises:

determining confidence scores as a product of probabilities of said inferred causal relationships included in the formed at least one causal path.

54. The method of claim 51 wherein said estimating an average causal delay comprises:

determining, for each pair of messages from a first node to a second node and from said second node to a third node, an amount of delay from receipt of said preceding message by said second node to the transmission of said later message from said second node to said third node; and

averaging the determined delays to estimate said average causal delay for each said pair of second and third nodes.

55. A method comprising:

receiving a trace of messages between nodes of a distributed computing environment;

estimating a standard delay for at least one pair of nodes in said trace, wherein said standard delay is estimated as a function of a delay from receipt of an immediately preceding message by said first node to the transmission of a message from said first node to said second node; and

based at least in part on said standard delay for said at least one pair of nodes, inferring a causal path comprising a plurality of causal links.

56. The method of claim 55 wherein said estimating said standard delay further comprises:

determining, for each of said pairs of nodes found in said trace, said delay from receipt of an immediately preceding message by said first node to the transmission of a message from said first node sending to said second node; and

averaging the determined delays to estimate said standard delay for said pair of nodes.

57. The method of claim 55 further comprising:

using said average causal delay to parameterize a service time distribution for said pair of nodes.

58. The method of claim 57 wherein said inferring comprises:

assigning a probability to each potential causal link found in said trace of messages based on the parameterized service time distribution for the pair of nodes comprising the second and third nodes in such causal link.

59. The method of claim 58 further comprising:

determining an overall probability that the inferred causal path is accurate.

60. The method of claim 59 wherein said determining an overall probability comprises:

determining said overall probability as a product of probabilities of said plurality of causal links included in the inferred causal path.