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

• US 7,436,780 B2
• Filed: 12/17/2003
• Issued: 10/14/2008
• 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
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): KAO, WEI PO ERIC
• Application Number:
  US10/739,889
• Publication Number:
  US 20050135257A1
• Time in Patent Office: 1,763 Days
• Field of Search: 370/218, 370/229, 370/232, 370/235, 370/247, 370/324, 370/241, 370/252, 370/245, 370/253, 370/254, 370/248, 370/255, 370/238, 370/346, 370/389, 370/390, 370/400, 370/432, 709/224, 455/404.2, 455/456.1, 455/456.6
• US Class Current: 370/252
• 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 communicatively coupled to a plurality of reference nodes over a computer network configured to support an IP communications protocol, the method comprising:

sending packets, formatted to support the IP communications protocol, between the reference nodes to determine reference latencies between each reference node and each of the other plurality of reference nodes, each reference latency including a measurement of communication latency between a specified reference node and another reference node from the plurality of reference nodes and excluding any measurement of communication latency between the target node and any one of the plurality of reference nodes;

updating a table of latency information on a periodically scheduled basis to maintain a record including a plurality of entries of the reference latencies between each reference node and each other reference node from the plurality of reference nodes, the entries being collected over a designated period of time;

measuring, from packets formatted to support the IP communications protocol and sent between the target node and the reference nodes, target latencies between the target node and a subset of the reference nodes, each target latency including a measurement of communication latency between the target node and a specified reference node; and

comparing the target latencies to identify at least three reference nodes having close proximity to the target node; and

triangulating reference latencies associated with the at least three reference nodes to approximate a geographic region within which the target node is located.

2. The method of claim 1, wherein the sending packets comprises:

noting a start time;

conveying a ping directive to the computer 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 the sending packets 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 the sending packets 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 the sending packets comprises determining communication latencies amongst a plurality of reference nodes for a plurality of time-slots.

6. The method of claim 1, wherein the measuring target latencies comprises:

noting a start time;

conveying a ping directive to the computer 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 the measuring target latencies 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 the comparing the target latencies 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, wherein the triangulating reference latencies comprises identifying a union of the first identified region and a region surrounding the second reference node out to a latency distance to either the first reference node or a third reference node when the latency distance between the target node and either the first reference node or the third reference node is less than the latency distance between the second node and either the first reference node or the third reference node.

10. A system for determining an approximate location of a target node communicatively coupled to a plurality of reference nodes over a computer network configured to support an IP communications protocol, the system comprising:

a referencing unit operably configured to cause the reference nodes to send packets, formatted to support the IP communications protocol, between the reference nodes to determine reference latencies between each reference node and each of the other plurality of reference nodes, wherein each reference latency includes a measurement of communication latency between a specified reference node and another reference node from the plurality of reference nodes and excludes any measurement of communication latency between the target node and any one of the plurality of reference nodes;

a latency memory controller operably configured to update a latency storage medium including latency information on a periodically scheduled basis to maintain a record including a plurality of entries of the reference latencies between each reference node and each other reference node from the plurality of reference nodes, wherein the latency memory controller is further configured to collect the entries over a designated period of time;

a targeting unit operably configured to determine, from packets formatted to support the IP communications protocol and sent between the target node and the reference nodes, target latencies between the target node and a subset of the reference nodes, wherein each target latency includes a measurement of communication latency between the target node and a specified reference node; and

an approximation unit operably configured to triangulate reference latencies associated with at least three reference nodes to approximate a geographic region within which the target node is located, wherein the approximation unit comprises,

a latency comparator operably configured to compare the target latencies to identify the at least three reference nodes based on close proximity to the target node.

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

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

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

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

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

a 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

a 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:

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

a 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;

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

a 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

a 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:

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

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

a 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 reference node and a second reference node and according to a time-slot indicator.

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

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

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

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

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

a 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

a 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:

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

a 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;

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

a 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

a 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:

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

a 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

a 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 the first reference node or a third reference node is greater than the radius from the second reference node to the target node, the system comprising:

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

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