net/quic/congestion_control/cubic_bytes.cc

   1 // Copyright (c) 2015 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/cubic_bytes.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9
  10 #include "base/basictypes.h"
  11 #include "base/logging.h"
  12 #include "net/quic/quic_protocol.h"
  13
  14 using std::max;
  15
  16 namespace net {
  17
  18 namespace {
  19
  20 // Constants based on TCP defaults.
  21 // The following constants are in 2^10 fractions of a second instead of ms to
  22 // allow a 10 shift right to divide.
  23 const int kCubeScale = 40;  // 1024*1024^3 (first 1024 is from 0.100^3)
  24                             // where 0.100 is 100 ms which is the scaling
  25                             // round trip time.
  26 const int kCubeCongestionWindowScale = 410;
  27 // The cube factor for packets in bytes.
  28 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) /
  29                            kCubeCongestionWindowScale / kDefaultTCPMSS;
  30
  31 const uint32 kDefaultNumConnections = 2;
  32 const float kBeta = 0.7f;  // Default Cubic backoff factor.
  33 // Additional backoff factor when loss occurs in the concave part of the Cubic
  34 // curve. This additional backoff factor is expected to give up bandwidth to
  35 // new concurrent flows and speed up convergence.
  36 const float kBetaLastMax = 0.85f;
  37
  38 }  // namespace
  39
  40 CubicBytes::CubicBytes(const QuicClock* clock)
  41     : clock_(clock),
  42       num_connections_(kDefaultNumConnections),
  43       epoch_(QuicTime::Zero()),
  44       last_update_time_(QuicTime::Zero()) {
  45   Reset();
  46 }
  47
  48 void CubicBytes::SetNumConnections(int num_connections) {
  49   num_connections_ = num_connections;
  50 }
  51
  52 float CubicBytes::Alpha() const {
  53   // TCPFriendly alpha is described in Section 3.3 of the CUBIC paper. Note that
  54   // beta here is a cwnd multiplier, and is equal to 1-beta from the paper.
  55   // We derive the equivalent alpha for an N-connection emulation as:
  56   const float beta = Beta();
  57   return 3 * num_connections_ * num_connections_ * (1 - beta) / (1 + beta);
  58 }
  59
  60 float CubicBytes::Beta() const {
  61   // kNConnectionBeta is the backoff factor after loss for our N-connection
  62   // emulation, which emulates the effective backoff of an ensemble of N
  63   // TCP-Reno connections on a single loss event. The effective multiplier is
  64   // computed as:
  65   return (num_connections_ - 1 + kBeta) / num_connections_;
  66 }
  67
  68 void CubicBytes::Reset() {
  69   epoch_ = QuicTime::Zero();             // Reset time.
  70   last_update_time_ = QuicTime::Zero();  // Reset time.
  71   last_congestion_window_ = 0;
  72   last_max_congestion_window_ = 0;
  73   acked_bytes_count_ = 0;
  74   estimated_tcp_congestion_window_ = 0;
  75   origin_point_congestion_window_ = 0;
  76   time_to_origin_point_ = 0;
  77   last_target_congestion_window_ = 0;
  78 }
  79
  80 QuicByteCount CubicBytes::CongestionWindowAfterPacketLoss(
  81     QuicByteCount current_congestion_window) {
  82   if (current_congestion_window < last_max_congestion_window_) {
  83     // We never reached the old max, so assume we are competing with another
  84     // flow. Use our extra back off factor to allow the other flow to go up.
  85     last_max_congestion_window_ =
  86         static_cast<int>(kBetaLastMax * current_congestion_window);
  87   } else {
  88     last_max_congestion_window_ = current_congestion_window;
  89   }
  90   epoch_ = QuicTime::Zero();  // Reset time.
  91   return static_cast<int>(current_congestion_window * Beta());
  92 }
  93
  94 QuicByteCount CubicBytes::CongestionWindowAfterAck(
  95     QuicByteCount acked_bytes,
  96     QuicByteCount current_congestion_window,
  97     QuicTime::Delta delay_min) {
  98   acked_bytes_count_ += acked_bytes;
  99   QuicTime current_time = clock_->ApproximateNow();
 100
 101   // Cubic is "independent" of RTT, the update is limited by the time elapsed.
 102   if (last_congestion_window_ == current_congestion_window &&
 103       (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) {
 104     return max(last_target_congestion_window_,
 105                estimated_tcp_congestion_window_);
 106   }
 107   last_congestion_window_ = current_congestion_window;
 108   last_update_time_ = current_time;
 109
 110   if (!epoch_.IsInitialized()) {
 111     // First ACK after a loss event.
 112     DVLOG(1) << "Start of epoch";
 113     epoch_ = current_time;             // Start of epoch.
 114     acked_bytes_count_ = acked_bytes;  // Reset count.
 115     // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
 116     estimated_tcp_congestion_window_ = current_congestion_window;
 117     if (last_max_congestion_window_ <= current_congestion_window) {
 118       time_to_origin_point_ = 0;
 119       origin_point_congestion_window_ = current_congestion_window;
 120     } else {
 121       time_to_origin_point_ =
 122           static_cast<uint32>(cbrt(kCubeFactor * (last_max_congestion_window_ -
 123                                                   current_congestion_window)));
 124       origin_point_congestion_window_ = last_max_congestion_window_;
 125     }
 126   }
 127   // Change the time unit from microseconds to 2^10 fractions per second. Take
 128   // the round trip time in account. This is done to allow us to use shift as a
 129   // divide operator.
 130   int64 elapsed_time =
 131       (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) /
 132       kNumMicrosPerSecond;
 133
 134   int64 offset = time_to_origin_point_ - elapsed_time;
 135   QuicByteCount delta_congestion_window =
 136       ((kCubeCongestionWindowScale * offset * offset * offset) >> kCubeScale) *
 137       kDefaultTCPMSS;
 138
 139   QuicByteCount target_congestion_window =
 140       origin_point_congestion_window_ - delta_congestion_window;
 141
 142   DCHECK_LT(0u, estimated_tcp_congestion_window_);
 143   // Increase the window by Alpha * 1 MSS of bytes every time we ack an
 144   // estimated tcp window of bytes.
 145   estimated_tcp_congestion_window_ += acked_bytes_count_ *
 146                                       (Alpha() * kDefaultTCPMSS) /
 147                                       estimated_tcp_congestion_window_;
 148   acked_bytes_count_ = 0;
 149
 150   // We have a new cubic congestion window.
 151   last_target_congestion_window_ = target_congestion_window;
 152
 153   // Compute target congestion_window based on cubic target and estimated TCP
 154   // congestion_window, use highest (fastest).
 155   if (target_congestion_window < estimated_tcp_congestion_window_) {
 156     target_congestion_window = estimated_tcp_congestion_window_;
 157   }
 158
 159   DVLOG(1) << "Target congestion_window: " << target_congestion_window;
 160   return target_congestion_window;
 161 }
 162
 163 }  // namespace net