Methods and systems for removing data inconsistencies for a network simulation

• US 7,613,105 B2
• Filed: 06/30/2004
• Issued: 11/03/2009
• 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
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Faroul; Farah
• Application Number:
  US10/881,751
• Publication Number:
  US 20050204028A1
• Time in Patent Office: 1,952 Days
• Field of Search: 370/242, 370/244, 370/245, 714/25, 709/223
• US Class Current: 370/216
• 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, each node comprising a processor, a memory, and a network connection device interconnecting the nodes in a network, wherein each report;

is formed by a respective node; and

includes trace data obtained from the respective node and at least one other node;

detecting by the processor an inconsistency in the trace data in a first report when compared with corresponding said trace data in a second report, wherein the detecting comprises;

constructing an inconsistency graph having vertices that reference one or more nodes;

adding an edge between at least two of the vertices if the referenced one or more nodes report inconsistent trace data; and

deriving a set of nodes that explain the inconsistent trace data that is reported as a set of vertices in the inconsistency graph having a fewest number of vertices that cover the inconsistency graph; and

finding a set of nodes that formed at least the first and second 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 deriving is performed as a minimum vertex cover problem, wherein the minimum vertex cover problem identifies the smallest set of vertices representing misbehaving nodes.

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

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

6. A method as described in claim 1, wherein the trace data is provided by a trace utility.

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

network topology;

traffic statistics;

physical medium; and

network performance.

8. 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.

9. A method as described in claim 8, wherein the network simulation outputs one or more network performance values that approximate corresponding network performance values observed from the network.

10. A computer readable storage medium storing computer executable instructions that, when executed on a computer, configure the computer to perform the method as described in claim 1.

11. A method comprising:

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

each report is provided by a respective one of a plurality of nodes, each node comprising a processor, a memory, and a network connection device interconnecting the nodes in a network; and

each one of the plurality of nodes performs neighbor monitoring;

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

finding a set of nodes referenced in the inconsistency graph that explain the inconsistency, wherein the finding comprises the processor deriving the set of nodes that explain the inconsistency as a smallest set of vertices that cover the inconsistency graph, wherein each vertex corresponds to a respective node; and

supplying corresponding 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.

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

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

14. A method as described in claim 11, wherein the at least one network setting is provided by a trace utility.

15. A method as described in claim 11, 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.

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

17. A computer readable storage medium storing computer executable instructions that, when executed on a computer, configure the computer to perform the method as described in claim 11.

18. A system comprising a plurality of nodes, each node comprising a processor, a memory, and a network connection device, that are communicatively coupled, one to another, to form a network, wherein:

one or more of the plurality of nodes includes a data collection module, wherein the data collection module performs acts comprising;

collecting trace data from at least two of the plurality of nodes; and

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

at least one node includes a manager module that;

receives each report;

detects an inconsistency in the trace data in one report when compared with corresponding trace data in another report, wherein detecting the inconsistency comprises;

constructing an inconsistency graph that references one or more nodes; and

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

finds a set of nodes that formed each report having the inconsistent trace data; and

supplies the collected trace data after removing the data from the nodes that are identified as supplying inconsistent trace data to form a network simulation of the network.

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

20. A system as described in claim 18, wherein the at least two of the plurality of nodes perform neighbor monitoring.

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

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

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

24. A system as described in claim 18, wherein the trace data is provided by a trace utility.

25. A system as described in claim 18, wherein the trace data is selected from a group consisting of:

network topology including routing;

traffic statistics;

physical medium; and

network performance.

26. A system as described in claim 18, wherein the network simulation outputs one or more network performance values that approximate corresponding network performance values observed from the network.

27. A node comprising:

a processor;

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

a memory configured to maintain a manager module that is executable on the processor, wherein the manager module performs acts comprising;

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

is formed by a respective one of a plurality of nodes, each one of the plurality of nodes comprising a processor, a memory, and a network connection device interconnecting the nodes in the network; and

describes one or more network settings of the respective node and at least one other node;

removing an inconsistency in at least one network setting of one report when compared with a corresponding network setting in at least one other report, wherein the removing resolves the inconsistency in the at least one network setting, wherein the manager module is executable on the processor to remove the inconsistency by deriving a set of nodes that explain the inconsistency as a smallest set of vertices that cover an inconsistency graph, wherein each vertex corresponds to a respective node; and

supplying resolved network settings to a network simulation thereby providing a network simulation of the network.

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

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

30. A node as described in claim 27, wherein the at least one network setting is provided by a trace utility.

31. A node as described in claim 27, 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.

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