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