# US 7,613,105 B2 · Methods and systems for removing data inconsistencies for a network simulation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,105 B2 - Document ID: US7613105B2 - Status: Granted - Kind: B2 - Application number: 10/881,751 - Filed: 2004-06-30 - Published: 2005-09-15 - Granted: 2009-11-03 - Earliest claimed: 2004-01-30 - Assignees: Microsoft Corporation - Inventors: Paramvir Bahl; Lidong Zhou; Lili Qiu; Ananth Rajagopala Rao - Web page: https://patentgrep.com/patent/US7613105B2 ## CPC - H04L 41/0873: Checking configuration conflicts between network elements - H04L 41/145: {involving simulating, designing, planning or modelling of a network} - H04L 43/04: Processing captured monitoring data, e.g. for logfile generation - H04L 41/12: Discovery or management of network topologies - H04L 41/142: using statistical or mathematical methods - H04L 45/02: Topology update or discovery - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) A method as described in claim 1, wherein each of the plurality of nodes perform neighbor monitoring. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) A method as described in claim 1, wherein the network is a multi-hop wireless network. ### Claim 5 (depends on 1) A method as described in claim 1, wherein the trace data describes information about network topology, routing, traffic statistics, physical medium, and network performance. ### Claim 6 (depends on 1) A method as described in claim 1, wherein the trace data is provided by a trace utility. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) A method as described in claim 11, wherein the deriving is performed as a minimum vertex cover problem. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 11) A method as described in claim 11, wherein the at least one network setting is provided by a trace utility. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 11) 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. ### Claim 17 (depends on 11) 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. ### Claim 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) A system as described in claim 18, wherein the at least two of the plurality of nodes perform neighbor monitoring. ### Claim 21 (depends on 18) A system as described in claim 18, wherein the deriving is performed as a minimum vertex cover problem. ### Claim 22 (depends on 18) A system as described in claim 18, wherein the network is a multi-hop wireless network. ### Claim 23 (depends on 18) A system as described in claim 18, wherein the trace data describes information about network topology, routing, traffic statistics, physical medium, and network performance. ### Claim 24 (depends on 18) A system as described in claim 18, wherein the trace data is provided by a trace utility. ### Claim 25 (depends on 18) 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. ### Claim 26 (depends on 18) 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. ### Claim 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. ### Claim 28 (depends on 27) A node as described in claim 27, wherein the deriving is performed as a minimum vertex cover problem. ### Claim 29 (depends on 27) 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. ### Claim 30 (depends on 27) A node as described in claim 27, wherein the at least one network setting is provided by a trace utility. ### Claim 31 (depends on 27) 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. ### Claim 32 (depends on 27) A node as described in claim 27, wherein the network is configured as a wireless mesh network.