Network latency estimation

• US 8,254,264 B1
• Filed: 04/28/2006
• Issued: 08/28/2012
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Banerjee, Sujata, Sharma, Puneet, Lee, Sung-Ju
• Primary Examiner(s): Vu, Huy D
• Assistant Examiner(s): Brockman, Angel
• Application Number:
  US11/414,059
• Time in Patent Office: 2,314 Days
• Field of Search: 370/238, 370/235
• US Class Current: 370/238
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

A method includes sending signals from two nodes to a landmark, identifying common milestones along the routes, and determining distance information from the nodes to at least one of the common milestones. A system includes a program configured to send signals from two nodes to a landmark, identify common milestones along the routes, and provide distance information from each node to at least one of the common milestones, and a program configured to receive the distance information and provide a latency estimate based on the distance information.

Claims

1. A method for estimating latency between a first node and a second node comprising:

sending a first signal from the first node to a landmark node along a first path;

sending a second signal from the second node to the landmark node along a second path;

wherein the second node is on the path between the first node and the landmark node;

identifying a common milestone on the first and second paths, wherein the common milestone is a node on the first path between the first node and the landmark node, and on the second path between the second node and the landmark node;

determining a first distance from the first node to the common milestone;

determining a second distance from the second node to the common milestone; and

estimating the latency based on the first and second distances by;

determining a common milestone that is positioned such that the second node is on a shortest path between the first node and the common milestone by subtracting the first distance from the second distance.

2. The method of claim 1 wherein identifying one or more common milestones on the first and second paths comprises:

identifying one or more milestones on the first path;

identifying one or more milestones on the second path; and

identifying common milestones by determining which milestones are on both the first path and the second path.

3. The method of claim 1 wherein estimating latency based on the first and second distances by determining the sum of the first distance and the second distance further comprises identifying an intermediate common milestone by determining the common milestone for which the sum of the first distance and the second distance is the smallest value.

4. The method of claim 1 further comprising providing the first distance and the second distance to a central processing node.

5. The method of claim 4 where the central processing node performs the steps of identifying a common milestone on the first and second path and estimating latency based on the distances from the first and second nodes to the common milestone.

6. The method of claim 1 wherein sending a signal from the first node to a landmark node along a first path comprises transmitting a first probe packet from the first node to the landmark node;

and wherein

sending a signal from the second node to the landmark node along a second path comprises transmitting a second probe packet from the second node to the landmark node.

7. The method of claim 6 wherein determining a distance from the first node to the common milestone comprises receiving an acknowledge message from the common milestone receiving the first probe packet;

and wherein

determining a distance from the second node to the common milestone comprises receiving an acknowledge message from the common milestone receiving the second probe packet.

8. The method of claim 1 wherein estimating latency based on the first and second distances by determining the sum of the first distance and the second distance further comprises identifying an intermediate common milestone from a plurality of common milestones by determining the common milestone for which the sum of the first distance and the second distance is a smallest value.

9. Computer software embedded on a non-transitory tangible computer readable storage medium, the computer software comprising instructions that when executed by a computer perform a method comprising:

identifying a milestone along a first path from a first node to a landmark node, wherein the milestone is a node on the first path between the first node and the landmark node;

determining a first distance from the milestone to the first node;

identifying the milestone along a second path from a second node to the landmark node,

wherein the milestone is on the second path between the second node and the landmark node;

determining a second distance from the milestone to the second node; and

determining an estimated latency between the first and second nodes based on the first and second distances by determining a common milestone that is positioned such that the second node is on a shortest path between the first node and the common milestone by subtracting the first distance from the second distance.

10. The computer software of claim 9 wherein instructions performing determining an estimated latency by determining the sum of the first distance and the second distance comprise identifying the milestone for which the sum of the first and second distances is the smallest value.

11. The computer software of claim 9 wherein:

identifying a milestone along a first path from a first node to a landmark node comprises identifying a plurality of milestones along a plurality of first paths from a first node to a plurality of landmark nodes;

determining a first distance from the milestone to the first node comprises determining a plurality of first distances from the plurality of milestones on the first paths to the first node;

identifying the milestone along a second path from a second node to the landmark node comprises identifying a plurality of milestones along a plurality of second paths from a second node to the plurality of land mark nodes;

determining a second distance from the milestone to the second node comprises determining a plurality of second distances from the plurality of milestones on the second paths to the second node; and

determining an estimated latency based on the first and second distances comprises;

identifying, for each landmark, a set of common milestones that are on a first path to a landmark and a second path to the landmark;

determining the distance from the first and second nodes to each milestone in the set of common milestones; and

determining the estimated latency between the first and second node by finding a smallest value for the sum of the distance from the first and second nodes to the same common milestone.

12. The computer software of claim 9 wherein instructions performing determining an estimated latency by determining a sum of the first distance and the second distance comprise identifying a milestone from a plurality of milestones for which the sum of the first and second distances is a smallest value.

13. The computer software of claim 9 wherein instructions performing determining an estimated latency by subtracting the first distance from the second distance comprise identifying the milestone from a plurality of milestones for which the first distance subtracted from the second distance has a largest absolute value.

14. A system for estimating latency between a first client node and second client node in a network, the system comprising:

a plurality of client nodes;

including a first and second client node, wherein the second client node is on the path between the first node and at least one landmark node, wherein the landmark node has an identified location;

a traceroute program configured to;

send a signal on a pathway from the first client node to the landmark node;

identify a milestone discovered on the pathway; and

determine the a distance between the first client node and the identified milestone on the pathway; and

a central processing program configured to receive the distance information generated by the traceroute program and perform latency calculations based on the received distance information by determining an identified milestone that is positioned such that the second client node is on a shortest path between the first client node and the identified milestone by subtracting a first distance for the first client node from a second distance for the second client node.

15. The system of claim 14 wherein the central processing program is further configured to identify a common milestone that is located on both a first path between the first client node and the landmark and a second path between the second client node and the landmark.

16. The system of claim 15 wherein the central processing program is further configured to identify a common intermediate milestone on the first and second paths.