SMOOTHING ALGORITHM FOR ROUND TRIP TIME (RTT) MEASUREMENTS

• US 20100061236A1
• Filed: 07/21/2008
• Published: 03/11/2010
• Est. Priority Date: 08/23/2004
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Joshi, Prajakta S.
• Granted Patent: US 7,885,188 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• 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. (canceled)

2. An apparatus, comprising:

a network device that includes;

at least one storage unit configured to store a current round trip time (RTT) value; and

a controller coupled to said at least one storage unit and configured to ignore received RTT values that are different from the stored current RTT value, by maintaining the stored current RTT value in said at least one storage unit,

wherein if a count of ignored RTT values exceeds an ignore count, the controller is configured to replace the current stored RTT value in said at least one storage unit with a first updated RTT value.

3. The apparatus of claim 2 wherein said at least one storage unit is further configured to store a maximum deviation value, and wherein the controller is configured to ignore received RTT values that have a deviation value that exceeds said maximum deviation value.

4. The apparatus of claim 3 wherein the controller is further configured to replace the stored current RTT value with a second updated RTT value, if a deviation value of a received RTT value from the stored current RTT value is within said maximum deviation value.

5. The apparatus of claim 4 wherein:

if the received RTT value is smaller than said stored current RTT value so as to exceed said maximum deviation value, said controller is configured to obtain said first updated RTT value by factoring the received RTT value into the stored current RTT value using a multiplicative decrease;

if said received RTT value is larger than said stored current RTT value so as to exceed said maximum deviation value, said controller is configured to obtain said first updated RTT value by factoring the received RTT value into the stored current RTT value using an additive increase; and

said controller is configured to obtain said second updated RTT value by adding a percentage of said received RTT value to a percentage of said stored current RTT value.

6. The apparatus of claim 2 wherein said network device includes a load balance switch.

7. A method by a network device to balance load, the method comprising:

storing a current round trip time (RTT) value in at least one storage unit;

ignoring, by said network device, received RTT values that are different from the stored current RTT value, by maintaining the stored current RTT value in said at least one storage unit; and

if a count of ignored RTT values exceeds an ignore count, replacing the current stored RTT value in said at least one storage unit with a first updated RTT value.

8. The method of claim 7, further comprising storing a maximum deviation value in said at least one storage unit, wherein said ignoring includes ignoring received RTT values that have a deviation value that exceeds said maximum deviation value.

9. The method of claim 8, further comprising replacing the stored current RTT value with a second updated RTT value, if a deviation value of a received RTT value from the stored current RTT value is within said maximum deviation value.

10. The method of claim 9 wherein:

if the received RTT value is smaller than said stored current RTT value so as to exceed said maximum deviation value, said first updated RTT value is obtained by said network device by factoring the received RTT value into the stored current RTT value using a multiplicative decrease;

if said received RTT value is larger than said stored current RTT value so as to exceed said maximum deviation value, said first updated RTT value is obtained by said network device by factoring the received RTT value into the stored current RTT value using an additive increase; and

said second updated RTT value is obtained by said network device by adding a percentage of said received RTT value to a percentage of said stored current RTT value.

11. The method of claim 7 wherein said network device includes a load balance switch.

12. An article of manufacture, comprising:

a computer-readable medium that stores computer-readable instructions that are executable by a processor of a network device to;

ignoring, by said network device, received RTT values that are different from a current round trip time (RTT) value, stored in at least one storage unit, by maintaining the stored current RTT value in said at least one storage unit; and

if a count of ignored RTT values exceeds an ignore count, replace the current stored RTT value in said at least one storage unit with a first updated RTT value.

13. The article of manufacture of claim 12 wherein to said ignore, the computer-readable medium further stores computer-readable instructions that are executable by said processor to:

ignore received RTT values that have a deviation value that exceeds a maximum deviation value that is stored in said at least one storage unit.

14. The article of manufacture of claim 13 wherein the computer-readable medium further stores computer-readable instructions that are executable by said processor to:

replace the stored current RTT value with a second updated RTT value, if a deviation value of a received RTT value from the stored current RTT value is within said maximum deviation value.

15. The article of manufacture of claim 14 wherein:

if the received RTT value is smaller than said stored current RTT value so as to exceed said maximum deviation value, said first updated RTT value is obtained by factoring the received RTT value into the stored current RTT value using a multiplicative decrease;

if said received RTT value is larger than said stored current RTT value so as to exceed said maximum deviation value, said first updated RTT value is obtained by factoring the received RTT value into the stored current RTT value using an additive increase; and

said second updated RTT value is obtained by adding a percentage of said received RTT value to a percentage of said stored current RTT value.

16. The article of manufacture of claim 12 wherein said network device includes a load balance switch