Smoothing algorithm for round trip time (RTT) measurements

• US 7,423,977 B1
• Filed: 08/23/2004
• Issued: 09/09/2008
• Est. Priority Date: 08/23/2004
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Joshi, Prajakta S.
• Primary Examiner(s): Moe; Aung S.
• Assistant Examiner(s): PASIA, REDENTOR M
• Application Number:
  US10/924,552
• Time in Patent Office: 1,478 Days
• Field of Search: 370229-232, 370235-2362, 370/241, 370/249, 370/252, 370/389, 370/395.1, 370/395.2, 370/395.21, 370/400, 370/465, 370/503, 370/508, 370/519, 370/248, 709220-230, 709232-235
• US Class Current: 370/252
• 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 43/022 by sampling
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A smoothing algorithm for round trip time (RTT) measurements is provided to a network device to effectively deal with variations or other potential anomalies that may occur in RTT measurements. The algorithm involves: first determining what should be considered a very high or a very small value for a RTT sample. If a new RTT sample is in an acceptable range, then the network device performs a relatively basic smoothing. If the new RTT sample is much higher than a current RTT value, then the network device ignores the value of this RTT sample a few times. If the network device still detects this large value after ignoring that value for some time, then the network device factors this value into the current RTT value using an additive increase. Similarly, if the value of the new RTT sample is much lower than current RTT value, the network device ignores the value of the new RTT sample a few times. If the network device still sees this small/low value after ignoring that value for sometime, then the network device factors this value into the current RTT value using a multiplicative decrease. An effective RTT value results, which can be used singly or in combination with other metrics to load balance network traffic.

Claims

1. A method, comprising:

defining a maximum deviation allowed for any round trip time (RTT) sample relative to a current RTT value;

computing a deviation of a RTT sample relative to the current RTT value;

if the computed deviation is greater than zero and greater than the maximum deviation allowed, then performing a first type of RTT smoothing operation wherein the RTT sample is factored into the current RTT value using an additive increase;

if the computed deviation is less than zero and an absolute value of the computed deviation is greater than the maximum deviation allowed, then performing a second type of RTT smoothing operation wherein the RTT sample is factored into the current RTT value using a multiplicative decrease; and

otherwise performing a third type of RTT smoothing operation wherein a percentage of the RTT sample is factored into a percentage of the current RTT value.

2. The method of claim 1, further comprising ignoring and counting a plurality of RTT samples whose absolute value of computed deviations relative to the current RTT value exceed the maximum deviation allowed, until a count of ignored RTT samples exceed a maximum ignore count.

3. The method of claim 1 wherein said defining the maximum deviation allowed for any RTT sample relative to the current RTT value includes defining the maximum deviation allowed as a percentage deviation from the current RTT value.

4. The method of claim 1 wherein the current RTT value into which the RTT sample is factored includes an effective RTT value, the method further comprising using the effective RTT value as a metric to load balance traffic to at least one network address.

5. The method of claim 1 wherein said performing the first type of RTT smoothing operation wherein the RTT sample is factored into the current RTT value using the additive increase includes:

setting an increment factor;

reducing the current RTT value by a first percentage based on the increment factor;

reducing the RTT sample by a second percentage based on the increment factor;

adding the reduced current RTT value to the reduced RTT sample to obtain an effective RTT value;

adding the increment factor to a ramp up factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

setting the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

using the new increment factor for at least one subsequent first type of RTT smoothing operation to obtain a new effective RTT value.

6. The method of claim 1 wherein said performing the second type of RTT smoothing operation wherein the RTT sample is factored into the current RTT value using the multiplicative decrease includes:

setting an increment factor;

reducing the current RTT value by a first percentage based on the increment factor;

reducing the RTT sample by a second percentage based on the increment factor;

subtracting the reduced RTT sample from the reduced current RTT value to obtain an effective RTT value;

multiplying the increment factor with a ramp down factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

setting the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

using the new increment factor for at least one subsequent second type of RTT smoothing operation to obtain a new effective RTT value.

7. The method of claim 1, further comprising adapting parameters of at least one of the first, second, and third types of RTT smoothing operations in response to network characteristics.

