net/quic/congestion_control/inter_arrival_bitrate_ramp_up.cc

   1 // Copyright (c) 2013 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 "net/quic/congestion_control/inter_arrival_bitrate_ramp_up.h"
   6
   7 #include "base/basictypes.h"
   8 #include "base/logging.h"
   9 #include "net/quic/congestion_control/cube_root.h"
  10 #include "net/quic/quic_protocol.h"
  11
  12 namespace {
  13 // The following constants are in 2^10 fractions of a second instead of ms to
  14 // allow a 10 shift right to divide.
  15 const int kCubeScale = 40;  // 1024*1024^3 (first 1024 is from 0.100^3)
  16                             // where 0.100 is 100 ms which is the scaling
  17                             // round trip time.
  18 // TODO(pwestin): Tuning parameter, currently close to TCP cubic at 100ms RTT.
  19 const int kPacedCubeScale = 6000;
  20 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) / kPacedCubeScale;
  21 }  // namespace
  22
  23 namespace net {
  24
  25 InterArrivalBitrateRampUp::InterArrivalBitrateRampUp(const QuicClock* clock)
  26     : clock_(clock),
  27       current_rate_(QuicBandwidth::Zero()),
  28       channel_estimate_(QuicBandwidth::Zero()),
  29       available_channel_estimate_(QuicBandwidth::Zero()),
  30       halfway_point_(QuicBandwidth::Zero()),
  31       epoch_(QuicTime::Zero()),
  32       last_update_time_(QuicTime::Zero()) {
  33 }
  34
  35 void InterArrivalBitrateRampUp::Reset(QuicBandwidth new_rate,
  36                                       QuicBandwidth available_channel_estimate,
  37                                       QuicBandwidth channel_estimate) {
  38   epoch_ = clock_->ApproximateNow();
  39   last_update_time_ = epoch_;
  40   available_channel_estimate_ = std::max(new_rate, available_channel_estimate);
  41   channel_estimate_ = std::max(channel_estimate, available_channel_estimate_);
  42
  43   halfway_point_ = available_channel_estimate_.Add(
  44       (channel_estimate_.Subtract(available_channel_estimate_)).Scale(0.5f));
  45
  46   if (new_rate < available_channel_estimate_) {
  47     time_to_origin_point_ = CalcuateTimeToOriginPoint(
  48         available_channel_estimate_.Subtract(new_rate));
  49   } else if (new_rate >= channel_estimate_) {
  50     time_to_origin_point_ = 0;
  51   } else if (new_rate >= halfway_point_) {
  52     time_to_origin_point_ =
  53         CalcuateTimeToOriginPoint(channel_estimate_.Subtract(new_rate));
  54   } else {
  55     time_to_origin_point_ = CalcuateTimeToOriginPoint(
  56         new_rate.Subtract(available_channel_estimate_));
  57   }
  58   current_rate_ = new_rate;
  59   DVLOG(1) << "Reset; time to origin point:" << time_to_origin_point_;
  60 }
  61
  62 void InterArrivalBitrateRampUp::UpdateChannelEstimate(
  63     QuicBandwidth channel_estimate) {
  64   if (available_channel_estimate_ > channel_estimate ||
  65       current_rate_ > channel_estimate ||
  66       channel_estimate_ == channel_estimate) {
  67     // Ignore, because one of the following reasons:
  68     // 1) channel estimate is bellow our current available estimate which we
  69     //    value higher that this estimate.
  70     // 2) channel estimate is bellow our current send rate.
  71     // 3) channel estimate has not changed.
  72     return;
  73   }
  74   if (available_channel_estimate_ == halfway_point_ &&
  75       channel_estimate_  == halfway_point_) {
  76     // First time we get a usable channel estimate.
  77     channel_estimate_ = channel_estimate;
  78     halfway_point_ = available_channel_estimate_.Add(
  79         (channel_estimate_.Subtract(available_channel_estimate_).Scale(0.5f)));
  80     DVLOG(1) << "UpdateChannelEstimate; first usable value:"
  81                << channel_estimate.ToKBitsPerSecond() << " Kbits/s";
  82     return;
  83   }
  84   if (current_rate_ < halfway_point_) {
  85     // Update channel estimate without recalculating if we are bellow the
  86     // halfway point.
  87     channel_estimate_ = channel_estimate;
  88     return;
  89   }
  90   // We are between halfway point and our channel_estimate.
  91   epoch_ = clock_->ApproximateNow();
  92   last_update_time_ = epoch_;
  93   channel_estimate_ = channel_estimate;
  94
  95   time_to_origin_point_ =
  96       CalcuateTimeToOriginPoint(channel_estimate_.Subtract(current_rate_));
  97
  98   DVLOG(1) << "UpdateChannelEstimate; time to origin point:"
  99              << time_to_origin_point_;
 100 }
 101
 102 QuicBandwidth InterArrivalBitrateRampUp::GetNewBitrate(
 103     QuicBandwidth sent_bitrate) {
 104   DCHECK(epoch_.IsInitialized());
 105   QuicTime current_time = clock_->ApproximateNow();
 106   // Cubic is "independent" of RTT, the update is limited by the time elapsed.
 107   if (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval()) {
 108     return current_rate_;
 109   }
 110   QuicTime::Delta time_from_last_update =
 111       current_time.Subtract(last_update_time_);
 112
 113   last_update_time_ = current_time;
 114
 115   if (!sent_bitrate.IsZero() &&
 116       sent_bitrate.Add(sent_bitrate) < current_rate_) {
 117     // Don't go up in bitrate when we are not sending.
 118     // We need to update the epoch to reflect this state.
 119     epoch_ = epoch_.Add(time_from_last_update);
 120     DVLOG(1) << "Don't increase; our sent bitrate is:"
 121                << sent_bitrate.ToKBitsPerSecond() << " Kbits/s"
 122                << " current target rate is:"
 123                << current_rate_.ToKBitsPerSecond() << " Kbits/s";
 124     return current_rate_;
 125   }
 126   QuicTime::Delta time_from_epoch = current_time.Subtract(epoch_);
 127
 128   // Change the time unit from microseconds to 2^10 fractions per second. This
 129   // is done to allow us to use shift as a divide operator.
 130   int64 elapsed_time = (time_from_epoch.ToMicroseconds() << 10) /
 131       kNumMicrosPerSecond;
 132
 133   int64 offset = time_to_origin_point_ - elapsed_time;
 134   // Note: using int64 since QuicBandwidth can't be negative
 135   int64 delta_pace_kbps = (kPacedCubeScale * offset * offset * offset) >>
 136         kCubeScale;
 137
 138   bool start_bellow_halfway_point = false;
 139   if (current_rate_ < halfway_point_) {
 140     start_bellow_halfway_point = true;
 141
 142     // available_channel_estimate_ is the orgin of the cubic function.
 143     QuicBandwidth current_rate = QuicBandwidth::FromBytesPerSecond(
 144         available_channel_estimate_.ToBytesPerSecond() -
 145             (delta_pace_kbps << 10));
 146
 147     if (start_bellow_halfway_point && current_rate >= halfway_point_) {
 148       // We passed the halfway point, recalculate with new orgin.
 149       epoch_ = clock_->ApproximateNow();
 150       // channel_estimate_ is the new orgin of the cubic function.
 151       if (current_rate >= channel_estimate_) {
 152         time_to_origin_point_ = 0;
 153       } else {
 154         time_to_origin_point_ =
 155             CalcuateTimeToOriginPoint(channel_estimate_.Subtract(current_rate));
 156       }
 157       DVLOG(1) << "Passed the halfway point; time to origin point:"
 158                  << time_to_origin_point_;
 159     }
 160     current_rate_ = current_rate;
 161   } else {
 162     // channel_estimate_ is the orgin of the cubic function.
 163     current_rate_ = QuicBandwidth::FromBytesPerSecond(
 164         channel_estimate_.ToBytesPerSecond() - (delta_pace_kbps << 10));
 165   }
 166   return current_rate_;
 167 }
 168
 169 uint32 InterArrivalBitrateRampUp::CalcuateTimeToOriginPoint(
 170     QuicBandwidth rate_difference) const {
 171   return CubeRoot::Root(kCubeFactor * rate_difference.ToKBytesPerSecond());
 172 }
 173
 174 }  // namespace net