text: // Copyright (c) 2015 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "net/third_party/quiche/src/quic/core/congestion_control/cubic_bytes.h"
  
  #include <algorithm>
  #include <cmath>
  #include <cstdint>
  
  #include "net/third_party/quiche/src/quic/core/quic_constants.h"
  #include "net/third_party/quiche/src/quic/core/quic_packets.h"
  #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h"
  #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
  #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
  
  namespace quic {
  
  namespace {
  
  // Constants based on TCP defaults.
  // The following constants are in 2^10 fractions of a second instead of ms to
  // allow a 10 shift right to divide.
  const int kCubeScale = 40;  // 1024*1024^3 (first 1024 is from 0.100^3)
                              // where 0.100 is 100 ms which is the scaling
                              // round trip time.
  const int kCubeCongestionWindowScale = 410;
  // The cube factor for packets in bytes.
  const uint64_t kCubeFactor =
      (UINT64_C(1) << kCubeScale) / kCubeCongestionWindowScale / kDefaultTCPMSS;
  
  const float kDefaultCubicBackoffFactor = 0.7f;  // Default Cubic backoff factor.
  // Additional backoff factor when loss occurs in the concave part of the Cubic
  // curve. This additional backoff factor is expected to give up bandwidth to
  // new concurrent flows and speed up convergence.
  const float kBetaLastMax = 0.85f;
  
  }  // namespace
  
  CubicBytes::CubicBytes(const QuicClock* clock)
      : clock_(clock),
        num_connections_(kDefaultNumConnections),
        epoch_(QuicTime::Zero()) {
    ResetCubicState();
  }
  
  void CubicBytes::SetNumConnections(int num_connections) {
    num_connections_ = num_connections;
  }
  
  float CubicBytes::Alpha() const {
    // TCPFriendly alpha is described in Section 3.3 of the CUBIC paper. Note that
    // beta here is a cwnd multiplier, and is equal to 1-beta from the paper.
    // We derive the equivalent alpha for an N-connection emulation as:
    const float beta = Beta();
    return 3 * num_connections_ * num_connections_ * (1 - beta) / (1 + beta);
  }
  
  float CubicBytes::Beta() const {
    // kNConnectionBeta is the backoff factor after loss for our N-connection
    // emulation, which emulates the effective backoff of an ensemble of N
    // TCP-Reno connections on a single loss event. The effective multiplier is
    // computed as:
    return (num_connections_ - 1 + kDefaultCubicBackoffFactor) / num_connections_;
  }
  
  float CubicBytes::BetaLastMax() const {
    // BetaLastMax is the additional backoff factor after loss for our
    // N-connection emulation, which emulates the additional backoff of
    // an ensemble of N TCP-Reno connections on a single loss event. The
    // effective multiplier is computed as:
    return (num_connections_ - 1 + kBetaLastMax) / num_connections_;
  }
  
  void CubicBytes::ResetCubicState() {
    epoch_ = QuicTime::Zero();             // Reset time.
    last_max_congestion_window_ = 0;
    acked_bytes_count_ = 0;
    estimated_tcp_congestion_window_ = 0;
    origin_point_congestion_window_ = 0;
    time_to_origin_point_ = 0;
    last_target_congestion_window_ = 0;
  }
  
  void CubicBytes::OnApplicationLimited() {
    // When sender is not using the available congestion window, the window does
    // not grow. But to be RTT-independent, Cubic assumes that the sender has been
    // using the entire window during the time since the beginning of the current
    // "epoch" (the end of the last loss recovery period). Since
    // application-limited periods break this assumption, we reset the epoch when
    // in such a period. This reset effectively freezes congestion window growth
    // through application-limited periods and allows Cubic growth to continue
    // when the entire window is being used.
    epoch_ = QuicTime::Zero();
  }
  
  QuicByteCount CubicBytes::CongestionWindowAfterPacketLoss(
      QuicByteCount current_congestion_window) {
    // Since bytes-mode Reno mode slightly under-estimates the cwnd, we
    // may never reach precisely the last cwnd over the course of an
    // RTT.  Do not interpret a slight under-estimation as competing traffic.
    if (current_congestion_window + kDefaultTCPMSS <
        last_max_congestion_window_) {
      // We never reached the old max, so assume we are competing with
      // another flow. Use our extra back off factor to allow the other
      // flow to go up.
      last_max_congestion_window_ =
          static_cast<int>(BetaLastMax() * current_congestion_window);
    } else {
      last_max_congestion_window_ = current_congestion_window;
    }
    epoch_ = QuicTime::Zero();  // Reset time.
    return static_cast<int>(current_congestion_window * Beta());
  }
  
  QuicByteCount CubicBytes::CongestionWindowAfterAck(
      QuicByteCount acked_bytes,
      QuicByteCount current_congestion_window,
      QuicTime::Delta delay_min,
      QuicTime event_time) {
    acked_bytes_count_ += acked_bytes;
  
    if (!epoch_.IsInitialized()) {
      // First ACK after a loss event.
      QUIC_DVLOG(1) << "Start of epoch";
      epoch_ = event_time;               // Start of epoch.
      acked_bytes_count_ = acked_bytes;  // Reset count.
      // Reset estimated_tcp_congestion_window_ to be in sync with cubic.
      estimated_tcp_congestion_window_ = current_congestion_window;
      if (last_max_congestion_window_ <= current_congestion_window) {
        time_to_origin_point_ = 0;
        origin_point_congestion_window_ = current_congestion_window;
      } else {
        time_to_origin_point_ = static_cast<uint32_t>(
            cbrt(kCubeFactor *
                 (last_max_congestion_window_ - current_congestion_window)));
        origin_point_congestion_window_ = last_max_congestion_window_;
      }
    }
    // Change the time unit from microseconds to 2^10 fractions per second. Take
    // the round trip time in account. This is done to allow us to use shift as a
    // divide operator.
    int64_t elapsed_time =
        ((event_time + delay_min - epoch_).ToMicroseconds() << 10) /
        kNumMicrosPerSecond;
  
    // Right-shifts of negative, signed numbers have implementation-dependent
    // behavior, so force the offset to be positive, as is done in the kernel.
    uint64_t offset = std::abs(time_to_origin_point_ - elapsed_time);
  
    QuicByteCount delta_congestion_window = (kCubeCongestionWindowScale * offset *
                                             offset * offset * kDefaultTCPMSS) >>
                                            kCubeScale;
  
    const bool add_delta = elapsed_time > time_to_origin_point_;
    DCHECK(add_delta ||
           (origin_point_congestion_window_ > delta_congestion_window));
    QuicByteCount target_congestion_window =
        add_delta ? origin_point_congestion_window_ + delta_congestion_window
                  : origin_point_congestion_window_ - delta_congestion_window;
    // Limit the CWND increase to half the acked bytes.
    target_congestion_window =
        std::min(target_congestion_window,
                 current_congestion_window + acked_bytes_count_ / 2);
  
    DCHECK_LT(0u, estimated_tcp_congestion_window_);
    // Increase the window by approximately Alpha * 1 MSS of bytes every
    // time we ack an estimated tcp window of bytes.  For small
    // congestion windows (less than 25), the formula below will
    // increase slightly slower than linearly per estimated tcp window
    // of bytes.
    estimated_tcp_congestion_window_ += acked_bytes_count_ *
                                        (Alpha() * kDefaultTCPMSS) /
                                        estimated_tcp_congestion_window_;
    acked_bytes_count_ = 0;
  
    // We have a new cubic congestion window.
    last_target_congestion_window_ = target_congestion_window;
  
    // Compute target congestion_window based on cubic target and estimated TCP
    // congestion_window, use highest (fastest).
    if (target_congestion_window < estimated_tcp_congestion_window_) {
      target_congestion_window = estimated_tcp_congestion_window_;
    }
  
    QUIC_DVLOG(1) << "Final target congestion_window: "
                  << target_congestion_window;
    return target_congestion_window;
  }
  
  }  // namespace quic
  