Constructing an inference graph for a network

• US 8,443,074 B2
• Filed: 02/28/2008
• Issued: 05/14/2013
• Est. Priority Date: 03/06/2007
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Chandra, Ranveer, Maltz, David A., Zhang, Ming, Greenberg, Albert, Kandula, Srikanth
• Primary Examiner(s): Patel, Chirag R
• Application Number:
  US12/039,714
• Publication Number:
  US 20080222287A1
• Time in Patent Office: 1,902 Days
• Field of Search: 714733-736, 714/4, 703/2, 703/22, 706/21, 706/52, 706/46, 709217-219, 709223-226, 715/734, 715/736, 715/771, 715/853
• US Class Current: 709/224
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/5058 Service discovery by the service manager

Abstract

Constructing an inference graph relates to the creation of a graph that reflects dependencies within a network. In an example embodiment, a method includes determining dependencies among components of a network and constructing an inference graph for the network responsive to the dependencies. The components of the network include services and hardware components, and the inference graph reflects cross-layer components including the services and the hardware components. In another example embodiment, a system includes a service dependency analyzer and an inference graph constructor. The service dependency analyzer is to determine dependencies among components of a network, the components including services and hardware components. The inference graph constructor is to construct an inference graph for the network responsive to the dependencies, the inference graph reflecting cross-layer components including the services and the hardware components.

Claims

1. A method, implemented by a processor, comprising:

determining dependencies among components of a network, the components including services and hardware components;

constructing an inference graph for the network responsive to the dependencies, the inference graph reflecting cross-layer components including the services and the hardware components, each of the services having one of three states comprising an up state when a response time is within a normal range, a down state when service requests result in an error status code or no response at all, and a troubled state when the response time fails to meet a predetermined performance goal; and

incorporating a load-balancing mechanism and a failover mechanism present in the network to the inference graph.

2. The method as recited in claim 1, wherein the act of determining comprises:

monitoring messages exchanged between endhosts of the network; and

capturing the dependencies among the components of the network based on the messages.

3. The method as recited in claim 2, wherein the act of monitoring comprises at least one act of:

monitoring the messages using agents executing on multiple endhost machines of the network;

or

monitoring the messages using packet sniffers at multiple hardware components of the network, the multiple hardware components including network elements and endhost machines.

4. The method as recited in claim 2, further comprising:

building service-level dependency graphs responsive to the dependencies that are captured among the components of the network by the act of capturing;

wherein the act of constructing comprises constructing the inference graph by combining the service-level dependency graphs.

5. The method as recited in claim 4, wherein the act of constructing further comprises:

constructing the inference graph using topology information for the network.

6. The method as recited in claim 2, wherein the acts of monitoring and capturing comprise:

computing the dependencies based on the messages that are detected by the act of monitoring and responsive to times or differences between the times at which the messages are detected.

7. The method as recited in claim 6, wherein the act of capturing further comprises:

rejecting a reported dependency on a given service as a false positive or replacing a reported dependency on a given service as a false negative based on a statistical analysis of respective message exchanges between a given endhost that corresponds to the given service and respective ones of other endhosts.

8. The method as recited in claim 6, wherein the act of computing comprises:

computing the dependencies based on the messages that are detected by the act of monitoring and responsive to a predefined dependency interval.

9. The method as recited in claim 8, wherein the act of computing further comprises:

rejecting a potential dependency on a given service as a false positive based on an average interval of a repeated message exchange to a given endhost that corresponds to the given service and responsive to a length of the predefined dependency interval.

10. The method as recited in claim 2, wherein the act of constructing comprises:

constructing the inference graph to include at least three different types of nodes, the three different types of nodes comprising;

root-cause nodes that correspond to hardware components or services whose failure or degradation can impact user-perceptible performance;

observation nodes that represent accesses to services of the network; and

meta-nodes that model dependencies between the observation nodes and the root-cause nodes.

11. The method as recited in claim 10, wherein the act of constructing further comprises:

constructing the inference graph to include meta-nodes that model dependency relationships between nodes of the inference graph other than noisy-max.

12. The method as recited in claim 10, wherein the act of constructing further comprises:

constructing the inference graph to include edges that interconnect the root-cause nodes, the observation nodes, and the meta-nodes;

wherein a particular edge from a first node to a second node encodes a probabilistic dependency in which a probability indicates how likely it is that a state of the first node affects a state of the second node.

13. A system comprising:

a memory;

one or more processors coupled to the memory;

a service dependency analyzer, stored in the memory and operable on the one or more processors, to determine dependencies among components of a network, the components including services and hardware components, each of the services associated with one of three states that include an up state when a response time is within a normal range, a down state when service requests result in an error status code or no response at all, and a troubled state when the response time fails to meet a predetermined performance goal; and

an inference graph constructor to construct an inference graph for the network responsive to the dependencies, the inference graph reflecting cross-layer components including the services and the hardware components and incorporating a load-balancing mechanism and a failover mechanism present in the network.

14. The system as recited in claim 13, wherein the service dependency analyzer comprises:

a packet trace obtainer to monitor messages exchanged between endhosts of the network; and

a service dependency determiner to capture the dependencies among the components of the network based on the messages.

15. The system as recited in claim 14, wherein the service dependency analyzer further comprises:

a service-level dependency graph builder to build service-level dependency graphs responsive to the dependencies that are captured among the components of the network by the service dependency determiner, each service-level dependency graph reflecting one or more respective dependency probabilities between a specified service and one or more respective dependent services on which performance of the specified service depends probabilistically;

wherein the inference graph constructor is further to construct the inference graph by combining the service-level dependency graphs.

16. A method, implemented by a processor, comprising:

determining dependencies among components of a network by monitoring messages exchanged between endhosts of the network and by capturing the dependencies among the components of the network based on the messages, the components including at least one of services or hardware components, the services comprising one of three states that include an up state when a response time is within a normal range, a down state when service requests result in an error status code or no response at all, and a troubled state when the response time fails to meet a predetermined performance goal; and

constructing an inference graph for the network responsive to the dependencies,

the inference graph including root-cause nodes, observation nodes, and meta-nodes;

wherein;

the root-cause nodes correspond to services whose failure or degradation can impact user-perceptible performance of the network;

the observation nodes represent accesses to services of the network; and

the meta-nodes model dependencies between the observation nodes and the root-cause nodes.

17. The method as recited in claim 16, wherein:

the act of capturing comprises computing a dependency probability, which reflects a probability that accessing a specified service is dependent on accessing a dependent service, responsive to a frequency at which accesses to the specified service and to the dependent service co-occur in time and based on time differences between the co-occurrences.

18. The method as recited in claim 16, wherein the act of constructing comprises:

creating a meta-node to represent a specified service that is to be monitored;

creating an observation node corresponding to an endhost client that is to report response time observations for the specified service; and

making the meta-node a parent of the observation node.

19. The method as recited in claim 18, wherein the acts of creating a meta-node, creating an observation node, and making the meta-node a parent of the observation node comprise:

merging the meta-node with the observation node by incorporating one or more probabilities associated with the meta-node into the observation node.

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

adding a service meta-node for each dependent service on which the specified service depends;

recursively adding service meta-nodes for services on which each dependent service of the specified service is dependent; and

creating respective root-cause nodes corresponding to respective endhosts that provide the specified service, at least one of the dependent services, or at least one of the services on which a dependent service depends.