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 <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   DVLOG(1) << "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     DVLOG(1) << "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   DVLOG(1) << "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     DVLOG(1) << "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       DVLOG(1) << "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
    177