Methods and systems for removing data inconsistencies for a network simulation

• US 20050204028A1
• Filed: 06/30/2004
• Published: 09/15/2005
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Qiu, Lili, Zhou, Lidong, Rao, Ananth Rajagopala
• Granted Patent: US 7,613,105 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• 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/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A network troubleshooting framework is described. In an implementation, a method includes forming a plurality of reports by a plurality of nodes in a network, wherein each of the reports is formed by a respective one of the nodes and includes trace data obtained from the respective node and another of the nodes. An inconsistency is detected in the trace data in one of the reports when compared with corresponding trace data in another of the reports. A set of the nodes is found that formed one or more of the reports having the inconsistency in the trace data.

Claims

1. A method comprising:

forming a plurality of reports by a plurality of nodes in a network, wherein each said report;

is formed by a respective said node; and

includes trace data obtained from the respective said node and another said node;

detecting an inconsistency in the trace data in one said report when compared with corresponding said trace data in another said report; and

finding a set of said nodes that formed one or more said reports having the inconsistency in the trace data.

2. A method as described in claim 1, wherein each of the plurality of nodes perform neighbor monitoring.

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

constructing an inconsistency graph for the detected inconsistency having vertices that reference one or more said nodes;

adding an edge between two said vertices if referenced said nodes report inconsistent trace data; and

deriving a set of said nodes that explain the detected inconsistency as a set of said vertices in the inconsistency graph having a fewest number of said vertices that cover the inconsistency graph.

4. A method as described in claim 3, wherein the deriving is performed as a minimum vertex cover problem.

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

7. A method as described in claim 1, wherein the trace data describes information about network topology, routing, traffic statistics, physical meium, and network performance.

8. A method as described in claim 1, wherein the trace data

is provided by a trace utility.

9. A method as described in claim 1, wherein the trace data is selected from the group consisting of:

network topology;

traffic statistics;

physical medium; and

network performance.

10. A method as described in claim 1, further comprising supplying said trace data after removing the data from the nodes that are identified as supplying inconsistent information to a simulator to form a network simulation of the network.

11. A method as described in claim 10, wherein the network simulation is configured to output one or more network performance values that approximate corresponding network performance values observed from the network.

12. One or more computer readable media comprising computer executable instructions that, when executed on a computer, direct the computer to perform the method as described in claim 1.

6. (canceled)

13. A method comprising:

noting an inconsistency in at least one network setting included in one or more of a plurality of reports, wherein;

each said report is provided by a respective one of a plurality of nodes in a network; and

each said node performs neighbor monitoring;

constructing an inconsistency graph for the noted inconsistency that references one or more said nodes; and

finding a set of said nodes referenced in the inconsistency graph that explain the inconsistency.

14. A method as described in claim 13, wherein the finding includes deriving a set of said nodes that explain the inconsistency as a smallest set of vertices that cover the inconsistency graph, wherein each said vertex corresponds to a respective one said node.

15. A method as described in claim 14, wherein the deriving is performed as a minimum vertex cover problem.

16. A method as described in claim 13, wherein the at least one network setting includes information about network topology, routing, traffic statistics, physical medium, and network performance.

17. A method as described in claim 13, wherein the at least one network setting

is provided by a trace utility.

18. A method as described in claim 13, wherein the at least one network setting includes trace data that is selected from the group consisting of:

network topology including routing;

traffic statistics;

physical medium; and

network performance.

19. A method as described in claim 13, further comprising supplying corresponding said network settings from the reports after removing the reports from the nodes that are identified as supplying inconsistent information to a simulator to form a network simulation of the network.

20. A method as described in claim 19, wherein the network simulation is configured to output one or more network performance values that approximate corresponding network performance values observed from the network.

21. One or more computer readable media comprising computer executable instructions that, when executed on a computer, direct the computer to perform the method as described in claim 13.

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

one or more said nodes include a data collection module that is executable thereon to;

collect trace data from at least two said nodes; and

form a report that includes the collected trace data for communication over the network; and

at least one said node includes a manager module that is executable thereon to;

receive each said report;

detect an inconsistency in the trace data in one said report when compared with corresponding said trace data in another said report; and

find a set of said nodes that formed each said report having the inconsistent trace data.

23. A system as described in claim 22, wherein the manager module is executable on a first said node to collect trace data from the first said node and a second said node that is communicatively coupled via the network to the first said node.

24. A system as described in claim 22, wherein the at least two said nodes perform neighbor monitoring.

25. A system as described in claim 22, wherein the manager module is executable to detect the inconsistency by:

constructing an inconsistency graph for the detected inconsistency that references one or more said nodes; and

deriving a set of said nodes that explain the inconsistency as a smallest set of vertices that cover the inconsistency graph, wherein each said vertex corresponds to a respective said node.

26. A system as described in claim 25, wherein the deriving is performed as a minimum vertex cover problem.

27. A system as described in claim 22, wherein the network is a multi-hop wireless network.

29. A system as described in claim 22, wherein the trace data describes information about network topology, routing, traffic statistics, physical medium, and network performance.

30. A system as described in claim 22, wherein the trace data

is provided by a trace utility.

31. A system as described in claim 22, wherein the trace data is selected from the group consisting of:

network topology including routing;

traffic statistics;

physical medium; and

network performance.

32. A system as described in claim 22, further comprising supplying said trace data that after removing the data from the nodes that are identified as supplying inconsistent data to form a network simulation of the network.

33. A system as described in claim 32, wherein the network simulation is configured to output one or more network performance values that approximate corresponding network performance values observed from the network.

28. (canceled)

34. A node comprising:

a processor;

a network connection device configured to communicatively couple the processor with a network; and

memory configured to maintain a manager module that is executable on the processor to;

collect a plurality of reports at the network connection device from the network, wherein each said report;

is formed by a respective one of a plurality of nodes in the network; and

describes one or more network settings of the respective said node and another said node;

remove an inconsistency in at least one said network setting of one said report when compared with a corresponding said network setting in another said report to form clean network settings; and

supply the clean network settings to a network simulation so that the network simulation is configured to provide a network simulation of the network.

35. A node as described in claim 34, wherein the manager module is executable on the processor to remove the inconsistency by deriving a set of said nodes that explain the inconsistency as a smallest set of vertices that cover an inconsistency graph, wherein each said vertex corresponds to a respective said node.

36. A node as described in claim 35, wherein the deriving is performed as a minimum vertex cover problem.

37. A node as described in claim 34, wherein the at least one network setting includes trace data that describes information about network topology, routing, traffic statistics, physical medium, and network performance.

38. A node as described in claim 34, wherein the at least one network setting

is provided by a trace utility.

39. A node as described in claim 34, wherein the at least one network setting includes trace data that is selected from the group consisting of:

network topology including routing;

traffic statistics;

physical medium; and

network performance.

40. A node as described in claim 34, wherein the network is configured as a wireless mesh network.