net/quic/congestion_control/cubic.cc

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