blob: 9bac153ac82f5273b255bfe53d53d46a99f32beb [file] [log] [blame]
/*
* Copyright (c) 2014 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 "webrtc/modules/remote_bitrate_estimator/aimd_rate_control.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include "webrtc/base/checks.h"
#include "webrtc/modules/remote_bitrate_estimator/overuse_detector.h"
#include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
namespace webrtc {
static const int64_t kDefaultRttMs = 200;
static const int64_t kLogIntervalMs = 1000;
static const double kWithinIncomingBitrateHysteresis = 1.05;
static const int64_t kMaxFeedbackIntervalMs = 1000;
AimdRateControl::AimdRateControl(uint32_t min_bitrate_bps)
: min_configured_bitrate_bps_(min_bitrate_bps),
max_configured_bitrate_bps_(30000000),
current_bitrate_bps_(max_configured_bitrate_bps_),
avg_max_bitrate_kbps_(-1.0f),
var_max_bitrate_kbps_(0.4f),
rate_control_state_(kRcHold),
rate_control_region_(kRcMaxUnknown),
time_last_bitrate_change_(-1),
current_input_(kBwNormal, 0, 1.0),
updated_(false),
time_first_incoming_estimate_(-1),
bitrate_is_initialized_(false),
beta_(0.85f),
rtt_(kDefaultRttMs),
time_of_last_log_(-1),
in_experiment_(AdaptiveThresholdExperimentIsEnabled()) {
}
uint32_t AimdRateControl::GetMinBitrate() const {
return min_configured_bitrate_bps_;
}
bool AimdRateControl::ValidEstimate() const {
return bitrate_is_initialized_;
}
int64_t AimdRateControl::GetFeedbackInterval() const {
// Estimate how often we can send RTCP if we allocate up to 5% of bandwidth
// to feedback.
static const int kRtcpSize = 80;
int64_t interval = static_cast<int64_t>(
kRtcpSize * 8.0 * 1000.0 / (0.05 * current_bitrate_bps_) + 0.5);
const int64_t kMinFeedbackIntervalMs = 200;
return std::min(std::max(interval, kMinFeedbackIntervalMs),
kMaxFeedbackIntervalMs);
}
bool AimdRateControl::TimeToReduceFurther(int64_t time_now,
uint32_t incoming_bitrate_bps) const {
const int64_t bitrate_reduction_interval =
std::max<int64_t>(std::min<int64_t>(rtt_, 200), 10);
if (time_now - time_last_bitrate_change_ >= bitrate_reduction_interval) {
return true;
}
if (ValidEstimate()) {
const int threshold = static_cast<int>(kWithinIncomingBitrateHysteresis *
incoming_bitrate_bps);
const int bitrate_difference = LatestEstimate() - incoming_bitrate_bps;
return bitrate_difference > threshold;
}
return false;
}
uint32_t AimdRateControl::LatestEstimate() const {
return current_bitrate_bps_;
}
uint32_t AimdRateControl::UpdateBandwidthEstimate(int64_t now_ms) {
current_bitrate_bps_ = ChangeBitrate(current_bitrate_bps_,
current_input_._incomingBitRate,
now_ms);
if (now_ms - time_of_last_log_ > kLogIntervalMs) {
time_of_last_log_ = now_ms;
}
return current_bitrate_bps_;
}
void AimdRateControl::SetRtt(int64_t rtt) {
rtt_ = rtt;
}
void AimdRateControl::Update(const RateControlInput* input, int64_t now_ms) {
assert(input);
// Set the initial bit rate value to what we're receiving the first half
// second.
if (!bitrate_is_initialized_) {
const int64_t kInitializationTimeMs = 5000;
DCHECK_LE(kBitrateWindowMs, kInitializationTimeMs);
if (time_first_incoming_estimate_ < 0) {
if (input->_incomingBitRate > 0) {
time_first_incoming_estimate_ = now_ms;
}
} else if (now_ms - time_first_incoming_estimate_ > kInitializationTimeMs &&
input->_incomingBitRate > 0) {
current_bitrate_bps_ = input->_incomingBitRate;
bitrate_is_initialized_ = true;
}
}
if (updated_ && current_input_._bwState == kBwOverusing) {
// Only update delay factor and incoming bit rate. We always want to react
// on an over-use.
current_input_._noiseVar = input->_noiseVar;
current_input_._incomingBitRate = input->_incomingBitRate;
} else {
updated_ = true;
current_input_ = *input;
}
}
void AimdRateControl::SetEstimate(int bitrate_bps, int64_t now_ms) {
updated_ = true;
bitrate_is_initialized_ = true;
current_bitrate_bps_ = ChangeBitrate(bitrate_bps, bitrate_bps, now_ms);
}
uint32_t AimdRateControl::ChangeBitrate(uint32_t current_bitrate_bps,
uint32_t incoming_bitrate_bps,
int64_t now_ms) {
if (!updated_) {
return current_bitrate_bps_;
}
// An over-use should always trigger us to reduce the bitrate, even though
// we have not yet established our first estimate. By acting on the over-use,
// we will end up with a valid estimate.
if (!bitrate_is_initialized_ && current_input_._bwState != kBwOverusing)
return current_bitrate_bps_;
updated_ = false;
ChangeState(current_input_, now_ms);
// Calculated here because it's used in multiple places.
const float incoming_bitrate_kbps = incoming_bitrate_bps / 1000.0f;
// Calculate the max bit rate std dev given the normalized
// variance and the current incoming bit rate.
const float std_max_bit_rate = sqrt(var_max_bitrate_kbps_ *
avg_max_bitrate_kbps_);
switch (rate_control_state_) {
case kRcHold:
break;
case kRcIncrease:
if (avg_max_bitrate_kbps_ >= 0 &&
incoming_bitrate_kbps >
avg_max_bitrate_kbps_ + 3 * std_max_bit_rate) {
ChangeRegion(kRcMaxUnknown);
avg_max_bitrate_kbps_ = -1.0;
}
if (rate_control_region_ == kRcNearMax) {
// Approximate the over-use estimator delay to 100 ms.
const int64_t response_time = rtt_ + 100;
uint32_t additive_increase_bps = AdditiveRateIncrease(
now_ms, time_last_bitrate_change_, response_time);
current_bitrate_bps += additive_increase_bps;
} else {
uint32_t multiplicative_increase_bps = MultiplicativeRateIncrease(
now_ms, time_last_bitrate_change_, current_bitrate_bps);
current_bitrate_bps += multiplicative_increase_bps;
}
time_last_bitrate_change_ = now_ms;
break;
case kRcDecrease:
bitrate_is_initialized_ = true;
if (incoming_bitrate_bps < min_configured_bitrate_bps_) {
current_bitrate_bps = min_configured_bitrate_bps_;
} else {
// Set bit rate to something slightly lower than max
// to get rid of any self-induced delay.
current_bitrate_bps = static_cast<uint32_t>(beta_ *
incoming_bitrate_bps + 0.5);
if (current_bitrate_bps > current_bitrate_bps_) {
// Avoid increasing the rate when over-using.
if (rate_control_region_ != kRcMaxUnknown) {
current_bitrate_bps = static_cast<uint32_t>(
beta_ * avg_max_bitrate_kbps_ * 1000 + 0.5f);
}
current_bitrate_bps = std::min(current_bitrate_bps,
current_bitrate_bps_);
}
ChangeRegion(kRcNearMax);
if (incoming_bitrate_kbps < avg_max_bitrate_kbps_ -
3 * std_max_bit_rate) {
avg_max_bitrate_kbps_ = -1.0f;
}
UpdateMaxBitRateEstimate(incoming_bitrate_kbps);
}
// Stay on hold until the pipes are cleared.
ChangeState(kRcHold);
time_last_bitrate_change_ = now_ms;
break;
default:
assert(false);
}
if ((incoming_bitrate_bps > 100000 || current_bitrate_bps > 150000) &&
current_bitrate_bps > 1.5 * incoming_bitrate_bps) {
// Allow changing the bit rate if we are operating at very low rates
// Don't change the bit rate if the send side is too far off
current_bitrate_bps = current_bitrate_bps_;
time_last_bitrate_change_ = now_ms;
}
return current_bitrate_bps;
}
uint32_t AimdRateControl::MultiplicativeRateIncrease(
int64_t now_ms, int64_t last_ms, uint32_t current_bitrate_bps) const {
double alpha = 1.08;
if (last_ms > -1) {
int time_since_last_update_ms = std::min(static_cast<int>(now_ms - last_ms),
1000);
alpha = pow(alpha, time_since_last_update_ms / 1000.0);
}
uint32_t multiplicative_increase_bps = std::max(
current_bitrate_bps * (alpha - 1.0), 1000.0);
return multiplicative_increase_bps;
}
uint32_t AimdRateControl::AdditiveRateIncrease(
int64_t now_ms, int64_t last_ms, int64_t response_time_ms) const {
assert(response_time_ms > 0);
double beta = 0.0;
if (last_ms > 0) {
beta = std::min((now_ms - last_ms) / static_cast<double>(response_time_ms),
1.0);
if (in_experiment_)
beta /= 2.0;
}
double bits_per_frame = static_cast<double>(current_bitrate_bps_) / 30.0;
double packets_per_frame = std::ceil(bits_per_frame / (8.0 * 1200.0));
double avg_packet_size_bits = bits_per_frame / packets_per_frame;
uint32_t additive_increase_bps = std::max(
1000.0, beta * avg_packet_size_bits);
return additive_increase_bps;
}
void AimdRateControl::UpdateMaxBitRateEstimate(float incoming_bitrate_kbps) {
const float alpha = 0.05f;
if (avg_max_bitrate_kbps_ == -1.0f) {
avg_max_bitrate_kbps_ = incoming_bitrate_kbps;
} else {
avg_max_bitrate_kbps_ = (1 - alpha) * avg_max_bitrate_kbps_ +
alpha * incoming_bitrate_kbps;
}
// Estimate the max bit rate variance and normalize the variance
// with the average max bit rate.
const float norm = std::max(avg_max_bitrate_kbps_, 1.0f);
var_max_bitrate_kbps_ = (1 - alpha) * var_max_bitrate_kbps_ +
alpha * (avg_max_bitrate_kbps_ - incoming_bitrate_kbps) *
(avg_max_bitrate_kbps_ - incoming_bitrate_kbps) / norm;
// 0.4 ~= 14 kbit/s at 500 kbit/s
if (var_max_bitrate_kbps_ < 0.4f) {
var_max_bitrate_kbps_ = 0.4f;
}
// 2.5f ~= 35 kbit/s at 500 kbit/s
if (var_max_bitrate_kbps_ > 2.5f) {
var_max_bitrate_kbps_ = 2.5f;
}
}
void AimdRateControl::ChangeState(const RateControlInput& input,
int64_t now_ms) {
switch (current_input_._bwState) {
case kBwNormal:
if (rate_control_state_ == kRcHold) {
time_last_bitrate_change_ = now_ms;
ChangeState(kRcIncrease);
}
break;
case kBwOverusing:
if (rate_control_state_ != kRcDecrease) {
ChangeState(kRcDecrease);
}
break;
case kBwUnderusing:
ChangeState(kRcHold);
break;
default:
assert(false);
}
}
void AimdRateControl::ChangeRegion(RateControlRegion region) {
rate_control_region_ = region;
}
void AimdRateControl::ChangeState(RateControlState new_state) {
rate_control_state_ = new_state;
}
} // namespace webrtc