Estimation of time-varying latency based on network trace information

• US 7,843,815 B2
• Filed: 05/22/2007
• Issued: 11/30/2010
• Est. Priority Date: 08/19/2005
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Strohm, John, Malloy, Patrick J, Znamova, Dana
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Ng; Fan
• Application Number:
  US11/752,283
• Publication Number:
  US 20070217343A1
• Time in Patent Office: 1,288 Days
• Field of Search: None
• US Class Current: 370/229
• CPC Class Codes: H04J 3/0682 by delay compensation, e.g. by compensation of propagation delay or variations thereof, by ranging
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/0864 Round trip delays

Abstract

Time-varying latency is estimated based on the round-trip time between the time of sending a message and the time of receiving an acknowledgement of receipt of the message. The round-trip time relative to a transmitter is modeled as a combination of known, or determinable, delays, plus an unknown latency, plus a processing/acknowledgement delay at the receiver. The estimated time-varying latency is further refined to give more weight to estimates based on fewer unknowns or a lesser magnitude of unknowns, and to impose physical constraints, such as assuring that the estimate does not imply an unrealizable event. TCP-specific constraints and assumptions are also applied to further refine the latency estimates.

Claims

1. A method comprising:

determining, by a network analysis system, a plurality of round-trip times at a first node, each roundtrip time being associated with communication of a pair of messages between the first node and a second node,

determining, by the network analysis system, first latency estimates corresponding to the roundtrip times of the plurality of roundtrip times, each first latency estimate being based on the corresponding roundtrip time and a minimum bandwidth delay associated with the pair of messages corresponding to the roundtrip time,

determining, by the network analysis system, a time-varying latency function based on the first latency estimates, and

estimating, by the network analysis system, one or more times of communication of one or more of the pairs of messages at the second node, based on the time-varying latency function and corresponding times of communication of the one or more pairs of messages at the first node.

2. The method of claim 1, including:

determining other times of communication between the first node and the second node at the first node, and

estimating one or more other times of communication at the second node, based on the time-varying latency function and the corresponding other times of communication at the first node.

3. The method of claim 2, including:

identifying one or more conflicting times of communication at the second node,

determining second latency estimates that resolve the conflicting times, and

modifying the time-varying latency function based on the second latency estimates.

4. The method of claim 1, including calculating the minimum bandwidth delay by dividing a size of the pair of messages by a bandwidth of a minimum bandwidth link between the source node and the destination node.

5. The method of claim 1, wherein determining each first latency estimate includes:

subtracting the minimum bandwidth delay from the corresponding roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

6. The method of claim 5, wherein allocating the remainder delay includes allocating half of the remainder delay to each of the transmit latency and the receive latency.

7. The method of claim 1, including identifying a sequence of the pairs of messages corresponding to a transmitted train of messages, wherein determining each first latency estimate includes:

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a first transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each preceding transmitted message of the transmitted train, and

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

8. The method of claim 7, including displaying a delay measure based on the composite bandwidth delay.

9. The method of claim 7, wherein allocating the remainder delay includes allocating half of the remainder delay to each of the transmit latency and the receive latency.

10. The method of claim 7, wherein estimating the one or more times of communication at the second node includes:

estimating a receive time of the first transmitted message at the second node based on the transmit latency and a bandwidth delay corresponding to the first transmitted message, and

estimating a receive time of each of other transmitted messages of the transmitted train based on the receive time of the first transmitted message and a bandwidth delay of each succeeding message of the transmitted train.

11. The method of claim 10, including displaying the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding receive times of the communications at the second node.

12. The method of claim 1, including identifying a sequence of the pairs of messages corresponding to a received train of messages, and determining each first latency estimate includes:

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a last transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each succeeding received message of the received train,

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

13. The method of claim 12, including displaying a delay measure based on the composite bandwidth delay.

14. The method of claim 12, wherein allocating the remainder delay includes allocating half of the remainder delay to each of the transmit latency and the receive latency.

15. The method of claim 12, wherein estimating the one or more times of communication at the second node includes:

estimating a transmit time of the last received message at the second node based on the receive latency and a bandwidth delay corresponding to the first received message, and

estimating a transmit time of each of other received messages of the received train based on the transmit time of the first received message and a bandwidth delay of each preceding message of the received train.

16. The method of claim 15, including displaying the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding transmit times of the communications at the second node.

17. The method of claim 1, including determining a minimum bandwidth between the first node and the second node, and determining the minimum bandwidth delay based on the minimum bandwidth and a size of each of the pair of messages.

18. The method of claim 1, including displaying the time-varying latency function as a function of time.

19. The method of claim 1, including displaying the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first and second nodes.

20. A system comprising:

a round-trip determinator that determines a plurality of round-trip times at a first node, each roundtrip time being associated with communication of a pair of messages between the first node and a second node,

a latency determinator that;

determines first latency estimates corresponding to the roundtrip times of the plurality of roundtrip times, each first latency estimate being based on the corresponding roundtrip time and a minimum bandwidth delay associated with the pair of messages corresponding to the roundtrip time, and

determines a time-varying latency function based on the first latency estimates, and

a time determinator that estimates one or more times of communication of one or more of the pairs of messages at the second node, based on the time-varying latency function and corresponding times of communication of the one or more pairs of messages at the first node.

21. The system of claim 20, wherein the latency determinator determines other times of communication between the first node and the second node at the first node, and the time determinator estimate one or more other times of communication at the second node, based on the time-varying latency function and the corresponding other times of communication at the first node.

22. The system of claim 21, wherein the latency determinator:

identifies one or more conflicting times of communication at the second node,

