Inferring candidates that are potentially responsible for user-perceptible network problems

• US 8,015,139 B2
• Filed: 02/28/2008
• Issued: 09/06/2011
• Est. Priority Date: 03/06/2007
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Microsoft Corporation
• Inventors: Kandula, Srikanth, Maltz, David A., Bahl, Paramvir, Chandra, Ranveer, Zhang, Ming, Greenberg, Albert
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): OLUDE AFOLABI, OLATOYOSI
• Application Number:
  US12/039,703
• Publication Number:
  US 20080222068A1
• Time in Patent Office: 1,286 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

Candidates that are potentially responsible for user-perceptible network problems may be inferred. In an example embodiment, a system includes an inference engine to produce a list of candidates that are potentially responsible for user-perceptible network problems, with the candidates being network components that may include both services and network elements. A response to a service request may be a non response, an incorrect response, an untimely correct response, or a timely correct response. The user-perceptible network problems may include the untimely correct response as well as the non response and the incorrect response. In another example embodiment, a method includes monitoring a network and producing a list of candidates that are potentially responsible for user-perceptible network problems. The candidates of the list may include both services and network elements of the monitored network.

Claims

1. A system comprising:

a processor;

an inference graph having multiple nodes, each node being associated with two or more possible states, a current state of a node being a probability distribution over the two or more possible states, the inference graph reflecting cross-layer components of a network and including multiple root-cause nodes, each root-cause node corresponding to a hardware component or a service whose failure or degradation can cause user-perceptible network problems; and

an inference engine executed on the processor to produce from the inference graph, a list of candidates that are potentially responsible for user-perceptible network problems.

2. The system as recited in claim 1, wherein the inference graph further includes one or more observation nodes, each observation node corresponding to at least one measureable quantity of the network.

3. The system as recited in claim 1, wherein:

the two or more possible states comprise an up state, a down state, and a troubled state;

nodes in the up state correspond to timely correct responses to service requests, nodes in the down state correspond to non responses to service requests and incorrect responses to service requests, and nodes in the troubled state correspond to untimely correct responses to service requests; and

the down state and the troubled state each represent a user-perceptible network problem.

4. The system as recited in claim 2, wherein the inference engine comprises:

a candidate ascertainer to ascertain multiple assignment vectors for candidate states of root-cause nodes of the inference graph;

a state propagator to determine probability distributions for observation nodes of the inference graph for each of the multiple assignment vectors;

a score calculator to calculate a respective score for each respective assignment vector based on respective ones of the probability distributions and responsive to observed values of the observation nodes; and

a candidate selector to select the multiple assignment vectors for the candidate states for the list of candidates using the calculated scores, the list of candidates to include a determinable number of top candidates.

5. The system as recited in claim 2, wherein the at least one measurable quantity to which each observation node corresponds is selected from a group of measurable quantities including:

response time, link utilization, rate or number of events, number of errors, and machine room temperature.

6. The system as recited in claim 4, wherein the candidate selector is to accumulate repeated selections of a particular assignment vector for particular candidate states that corresponds to at least one particular user-perceptible network problem and is to report the particular assignment vector as a recurring source of the at least one particular user-perceptible network problem.

7. The system as recited in claim 6, wherein the inference engine is to report on impacts of the at least one particular user-perceptible network problem corresponding to the particular assignment vector by reporting a set of impacts that include:

a number of effected users, an average duration, and a frequency of occurrence of the at least one particular user-perceptible network problem.

8. The system as recited in claim 4, wherein the state propagator is further to propagate probabilistic states for noisy-max meta-nodes of the inference graph in linear time for a given number of parents using one or more approximation techniques that involve:

(i) computing a probability that a child is up based on a property that a child is up when it does not depend on any parents that are not up or (ii) computing a probability that a child is down based on a property that a child is down unless each of its parents are not down or the child does not depend on them when they are down.

9. The system as recited in claim 4, wherein the candidate ascertainer is further to ascertain the multiple assignment vectors for the candidate states by setting a number of simultaneously faulty root-cause nodes of the inference graph to a predetermined maximum number.

10. The system as recited in claim 4, wherein the inference engine further comprises:

a significance tester to filter alerts on possible user-perceptible network problems based on a statistical technique that is responsive (i) to particular scores for particular assignment vectors for particular candidate states and (ii) to baseline scores for a baseline assignment vector for candidate states in which each of the root-cause nodes are given to correspond to an up state;

wherein the significance tester calculates the particular scores and the baseline scores over time using different sets of observation evidence.

11. The system as recited in claim 4, wherein the inference engine further comprises:

an inference graph pre-processor to pre-compute the probability distributions for the observation nodes of the inference graph given that each of the root-cause nodes corresponds to an up state;

