net/curvecp/rtt_and_send_rate_calculator.cc

   1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <stdlib.h>
   6
   7 #include "net/curvecp/rtt_and_send_rate_calculator.h"
   8
   9 namespace net {
  10
  11 RttAndSendRateCalculator::RttAndSendRateCalculator()
  12     : rtt_latest_(0),
  13       rtt_average_(0),
  14       rtt_deviation_(0),
  15       rtt_lowwater_(0),
  16       rtt_highwater_(0),
  17       rtt_timeout_(base::Time::kMicrosecondsPerSecond),
  18       send_rate_(1000000),
  19       rtt_seenrecenthigh_(0),
  20       rtt_seenrecentlow_(0),
  21       rtt_seenolderhigh_(0),
  22       rtt_seenolderlow_(0),
  23       rtt_phase_(false) {
  24 }
  25
  26 void RttAndSendRateCalculator::OnMessage(int32 rtt_us) {
  27   UpdateRTT(rtt_us);
  28   AdjustSendRate();
  29 }
  30
  31 void RttAndSendRateCalculator::OnTimeout() {
  32   base::TimeDelta time_since_last_loss = last_sample_time_ - last_loss_time_;
  33   if (time_since_last_loss.InMilliseconds() < 4 * rtt_timeout_)
  34     return;
  35   send_rate_ *= 2;
  36   last_loss_time_ = last_sample_time_;
  37   last_edge_time_ = last_sample_time_;
  38 }
  39
  40 // Updates RTT
  41 void RttAndSendRateCalculator::UpdateRTT(int32 rtt_us) {
  42   rtt_latest_ = rtt_us;
  43   last_sample_time_ = base::TimeTicks::Now();
  44
  45   // Initialize for the first sample.
  46   if (!rtt_average_) {
  47     rtt_average_ = rtt_latest_;
  48     rtt_deviation_ = rtt_latest_;
  49     rtt_highwater_ = rtt_latest_;
  50     rtt_lowwater_ = rtt_latest_;
  51   }
  52
  53   // Jacobson's retransmission timeout calculation.
  54   int32 rtt_delta = rtt_latest_ - rtt_average_;
  55   rtt_average_ += rtt_delta / 8;
  56   if (rtt_delta < 0)
  57     rtt_delta = -rtt_delta;
  58   rtt_delta -= rtt_deviation_;
  59   rtt_deviation_ += rtt_delta / 4;
  60   rtt_timeout_ = rtt_average_ + (4 * rtt_deviation_);
  61
  62   // Adjust for delayed acks with anti-spiking.
  63   // TODO(mbelshe): this seems high.
  64   rtt_timeout_ += 8 * send_rate_;
  65
  66   // Recognize the top and bottom of the congestion cycle.
  67   rtt_delta = rtt_latest_ - rtt_highwater_;
  68   rtt_highwater_ += rtt_delta / 1024;
  69
  70   rtt_delta = rtt_latest_ - rtt_lowwater_;
  71   if (rtt_delta > 0)
  72     rtt_lowwater_ += rtt_delta / 8192;
  73   else
  74     rtt_lowwater_ += rtt_delta / 256;
  75 }
  76
  77 void RttAndSendRateCalculator::AdjustSendRate() {
  78   last_sample_time_ = base::TimeTicks::Now();
  79
  80   base::TimeDelta time = last_sample_time_ - last_send_adjust_time_;
  81
  82   // We only adjust the send rate approximately every 16 samples.
  83   if (time.InMicroseconds() < 16 * send_rate_)
  84     return;
  85
  86   if (rtt_average_ >
  87       rtt_highwater_ + (5 * base::Time::kMicrosecondsPerMillisecond))
  88     rtt_seenrecenthigh_ = true;
  89   else if (rtt_average_ < rtt_lowwater_)
  90     rtt_seenrecentlow_ = true;
  91
  92   last_send_adjust_time_ = last_sample_time_;
  93
  94   // If too much time has elapsed, re-initialize the send_rate.
  95   if (time.InMicroseconds() >  10 * base::Time::kMicrosecondsPerSecond) {
  96     send_rate_ =  base::Time::kMicrosecondsPerSecond;  // restart.
  97     send_rate_ += randommod(send_rate_ / 8);
  98   }
  99
 100   // TODO(mbelshe):  Why is 128us a lower bound?
 101   if (send_rate_ >= 128) {
 102     // Additive increase:  adjust 1/N by a constant c.
 103     // rtt-fair additive increase: adjust 1/N by a constant c every nanosec.
 104     // approximation: adjust 1/N by cN every N nanoseconds.
 105
 106     // TODO(mbelshe): he used c == 2^-51. for nanosecs.
 107     //                I use c ==  2^31, for microsecs.
 108
 109     // i.e. N <- 1/(1/N + cN) = N/(1 + cN^2) every N nanosec.
 110     if (false && send_rate_ < 16384) {
 111       // N/(1+cN^2) approx N - cN^3
 112       // TODO(mbelshe):  note that he is using (cN)^3 here, not what he wrote.
 113       int32 msec = send_rate_ / 128;
 114       send_rate_ -= msec * msec * msec;
 115     } else {
 116       double d = send_rate_;
 117       send_rate_ = d / (1 + d * d / 2147483648.0);  // 2^31
 118     }
 119   }
 120
 121   if (rtt_phase_ == false) {
 122     if (rtt_seenolderhigh_) {
 123       rtt_phase_ = true;
 124       last_edge_time_ = last_sample_time_;
 125       send_rate_ += randommod(send_rate_ / 4);
 126     }
 127   } else {
 128     if (rtt_seenolderlow_) {
 129       rtt_phase_ = false;
 130     }
 131   }
 132
 133   rtt_seenolderhigh_ = rtt_seenrecenthigh_;
 134   rtt_seenolderlow_ = rtt_seenrecentlow_;
 135   rtt_seenrecenthigh_ = false;
 136   rtt_seenrecentlow_ = false;
 137
 138   AttemptToDoubleSendRate();
 139 }
 140
 141 void RttAndSendRateCalculator::AttemptToDoubleSendRate() {
 142   base::TimeDelta time_since_edge = last_sample_time_ - last_edge_time_;
 143   base::TimeDelta time_since_doubling =
 144       last_sample_time_ - last_doubling_time_;
 145
 146
 147   int32 threshold = 0;
 148   if (time_since_edge.InMicroseconds() <
 149       base::Time::kMicrosecondsPerSecond * 60) {
 150     threshold = (4 * send_rate_) +
 151                 (64 * rtt_timeout_) +
 152                 (5 * base::Time::kMicrosecondsPerSecond);
 153   } else {
 154     threshold = (4 * send_rate_) +
 155                 (2 * rtt_timeout_);
 156   }
 157   if (time_since_doubling.InMicroseconds() < threshold)
 158     return;
 159
 160   if (send_rate_ < 64)
 161     return;
 162
 163   send_rate_ /= 2;
 164   last_doubling_time_ = last_sample_time_;
 165 }
 166
 167 // returns a random number from 0 to val-1.
 168 int32 RttAndSendRateCalculator::randommod(int32 val) {
 169   return rand() % val;
 170 }
 171
 172 }  // namespace net