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
   9 #include "base/basictypes.h"
  10 #include "base/logging.h"
  11 #include "base/time/time.h"
  12 #include "net/quic/congestion_control/cube_root.h"
  13 #include "net/quic/quic_protocol.h"
  14
  15 using std::max;
  16
  17 namespace net {
  18
  19 namespace {
  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 const uint64 kCubeFactor = (GG_UINT64_C(1) << kCubeScale) /
  28     kCubeCongestionWindowScale;
  29 const uint32 kBetaSPDY = 939;  // Back off factor after loss for SPDY, reduces
  30                                // the CWND by 1/12th.
  31 const uint32 kBetaLastMax = 871;  // Additional back off factor after loss for
  32                                   // the stored max value.
  33 }  // namespace
  34
  35 Cubic::Cubic(const QuicClock* clock)
  36     : clock_(clock),
  37       epoch_(QuicTime::Zero()),
  38       last_update_time_(QuicTime::Zero()) {
  39   Reset();
  40 }
  41
  42 void Cubic::Reset() {
  43   epoch_ = QuicTime::Zero();  // Reset time.
  44   last_update_time_ = QuicTime::Zero();  // Reset time.
  45   last_congestion_window_ = 0;
  46   last_max_congestion_window_ = 0;
  47   acked_packets_count_ = 0;
  48   estimated_tcp_congestion_window_ = 0;
  49   origin_point_congestion_window_ = 0;
  50   time_to_origin_point_ = 0;
  51   last_target_congestion_window_ = 0;
  52 }
  53
  54 QuicTcpCongestionWindow Cubic::CongestionWindowAfterPacketLoss(
  55     QuicTcpCongestionWindow current_congestion_window) {
  56   if (current_congestion_window < last_max_congestion_window_) {
  57     // We never reached the old max, so assume we are competing with another
  58     // flow. Use our extra back off factor to allow the other flow to go up.
  59     last_max_congestion_window_ =
  60         (kBetaLastMax * current_congestion_window) >> 10;
  61   } else {
  62     last_max_congestion_window_ = current_congestion_window;
  63   }
  64   epoch_ = QuicTime::Zero();  // Reset time.
  65   return (current_congestion_window * kBetaSPDY) >> 10;
  66 }
  67
  68 QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck(
  69     QuicTcpCongestionWindow current_congestion_window,
  70     QuicTime::Delta delay_min) {
  71   acked_packets_count_ += 1;  // Packets acked.
  72   QuicTime current_time = clock_->ApproximateNow();
  73
  74   // Cubic is "independent" of RTT, the update is limited by the time elapsed.
  75   if (last_congestion_window_ == current_congestion_window &&
  76       (current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) {
  77     return max(last_target_congestion_window_,
  78                estimated_tcp_congestion_window_);
  79   }
  80   last_congestion_window_ = current_congestion_window;
  81   last_update_time_ = current_time;
  82
  83   if (!epoch_.IsInitialized()) {
  84     // First ACK after a loss event.
  85     DVLOG(1) << "Start of epoch";
  86     epoch_ = current_time;  // Start of epoch.
  87     acked_packets_count_ = 1;  // Reset count.
  88     // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
  89     estimated_tcp_congestion_window_ = current_congestion_window;
  90     if (last_max_congestion_window_ <= current_congestion_window) {
  91       time_to_origin_point_ = 0;
  92       origin_point_congestion_window_ = current_congestion_window;
  93     } else {
  94       time_to_origin_point_ = CubeRoot::Root(kCubeFactor *
  95           (last_max_congestion_window_ - current_congestion_window));
  96       origin_point_congestion_window_ =
  97           last_max_congestion_window_;
  98     }
  99   }
 100   // Change the time unit from microseconds to 2^10 fractions per second. Take
 101   // the round trip time in account. This is done to allow us to use shift as a
 102   // divide operator.
 103   int64 elapsed_time =
 104       (current_time.Add(delay_min).Subtract(epoch_).ToMicroseconds() << 10) /
 105       base::Time::kMicrosecondsPerSecond;
 106
 107   int64 offset = time_to_origin_point_ - elapsed_time;
 108   QuicTcpCongestionWindow delta_congestion_window = (kCubeCongestionWindowScale
 109       * offset * offset * offset) >> kCubeScale;
 110
 111   QuicTcpCongestionWindow target_congestion_window =
 112       origin_point_congestion_window_ - delta_congestion_window;
 113
 114   // We have a new cubic congestion window.
 115   last_target_congestion_window_ = target_congestion_window;
 116
 117   // Update estimated TCP congestion_window.
 118   // Note: we do a normal Reno congestion avoidance calculation not the
 119   // calculation described in section 3.3 TCP-friendly region of the document.
 120   while (acked_packets_count_ >= estimated_tcp_congestion_window_) {
 121     acked_packets_count_ -= estimated_tcp_congestion_window_;
 122     estimated_tcp_congestion_window_++;
 123   }
 124   // Compute target congestion_window based on cubic target and estimated TCP
 125   // congestion_window, use highest (fastest).
 126   if (target_congestion_window < estimated_tcp_congestion_window_) {
 127     target_congestion_window = estimated_tcp_congestion_window_;
 128   }
 129   DVLOG(1) << "Target congestion_window:" << target_congestion_window;
 130   return target_congestion_window;
 131 }
 132
 133 }  // namespace net