Fault detection and diagnosis

• US 7,583,587 B2
• Filed: 06/30/2004
• Issued: 09/01/2009
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Qiu, Lili, Rao, Ananth Rajagopala, Bahl, Paramvir, Zhou, Lidong
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Faroul; Farah
• Application Number:
  US10/881,695
• Publication Number:
  US 20050169185A1
• Time in Patent Office: 1,889 Days
• Field of Search: 370/216, 370/241, 370/242, 370/245, 714/37, 714/43
• US Class Current: 370/216
• CPC Class Codes: G05B 23/0256 injecting test signals and analyzing monitored process response, e.g. injecting the test signal while interrupting the normal operation of the monitored system; superimposing the test signal onto a control signal during normal operation of the monitored system
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/0829 Packet loss

Abstract

A network troubleshooting framework is described. In an implementation, a method includes detecting discrepancy in operation of a network by supplying data that describes the network to a network simulation so that the network simulation provides an estimation of network performance. A determination is made as to whether the estimation of network performance differs from observed network performance of the network. A root cause of the discrepancy is diagnosed by injecting one or more of a plurality of faults into the network simulation until the estimation of network performance approximates the observed network performance.

Claims

1. A method comprising:

detecting a discrepancy in operation of an actual network by;

supplying trace data that describes the actual network to a network simulator in order for the network simulator to provide an estimate of a simulated network performance of a trace-driven simulation of the actual network, the trace data being collected through operation of the actual network and comprising one or more of network topology data, traffic statistics data, physical medium data, and network operation data of the actual network, wherein the simulated network is;

implemented by software to perform traffic load simulation, routing simulation, signal strength simulation, and fault injection simulation of the actual network; and

configured to reflect an accurate depiction of the actual network based on the collected trace data of the actual network; and

determining the estimate of the simulated network performance differs from an observed network performance of the actual network; and

diagnosing a root cause of the discrepancy by injecting one or more of a plurality of faults into the simulated network until the estimate of the simulated network performance approximates the observed actual network performance.

2. A method as described in claim 1, wherein the determining includes ascertaining whether the estimate of the simulated network performance differs from the observed network performance of the actual network by more than a corresponding threshold.

3. A method as described in claim 1, wherein the diagnosing includes:

translating the difference between the estimated and the observed network performances into a fault magnitude; and

determining if the fault magnitude moves the simulated network to approximate the observed network performance of the actual network.

4. A method as described in claim 1, wherein the diagnosing includes:

translating the difference between the estimated and the observed network performances into a fault magnitude;

determining whether the fault magnitude is less than a corresponding threshold; and

when the fault magnitude is less than the corresponding threshold, removing a fault from a fault set that is utilized as an input to the simulated network.

5. A method as described in claim 1, wherein the diagnosing includes:

making an initial diagnosis to generate an initial fault set; and

iteratively refining the initial fault set to arrive at a current fault set that, when utilized as an input by the network simulation, causes the estimate of network performance provided by the simulated network to approximate the observed network performance of the actual network.

6. A method as described in claim 1, wherein the actual network is a multi-hop wireless network.

7. A method as described in claim 1, wherein the actual network is a wired network.

8. A method as described in claim 1, wherein the trace data describes a route formed by a series of hops taken by a data packet through the network between an originating node and a target node of the actual network.

9. A computer readable medium comprising computer executable instructions that, when executed by a computer, direct the computer to perform the method of claim 1.

10. A method comprising:

estimating a performance of an actual network by execution of a network simulator to provide a simulated network that uses one or more network settings obtained from the actual network as an input, the one or more network settings being collected through operation of the actual network and comprising network topology data, traffic statistics data, physical medium data, and network operation data of the actual network, wherein the simulated network is;

implemented by software to perform traffic load simulation, routing simulation, signal strength simulation, and fault injection simulation of the actual network, and

configured to reflect an accurate depiction of the actual network based on the one or more network settings of the actual network; and

when a difference between the estimated network performance of the simulated network and observed network performance of the actual network is greater than a corresponding threshold;

making an initial diagnosis to generate an initial fault set; and

iteratively refining the initial fault set to arrive at a current fault set that, when utilized as an input by the network simulation, causes the simulated network to output another estimate of network performance that approximates the network performance of the actual network.

11. A method as described in claim 10, wherein the initial diagnosis is performed by utilizing a decision tree to determine a fault type.

12. A method as described in claim 10, wherein the iterative refining of the initial fault set to arrive at the current fault set is performed by:

computing, for each fault in the current fault set, a fault magnitude from a difference in the observed network performance of the actual network and an estimated network performance caused by including the fault in the simulated network; and

removing each said fault having a respective said fault magnitude that is less than a corresponding threshold.

13. A method as described in claim 10, wherein the network settings include data that describes a route formed by a series of hops taken by a data packet through the network between an originating node and a target node of the actual network.

14. A method as described in claim 10, wherein the current fault set describes one or more root causes of the difference between the estimated network performance of the simulated network and observed network performance of the actual network.

15. A method as described in claim 10, wherein at least one said network setting is provided by a trace utility.

16. A method as described in claim 10, wherein the iterative refining of the initial fault set to arrive at the current fault set is performed by:

adding one of a plurality of faults to the current fault set;

estimating network performance using the simulated network and the current fault set; and

determining whether the estimated network performance that was estimated using the current fault set converges with the observed network performance of the actual network.

17. A computer readable medium comprising computer executable instructions that, when executed by a computer, direct the computer to perform the method of claim 10.

18. A computer readable medium comprising computer executable instructions that, when executed on a computer, direct the computer to perform a method comprising:

