Automatic estimation of node location based on trace information
View Patent ↗The locations of nodes in a network are determined relative to the location of monitoring devices that collect trace information on the network. By appropriate sorting, filtering, and characterizing the trace information, nodes are identified as being local to or remote from each monitoring device that detects traffic to or from the node. If the trace information is insufficient to determine the relative location of a node, the node is identified as such. By identifying the nodes whose locations can be determined automatically by this analysis of the trace information, the number of nodes whose locations must be determined by more costly manual methods can be substantially reduced.
1. A method comprising:
obtaining, at a network analysis device, trace records from a trace device, each trace record identifying a message detected by the trace device and including an identification of a source node, a destination node, and a time at which the message was detected at the trace device, the trace device being at an unknown location relative to the source and destination nodes,
determining, by the network analysis device, a plurality of round-trip times associated with pairs of messages to and from a node of a pair of source-destination nodes, based on the time at which each message was detected by the trace device,
characterizing, by the network analysis device, the plurality of round-trip times to provide one or more statistics related to the round-trip times to and from the node, and
determining, by the network analysis device, a location of the node relative to the trace device based on the one or more statistics;
wherein:
the pairs of messages to and from the node correspond to messages from and to each of one or more other nodes that each form a node pair with the node,
the one or more statistics correspond to each node pair, and
determining the location includes
determining one or more tentative locations based on the one or more statistics associated with each node pair, and
determining the location based on an assessment of each of the one or more tentative locations.
2. The method of claim 1 , wherein determining each round-trip time includes:
identifying an acknowledgement message,
determining a prior message corresponding to the acknowledgement message, and
determining the round-trip time based on the times at which the acknowledgement message and the prior message were detected at the trace device.
3. The method of claim 2 , wherein determining each round-trip time includes identifying an occurrence of an immediate response, and determining the location is based at least in part on the occurrence of the immediate response.
4. The method of claim 3 , wherein the one or more statistics include a minimum round-trip time, and determining the location is based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
5. The method of claim 4 , wherein the one or more statistics include a maximum round-trip time, and determining the location is based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
6. The method of claim 1 , wherein determining each round-trip time includes:
identifying an acknowledgement message,
determining a prior message corresponding to the acknowledgement message, and
determining the round-trip time based on the times at which the acknowledgement message and the prior message were detected at the trace device.
7. The method of claim 6 , wherein determining each round-trip time includes identifying an occurrence of an immediate response, and determining the location is based at least in part on the occurrence of the immediate response.
8. The method of claim 7 , wherein the one or more statistics include a minimum round-trip time, and determining the location is based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
9. The method of claim 8 , wherein the one or more statistics include a maximum round-trip time, and determining the location is based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
10. The method of claim 1 , wherein determining each round-trip time includes identifying an occurrence of an immediate response, and determining the location is based at least in part on the occurrence of the immediate response.
11. The method of claim 10 , wherein the one or more statistics include a minimum round-trip time, and determining the location is based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
12. The method of claim 11 , wherein the one or more statistics include a maximum round-trip time, and determining the location is based at least in part on whether the maximum round-trip time exceeds a time associated with remote communications.
13. The method of claim 1 , wherein the one or more statistics include a minimum round-trip time, and determining the location is based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
14. The method of claim 13 , wherein the one or more statistics include a maximum round-trip time, and determining the location is based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
15. The method of claim 1 , wherein the one or more statistics include a maximum round-trip time, and determining the location is based at least in part on whether the maximum round-trip time exceeds a time associated with remote communications.
16. The method of claim 1 , wherein characterizing the plurality of round-trip times includes determining a reliability associated with the plurality of round-trip times.
17. The method of claim 16 , wherein determining the reliability includes detecting evidence of spoofing.
18. The method of claim 17 , wherein the evidence of spoofing is based at least in part on a round-trip time associated with a TCP SYN message.
19. A system comprising:
a trace device that is configured to record occurrences of messages between nodes of a network, each trace record identifying a message detected by the trace device and including an identification of a source node, a destination node, and a time at which the message was detected at the trace device, the trace device being at an unknown location relative to the source and destination nodes,
a processing system that is configured to:
determine a plurality of round-trip times associated with pairs of messages to and from a node of the plurality of nodes, based on the time at which each message was detected by the trace device,
characterize the plurality of round-trip times to provide one or more statistics related to the round-trip times to and from the node, and
determine a location of the node relative to the trace device based on the one or more statistics;
wherein:
the pairs of messages to and from the node correspond to messages from and to each of one or more other nodes that each form a node pair with the node,
the one or more statistics correspond to each node pair, and
the processing system is configured to determine the location by:
determining one or more tentative locations based on the one or more statistics associated with each node pair, and
determining the location based on an assessment of each of the one or more tentative locations.
20. The system of claim 19 , wherein the processing system is configured to determine each round-trip time by:
identifying an acknowledgement message,
determining a prior message corresponding to the acknowledgement message, and
determining the round-trip time based on the times at which the acknowledgement message and the prior message were detected at the trace device.
21. The system of claim 19 , wherein the processing system is configured to:
determine each round-trip time by identifying an occurrence of an immediate response, and
determine the location based at least in part on the occurrence of the immediate response.
22. The system of claim 19 , wherein the one or more statistics include a minimum round-trip time, and the processing system is configured to determine the location based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
23. The system of claim 22 , wherein the one or more statistics include a maximum round-trip time, and the processing system is configured to determine the location based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
24. The system of claim 19 , wherein the one or more statistics include a maximum round-trip time, and the processing system is configured to determine the location based at least in part on whether the maximum round-trip time exceeds a time associated with remote communications.
25. The system of claim 19 , wherein the processing system is configured to:
determine a reliability associated with the plurality of round-trip times based at least in part on a round-trip time associated with a TCP SYN message, and
disqualify some or all of the plurality of round-trip times for providing the one or more statistics, based on the reliability.
26. A computer program stored on a non-transitory computer-readable storage medium, that, when executed on a processing system, causes the processing system to:
receive a record occurrences of messages between nodes of a network from a trace device, each trace record identifying a message detected by the trace device and including an identification of a source node, a destination node, and a time at which the message was detected at the trace device, the trace device being at an unknown location relative to the source and destination nodes,
determine a plurality of round-trip times associated with pairs of messages to and from a node of the plurality of nodes, based on the time at which each message was detected by the trace device,
characterize the plurality of round-trip times to provide one or more statistics related to the round-trip times to and from the node, and
determine a location of the node relative to the trace device based on the one or more statistics:
wherein:
the pairs of messages to and from the node correspond to messages from and to each of one or more other nodes that each form a node pair with the node,
the one or more statistics correspond to each node pair, and
to determine the location, the computer program causes the processing system to:
determine one or more tentative locations based on the one or more statistics associated with each node pair, and
determine the location based on an assessment of each of the one or more tentative locations.
27. The computer program of claim 26 , wherein to determine each round-trip time, the computer program causes the processing system to:
identify an acknowledgement message,
determine a prior message corresponding to the acknowledgement message, and
determine the round-trip time based on the times at which the acknowledgement message and the prior message were detected at the trace device.
28. The computer program of claim 26 , wherein the computer program causes the processing system to identify an occurrence of an immediate response to determine each round-trip time, and to determine the location based at least in part on the occurrence of the immediate response.
29. The computer program of claim 26 , wherein the one or more statistics include a minimum round-trip time, and the computer program causes the processing system to determine the location based at least in part on whether the minimum round-trip time is less than a time associated with local communications.
30. The computer program of claim 29 , wherein the one or more statistics include a maximum round-trip time, and the computer program causes the processing system to determine the location based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
31. The computer program of claim 26 , wherein the one or more statistics include a maximum round-trip time, and the computer program causes the processing system to determine the location based at least in part on whether the maximum round-trip time exceeds the time associated with remote communications.
32. The computer program of claim 26 , wherein the computer program causes the processing system to:
determine a reliability associated with the plurality of round-trip times based at least in part on a round-trip time associated with a TCP SYN message, and
disqualify some or all of the plurality of round-trip times for providing the one or more statistics, based on the reliability.