Method and apparatus for approximating location of node attached to a network

• US 20050135257A1
• Filed: 12/17/2003
• Published: 06/23/2005
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Time Warner Inc. (Warner Bros. Discovery, Inc.)
• Original Assignee: Time Warner Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Stephens, Spencer, Cookson, Christopher, Dages, Chuck
• Granted Patent: US 7,436,780 B2
• Time in Patent Office: Days
• US Class Current: 370/241
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

A plurality of reference nodes that are attached to the network are correlated with geographic location. Communication latency between the reference nodes are used to approximate the location of a target node once the communication latency from one of the reference nodes to the target node is determined.

Claims

1. A method for determining an approximate location of a target node attached to a network comprising:

determining communication latencies amongst a plurality of reference nodes;

measuring the communication latency between the target node and at least one of the reference nodes; and

approximating a geographic region within which the target node is located according to the communication latency between the target node and at least one of the reference nodes.

2. The method of claim 1 wherein determining communication latencies amongst a plurality of reference nodes comprises:

noting a start time;

conveying a ping directive to the network from a first reference node to a second reference node;

noting an end time when a response to the ping directive is received; and

determining the difference between the start time and the end time.

3. The method of claim 1 wherein determining communication latencies amongst a plurality of reference nodes comprises:

transmitting a sounding message from a first reference node, wherein the sounding message includes a time-to-live protocol parameter and an initial time-to-live value;

receiving the sounding message in a second reference node; and

determining a hop-distance according to a time-to-live value stored in the protocol parameter and the initial time-to-live value included in the received sounding message.

4. The method of claim 1 wherein determining communication latencies amongst a plurality of reference nodes comprises determining communication latencies amongst a plurality of reference nodes on a periodic basis and generating a moving average according to the periodic communication latency determinations.

5. The method of claim 1 wherein determining communication latencies amongst a plurality of reference nodes comprises determining communication latencies amongst a plurality of reference nodes for a plurality of time-slots.

6. The method of claim 1 wherein measuring the communication latency between the target node and at least one of the reference nodes comprises:

noting a start time;

conveying a ping directive to the network from a first reference node to the target node;

noting an end time when a response to the ping directive is received; and

determining the difference between the start time and the end time.

7. The method of claim 1 wherein measuring the communication latency between the target node and at least one of the reference nodes comprises:

transmitting a sounding message from the target node, wherein the sounding message includes a time-to-live protocol parameter and an initial time-to-live value;

receiving the sounding message in a reference node; and

determining a hop-distance according to a time-to-live value stored in the protocol parameter and the initial time-to-live value included in the received sounding message.

8. The method of claim 1 wherein approximating a geographic region within which the target node is located comprises identifying a first region surrounding a first reference node out to a latency distance to a second reference node when the latency distance between the target node and the first reference node is less than the latency distance between the first reference node and the second reference node.

9. The method of claim 8 further comprising identifying a union of the first identified region and a region surrounding the second reference node out to a latency distance to either of the first reference node and a third reference node when the latency distance between the target node and either of the first reference node and the third reference node is less than the latency distance between the second node and either of the first reference node and the third reference node.

10. A system for determining an approximate location of a target node attached to a network comprising:

referencing unit capable of determining the communication latency amongst a plurality of reference nodes;

targeting unit capable of determining the communication latency from at least one of the reference nodes to the target node; and

approximation unit that determines a region within which the target node is located according to the communication latency between the target node and at least one of the reference nodes.

11. The system of claim 10 wherein the referencing unit comprises:

controller that issues a send ping signal and issues a stop signal when it recognizes a ping response;

start register that captures a start time according to the send ping signal;

end register that captures an end time according to the stop signal;

index register that captures source and destination indicators for a ping;

latency differencing unit that generates a latency value according to the difference between a value stored in the start register and a value stored in the end register; and

latency storage unit that stores the generated latency value in a location according to an index stored in the index register.

12. The system of claim 10 wherein the referencing unit comprises:

controller that causes a first reference node to transmit a sounding message;

message capture register that captures a time-to-live protocol parameter and an initial time-to-live value from the sounding message as it arrives at a second reference node;

index register that stores an index according to a source and destination of the sounding message arriving at the second reference node;

differencing unit that generates a hop-distance according to the difference between the time-to-live protocol parameter and an initial time-to-live value; and

latency storage unit that stores the generated hop-distance in a location according to an index stored in the index register.

13. The system of claim 10 wherein the referencing unit comprises:

latency storage unit capable of storing one or more values indexed according to addresses for a first and second reference nodes;

summing unit capable of adding a current latency value with one or more values retrieved from the latency storage unit according to an index;

multiplier capable of multiplying an output from the summing unit by an inverse of the sum of one plus the quantity of values retrieved from the latency storage unit, wherein the output of the multiplier is stored in the latency storage unit according to the index.

14. The system of claim 10 wherein the referencing unit comprises a latency storage unit capable of storing one or more values indexed according to addresses for a first and second reference nodes and according to a time-slot indicator.

15. The system of claim 10 wherein the targeting unit comprises:

controller that issues a send ping signal and issues a stop signal when it recognizes a ping response;

start register that captures a start time according to the send ping signal;

end register that captures an end time according to the stop signal;

index register that captures source and destination indicators for a ping;

latency differencing unit that generates a latency value according to the difference between a value stored in the start register and a value stored in the end register; and

latency storage unit that stores the generated latency value in a location according to an index stored in the index register.

16. The system of claim 10 wherein the targeting unit comprises:

controller that causes the target node to transmit a sounding message;

message capture register that captures a time-to-live protocol parameter and an initial time-to-live value from the sounding message as it arrives at a reference node;

index register that stores an index according to a source and destination of the sounding message arriving at the reference node;

differencing unit that generates a hop-distance according to the difference between the time-to-live protocol parameter and an initial time-to-live value; and

latency storage unit that stores the generated hop-distance in a location according to an index stored in the index register.

17. The system of claim 10 wherein the approximation unit comprises:

location map that that transforms a reference node index to a geographic location;

radius comparator that generates a first capture signal when a radius from a first reference node to a second reference node is greater than the radius from the first reference node to the target node; and

first region register that stores a geographic location of the first reference node according to the first capture signal.

18. The system of claim 17 wherein the radius comparator generates a second capture signal when a radius from a second reference node to either of the first reference node or a third reference node is greater than the radius from the second reference node to the target node further comprising:

second region register that stores a geographic location for the second node according to the second capture signal; and

triangulation unit that generates an approximate location for the target node according to a location stored in the first and second region registers.