wherein the state propagator is to determine the probability distributions for the observation nodes of the inference graph for each of the multiple assignment vectors by re-computing probability distributions for those observation nodes having a state change to at least one ancestral node and by maintaining the pre-computed probability distributions for those observation nodes that do not have a state change to an ancestral node.

12. A method comprising:

monitoring a network in which a response to a service request is selected from a group of responses comprising;

a non response, an incorrect response, an untimely correct response, and a timely correct response, the non-response, the incorrect response, and the untimely correct response each considered a user-perceptible network problem; and

using an inference graph to produce a list of candidates that are potentially responsible for user-perceptible network problems, the candidates comprising network components including services and network elements, the inference graph including;

root-cause nodes that correspond to hardware components or services whose failure or degradation can cause the user-perceptible network problems; and

observation nodes that represent at least accesses to the services of the network.

13. The method as recited in claim 12, wherein

each node is associated with two or more possible states and corresponds to an actual state that is a probability distribution over the two or more possible states.

14. The method as recited in claim 12, wherein using the inference graph to produce the list of candidates further comprises:

ascertaining multiple assignment vectors for candidate states of the root-cause nodes of the inference graph;

determining probability distributions for the observation nodes of the inference graph for each of the multiple assignment vectors;

calculating a respective score for each respective assignment vector based on respective ones of the probability distributions and responsive to observed values of the observation nodes; and

selecting at least one candidate from the multiple assignment vectors for the candidate states for the list of candidates using the calculated scores, the list of candidates to include a determinable number of top candidates.

15. A method comprising:

ascertaining multiple assignment vectors for candidate states of root-cause nodes of an inference graph, the inference graph reflecting cross-layer components including services and hardware components of a network, the root-cause nodes corresponding to the hardware components or the services whose failure or degradation can cause user-perceptible network problems;

determining probability distributions for observation nodes of the inference graph for each of the multiple assignment vectors, each of the observation nodes corresponding to at least one measurable quantity of the network;

calculating a respective score for each respective assignment vector based on respective ones of the probability distributions and responsive to observed values of the observation nodes; and

selecting at least one candidate from the multiple assignment vectors for the candidate states for a list of candidates using the calculated scores, the list of candidates to include a determinable number of top candidates.

16. The method as recited in claim 15, further comprising:

calculating baseline scores for a baseline assignment vector for candidate states in which each of the root-cause nodes are given to correspond to an up state;

determining a particular assignment vector of the multiple assignment vectors for particular candidate states that has a particular score indicating that the particular assignment vector is likely to represent a user-perceptible network problem;

creating a probability distribution responsive to differences between the baseline scores and multiple instances of the particular score over time using different sets of observation evidence; and

applying a statistical technique to filter alerts to those that are significant given the probability distribution and based on at least one predefined criterion.

17. The method as recited in claim 15, wherein the act of calculating comprises:

calculating each respective score for each respective assignment vector by assigning a relatively higher score at each observation node having an observed value that statistically matches the corresponding probability distribution and assigning a relatively lower score at each observation node having an observed value that fails to statistically match the corresponding probability distribution.

18. The method as recited in claim 15, further comprising:

pre-processing the inference graph to pre-compute the probability distributions for each of the observation nodes of the inference graph given that each of the root-cause nodes corresponds to an up state;

wherein the act of determining comprises;

applying the multiple assignment vectors to the root-cause nodes of the inference graph; and

propagating states to determine the probability distributions for the observation nodes by computing a probability distribution for those observation nodes with at least one ancestral node having a state change resulting from the applied assignment vector.

19. The method as recited in claim 18, wherein the act of propagating comprises:

propagating probabilistic states for noisy-max meta-nodes of the inference graph in linear time for a given number of parents using one or more approximation techniques that involve;

(i) computing a probability that a child is up based on a property that a child is up when it does not depend on any parents that are not up or (ii) computing a probability that a child is down based on a property that a child is down unless each of its parents are not down or the child does not depend on them when they are down;

wherein each of the observation nodes converts the corresponding at least one measurable quantity into a probability distribution over two or more states.

20. The method as recited in claim 18, wherein the act of propagating comprises:

propagating probabilistic states for noisy-max meta-nodes of the inference graph in linear time for a given number of parents responsive to a product of respective values corresponding to each respective parent;

each respective value based on up, down, and troubled probabilities of the corresponding respective parent; and

propagating probabilistic states for selector meta-nodes and fail-over meta-nodes of the inference graph that correspond to load balancing infrastructure and redundancy mechanisms, respectively, of the network;

wherein meta-nodes of the inference graph are to model dependencies between the observation nodes and the root-cause nodes.