8. The method of claim 7 wherein said adapting the parameters includes adapting at least one of the maximum deviation allowed, a maximum count of ignored RTT samples that exceed the maximum deviation allowed, a ramp up factor that specifies increments in which a large RTT sample that exceeds the maximum deviation allowed should be factored into the current RTT value, a ramp down factor that specifies increments in which a small RTT sample that exceeds the maximum deviation allowed should be factored into the current RTT value, and a normal ramp factor that specifies how much a RTT sample that is less than or equal to the maximum deviation allowed should be factored into the current RTT value.

9. The method of claim 1, further comprising applying none of the first, second, and third RTT smoothing operations to a first current RTT value.

10. The method of claim 1, further comprising selectively enabling or disabling the first and second types of RTT smoothing operations for different sites that are being load balanced.

11. A method, comprising:

determining whether an allowed maximum deviation of a round trip time (RTT) sample relative to a current RTT value is exceeded;

if the RTT sample is larger than the current RTT value so as to exceed the allowed maximum deviation, adjusting the current RTT value using a first type of RTT smoothing operation;

if the RTT sample is smaller than the current RTT value so as to exceed the allowed maximum deviation, adjusting the current RTT value using a second type of RTT smoothing operation;

if the RTT sample relative to the current RTT value is within the allowed maximum deviation, adjusting the current RTT value using a third type of RTT smoothing operation; and

ignoring and counting a plurality of RTT samples whose computed deviations relative to the current RTT value exceed the allowed maximum deviation, until a count of ignored RTT samples exceed a maximum ignore count.

12. The method of claim 11 wherein said adjusting the current RTT value using the first type of RTT smoothing operation includes using an additive increase that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values.

13. The method of claim 12 wherein said using the first type of RTT smoothing operation that includes using the additive increase includes:

reducing the current RTT value by a first percentage based on an increment factor;

reducing the RTT sample by a second percentage based on the increment factor;

adding the reduced current RTT value to the reduced RTT sample to obtain an effective RTT value;

adding the increment factor to a ramp up factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

setting the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

using the new increment factor for at least one subsequent first type of RTT smoothing operation to obtain a new effective RTT value.

14. The method of claim 11 wherein said adjusting the current RTT value using the second type of RTT smoothing operation includes using multiplicative decrease that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values.

15. The method of claim 14 wherein said using the second type of RTT smoothing operation that includes using the multiplicative decrease includes:

reducing the current RTT value by a first percentage based on an increment factor;

reducing the RTT sample by a second percentage based on the increment factor;

subtracting the reduced RTT sample from the reduced current RTT value to obtain an effective RTT value;

multiplying the increment factor with a ramp down factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

setting the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

using the new increment factor for at least one subsequent second type of RTT smoothing operation to obtain a new effective RTT value.

16. The method of claim 11 wherein said adjusting the current RTT value using the third type of RTT smoothing operation includes factoring a percentage of the RTT sample into a percentage of the current RTT value.

17. The method of claim 11, further comprising using the adjusted current RTT value as a metric to load balance traffic to at least one network address.

18. A method, comprising:

determining whether an allowed maximum deviation of a round trip time (RTT) sample relative to a current RTT value is exceeded;

if the RTT sample is larger than the current RTT value so as to exceed the allowed maximum deviation, adjusting the current RTT value using a first type of RTT smoothing operation;

if the RTT sample is smaller than the current RTT value so as to exceed the allowed maximum deviation, adjusting the current RTT value using a second type of RTT smoothing operation; and

if the RTT sample relative to the current RTT value is within the allowed maximum deviation, adjusting the current RTT value using a third type of RTT smoothing operation; and

at least one of;

a) wherein said adjusting the current RTT value using the first type of RTT smoothing operation includes using an additive increase that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values;

b) wherein said adjusting the current RTT value using the second type of RTT smoothing operation includes using a multiplicative decrease that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values; and

c) wherein said adjusting the current RTT value using the third type of RTT smoothing operation includes factoring a percentage of the RTT sample into a percentage of the current RTT value.

