Home | History | Annotate | Download | only in congestion_control 
      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   DLOG(INFO) << "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     DLOG(INFO) << "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   DLOG(INFO) << "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     DLOG(INFO) << "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       DLOG(INFO) << "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
    175