/*
 *  Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

#include "modules/congestion_controller/bbr/bbr_network_controller.h"

#include <algorithm>
#include <array>
#include <string>
#include <vector>

#include "rtc_base/checks.h"
#include "rtc_base/experiments/congestion_controller_experiment.h"
#include "rtc_base/logging.h"
#include "rtc_base/system/fallthrough.h"

namespace webrtc {
namespace bbr {
namespace {

// If greater than zero, mean RTT variation is multiplied by the specified
// factor and added to the congestion window limit.
const double kBbrRttVariationWeight = 0.0f;

// Congestion window gain for QUIC BBR during PROBE_BW phase.
const double kProbeBWCongestionWindowGain = 2.0f;

// The maximum packet size of any QUIC packet, based on ethernet's max size,
// minus the IP and UDP headers. IPv6 has a 40 byte header, UDP adds an
// additional 8 bytes.  This is a total overhead of 48 bytes.  Ethernet's
// max packet size is 1500 bytes,  1500 - 48 = 1452.
const DataSize kMaxPacketSize = DataSize::bytes(1452);

// Default maximum packet size used in the Linux TCP implementation.
// Used in QUIC for congestion window computations in bytes.
const DataSize kDefaultTCPMSS = DataSize::bytes(1460);
// Constants based on TCP defaults.
const DataSize kMaxSegmentSize = kDefaultTCPMSS;
// The minimum CWND to ensure delayed acks don't reduce bandwidth measurements.
// Does not inflate the pacing rate.
const DataSize kMinimumCongestionWindow = DataSize::bytes(1000);

// The gain used for the slow start, equal to 2/ln(2).
const double kHighGain = 2.885f;
// The gain used in STARTUP after loss has been detected.
// 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
// in measured bandwidth.
const double kStartupAfterLossGain = 1.5;
// The gain used to drain the queue after the slow start.
const double kDrainGain = 1.f / kHighGain;

// The length of the gain cycle.
const size_t kGainCycleLength = 8;
// The size of the bandwidth filter window, in round-trips.
const BbrRoundTripCount kBandwidthWindowSize = kGainCycleLength + 2;

// The time after which the current min_rtt value expires.
constexpr int64_t kMinRttExpirySeconds = 10;
// The minimum time the connection can spend in PROBE_RTT mode.
constexpr int64_t kProbeRttTimeMs = 200;
// If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
// within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
// will exit the STARTUP mode.
const double kStartupGrowthTarget = 1.25;
// Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
// we don't need to enter PROBE_RTT.
const double kSimilarMinRttThreshold = 1.125;

constexpr int64_t kInitialRttMs = 200;
constexpr int64_t kInitialBandwidthKbps = 300;

constexpr int64_t kMaxRttMs = 1000;
constexpr int64_t kMaxBandwidthKbps = 5000;

constexpr int64_t kInitialCongestionWindowBytes =
    (kInitialRttMs * kInitialBandwidthKbps) / 8;
constexpr int64_t kDefaultMaxCongestionWindowBytes =
    (kMaxRttMs * kMaxBandwidthKbps) / 8;
}  // namespace

BbrNetworkController::BbrControllerConfig
BbrNetworkController::BbrControllerConfig::DefaultConfig() {
  BbrControllerConfig config;
  config.probe_bw_pacing_gain_offset = 0.25;
  config.encoder_rate_gain = 1;
  config.encoder_rate_gain_in_probe_rtt = 1;
  config.exit_startup_rtt_threshold_ms = 0;
  config.probe_rtt_congestion_window_gain = 0.75;
  config.exit_startup_on_loss = true;
  config.num_startup_rtts = 3;
  config.rate_based_recovery = false;
  config.max_aggregation_bytes_multiplier = 0;
  config.slower_startup = false;
  config.rate_based_startup = false;
  config.fully_drain_queue = false;
  config.initial_conservation_in_startup = CONSERVATION;
  config.max_ack_height_window_multiplier = 1;
  config.probe_rtt_based_on_bdp = false;
  config.probe_rtt_skipped_if_similar_rtt = false;
  config.probe_rtt_disabled_if_app_limited = false;

  return config;
}

BbrNetworkController::BbrControllerConfig
BbrNetworkController::BbrControllerConfig::ExperimentConfig() {
  auto exp = CongestionControllerExperiment::GetBbrExperimentConfig();
  if (exp) {
    BbrControllerConfig config;
    config.exit_startup_on_loss = exp->exit_startup_on_loss;
    config.exit_startup_rtt_threshold_ms = exp->exit_startup_rtt_threshold_ms;
    config.fully_drain_queue = exp->fully_drain_queue;
    config.initial_conservation_in_startup =
        static_cast<RecoveryState>(exp->initial_conservation_in_startup);
    config.num_startup_rtts = exp->num_startup_rtts;
    config.probe_rtt_based_on_bdp = exp->probe_rtt_based_on_bdp;
    config.probe_rtt_disabled_if_app_limited =
        exp->probe_rtt_disabled_if_app_limited;
    config.probe_rtt_skipped_if_similar_rtt =
        exp->probe_rtt_skipped_if_similar_rtt;
    config.rate_based_recovery = exp->rate_based_recovery;
    config.rate_based_startup = exp->rate_based_startup;
    config.slower_startup = exp->slower_startup;
    config.encoder_rate_gain = exp->encoder_rate_gain;
    config.encoder_rate_gain_in_probe_rtt = exp->encoder_rate_gain_in_probe_rtt;
    config.max_ack_height_window_multiplier =
        exp->max_ack_height_window_multiplier;
    config.max_aggregation_bytes_multiplier =
        exp->max_aggregation_bytes_multiplier;
    config.probe_bw_pacing_gain_offset = exp->probe_bw_pacing_gain_offset;
    config.probe_rtt_congestion_window_gain =
        exp->probe_rtt_congestion_window_gain;
    return config;
  } else {
    return DefaultConfig();
  }
}

BbrNetworkController::DebugState::DebugState(const BbrNetworkController& sender)
    : mode(sender.mode_),
      max_bandwidth(sender.max_bandwidth_.GetBest()),
      round_trip_count(sender.round_trip_count_),
      gain_cycle_index(sender.cycle_current_offset_),
      congestion_window(sender.congestion_window_),
      is_at_full_bandwidth(sender.is_at_full_bandwidth_),
      bandwidth_at_last_round(sender.bandwidth_at_last_round_),
      rounds_without_bandwidth_gain(sender.rounds_without_bandwidth_gain_),
      min_rtt(sender.min_rtt_),
      min_rtt_timestamp(sender.min_rtt_timestamp_),
      recovery_state(sender.recovery_state_),
      recovery_window(sender.recovery_window_),
      last_sample_is_app_limited(sender.last_sample_is_app_limited_),
      end_of_app_limited_phase(sender.sampler_->end_of_app_limited_phase()) {}

BbrNetworkController::DebugState::DebugState(const DebugState& state) = default;

BbrNetworkController::BbrNetworkController(NetworkControllerConfig config)
    : rtt_stats_(),
      random_(10),
      loss_rate_(),
      mode_(STARTUP),
      sampler_(new BandwidthSampler()),
      round_trip_count_(0),
      last_sent_packet_(0),
      current_round_trip_end_(0),
      max_bandwidth_(kBandwidthWindowSize, DataRate::Zero(), 0),
      default_bandwidth_(DataRate::kbps(kInitialBandwidthKbps)),
      max_ack_height_(kBandwidthWindowSize, DataSize::Zero(), 0),
      aggregation_epoch_start_time_(),
      aggregation_epoch_bytes_(DataSize::Zero()),
      bytes_acked_since_queue_drained_(DataSize::Zero()),
      max_aggregation_bytes_multiplier_(0),
      min_rtt_(TimeDelta::Zero()),
      last_rtt_(TimeDelta::Zero()),
      min_rtt_timestamp_(Timestamp::ms(0)),
      congestion_window_(DataSize::bytes(kInitialCongestionWindowBytes)),
      initial_congestion_window_(
          DataSize::bytes(kInitialCongestionWindowBytes)),
      max_congestion_window_(DataSize::bytes(kDefaultMaxCongestionWindowBytes)),
      pacing_rate_(DataRate::Zero()),
      pacing_gain_(1),
      congestion_window_gain_constant_(kProbeBWCongestionWindowGain),
      rtt_variance_weight_(kBbrRttVariationWeight),
      cycle_current_offset_(0),
      last_cycle_start_(Timestamp::ms(0)),
      is_at_full_bandwidth_(false),
      rounds_without_bandwidth_gain_(0),
      bandwidth_at_last_round_(DataRate::Zero()),
      exit_probe_rtt_at_(),
      probe_rtt_round_passed_(false),
      last_sample_is_app_limited_(false),
      recovery_state_(NOT_IN_RECOVERY),
      end_recovery_at_(),
      recovery_window_(max_congestion_window_),
      app_limited_since_last_probe_rtt_(false),
      min_rtt_since_last_probe_rtt_(TimeDelta::PlusInfinity()) {
  RTC_LOG(LS_INFO) << "Creating BBR controller";
  config_ = BbrControllerConfig::ExperimentConfig();
  if (config.starting_bandwidth.IsFinite())
    default_bandwidth_ = config.starting_bandwidth;
  constraints_ = config.constraints;
  Reset();
  if (config_.num_startup_rtts > 0) {
    EnterStartupMode();
  } else {
    is_at_full_bandwidth_ = true;
    EnterProbeBandwidthMode(constraints_->at_time);
  }
}

BbrNetworkController::~BbrNetworkController() {}

void BbrNetworkController::Reset() {
  round_trip_count_ = 0;
  rounds_without_bandwidth_gain_ = 0;
  is_at_full_bandwidth_ = false;
  EnterStartupMode();
}

NetworkControlUpdate BbrNetworkController::CreateRateUpdate(Timestamp at_time) {
  DataRate bandwidth = BandwidthEstimate();
  if (bandwidth.IsZero())
    bandwidth = default_bandwidth_;
  TimeDelta rtt = GetMinRtt();
  DataRate pacing_rate = PacingRate();
  DataRate target_rate = bandwidth;
  if (mode_ == PROBE_RTT)
    target_rate = bandwidth * config_.encoder_rate_gain_in_probe_rtt;
  else
    target_rate = bandwidth * config_.encoder_rate_gain;
  target_rate = std::min(target_rate, pacing_rate);

  if (constraints_) {
    if (constraints_->max_data_rate) {
      target_rate = std::min(target_rate, *constraints_->max_data_rate);
      pacing_rate = std::min(pacing_rate, *constraints_->max_data_rate);
    }
    if (constraints_->min_data_rate) {
      target_rate = std::max(target_rate, *constraints_->min_data_rate);
      pacing_rate = std::max(pacing_rate, *constraints_->min_data_rate);
    }
  }

  NetworkControlUpdate update;

  TargetTransferRate target_rate_msg;
  target_rate_msg.network_estimate.at_time = at_time;
  target_rate_msg.network_estimate.bandwidth = bandwidth;
  target_rate_msg.network_estimate.round_trip_time = rtt;

  // TODO(srte): Fill in field below with proper value.
  target_rate_msg.network_estimate.loss_rate_ratio = 0;
  // In in PROBE_BW, target bandwidth is expected to vary over the cycle period.
  // In other modes the is no given period, therefore the same value as in
  // PROBE_BW is used for consistency.
  target_rate_msg.network_estimate.bwe_period =
      rtt * static_cast<int64_t>(kGainCycleLength);

  target_rate_msg.target_rate = target_rate;
  target_rate_msg.at_time = at_time;
  update.target_rate = target_rate_msg;

  PacerConfig pacer_config;
  // A small time window ensures an even pacing rate.
  pacer_config.time_window = rtt * 0.25;
  pacer_config.data_window = pacer_config.time_window * pacing_rate;

  if (IsProbingForMoreBandwidth())
    pacer_config.pad_window = pacer_config.data_window;
  else
    pacer_config.pad_window = DataSize::Zero();

  pacer_config.at_time = at_time;
  update.pacer_config = pacer_config;

  update.congestion_window = GetCongestionWindow();
  return update;
}

NetworkControlUpdate BbrNetworkController::OnNetworkAvailability(
    NetworkAvailability msg) {
  Reset();
  rtt_stats_.OnConnectionMigration();
  return CreateRateUpdate(msg.at_time);
}

NetworkControlUpdate BbrNetworkController::OnNetworkRouteChange(
    NetworkRouteChange msg) {
  constraints_ = msg.constraints;
  Reset();
  if (msg.starting_rate)
    default_bandwidth_ = *msg.starting_rate;

  rtt_stats_.OnConnectionMigration();
  return CreateRateUpdate(msg.at_time);
}

NetworkControlUpdate BbrNetworkController::OnProcessInterval(
    ProcessInterval msg) {
  return CreateRateUpdate(msg.at_time);
}

NetworkControlUpdate BbrNetworkController::OnStreamsConfig(StreamsConfig msg) {
  return NetworkControlUpdate();
}

NetworkControlUpdate BbrNetworkController::OnTargetRateConstraints(
    TargetRateConstraints msg) {
  constraints_ = msg;
  return CreateRateUpdate(msg.at_time);
}

bool BbrNetworkController::InSlowStart() const {
  return mode_ == STARTUP;
}

NetworkControlUpdate BbrNetworkController::OnSentPacket(SentPacket msg) {
  last_sent_packet_ = msg.sequence_number;

  if (!aggregation_epoch_start_time_) {
    aggregation_epoch_start_time_ = msg.send_time;
  }

  sampler_->OnPacketSent(msg.send_time, msg.sequence_number, msg.size,
                         msg.data_in_flight);
  return NetworkControlUpdate();
}

bool BbrNetworkController::CanSend(DataSize bytes_in_flight) {
  return bytes_in_flight < GetCongestionWindow();
}

DataRate BbrNetworkController::PacingRate() const {
  if (pacing_rate_.IsZero()) {
    return kHighGain * initial_congestion_window_ / GetMinRtt();
  }
  return pacing_rate_;
}

DataRate BbrNetworkController::BandwidthEstimate() const {
  return max_bandwidth_.GetBest();
}

DataSize BbrNetworkController::GetCongestionWindow() const {
  if (mode_ == PROBE_RTT) {
    return ProbeRttCongestionWindow();
  }

  if (InRecovery() && !config_.rate_based_recovery &&
      !(config_.rate_based_startup && mode_ == STARTUP)) {
    return std::min(congestion_window_, recovery_window_);
  }

  return congestion_window_;
}

double BbrNetworkController::GetPacingGain(int round_offset) const {
  if (round_offset == 0)
    return 1 + config_.probe_bw_pacing_gain_offset;
  else if (round_offset == 1)
    return 1 - config_.probe_bw_pacing_gain_offset;
  else
    return 1;
}

bool BbrNetworkController::InRecovery() const {
  return recovery_state_ != NOT_IN_RECOVERY;
}

bool BbrNetworkController::IsProbingForMoreBandwidth() const {
  return (mode_ == PROBE_BW && pacing_gain_ > 1) || mode_ == STARTUP;
}

NetworkControlUpdate BbrNetworkController::OnTransportPacketsFeedback(
    TransportPacketsFeedback msg) {
  Timestamp feedback_recv_time = msg.feedback_time;
  rtc::Optional<SentPacket> last_sent_packet =
      msg.PacketsWithFeedback().back().sent_packet;
  if (!last_sent_packet.has_value()) {
    RTC_LOG(LS_WARNING) << "Last ack packet not in history, no RTT update";
  } else {
    Timestamp send_time = last_sent_packet->send_time;
    TimeDelta send_delta = feedback_recv_time - send_time;
    rtt_stats_.UpdateRtt(send_delta, TimeDelta::Zero(), feedback_recv_time);
  }

  const DataSize total_data_acked_before = sampler_->total_data_acked();

  bool is_round_start = false;
  bool min_rtt_expired = false;

  std::vector<PacketResult> lost_packets = msg.LostWithSendInfo();
  DiscardLostPackets(lost_packets);

  std::vector<PacketResult> acked_packets = msg.ReceivedWithSendInfo();

  int packets_sent =
      static_cast<int>(lost_packets.size() + acked_packets.size());
  int packets_lost = static_cast<int>(lost_packets.size());
  loss_rate_.UpdateWithLossStatus(msg.feedback_time.ms(), packets_sent,
                                  packets_lost);

  // Input the new data into the BBR model of the connection.
  if (!acked_packets.empty()) {
    int64_t last_acked_packet =
        acked_packets.rbegin()->sent_packet->sequence_number;

    is_round_start = UpdateRoundTripCounter(last_acked_packet);
    min_rtt_expired =
        UpdateBandwidthAndMinRtt(msg.feedback_time, acked_packets);
    UpdateRecoveryState(last_acked_packet, !lost_packets.empty(),
                        is_round_start);

    const DataSize data_acked =
        sampler_->total_data_acked() - total_data_acked_before;

    UpdateAckAggregationBytes(msg.feedback_time, data_acked);
    if (max_aggregation_bytes_multiplier_ > 0) {
      if (msg.data_in_flight <=
          1.25 * GetTargetCongestionWindow(pacing_gain_)) {
        bytes_acked_since_queue_drained_ = DataSize::Zero();
      } else {
        bytes_acked_since_queue_drained_ += data_acked;
      }
      }
  }

  // Handle logic specific to PROBE_BW mode.
  if (mode_ == PROBE_BW) {
    UpdateGainCyclePhase(msg.feedback_time, msg.prior_in_flight,
                         !lost_packets.empty());
  }

  // Handle logic specific to STARTUP and DRAIN modes.
  if (is_round_start && !is_at_full_bandwidth_) {
    CheckIfFullBandwidthReached();
  }
  MaybeExitStartupOrDrain(msg);

  // Handle logic specific to PROBE_RTT.
  MaybeEnterOrExitProbeRtt(msg, is_round_start, min_rtt_expired);

  // Calculate number of packets acked and lost.
  DataSize data_acked = sampler_->total_data_acked() - total_data_acked_before;
  DataSize data_lost = DataSize::Zero();
  for (const PacketResult& packet : lost_packets) {
    data_lost += packet.sent_packet->size;
  }

  // After the model is updated, recalculate the pacing rate and congestion
  // window.
  CalculatePacingRate();
  CalculateCongestionWindow(data_acked);
  CalculateRecoveryWindow(data_acked, data_lost, msg.data_in_flight);
  // Cleanup internal state.
  if (!acked_packets.empty()) {
    sampler_->RemoveObsoletePackets(
        acked_packets.back().sent_packet->sequence_number);
  }
  return CreateRateUpdate(msg.feedback_time);
}

NetworkControlUpdate BbrNetworkController::OnRemoteBitrateReport(
    RemoteBitrateReport msg) {
  return NetworkControlUpdate();
}
NetworkControlUpdate BbrNetworkController::OnRoundTripTimeUpdate(
    RoundTripTimeUpdate msg) {
  return NetworkControlUpdate();
}
NetworkControlUpdate BbrNetworkController::OnTransportLossReport(
    TransportLossReport msg) {
  return NetworkControlUpdate();
}

TimeDelta BbrNetworkController::GetMinRtt() const {
  return !min_rtt_.IsZero() ? min_rtt_
                            : TimeDelta::us(rtt_stats_.initial_rtt_us());
}

DataSize BbrNetworkController::GetTargetCongestionWindow(double gain) const {
  DataSize bdp = GetMinRtt() * BandwidthEstimate();
  DataSize congestion_window = gain * bdp;

  // BDP estimate will be zero if no bandwidth samples are available yet.
  if (congestion_window.IsZero()) {
    congestion_window = gain * initial_congestion_window_;
  }

  return std::max(congestion_window, kMinimumCongestionWindow);
}

DataSize BbrNetworkController::ProbeRttCongestionWindow() const {
  if (config_.probe_rtt_based_on_bdp) {
    return GetTargetCongestionWindow(config_.probe_rtt_congestion_window_gain);
  }
  return kMinimumCongestionWindow;
}

void BbrNetworkController::EnterStartupMode() {
  mode_ = STARTUP;
  pacing_gain_ = kHighGain;
  congestion_window_gain_ = kHighGain;
}

void BbrNetworkController::EnterProbeBandwidthMode(Timestamp now) {
  mode_ = PROBE_BW;
  congestion_window_gain_ = congestion_window_gain_constant_;

  // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
  // excluded because in that case increased gain and decreased gain would not
  // follow each other.
  cycle_current_offset_ = random_.Rand(kGainCycleLength - 2);
  if (cycle_current_offset_ >= 1) {
    cycle_current_offset_ += 1;
  }

  last_cycle_start_ = now;
  pacing_gain_ = GetPacingGain(cycle_current_offset_);
}

void BbrNetworkController::DiscardLostPackets(
    const std::vector<PacketResult>& lost_packets) {
  for (const PacketResult& packet : lost_packets) {
    sampler_->OnPacketLost(packet.sent_packet->sequence_number);
  }
}

bool BbrNetworkController::UpdateRoundTripCounter(int64_t last_acked_packet) {
  if (last_acked_packet > current_round_trip_end_) {
    round_trip_count_++;
    current_round_trip_end_ = last_sent_packet_;
    return true;
  }

  return false;
}

bool BbrNetworkController::UpdateBandwidthAndMinRtt(
    Timestamp now,
    const std::vector<PacketResult>& acked_packets) {
  TimeDelta sample_rtt = TimeDelta::PlusInfinity();
  for (const auto& packet : acked_packets) {
    BandwidthSample bandwidth_sample = sampler_->OnPacketAcknowledged(
        now, packet.sent_packet->sequence_number);
    last_sample_is_app_limited_ = bandwidth_sample.is_app_limited;
    if (!bandwidth_sample.rtt.IsZero()) {
      sample_rtt = std::min(sample_rtt, bandwidth_sample.rtt);
    }

    if (!bandwidth_sample.is_app_limited ||
        bandwidth_sample.bandwidth > BandwidthEstimate()) {
      max_bandwidth_.Update(bandwidth_sample.bandwidth, round_trip_count_);
    }
  }

  // If none of the RTT samples are valid, return immediately.
  if (sample_rtt.IsInfinite()) {
    return false;
  }

  last_rtt_ = sample_rtt;
  min_rtt_since_last_probe_rtt_ =
      std::min(min_rtt_since_last_probe_rtt_, sample_rtt);

  const TimeDelta kMinRttExpiry = TimeDelta::seconds(kMinRttExpirySeconds);
  // Do not expire min_rtt if none was ever available.
  bool min_rtt_expired =
      !min_rtt_.IsZero() && (now > (min_rtt_timestamp_ + kMinRttExpiry));

  if (min_rtt_expired || sample_rtt < min_rtt_ || min_rtt_.IsZero()) {
    if (ShouldExtendMinRttExpiry()) {
      min_rtt_expired = false;
    } else {
      min_rtt_ = sample_rtt;
    }
    min_rtt_timestamp_ = now;
    // Reset since_last_probe_rtt fields.
    min_rtt_since_last_probe_rtt_ = TimeDelta::PlusInfinity();
    app_limited_since_last_probe_rtt_ = false;
  }

  return min_rtt_expired;
}

bool BbrNetworkController::ShouldExtendMinRttExpiry() const {
  if (config_.probe_rtt_disabled_if_app_limited &&
      app_limited_since_last_probe_rtt_) {
    // Extend the current min_rtt if we've been app limited recently.
    return true;
  }
  const bool min_rtt_increased_since_last_probe =
      min_rtt_since_last_probe_rtt_ > min_rtt_ * kSimilarMinRttThreshold;
  if (config_.probe_rtt_skipped_if_similar_rtt &&
      app_limited_since_last_probe_rtt_ &&
      !min_rtt_increased_since_last_probe) {
    // Extend the current min_rtt if we've been app limited recently and an rtt
    // has been measured in that time that's less than 12.5% more than the
    // current min_rtt.
    return true;
  }
  return false;
}

void BbrNetworkController::UpdateGainCyclePhase(Timestamp now,
                                                DataSize prior_in_flight,
                                                bool has_losses) {
  // In most cases, the cycle is advanced after an RTT passes.
  bool should_advance_gain_cycling = now - last_cycle_start_ > GetMinRtt();

  // If the pacing gain is above 1.0, the connection is trying to probe the
  // bandwidth by increasing the number of bytes in flight to at least
  // pacing_gain * BDP.  Make sure that it actually reaches the target, as long
  // as there are no losses suggesting that the buffers are not able to hold
  // that much.
  if (pacing_gain_ > 1.0 && !has_losses &&
      prior_in_flight < GetTargetCongestionWindow(pacing_gain_)) {
    should_advance_gain_cycling = false;
  }

  // If pacing gain is below 1.0, the connection is trying to drain the extra
  // queue which could have been incurred by probing prior to it.  If the number
  // of bytes in flight falls down to the estimated BDP value earlier, conclude
  // that the queue has been successfully drained and exit this cycle early.
  if (pacing_gain_ < 1.0 && prior_in_flight <= GetTargetCongestionWindow(1)) {
    should_advance_gain_cycling = true;
  }

  if (should_advance_gain_cycling) {
    cycle_current_offset_ = (cycle_current_offset_ + 1) % kGainCycleLength;
    last_cycle_start_ = now;
    // Stay in low gain mode until the target BDP is hit.
    // Low gain mode will be exited immediately when the target BDP is achieved.
    if (config_.fully_drain_queue && pacing_gain_ < 1 &&
        GetPacingGain(cycle_current_offset_) == 1 &&
        prior_in_flight > GetTargetCongestionWindow(1)) {
      return;
    }
    pacing_gain_ = GetPacingGain(cycle_current_offset_);
  }
}

void BbrNetworkController::CheckIfFullBandwidthReached() {
  if (last_sample_is_app_limited_) {
    return;
  }

  DataRate target = bandwidth_at_last_round_ * kStartupGrowthTarget;
  if (BandwidthEstimate() >= target) {
    bandwidth_at_last_round_ = BandwidthEstimate();
    rounds_without_bandwidth_gain_ = 0;
    return;
  }

  rounds_without_bandwidth_gain_++;
  if ((rounds_without_bandwidth_gain_ >= config_.num_startup_rtts) ||
      (config_.exit_startup_on_loss && InRecovery())) {
    is_at_full_bandwidth_ = true;
  }
}

void BbrNetworkController::MaybeExitStartupOrDrain(
    const TransportPacketsFeedback& msg) {
  int64_t exit_threshold_ms = config_.exit_startup_rtt_threshold_ms;
  bool rtt_over_threshold =
      exit_threshold_ms > 0 && (last_rtt_ - min_rtt_).ms() > exit_threshold_ms;
  if (mode_ == STARTUP && (is_at_full_bandwidth_ || rtt_over_threshold)) {
    if (rtt_over_threshold)
      RTC_LOG(LS_INFO) << "Exiting startup due to rtt increase from: "
                       << ToString(min_rtt_) << " to:" << ToString(last_rtt_)
                       << " > "
                       << ToString(min_rtt_ + TimeDelta::ms(exit_threshold_ms));
    mode_ = DRAIN;
    pacing_gain_ = kDrainGain;
    congestion_window_gain_ = kHighGain;
  }
  if (mode_ == DRAIN && msg.data_in_flight <= GetTargetCongestionWindow(1)) {
    EnterProbeBandwidthMode(msg.feedback_time);
  }
}

void BbrNetworkController::MaybeEnterOrExitProbeRtt(
    const TransportPacketsFeedback& msg,
    bool is_round_start,
    bool min_rtt_expired) {
  if (min_rtt_expired && mode_ != PROBE_RTT) {
    mode_ = PROBE_RTT;
    pacing_gain_ = 1;
    // Do not decide on the time to exit PROBE_RTT until the |bytes_in_flight|
    // is at the target small value.
    exit_probe_rtt_at_.reset();
  }

  if (mode_ == PROBE_RTT) {
    sampler_->OnAppLimited();

    if (!exit_probe_rtt_at_) {
      // If the window has reached the appropriate size, schedule exiting
      // PROBE_RTT.  The CWND during PROBE_RTT is kMinimumCongestionWindow, but
      // we allow an extra packet since QUIC checks CWND before sending a
      // packet.
      if (msg.data_in_flight < ProbeRttCongestionWindow() + kMaxPacketSize) {
        exit_probe_rtt_at_ = msg.feedback_time + TimeDelta::ms(kProbeRttTimeMs);
        probe_rtt_round_passed_ = false;
      }
    } else {
      if (is_round_start) {
        probe_rtt_round_passed_ = true;
      }
      if (msg.feedback_time >= *exit_probe_rtt_at_ && probe_rtt_round_passed_) {
        min_rtt_timestamp_ = msg.feedback_time;
        if (!is_at_full_bandwidth_) {
          EnterStartupMode();
        } else {
          EnterProbeBandwidthMode(msg.feedback_time);
        }
      }
    }
  }
}

void BbrNetworkController::UpdateRecoveryState(int64_t last_acked_packet,
                                               bool has_losses,
                                               bool is_round_start) {
  // Exit recovery when there are no losses for a round.
  if (has_losses) {
    end_recovery_at_ = last_sent_packet_;
  }

  switch (recovery_state_) {
    case NOT_IN_RECOVERY:
      // Enter conservation on the first loss.
      if (has_losses) {
        recovery_state_ = CONSERVATION;
        if (mode_ == STARTUP) {
          recovery_state_ = config_.initial_conservation_in_startup;
        }
        // This will cause the |recovery_window_| to be set to the correct
        // value in CalculateRecoveryWindow().
        recovery_window_ = DataSize::Zero();
        // Since the conservation phase is meant to be lasting for a whole
        // round, extend the current round as if it were started right now.
        current_round_trip_end_ = last_sent_packet_;
      }
      break;

    case CONSERVATION:
    case MEDIUM_GROWTH:
      if (is_round_start) {
        recovery_state_ = GROWTH;
      }
      RTC_FALLTHROUGH();
    case GROWTH:
      // Exit recovery if appropriate.
      if (!has_losses && end_recovery_at_ &&
          last_acked_packet > *end_recovery_at_) {
        recovery_state_ = NOT_IN_RECOVERY;
      }

      break;
  }
}

void BbrNetworkController::UpdateAckAggregationBytes(
    Timestamp ack_time,
    DataSize newly_acked_bytes) {
  if (!aggregation_epoch_start_time_) {
    RTC_LOG(LS_ERROR)
        << "Received feedback before information about sent packets.";
    RTC_DCHECK(aggregation_epoch_start_time_.has_value());
    return;
  }
  // Compute how many bytes are expected to be delivered, assuming max bandwidth
  // is correct.
  DataSize expected_bytes_acked =
      max_bandwidth_.GetBest() * (ack_time - *aggregation_epoch_start_time_);
  // Reset the current aggregation epoch as soon as the ack arrival rate is less
  // than or equal to the max bandwidth.
  if (aggregation_epoch_bytes_ <= expected_bytes_acked) {
    // Reset to start measuring a new aggregation epoch.
    aggregation_epoch_bytes_ = newly_acked_bytes;
    aggregation_epoch_start_time_ = ack_time;
    return;
  }

  // Compute how many extra bytes were delivered vs max bandwidth.
  // Include the bytes most recently acknowledged to account for stretch acks.
  aggregation_epoch_bytes_ += newly_acked_bytes;
  max_ack_height_.Update(aggregation_epoch_bytes_ - expected_bytes_acked,
                         round_trip_count_);
}

void BbrNetworkController::CalculatePacingRate() {
  if (BandwidthEstimate().IsZero()) {
    return;
  }

  DataRate target_rate = pacing_gain_ * BandwidthEstimate();
  if (config_.rate_based_recovery && InRecovery()) {
    pacing_rate_ = pacing_gain_ * max_bandwidth_.GetThirdBest();
  }
  if (is_at_full_bandwidth_) {
    pacing_rate_ = target_rate;
    return;
  }

  // Pace at the rate of initial_window / RTT as soon as RTT measurements are
  // available.
  if (pacing_rate_.IsZero() && !rtt_stats_.min_rtt().IsZero()) {
    pacing_rate_ = initial_congestion_window_ / rtt_stats_.min_rtt();
    return;
  }
  // Slow the pacing rate in STARTUP once loss has ever been detected.
  const bool has_ever_detected_loss = end_recovery_at_.has_value();
  if (config_.slower_startup && has_ever_detected_loss) {
    pacing_rate_ = kStartupAfterLossGain * BandwidthEstimate();
    return;
  }

  // Do not decrease the pacing rate during the startup.
  pacing_rate_ = std::max(pacing_rate_, target_rate);
}

void BbrNetworkController::CalculateCongestionWindow(DataSize bytes_acked) {
  if (mode_ == PROBE_RTT) {
    return;
  }

  DataSize target_window = GetTargetCongestionWindow(congestion_window_gain_);

  if (rtt_variance_weight_ > 0.f && !BandwidthEstimate().IsZero()) {
    target_window += rtt_variance_weight_ * rtt_stats_.mean_deviation() *
                     BandwidthEstimate();
  } else if (max_aggregation_bytes_multiplier_ > 0 && is_at_full_bandwidth_) {
    // Subtracting only half the bytes_acked_since_queue_drained ensures sending
    // doesn't completely stop for a long period of time if the queue hasn't
    // been drained recently.
    if (max_aggregation_bytes_multiplier_ * max_ack_height_.GetBest() >
        bytes_acked_since_queue_drained_ / 2) {
      target_window +=
          max_aggregation_bytes_multiplier_ * max_ack_height_.GetBest() -
          bytes_acked_since_queue_drained_ / 2;
    }
  } else if (is_at_full_bandwidth_) {
    target_window += max_ack_height_.GetBest();
  }

  // Instead of immediately setting the target CWND as the new one, BBR grows
  // the CWND towards |target_window| by only increasing it |bytes_acked| at a
  // time.
  if (is_at_full_bandwidth_) {
    congestion_window_ =
        std::min(target_window, congestion_window_ + bytes_acked);
  } else if (congestion_window_ < target_window ||
             sampler_->total_data_acked() < initial_congestion_window_) {
    // If the connection is not yet out of startup phase, do not decrease the
    // window.
    congestion_window_ = congestion_window_ + bytes_acked;
  }

  // Enforce the limits on the congestion window.
  congestion_window_ = std::max(congestion_window_, kMinimumCongestionWindow);
  congestion_window_ = std::min(congestion_window_, max_congestion_window_);
}

void BbrNetworkController::CalculateRecoveryWindow(DataSize bytes_acked,
                                                   DataSize bytes_lost,
                                                   DataSize bytes_in_flight) {
  if (config_.rate_based_recovery ||
      (config_.rate_based_startup && mode_ == STARTUP)) {
    return;
  }

  if (recovery_state_ == NOT_IN_RECOVERY) {
    return;
  }

  // Set up the initial recovery window.
  if (recovery_window_.IsZero()) {
    recovery_window_ = bytes_in_flight + bytes_acked;
    recovery_window_ = std::max(kMinimumCongestionWindow, recovery_window_);
    return;
  }

  // Remove losses from the recovery window, while accounting for a potential
  // integer underflow.
  recovery_window_ = recovery_window_ >= bytes_lost
                         ? recovery_window_ - bytes_lost
                         : kMaxSegmentSize;

  // In CONSERVATION mode, just subtracting losses is sufficient.  In GROWTH,
  // release additional |bytes_acked| to achieve a slow-start-like behavior.
  // In MEDIUM_GROWTH, release |bytes_acked| / 2 to split the difference.
  if (recovery_state_ == GROWTH) {
    recovery_window_ += bytes_acked;
  } else if (recovery_state_ == MEDIUM_GROWTH) {
    recovery_window_ += bytes_acked / 2;
  }

  // Sanity checks.  Ensure that we always allow to send at least
  // |bytes_acked| in response.
  recovery_window_ = std::max(recovery_window_, bytes_in_flight + bytes_acked);
  recovery_window_ = std::max(kMinimumCongestionWindow, recovery_window_);
}

void BbrNetworkController::OnApplicationLimited(DataSize bytes_in_flight) {
  if (bytes_in_flight >= GetCongestionWindow()) {
    return;
  }

  app_limited_since_last_probe_rtt_ = true;
  sampler_->OnAppLimited();

  RTC_LOG(LS_INFO) << "Becoming application limited. Last sent packet: "
                   << last_sent_packet_
                   << ", CWND: " << ToString(GetCongestionWindow());
}
}  // namespace bbr
}  // namespace webrtc