19. The method of claim 18, further comprising:

using the adjusted current RTT value as a metric to load balance traffic to at least one network address.

20. The method of claim 18, further comprising adapting parameters of at least one of the first, second, and third types of RTT smoothing operations in response to network characteristics.

21. A computer-readable medium that stores instructions executable by a processor to:

obtain a maximum deviation allowed for any round trip time (RTT) sample relative to a current RTT value;

compute a deviation of a RTT sample relative to the current RTT value;

perform a first type of RTT smoothing operation to factor the RTT sample into the current RTT value using an additive increase, if the computed deviation is greater than zero and greater than the maximum deviation allowed;

perform a second type of RTT smoothing operation to factor the RTT sample into the current RTT value using a multiplicative decrease, if the computed deviation is less than zero and greater than the maximum deviation allowed; and

otherwise perform a third type of RTT smoothing operation to factor a fixed percentage of the RTT sample into a fixed percentage of the current RTT value.

22. The computer-readable medium of claim 21, further including instructions stored thereon that are executable by said processor to:

ignore and count a plurality of RTT samples whose computed deviations relative to the current RTT value exceed the maximum deviation allowed, until a count of ignored RTT samples exceed a maximum ignore count.

23. The computer-readable medium of claim 21 wherein the instructions to perform the first type of RTT smoothing operation to factor the RTT sample into the current RTT value using the additive increase include instructions executable by said processor to:

reduce the current RTT value by a first percentage based on an increment factor;

reduce the RTT sample by a second percentage based on the increment factor;

add the reduce current RTT value to the reduced RTT sample to obtain an effective RTT value;

add the increment factor to a ramp up factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

set the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

use the new increment factor for at least one subsequent first type of RTT smoothing operation to obtain a new effective RTT value.

24. The computer-readable medium of claim 21 wherein the instructions to perform the second type of RTT smoothing operation to factor the RTT sample into the current RTT value using the multiplicative decrease include instructions executable by said processor to:

reduce the current RTT value by a first percentage based on an increment factor;

reduce the RTT sample by a second percentage based on the increment factor;

subtract the reduced RTT sample from the reduced current RTT value to obtain an effective RTT value;

multiply the increment factor with a ramp down factor to obtain a new increment factor, if the increment factor is less than a normal ramp factor;

set the new increment factor equal to the normal ramp factor, if the increment factor exceeds the normal ramp factor; and

use the new increment factor for at least one subsequent second type of RTT smoothing operation to obtain a new effective RTT value.

25. The computer-readable medium of claim 21, further including instructions stored thereon that are executable by said processor to:

use the current RTT value, having the RTT sample factored thereto, as a metric to load balance network traffic.

26. A system, comprising:

storage means for storing at least one round trip time (RTT) value; and

means for determining whether an allowed maximum deviation of a round trip time (RTT) sample relative to a current RTT value is exceeded;

for adjusting the current RTT value using a first type of RTT smoothing operation, if the RTT sample is larger than the current RTT value so as to exceed the allowed maximum deviation;

for adjusting the current RTT value using a second type of RTT smoothing operation, if the RTT sample is smaller than the current RTT value so as to exceed the allowed maximum deviation; and

for adjusting the current RTT value using a third type of RTT smoothing operation, if the RTT sample relative to the current RTT value is within the allowed maximum deviation; and

at least one of;

a) wherein the means for adjusting the current RTT value using the first type of RTT smoothing operation uses an additive increase that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values;

b) wherein the means for adjusting the current RTT value using the second type of RTT smoothing operation uses a multiplicative decrease that adds progressively increasing percentages of RTT samples to corresponding progressively decreasing percentages of current RTT values; and

c) wherein said means for adjusting the current RTT value using the third type of RTT smoothing operation factors a percentage of the RTT sample into a percentage of the current RTT value.

27. The system of claim 26, further comprising:

means for adapting parameters of at least one of the first, second, and third types of RTT smoothing operations in response to network characteristics.

28. The system of claim 26, further comprising means for using the adjusted current RTT value as a metric, either singly or in combination with other metrics, to load balance network traffic.