Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation).
Theil and Sen's estimator essentially looks at the line through every pair of points and selects the median slope. This is robust to corruption of up to 29% of the data points.
Wire up new estimator to field trial experiment. Add unit and integration tests. Results are promising.
BUG=webrtc:6728
Review-Url: https://codereview.webrtc.org/2512693002
Cr-Original-Commit-Position: refs/heads/master@{#15508}
Cr-Mirrored-From: https://chromium.googlesource.com/external/webrtc
Cr-Mirrored-Commit: 5a388368a220cb975cbada5129dd94a104a77497
diff --git a/base/analytics/percentile_filter.h b/base/analytics/percentile_filter.h
index b3c8f8d..7cfba5a 100644
--- a/base/analytics/percentile_filter.h
+++ b/base/analytics/percentile_filter.h
@@ -33,9 +33,10 @@
// the size of the container.
void Insert(const T& value);
- // Remove one observation. The complexity of this operation is logarithmic in
- // the size of the container.
- void Erase(const T& value);
+ // Remove one observation or return false if |value| doesn't exist in the
+ // container. The complexity of this operation is logarithmic in the size of
+ // the container.
+ bool Erase(const T& value);
// Get the percentile value. The complexity of this operation is constant.
T GetPercentileValue() const;
@@ -76,11 +77,11 @@
}
template <typename T>
-void PercentileFilter<T>::Erase(const T& value) {
+bool PercentileFilter<T>::Erase(const T& value) {
typename std::multiset<T>::const_iterator it = set_.lower_bound(value);
// Ignore erase operation if the element is not present in the current set.
if (it == set_.end() || *it != value)
- return;
+ return false;
if (it == percentile_it_) {
// If same iterator, update to the following element. Index is not
// affected.
@@ -92,6 +93,7 @@
--percentile_index_;
}
UpdatePercentileIterator();
+ return true;
}
template <typename T>
diff --git a/base/analytics/percentile_filter_unittest.cc b/base/analytics/percentile_filter_unittest.cc
index 98168fd..02b7d09 100644
--- a/base/analytics/percentile_filter_unittest.cc
+++ b/base/analytics/percentile_filter_unittest.cc
@@ -84,15 +84,18 @@
TEST_P(PercentileFilterTest, EmptyFilter) {
EXPECT_EQ(0, filter_.GetPercentileValue());
filter_.Insert(3);
- filter_.Erase(3);
+ bool success = filter_.Erase(3);
+ EXPECT_TRUE(success);
EXPECT_EQ(0, filter_.GetPercentileValue());
}
TEST_P(PercentileFilterTest, EraseNonExistingElement) {
- filter_.Erase(3);
+ bool success = filter_.Erase(3);
+ EXPECT_FALSE(success);
EXPECT_EQ(0, filter_.GetPercentileValue());
filter_.Insert(4);
- filter_.Erase(3);
+ success = filter_.Erase(3);
+ EXPECT_FALSE(success);
EXPECT_EQ(4, filter_.GetPercentileValue());
}
diff --git a/modules/BUILD.gn b/modules/BUILD.gn
index 4abd193..ca519e7 100644
--- a/modules/BUILD.gn
+++ b/modules/BUILD.gn
@@ -394,6 +394,7 @@
"congestion_controller/delay_based_bwe_unittest.cc",
"congestion_controller/delay_based_bwe_unittest_helper.cc",
"congestion_controller/delay_based_bwe_unittest_helper.h",
+ "congestion_controller/median_slope_estimator_unittest.cc",
"congestion_controller/probe_bitrate_estimator_unittest.cc",
"congestion_controller/probe_controller_unittest.cc",
"congestion_controller/probing_interval_estimator_unittest.cc",
diff --git a/modules/congestion_controller/BUILD.gn b/modules/congestion_controller/BUILD.gn
index 09b3388..d2dc680 100644
--- a/modules/congestion_controller/BUILD.gn
+++ b/modules/congestion_controller/BUILD.gn
@@ -14,6 +14,8 @@
"delay_based_bwe.cc",
"delay_based_bwe.h",
"include/congestion_controller.h",
+ "median_slope_estimator.cc",
+ "median_slope_estimator.h",
"probe_bitrate_estimator.cc",
"probe_bitrate_estimator.h",
"probe_controller.cc",
@@ -41,6 +43,7 @@
}
deps = [
+ "../../base:rtc_analytics",
"../bitrate_controller",
"../pacing",
]
diff --git a/modules/congestion_controller/delay_based_bwe.cc b/modules/congestion_controller/delay_based_bwe.cc
index 04dadc4..bb63f35 100644
--- a/modules/congestion_controller/delay_based_bwe.cc
+++ b/modules/congestion_controller/delay_based_bwe.cc
@@ -21,6 +21,7 @@
#include "webrtc/modules/congestion_controller/include/congestion_controller.h"
#include "webrtc/modules/pacing/paced_sender.h"
#include "webrtc/modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
#include "webrtc/system_wrappers/include/field_trial.h"
#include "webrtc/system_wrappers/include/metrics.h"
#include "webrtc/typedefs.h"
@@ -39,12 +40,18 @@
constexpr int kInitialRateWindowMs = 500;
constexpr int kRateWindowMs = 150;
+// Parameters for linear least squares fit of regression line to noisy data.
constexpr size_t kDefaultTrendlineWindowSize = 15;
constexpr double kDefaultTrendlineSmoothingCoeff = 0.9;
constexpr double kDefaultTrendlineThresholdGain = 4.0;
+// Parameters for Theil-Sen robust fitting of line to noisy data.
+constexpr size_t kDefaultMedianSlopeWindowSize = 20;
+constexpr double kDefaultMedianSlopeThresholdGain = 4.0;
+
const char kBitrateEstimateExperiment[] = "WebRTC-ImprovedBitrateEstimate";
const char kBweTrendlineFilterExperiment[] = "WebRTC-BweTrendlineFilter";
+const char kBweMedianSlopeFilterExperiment[] = "WebRTC-BweMedianSlopeFilter";
bool BitrateEstimateExperimentIsEnabled() {
return webrtc::field_trial::FindFullName(kBitrateEstimateExperiment) ==
@@ -58,16 +65,27 @@
return experiment_string.find("Enabled") == 0;
}
-bool ReadTrendlineFilterExperimentParameters(size_t* window_points,
+bool MedianSlopeFilterExperimentIsEnabled() {
+ std::string experiment_string =
+ webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
+ // The experiment is enabled iff the field trial string begins with "Enabled".
+ return experiment_string.find("Enabled") == 0;
+}
+
+bool ReadTrendlineFilterExperimentParameters(size_t* window_size,
double* smoothing_coef,
double* threshold_gain) {
RTC_DCHECK(TrendlineFilterExperimentIsEnabled());
+ RTC_DCHECK(!MedianSlopeFilterExperimentIsEnabled());
+ RTC_DCHECK(window_size != nullptr);
+ RTC_DCHECK(smoothing_coef != nullptr);
+ RTC_DCHECK(threshold_gain != nullptr);
std::string experiment_string =
webrtc::field_trial::FindFullName(kBweTrendlineFilterExperiment);
int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf,%lf",
- window_points, smoothing_coef, threshold_gain);
+ window_size, smoothing_coef, threshold_gain);
if (parsed_values == 3) {
- RTC_CHECK_GT(*window_points, 1) << "Need at least 2 points to fit a line.";
+ RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
RTC_CHECK(0 <= *smoothing_coef && *smoothing_coef <= 1)
<< "Coefficient needs to be between 0 and 1 for weighted average.";
RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
@@ -75,12 +93,33 @@
}
LOG(LS_WARNING) << "Failed to parse parameters for BweTrendlineFilter "
"experiment from field trial string. Using default.";
- *window_points = kDefaultTrendlineWindowSize;
+ *window_size = kDefaultTrendlineWindowSize;
*smoothing_coef = kDefaultTrendlineSmoothingCoeff;
*threshold_gain = kDefaultTrendlineThresholdGain;
return false;
}
+bool ReadMedianSlopeFilterExperimentParameters(size_t* window_size,
+ double* threshold_gain) {
+ RTC_DCHECK(!TrendlineFilterExperimentIsEnabled());
+ RTC_DCHECK(MedianSlopeFilterExperimentIsEnabled());
+ RTC_DCHECK(window_size != nullptr);
+ RTC_DCHECK(threshold_gain != nullptr);
+ std::string experiment_string =
+ webrtc::field_trial::FindFullName(kBweMedianSlopeFilterExperiment);
+ int parsed_values = sscanf(experiment_string.c_str(), "Enabled-%zu,%lf",
+ window_size, threshold_gain);
+ if (parsed_values == 2) {
+ RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
+ RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
+ return true;
+ }
+ LOG(LS_WARNING) << "Failed to parse parameters for BweMedianSlopeFilter "
+ "experiment from field trial string. Using default.";
+ *window_size = kDefaultMedianSlopeWindowSize;
+ *threshold_gain = kDefaultMedianSlopeThresholdGain;
+ return false;
+}
} // namespace
namespace webrtc {
@@ -168,7 +207,9 @@
}
DelayBasedBwe::DelayBasedBwe(Clock* clock)
- : clock_(clock),
+ : in_trendline_experiment_(TrendlineFilterExperimentIsEnabled()),
+ in_median_slope_experiment_(MedianSlopeFilterExperimentIsEnabled()),
+ clock_(clock),
inter_arrival_(),
kalman_estimator_(),
trendline_estimator_(),
@@ -180,13 +221,19 @@
trendline_window_size_(kDefaultTrendlineWindowSize),
trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff),
trendline_threshold_gain_(kDefaultTrendlineThresholdGain),
- in_trendline_experiment_(TrendlineFilterExperimentIsEnabled()),
- probing_interval_estimator_(&rate_control_) {
+ probing_interval_estimator_(&rate_control_),
+ median_slope_window_size_(kDefaultMedianSlopeWindowSize),
+ median_slope_threshold_gain_(kDefaultMedianSlopeThresholdGain) {
if (in_trendline_experiment_) {
ReadTrendlineFilterExperimentParameters(&trendline_window_size_,
&trendline_smoothing_coeff_,
&trendline_threshold_gain_);
}
+ if (in_median_slope_experiment_) {
+ ReadMedianSlopeFilterExperimentParameters(&trendline_window_size_,
+ &trendline_threshold_gain_);
+ }
+
network_thread_.DetachFromThread();
}
@@ -224,6 +271,8 @@
trendline_estimator_.reset(new TrendlineEstimator(
trendline_window_size_, trendline_smoothing_coeff_,
trendline_threshold_gain_));
+ median_slope_estimator_.reset(new MedianSlopeEstimator(
+ median_slope_window_size_, median_slope_threshold_gain_));
}
last_seen_packet_ms_ = now_ms;
@@ -249,7 +298,12 @@
detector_.Detect(trendline_estimator_->trendline_slope(), ts_delta_ms,
trendline_estimator_->num_of_deltas(),
info.arrival_time_ms);
-
+ } else if (in_median_slope_experiment_) {
+ median_slope_estimator_->Update(t_delta, ts_delta_ms,
+ info.arrival_time_ms);
+ detector_.Detect(median_slope_estimator_->trendline_slope(), ts_delta_ms,
+ median_slope_estimator_->num_of_deltas(),
+ info.arrival_time_ms);
} else {
kalman_estimator_->Update(t_delta, ts_delta_ms, size_delta,
detector_.State(), info.arrival_time_ms);
@@ -288,8 +342,11 @@
UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
&result.target_bitrate_bps);
}
- if (result.updated)
+ if (result.updated) {
last_update_ms_ = now_ms;
+ BWE_TEST_LOGGING_PLOT(1, "target_bitrate_bps", now_ms,
+ result.target_bitrate_bps);
+ }
return result;
}
diff --git a/modules/congestion_controller/delay_based_bwe.h b/modules/congestion_controller/delay_based_bwe.h
index c5a599f..6e7a6f8 100644
--- a/modules/congestion_controller/delay_based_bwe.h
+++ b/modules/congestion_controller/delay_based_bwe.h
@@ -19,6 +19,7 @@
#include "webrtc/base/constructormagic.h"
#include "webrtc/base/rate_statistics.h"
#include "webrtc/base/thread_checker.h"
+#include "webrtc/modules/congestion_controller/median_slope_estimator.h"
#include "webrtc/modules/congestion_controller/probe_bitrate_estimator.h"
#include "webrtc/modules/congestion_controller/probing_interval_estimator.h"
#include "webrtc/modules/congestion_controller/trendline_estimator.h"
@@ -84,12 +85,15 @@
int64_t now_ms,
rtc::Optional<uint32_t> acked_bitrate_bps,
uint32_t* target_bitrate_bps);
+ const bool in_trendline_experiment_;
+ const bool in_median_slope_experiment_;
rtc::ThreadChecker network_thread_;
Clock* const clock_;
std::unique_ptr<InterArrival> inter_arrival_;
std::unique_ptr<OveruseEstimator> kalman_estimator_;
std::unique_ptr<TrendlineEstimator> trendline_estimator_;
+ std::unique_ptr<MedianSlopeEstimator> median_slope_estimator_;
OveruseDetector detector_;
BitrateEstimator receiver_incoming_bitrate_;
int64_t last_update_ms_;
@@ -100,8 +104,9 @@
size_t trendline_window_size_;
double trendline_smoothing_coeff_;
double trendline_threshold_gain_;
- const bool in_trendline_experiment_;
ProbingIntervalEstimator probing_interval_estimator_;
+ size_t median_slope_window_size_;
+ double median_slope_threshold_gain_;
RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(DelayBasedBwe);
};
diff --git a/modules/congestion_controller/delay_based_bwe_unittest.cc b/modules/congestion_controller/delay_based_bwe_unittest.cc
index c242bf4..d4b3a72 100644
--- a/modules/congestion_controller/delay_based_bwe_unittest.cc
+++ b/modules/congestion_controller/delay_based_bwe_unittest.cc
@@ -175,13 +175,11 @@
class DelayBasedBweExperimentTest : public DelayBasedBweTest {
public:
DelayBasedBweExperimentTest()
- : override_field_trials_("WebRTC-ImprovedBitrateEstimate/Enabled/") {}
-
- protected:
- void SetUp() override {
+ : override_field_trials_("WebRTC-ImprovedBitrateEstimate/Enabled/") {
bitrate_estimator_.reset(new DelayBasedBwe(&clock_));
}
+ private:
test::ScopedFieldTrials override_field_trials_;
};
@@ -208,13 +206,11 @@
class DelayBasedBweTrendlineExperimentTest : public DelayBasedBweTest {
public:
DelayBasedBweTrendlineExperimentTest()
- : override_field_trials_("WebRTC-BweTrendlineFilter/Enabled-15,0.9,4/") {}
-
- protected:
- void SetUp() override {
+ : override_field_trials_("WebRTC-BweTrendlineFilter/Enabled-15,0.9,4/") {
bitrate_estimator_.reset(new DelayBasedBwe(&clock_));
}
+ private:
test::ScopedFieldTrials override_field_trials_;
};
@@ -238,4 +234,35 @@
CapacityDropTestHelper(1, true, 600, 0);
}
+class DelayBasedBweMedianSlopeExperimentTest : public DelayBasedBweTest {
+ public:
+ DelayBasedBweMedianSlopeExperimentTest()
+ : override_field_trials_("WebRTC-BweMedianSlopeFilter/Enabled-20,4/") {
+ bitrate_estimator_.reset(new DelayBasedBwe(&clock_));
+ }
+
+ private:
+ test::ScopedFieldTrials override_field_trials_;
+};
+
+TEST_F(DelayBasedBweMedianSlopeExperimentTest, RateIncreaseRtpTimestamps) {
+ RateIncreaseRtpTimestampsTestHelper(1240);
+}
+
+TEST_F(DelayBasedBweMedianSlopeExperimentTest, CapacityDropOneStream) {
+ CapacityDropTestHelper(1, false, 600, 0);
+}
+
+TEST_F(DelayBasedBweMedianSlopeExperimentTest, CapacityDropPosOffsetChange) {
+ CapacityDropTestHelper(1, false, 600, 30000);
+}
+
+TEST_F(DelayBasedBweMedianSlopeExperimentTest, CapacityDropNegOffsetChange) {
+ CapacityDropTestHelper(1, false, 1267, -30000);
+}
+
+TEST_F(DelayBasedBweMedianSlopeExperimentTest, CapacityDropOneStreamWrap) {
+ CapacityDropTestHelper(1, true, 600, 0);
+}
+
} // namespace webrtc
diff --git a/modules/congestion_controller/median_slope_estimator.cc b/modules/congestion_controller/median_slope_estimator.cc
new file mode 100644
index 0000000..488831e
--- /dev/null
+++ b/modules/congestion_controller/median_slope_estimator.cc
@@ -0,0 +1,83 @@
+/*
+ * Copyright (c) 2016 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/congestion_controller/median_slope_estimator.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "webrtc/base/logging.h"
+#include "webrtc/modules/remote_bitrate_estimator/include/bwe_defines.h"
+#include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+
+namespace webrtc {
+
+constexpr unsigned int kDeltaCounterMax = 1000;
+
+MedianSlopeEstimator::MedianSlopeEstimator(size_t window_size,
+ double threshold_gain)
+ : window_size_(window_size),
+ threshold_gain_(threshold_gain),
+ num_of_deltas_(0),
+ accumulated_delay_(0),
+ delay_hist_(),
+ median_filter_(0.5),
+ trendline_(0) {}
+
+MedianSlopeEstimator::~MedianSlopeEstimator() {}
+
+void MedianSlopeEstimator::Update(double recv_delta_ms,
+ double send_delta_ms,
+ double now_ms) {
+ const double delta_ms = recv_delta_ms - send_delta_ms;
+ ++num_of_deltas_;
+ if (num_of_deltas_ > kDeltaCounterMax) {
+ num_of_deltas_ = kDeltaCounterMax;
+ }
+
+ accumulated_delay_ += delta_ms;
+ BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", now_ms, accumulated_delay_);
+
+ // If the window is full, remove the |window_size_| - 1 slopes that belong to
+ // the oldest point.
+ if (delay_hist_.size() == window_size_) {
+ for (double slope : delay_hist_.front().slopes) {
+ const bool success = median_filter_.Erase(slope);
+ RTC_CHECK(success);
+ }
+ delay_hist_.pop_front();
+ }
+ // Add |window_size_| - 1 new slopes.
+ for (auto& old_delay : delay_hist_) {
+ if (now_ms - old_delay.time != 0) {
+ // The C99 standard explicitly states that casts and assignments must
+ // perform the associated conversions. This means that |slope| will be
+ // a 64-bit double even if the division is computed using, e.g., 80-bit
+ // extended precision. I believe this also holds in C++ even though the
+ // C++11 standard isn't as explicit. Furthermore, there are good reasons
+ // to believe that compilers couldn't perform optimizations that break
+ // this assumption even if they wanted to.
+ double slope =
+ (accumulated_delay_ - old_delay.delay) / (now_ms - old_delay.time);
+ median_filter_.Insert(slope);
+ // We want to avoid issues with different rounding mode / precision
+ // which we might get if we recomputed the slope when we remove it.
+ old_delay.slopes.push_back(slope);
+ }
+ }
+ delay_hist_.emplace_back(now_ms, accumulated_delay_, window_size_ - 1);
+ // Recompute the median slope.
+ if (delay_hist_.size() == window_size_)
+ trendline_ = median_filter_.GetPercentileValue();
+
+ BWE_TEST_LOGGING_PLOT(1, "trendline_slope", now_ms, trendline_);
+}
+
+} // namespace webrtc
diff --git a/modules/congestion_controller/median_slope_estimator.h b/modules/congestion_controller/median_slope_estimator.h
new file mode 100644
index 0000000..26d7f61
--- /dev/null
+++ b/modules/congestion_controller/median_slope_estimator.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (c) 2016 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 WEBRTC_MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
+#define WEBRTC_MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
+
+#include <list>
+#include <utility>
+#include <vector>
+
+#include "webrtc/base/analytics/percentile_filter.h"
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/common_types.h"
+
+namespace webrtc {
+
+class MedianSlopeEstimator {
+ public:
+ // |window_size| is the number of points required to compute a trend line.
+ // |threshold_gain| is used to scale the trendline slope for comparison to
+ // the old threshold. Once the old estimator has been removed (or the
+ // thresholds been merged into the estimators), we can just set the
+ // threshold instead of setting a gain.
+ MedianSlopeEstimator(size_t window_size, double threshold_gain);
+ ~MedianSlopeEstimator();
+
+ // 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, double now_ms);
+
+ // Returns the estimated trend k multiplied by some gain.
+ // 0 < k < 1 -> the delay increases, queues are filling up
+ // k == 0 -> the delay does not change
+ // k < 0 -> the delay decreases, queues are being emptied
+ double trendline_slope() const { return trendline_ * threshold_gain_; }
+
+ // Returns the number of deltas which the current estimator state is based on.
+ unsigned int num_of_deltas() const { return num_of_deltas_; }
+
+ private:
+ struct DelayInfo {
+ DelayInfo(double time, double delay, size_t slope_count)
+ : time(time), delay(delay) {
+ slopes.reserve(slope_count);
+ }
+ double time;
+ double delay;
+ std::vector<double> slopes;
+ };
+ // Parameters.
+ const size_t window_size_;
+ const double threshold_gain_;
+ // Used by the existing threshold.
+ unsigned int num_of_deltas_;
+ // Theil-Sen robust line fitting
+ double accumulated_delay_;
+ std::list<DelayInfo> delay_hist_;
+ PercentileFilter<double> median_filter_;
+ double trendline_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(MedianSlopeEstimator);
+};
+} // namespace webrtc
+
+#endif // WEBRTC_MODULES_CONGESTION_CONTROLLER_MEDIAN_SLOPE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/median_slope_estimator_unittest.cc b/modules/congestion_controller/median_slope_estimator_unittest.cc
new file mode 100644
index 0000000..ef942f1
--- /dev/null
+++ b/modules/congestion_controller/median_slope_estimator_unittest.cc
@@ -0,0 +1,113 @@
+/*
+ * Copyright (c) 2016 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/test/gtest.h"
+#include "webrtc/base/random.h"
+#include "webrtc/modules/congestion_controller/median_slope_estimator.h"
+
+namespace webrtc {
+
+namespace {
+constexpr size_t kWindowSize = 20;
+constexpr double kGain = 1;
+constexpr int64_t kAvgTimeBetweenPackets = 10;
+} // namespace
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeOneHalf) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = 2 * send_delta;
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), 0.5, 0.001);
+ }
+}
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeMinusOne) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = 0.5 * send_delta;
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), -1, 0.001);
+ }
+}
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeZero) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = send_delta;
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ }
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeOneHalf) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = 2 * send_delta + rand.Gaussian(0, send_delta / 3);
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), 0.5, 0.1);
+ }
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeMinusOne) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = 0.5 * send_delta + rand.Gaussian(0, send_delta / 20);
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), -1, 0.1);
+ }
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeZero) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random rand(0x1234567);
+ double now_ms = rand.Rand<double>() * 10000;
+ for (size_t i = 1; i < 2 * kWindowSize; i++) {
+ double send_delta = rand.Rand<double>() * 2 * kAvgTimeBetweenPackets;
+ double recv_delta = send_delta + rand.Gaussian(0, send_delta / 5);
+ now_ms += recv_delta;
+ estimator.Update(recv_delta, send_delta, now_ms);
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.1);
+ }
+}
+
+} // namespace webrtc
diff --git a/modules/remote_bitrate_estimator/test/plot_dynamics.py b/modules/remote_bitrate_estimator/test/plot_dynamics.py
index 5fdac51..40f1778 100755
--- a/modules/remote_bitrate_estimator/test/plot_dynamics.py
+++ b/modules/remote_bitrate_estimator/test/plot_dynamics.py
@@ -145,8 +145,11 @@
"Time (s)", "Delay (ms)")
trendline_state.addSubplot(["trendline_slope"], "Time (s)", "Slope")
+ target_bitrate = Figure("TargetBitrate")
+ target_bitrate.addSubplot(['target_bitrate_bps'], "Time (s)", "Bitrate (bps)")
+
# Select which figures to plot here.
- figures = [receiver, detector_state, trendline_state]
+ figures = [receiver, detector_state, trendline_state, target_bitrate]
# Add samples to the figures.
for line in sys.stdin:
