Merge OveruseDetector into the TrendlineEstimator (send side BWE only)
Merge OveruseDetector into the TrendlineEstimator (send side BWE only) and remove the OveruseDetector from DelayBasedBwe. The behavior should be the same as before. One expection is that if no packets were received for kStreamTimeOutMs (2 seconds), it would previously reset the trendline estimator but not the detector. Since they have been merged, it now resets both.
Create an interface that the estimators will implement to facilitate experimentation with different estimators/detectors.
Bug: webrtc:8729
Change-Id: I5c3d2161a0d0dcb2e8a140c0fd887f0286d70fd4
Reviewed-on: https://webrtc-review.googlesource.com/38781
Reviewed-by: Sebastian Jansson <srte@webrtc.org>
Commit-Queue: Björn Terelius <terelius@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#21852}diff --git a/modules/congestion_controller/BUILD.gn b/modules/congestion_controller/BUILD.gn
index 0d314c2..e6fd393 100644
--- a/modules/congestion_controller/BUILD.gn
+++ b/modules/congestion_controller/BUILD.gn
@@ -84,6 +84,7 @@
"acknowledged_bitrate_estimator.h",
"bitrate_estimator.cc",
"bitrate_estimator.h",
+ "delay_increase_detector_interface.h",
"median_slope_estimator.cc",
"median_slope_estimator.h",
"probe_bitrate_estimator.cc",
diff --git a/modules/congestion_controller/delay_based_bwe.cc b/modules/congestion_controller/delay_based_bwe.cc
index 78423e2..9f0e01d 100644
--- a/modules/congestion_controller/delay_based_bwe.cc
+++ b/modules/congestion_controller/delay_based_bwe.cc
@@ -17,6 +17,7 @@
#include "logging/rtc_event_log/events/rtc_event_bwe_update_delay_based.h"
#include "logging/rtc_event_log/rtc_event_log.h"
+#include "modules/congestion_controller/trendline_estimator.h"
#include "modules/pacing/paced_sender.h"
#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
@@ -88,8 +89,7 @@
: event_log_(event_log),
clock_(clock),
inter_arrival_(),
- trendline_estimator_(),
- detector_(),
+ delay_detector_(),
last_seen_packet_ms_(-1),
uma_recorded_(false),
probe_bitrate_estimator_(event_log),
@@ -105,6 +105,9 @@
RTC_LOG(LS_INFO)
<< "Using Trendline filter for delay change estimation with window size "
<< trendline_window_size_;
+ delay_detector_.reset(new TrendlineEstimator(trendline_window_size_,
+ trendline_smoothing_coeff_,
+ trendline_threshold_gain_));
}
DelayBasedBwe::~DelayBasedBwe() {}
@@ -133,17 +136,17 @@
}
bool delayed_feedback = true;
bool recovered_from_overuse = false;
- BandwidthUsage prev_detector_state = detector_.State();
+ BandwidthUsage prev_detector_state = delay_detector_->State();
for (const auto& packet_feedback : packet_feedback_vector) {
if (packet_feedback.send_time_ms < 0)
continue;
delayed_feedback = false;
IncomingPacketFeedback(packet_feedback);
if (prev_detector_state == BandwidthUsage::kBwUnderusing &&
- detector_.State() == BandwidthUsage::kBwNormal) {
+ delay_detector_->State() == BandwidthUsage::kBwNormal) {
recovered_from_overuse = true;
}
- prev_detector_state = detector_.State();
+ prev_detector_state = delay_detector_->State();
}
if (delayed_feedback) {
@@ -185,9 +188,9 @@
inter_arrival_.reset(
new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
kTimestampToMs, true));
- trendline_estimator_.reset(new TrendlineEstimator(
- trendline_window_size_, trendline_smoothing_coeff_,
- trendline_threshold_gain_));
+ delay_detector_.reset(new TrendlineEstimator(trendline_window_size_,
+ trendline_smoothing_coeff_,
+ trendline_threshold_gain_));
}
last_seen_packet_ms_ = now_ms;
@@ -209,11 +212,8 @@
now_ms, packet_feedback.payload_size,
&ts_delta, &t_delta, &size_delta)) {
double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
- trendline_estimator_->Update(t_delta, ts_delta_ms,
- packet_feedback.arrival_time_ms);
- detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms,
- trendline_estimator_->num_of_deltas(),
- packet_feedback.arrival_time_ms);
+ delay_detector_->Update(t_delta, ts_delta_ms,
+ packet_feedback.arrival_time_ms);
}
if (packet_feedback.pacing_info.probe_cluster_id !=
PacedPacketInfo::kNotAProbe) {
@@ -230,7 +230,7 @@
rtc::Optional<int> probe_bitrate_bps =
probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps();
// Currently overusing the bandwidth.
- if (detector_.State() == BandwidthUsage::kBwOverusing) {
+ if (delay_detector_->State() == BandwidthUsage::kBwOverusing) {
if (acked_bitrate_bps &&
rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) {
result.updated =
@@ -260,8 +260,9 @@
result.recovered_from_overuse = recovered_from_overuse;
}
}
+ BandwidthUsage detector_state = delay_detector_->State();
if ((result.updated && prev_bitrate_ != result.target_bitrate_bps) ||
- detector_.State() != prev_state_) {
+ detector_state != prev_state_) {
uint32_t bitrate_bps =
result.updated ? result.target_bitrate_bps : prev_bitrate_;
@@ -269,11 +270,11 @@
if (event_log_) {
event_log_->Log(rtc::MakeUnique<RtcEventBweUpdateDelayBased>(
- bitrate_bps, detector_.State()));
+ bitrate_bps, detector_state));
}
prev_bitrate_ = bitrate_bps;
- prev_state_ = detector_.State();
+ prev_state_ = detector_state;
}
return result;
}
@@ -283,7 +284,7 @@
uint32_t* target_bitrate_bps) {
// TODO(terelius): RateControlInput::noise_var is deprecated and will be
// removed. In the meantime, we set it to zero.
- const RateControlInput input(detector_.State(), acked_bitrate_bps, 0);
+ const RateControlInput input(delay_detector_->State(), acked_bitrate_bps, 0);
*target_bitrate_bps = rate_control_.Update(&input, now_ms);
return rate_control_.ValidEstimate();
}
diff --git a/modules/congestion_controller/delay_based_bwe.h b/modules/congestion_controller/delay_based_bwe.h
index 79af11b..dbe759e 100644
--- a/modules/congestion_controller/delay_based_bwe.h
+++ b/modules/congestion_controller/delay_based_bwe.h
@@ -15,14 +15,11 @@
#include <utility>
#include <vector>
-#include "modules/congestion_controller/median_slope_estimator.h"
+#include "modules/congestion_controller/delay_increase_detector_interface.h"
#include "modules/congestion_controller/probe_bitrate_estimator.h"
-#include "modules/congestion_controller/trendline_estimator.h"
#include "modules/remote_bitrate_estimator/aimd_rate_control.h"
#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
#include "modules/remote_bitrate_estimator/inter_arrival.h"
-#include "modules/remote_bitrate_estimator/overuse_detector.h"
-#include "modules/remote_bitrate_estimator/overuse_estimator.h"
#include "rtc_base/checks.h"
#include "rtc_base/constructormagic.h"
#include "rtc_base/race_checker.h"
@@ -73,8 +70,7 @@
RtcEventLog* const event_log_;
const Clock* const clock_;
std::unique_ptr<InterArrival> inter_arrival_;
- std::unique_ptr<TrendlineEstimator> trendline_estimator_;
- OveruseDetector detector_;
+ std::unique_ptr<DelayIncreaseDetectorInterface> delay_detector_;
int64_t last_seen_packet_ms_;
bool uma_recorded_;
AimdRateControl rate_control_;
diff --git a/modules/congestion_controller/delay_increase_detector_interface.h b/modules/congestion_controller/delay_increase_detector_interface.h
new file mode 100644
index 0000000..b04c857
--- /dev/null
+++ b/modules/congestion_controller/delay_increase_detector_interface.h
@@ -0,0 +1,37 @@
+/*
+ * 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.
+ */
+#ifndef MODULES_CONGESTION_CONTROLLER_DELAY_INCREASE_DETECTOR_INTERFACE_H_
+#define MODULES_CONGESTION_CONTROLLER_DELAY_INCREASE_DETECTOR_INTERFACE_H_
+
+#include <stdint.h>
+
+#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
+#include "rtc_base/constructormagic.h"
+
+namespace webrtc {
+
+class DelayIncreaseDetectorInterface {
+ public:
+ DelayIncreaseDetectorInterface() {}
+ virtual ~DelayIncreaseDetectorInterface() {}
+
+ // Update the detector with a new sample. The deltas should represent deltas
+ // between timestamp groups as defined by the InterArrival class.
+ virtual void Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms) = 0;
+
+ virtual BandwidthUsage State() const = 0;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(DelayIncreaseDetectorInterface);
+};
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_DELAY_INCREASE_DETECTOR_INTERFACE_H_
diff --git a/modules/congestion_controller/trendline_estimator.cc b/modules/congestion_controller/trendline_estimator.cc
index eeb5edf..9ebe177 100644
--- a/modules/congestion_controller/trendline_estimator.cc
+++ b/modules/congestion_controller/trendline_estimator.cc
@@ -10,11 +10,14 @@
#include "modules/congestion_controller/trendline_estimator.h"
+#include <math.h>
+
#include <algorithm>
#include "api/optional.h"
#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
#include "rtc_base/checks.h"
+#include "rtc_base/numerics/safe_minmax.h"
namespace webrtc {
@@ -42,6 +45,11 @@
return rtc::nullopt;
return numerator / denominator;
}
+
+constexpr double kMaxAdaptOffsetMs = 15.0;
+constexpr double kOverUsingTimeThreshold = 10;
+constexpr int kMinNumDeltas = 60;
+
} // namespace
enum { kDeltaCounterMax = 1000 };
@@ -53,11 +61,20 @@
smoothing_coef_(smoothing_coef),
threshold_gain_(threshold_gain),
num_of_deltas_(0),
- first_arrival_time_ms(-1),
+ first_arrival_time_ms_(-1),
accumulated_delay_(0),
smoothed_delay_(0),
delay_hist_(),
- trendline_(0) {}
+ trendline_(0),
+ k_up_(0.0087),
+ k_down_(0.039),
+ overusing_time_threshold_(kOverUsingTimeThreshold),
+ threshold_(12.5),
+ last_update_ms_(-1),
+ prev_offset_(0.0),
+ time_over_using_(-1),
+ overuse_counter_(0),
+ hypothesis_(BandwidthUsage::kBwNormal) {}
TrendlineEstimator::~TrendlineEstimator() {}
@@ -68,8 +85,8 @@
++num_of_deltas_;
if (num_of_deltas_ > kDeltaCounterMax)
num_of_deltas_ = kDeltaCounterMax;
- if (first_arrival_time_ms == -1)
- first_arrival_time_ms = arrival_time_ms;
+ if (first_arrival_time_ms_ == -1)
+ first_arrival_time_ms_ = arrival_time_ms;
// Exponential backoff filter.
accumulated_delay_ += delta_ms;
@@ -82,7 +99,7 @@
// Simple linear regression.
delay_hist_.push_back(std::make_pair(
- static_cast<double>(arrival_time_ms - first_arrival_time_ms),
+ static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
smoothed_delay_));
if (delay_hist_.size() > window_size_)
delay_hist_.pop_front();
@@ -92,6 +109,75 @@
}
BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trendline_);
+
+ Detect(trendline_slope(), send_delta_ms, num_of_deltas(), arrival_time_ms);
+}
+
+BandwidthUsage TrendlineEstimator::State() const {
+ return hypothesis_;
+}
+
+void TrendlineEstimator::Detect(double offset,
+ double ts_delta,
+ int num_of_deltas,
+ int64_t now_ms) {
+ if (num_of_deltas < 2) {
+ hypothesis_ = BandwidthUsage::kBwNormal;
+ return;
+ }
+ const double T = std::min(num_of_deltas, kMinNumDeltas) * offset;
+ BWE_TEST_LOGGING_PLOT(1, "T", now_ms, T);
+ BWE_TEST_LOGGING_PLOT(1, "threshold", now_ms, threshold_);
+ if (T > threshold_) {
+ if (time_over_using_ == -1) {
+ // Initialize the timer. Assume that we've been
+ // over-using half of the time since the previous
+ // sample.
+ time_over_using_ = ts_delta / 2;
+ } else {
+ // Increment timer
+ time_over_using_ += ts_delta;
+ }
+ overuse_counter_++;
+ if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
+ if (offset >= prev_offset_) {
+ time_over_using_ = 0;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwOverusing;
+ }
+ }
+ } else if (T < -threshold_) {
+ time_over_using_ = -1;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwUnderusing;
+ } else {
+ time_over_using_ = -1;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwNormal;
+ }
+ prev_offset_ = offset;
+
+ UpdateThreshold(T, now_ms);
+}
+
+void TrendlineEstimator::UpdateThreshold(double modified_offset,
+ int64_t now_ms) {
+ if (last_update_ms_ == -1)
+ last_update_ms_ = now_ms;
+
+ if (fabs(modified_offset) > threshold_ + kMaxAdaptOffsetMs) {
+ // Avoid adapting the threshold to big latency spikes, caused e.g.,
+ // by a sudden capacity drop.
+ last_update_ms_ = now_ms;
+ return;
+ }
+
+ const double k = fabs(modified_offset) < threshold_ ? k_down_ : k_up_;
+ const int64_t kMaxTimeDeltaMs = 100;
+ int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
+ threshold_ += k * (fabs(modified_offset) - threshold_) * time_delta_ms;
+ threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
+ last_update_ms_ = now_ms;
}
} // namespace webrtc
diff --git a/modules/congestion_controller/trendline_estimator.h b/modules/congestion_controller/trendline_estimator.h
index 7ee27cd..9182647 100644
--- a/modules/congestion_controller/trendline_estimator.h
+++ b/modules/congestion_controller/trendline_estimator.h
@@ -16,11 +16,12 @@
#include <deque>
#include <utility>
+#include "modules/congestion_controller/delay_increase_detector_interface.h"
#include "rtc_base/constructormagic.h"
namespace webrtc {
-class TrendlineEstimator {
+class TrendlineEstimator : public DelayIncreaseDetectorInterface {
public:
// |window_size| is the number of points required to compute a trend line.
// |smoothing_coef| controls how much we smooth out the delay before fitting
@@ -31,13 +32,16 @@
TrendlineEstimator(size_t window_size,
double smoothing_coef,
double threshold_gain);
- ~TrendlineEstimator();
+
+ ~TrendlineEstimator() override;
// Update the estimator with a new sample. The deltas should represent deltas
// between timestamp groups as defined by the InterArrival class.
void Update(double recv_delta_ms,
double send_delta_ms,
- int64_t arrival_time_ms);
+ int64_t arrival_time_ms) override;
+
+ BandwidthUsage State() const override;
// Returns the estimated trend k multiplied by some gain.
// 0 < k < 1 -> the delay increases, queues are filling up
@@ -49,6 +53,13 @@
unsigned int num_of_deltas() const { return num_of_deltas_; }
private:
+ void Detect(double offset,
+ double ts_delta,
+ int num_of_deltas,
+ int64_t now_ms);
+
+ void UpdateThreshold(double modified_offset, int64_t now_ms);
+
// Parameters.
const size_t window_size_;
const double smoothing_coef_;
@@ -56,7 +67,7 @@
// Used by the existing threshold.
unsigned int num_of_deltas_;
// Keep the arrival times small by using the change from the first packet.
- int64_t first_arrival_time_ms;
+ int64_t first_arrival_time_ms_;
// Exponential backoff filtering.
double accumulated_delay_;
double smoothed_delay_;
@@ -64,6 +75,16 @@
std::deque<std::pair<double, double>> delay_hist_;
double trendline_;
+ const double k_up_;
+ const double k_down_;
+ double overusing_time_threshold_;
+ double threshold_;
+ int64_t last_update_ms_;
+ double prev_offset_;
+ double time_over_using_;
+ int overuse_counter_;
+ BandwidthUsage hypothesis_;
+
RTC_DISALLOW_COPY_AND_ASSIGN(TrendlineEstimator);
};
} // namespace webrtc