determines second latency estimates that resolve the conflicting times, and

modifies the time-varying latency function based on the second latency estimates.

23. The system of claim 20, wherein the latency determinator:

identifies a sequence of the pairs of messages corresponding to a transmitted train of messages, and

determines each first latency estimate by;

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a first transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each preceding transmitted message of the transmitted train, and

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

24. The system of claim 23, wherein the latency determinator displays a delay measure based on the composite bandwidth delay.

25. The system of claim 23, wherein the time determinator estimates the one or more times of communication at the second node by:

estimating a receive time of the first transmitted message at the second node based on the transmit latency and a bandwidth delay corresponding to the first transmitted message, and

estimating a receive time of each of other transmitted messages of the transmitted train based on the receive time of the first transmitted message and a bandwidth delay of each succeeding message of the transmitted train.

26. The system of claim 25, wherein the latency determinator displays the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding receive times of the communications at the second node.

27. The system of claim 20, wherein the latency determinator:

identifies a sequence of the pairs of messages corresponding to a received train of messages, and

determines each first latency estimate by;

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a last transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each succeeding received message of the received train,

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

28. The system of claim 27, wherein the latency determinator displays a delay measure based on the composite bandwidth delay.

29. The system of claim 27, wherein the time estimator estimates the one or more times of communication at the second node by:

estimating a transmit time of the last received message at the second node based on the receive latency and a bandwidth delay corresponding to the first received message, and

estimating a transmit time of each of other received messages of the received train based on the transmit time of the first received message and a bandwidth delay of each preceding message of the received train.

30. The system of claim 29, wherein the latency determinator displays the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding transmit times of the communications at the second node.

31. The system of claim 20, wherein the latency determinator:

determines a minimum bandwidth between the first node and the second node, and

determines the minimum bandwidth delay based on the minimum bandwidth and a size of each of the pair of messages.

32. The system of claim 20, wherein the latency determinator displays the time-varying latency function as a function of time.

33. The system of claim 20, wherein the latency determinator displays the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first and second nodes.

34. A computer program stored on a non-transitory computer readable medium that is configured to cause a processor to:

determine a plurality of round-trip times at a first node, each roundtrip time being associated with communication of a pair of messages between the first node and a second node, and

determine first latency estimates corresponding to the roundtrip times of the plurality of roundtrip times, each first latency estimate being based on the corresponding roundtrip time and a minimum bandwidth delay associated with the pair of messages corresponding to the roundtrip time,

determine a time-varying latency function based on the first latency estimates, and

estimate one or more times of communication of one or more of the pairs of messages at the second node, based on the time-varying latency function and corresponding times of communication of the one or more pairs of messages at the first node.

35. The computer program of claim 34, that is configured to cause the processor to:

determine other times of communication between the first node and the second node at the first node, and

estimate one or more other times of communication at the second node, based on the time-varying latency function and the corresponding other times of communication at the first node.

36. The computer program of claim 35, that is configured to cause the processor to:

identify one or more conflicting times of communication at the second node,

determine second latency estimates that resolve the conflicting times, and

modifying the time-varying latency function based on the second latency estimates.

37. The computer program of claim 34, that is configured to cause the processor to:

determine each first latency estimate by;

subtracting the minimum bandwidth delay from the corresponding roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

38. The computer program of claim 34, that is configured to cause the processor to:

identify a sequence of the pairs of messages corresponding to a transmitted train of messages, and

determine each first latency estimate by;

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a first transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each preceding transmitted message of the transmitted train, and

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

39. The computer program of claim 38, that is configured to cause the processor to estimate the one or more times of communication at the second node by:

estimating a receive time of the first transmitted message at the second node based on the transmit latency and a bandwidth delay corresponding to the first transmitted message, and

estimating a receive time of each of other transmitted messages of the transmitted train based on the receive time of the first transmitted message and a bandwidth delay of each succeeding message of the transmitted train.

40. The computer program of claim 39, that is configured to cause the processor to display the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding receive times of the communications at the second node.

41. The computer program of claim 34, that is configured to cause the processor to:

identify a sequence of the pairs of messages corresponding to a received train of messages, and

determine each first latency estimate by;

determining a revised roundtrip time for each pair of messages relative to a time of transmission of a last transmitted message of the transmitted train of messages,

determining a composite bandwidth delay corresponding to the minimum bandwidth delay of each succeeding received message of the received train,

subtracting the composite bandwidth delay from the revised roundtrip time to provide a remainder delay, and

allocating the remainder delay to a transmit latency associated with a communication path from the first node to the second node and a receive latency associated with a communication path from the second node to the first node.

42. The computer program of claim 41, that is configured to cause the processor to display a delay measure based on the composite bandwidth delay.

43. The computer program of claim 41, that is configured to cause the processor to estimate the one or more times of communication at the second node by:

estimating a transmit time of the last received message at the second node based on the receive latency and a bandwidth delay corresponding to the first received message, and

estimating a transmit time of each of other received messages of the received train based on the transmit time of the first received message and a bandwidth delay of each preceding message of the received train.

44. The computer program of claim 43, that is configured to cause the processor to display the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first node and the corresponding transmit times of the communications at the second node.

45. The computer program of claim 34, that is configured to cause the processor to:

determine a minimum bandwidth between the first node and the second node, and

determine the minimum bandwidth delay based on the minimum bandwidth and a size of each of the pair of messages.

46. The computer program of claim 34, that is configured to cause the processor to display the time-varying latency function as a function of time.

47. The computer program of claim 34, that is configured to cause the processor to display the communication of the one or more of the pairs of messages as a function of time, based on the times of communication at the first and second nodes.