establishing whether an observation of network performance of an actual network differs from an estimate of network performance output by a simulated network that simulates the actual network, wherein;

network settings comprising one or more of network topology data, traffic statistics data, physical medium data, and network operation data of the actual network are collected through operation of the actual network and supplied to the simulated network; and

the simulated network is implemented by software and configured to reflect an accurate depiction of the actual network based on the collected network settings; and

if so, determining a root cause of the difference by adding or removing one or more faults from a fault set until the fault set, when utilized by the simulated network, causes the simulated network to provide another estimate of network performance that approximates the observation of network performance of the actual network.

19. A computer readable medium as described in claim 18, wherein the method further comprises:

obtaining data that describes one or more network settings of the actual network;

supplying the obtained data to a simulator to provide the simulated network; and

receiving the estimate of network performance of the simulated network from the simulator.

20. A computer readable medium as described in claim 18, wherein the root cause of the difference is determined by:

computing, for each fault in the fault set, a fault magnitude from a difference in observed network performance of the actual network and estimated network performance caused by including the fault in the simulated network; and

removing each said fault in the fault set having a respective said fault magnitude that is less than a corresponding threshold.

21. A computer readable medium as described in claim 18, wherein the simulated network is generated from network settings that describe a route formed by a series of hops taken by a data packet through the network between an originating node and a target node of the actual network.

22. A computer readable medium as described in claim 18, wherein the simulated network is generated from network settings that are provided by a trace utility which collects information that describes network topology, routing, traffic statistics, physical medium and network performance of the actual network.

23. A system comprising a plurality of nodes that are communicatively coupled, one to another, to form a real network, wherein:

each of the plurality of nodes comprises at least a processor and memory coupled to the processor;

one or more nodes from the plurality of nodes include an agent module that is executable on the processor of each of the one or more nodes to perform a first method comprising;

collecting network settings comprising network topology settings, traffic statistics settings, physical medium settings, and network operation settings; and

forming a communication that includes the network settings for communication over the network; and

at least one node from the plurality of nodes includes a manager module that is executable on the processor of the one node to perform a second method comprising;

receiving the communication;

generating a simulation of the real network based on the network settings obtained from the communication, wherein the simulation of the real network is implemented by software executable on the processor of the one node and the simulation of the real network is configured to reflect an accurate depiction of the real network by retrieving the network settings from the received communication;

detecting a fault in real network operation by comparing an estimate of network performance of the simulation of the real network with an observation of network performance of the real network; and

diagnosing the fault by injecting one or more of a plurality of faults into the simulation of the real network until the estimate of network performance of the simulation approximates the observation of the real network.

24. A system as described in claim 23, wherein at least two said nodes include a respective said manager module.

25. A system as described in claim 23, wherein each said node includes a respective said agent module.

26. A system as described in claim 23, wherein the manager module is further executable to perform a method comprising:

deriving a corrective action based on the detected fault; and

causing the agent module to perform the corrective action.

27. A system as described in claim 23, wherein the fault in network operation is detected by determining whether a difference between the estimate of the simulation of the real network and the observation of the real network is more than a corresponding threshold.

28. A system as described in claim 23, wherein the manager module is further executable to diagnose the fault by:

translating a difference between the estimate of the simulation of the real network and the observation of the real network into a fault magnitude; and

determining if the fault magnitude moves the estimate provided by the simulation of the network to approximate the observation of the real network.

29. A system as described in claim 23, wherein the manager module is further executable to diagnose the fault by:

translating a difference between the estimate of the simulation of the real network and the observation of the real network into a fault magnitude; and

determining whether the fault magnitude is less than a corresponding threshold; and

when the fault magnitude is less than the corresponding threshold, removing a fault from a fault set that is utilized as an input by the generated simulation of the real network to produce the estimate.

30. A system as described in claim 23, wherein the manager module is further executable on the processor to diagnose the fault by:

making an initial diagnosis to generate an initial fault set;

iteratively refining the initial fault set to arrive at a current fault set that, when utilized as an input by the simulation of the real network, causes the estimate performance of the simulation of the real network to approximate the observation of performance of the real network.

31. A system as described in claim 23, wherein the real network is a mesh network;

and each node in the mesh network is configured to share an Internet gateway.

32. A system as described in claim 23, wherein the network settings describe a route formed by a series of hops taken by a data packet through the network between an originating said node and a target said node of the real network.

33. A node comprising:

means for managing operation of an actual network having a plurality of means for routing data packets, wherein;

each said routing means is communicatively coupled to another said routing means; and

the means for managing operation of the actual network includes;

means for simulating the actual network configured to provide a simulated network of the actual network, the simulated network being implemented by software;

means for providing network settings obtained from the actual network to the means for simulating the actual network, wherein;

the network settings comprise network topology data, traffic statistics data, physical medium data, and network operation data; and

the means for simulating the actual network is configured to reflect an accurate depiction of the actual network based on the obtained network settings;

means for receiving an output from the means for simulating the actual network, wherein the output estimates network performance of the simulated network;

means for detecting a fault by comparing the output of network performance of the simulated network with an observation of network performance of the actual network; and

means for diagnosing the fault configured to diagnose by injecting one or more of a plurality of faults into the simulated network until estimate of network performance of the simulated network approximates the observation of network performance of the actual network.

34. A node as described in claim 33, wherein the actual network is a mesh network;

and each said routing means in the mesh network is configured to share an Internet gateway.

35. A node as described in claim 33, wherein the managing means further includes means for deriving a corrective action based on the detected fault;

and causing at least one said routing means to perform the corrective action.