Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation).

webrtc/modules/congestion_controller/delay_based_bwe.cc

Index: webrtc/modules/congestion_controller/delay_based_bwe.cc
diff --git a/webrtc/modules/congestion_controller/delay_based_bwe.cc b/webrtc/modules/congestion_controller/delay_based_bwe.cc
index 04dadc489c0afac2a17e88510e2ea4397b5e9f4b..bb63f353daf31f3fd3d413a3ae0fc39c93bf5f86 100644
--- a/webrtc/modules/congestion_controller/delay_based_bwe.cc
+++ b/webrtc/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 uint32_t kFixedSsrc = 0;
 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 @@ bool TrendlineFilterExperimentIsEnabled() {
   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 @@ bool ReadTrendlineFilterExperimentParameters(size_t* window_points,
   }
   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 @@ rtc::Optional<uint32_t> DelayBasedBwe::BitrateEstimator::bitrate_bps() const {
 }
 
 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 @@ DelayBasedBwe::DelayBasedBwe(Clock* clock)
       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 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
     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 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
       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 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
         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;
 }