Smoothing algorithm for round trip time (RTT) measurements

• US 8,755,279 B2
• Filed: 01/18/2011
• Issued: 06/17/2014
• Est. Priority Date: 08/23/2004
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Joshi, Prajakta S.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US13/008,321
• Publication Number:
  US 20110122771A1
• Time in Patent Office: 1,246 Days
• Field of Search: None
• 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. An apparatus, comprising:

a network device to receive a domain name system (DNS) reply and to balance load based on a round trip time (RTT) algorithm, said RTT algorithm being usable by the network device to rank at least one address in the DNS reply,

wherein said RTT algorithm is configured to ignore at least one received RTT value and to use at least one other received RTT value, which is received after said ignored at least one RTT value, to determine an updated RTT value for said RTT algorithm.

2. The apparatus of claim 1 wherein said ignored at least one received RTT value is higher or lower than a current RTT value, and wherein said network device is configured to track a count of said ignored at least one received RTT value and to replace the current RTT value if said at least one other received RTT value causes said count of ignored at least one received RTT value to exceed a maximum count.

3. The apparatus of claim 1 wherein said network device is configured to receive said received RTT values from a site switch.

4. The apparatus of claim 1 wherein network device is configured to receive said DNS reply from an authoritative DNS server.

5. The apparatus of claim 1 wherein said network device includes a load balance switch.

6. A method, comprising:

receiving, by a network device, a domain name system (DNS) reply; and

balancing load, by said network device, based on a round trip time (RTT) algorithm, said RTT algorithm being usable by the network device to rank at least one address in the DNS reply,

wherein said RTT algorithm ignores at least one received RTT value and uses at least one other received RTT value, which is received after said ignored at least one RTT value, to determine an updated RTT value for said RTT algorithm.

7. The method of claim 6 wherein said ignored at least one received RTT value is higher or lower than a current RTT value, the method further comprising:

tracking, by said network device, a count of said ignored at least one received RTT value; and

replacing, by said network device, the current RTT value if said at least one other received RTT value causes said count of ignored at least one received RTT value to exceed a maximum count.

8. The method of claim 6, further comprising receiving, by said network device, said received RTT values from a site switch.

9. The method of claim 6 wherein said receiving the DNS reply includes receiving, by said network device, the DNS reply from an authoritative DNS server.

10. The method of claim 6 wherein said network device includes a load balance switch.

11. An apparatus, comprising:

storage means for storing a current round trip time (RTT) value; and

network device means for receiving a domain name system (DNS) reply and for balancing load based on a RTT algorithm, said network device means using said RTT algorithm to rank at least one address in the DNS reply,

wherein said RTT algorithm ignores at least one received RTT value and uses at least one other received RTT value, which is received after said ignored at least one RTT value, to determine an updated RTT value to replace said stored current RTT value in said RTT algorithm.

12. The apparatus of claim 11 wherein said ignored at least one received RTT value is higher or lower than the stored current RTT value, and wherein said network device means tracks a count of said ignored at least one received RTT value and said network device means replaces the stored current RTT value with said updated RTT value if said at least one other received RTT value causes said count of ignored at least one received RTT value to exceed a maximum count.

13. The apparatus of claim 11 wherein said network device means receives said received RTT values from a site switch.

14. The apparatus of claim 11 wherein network device means receives said DNS reply from an authoritative DNS server.

15. The apparatus of claim 11 wherein said network device means includes a load balance switch.