Use bayesian estimate of acked bitrate.

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 55d29fb430ebdb0eb4c8a8d50f7359bbfedb4afa..c349fcbf1b6f05d2ababad7fb39abd2f4bf64536 100644
--- a/webrtc/modules/congestion_controller/delay_based_bwe.cc
+++ b/webrtc/modules/congestion_controller/delay_based_bwe.cc
@@ -35,16 +35,76 @@ constexpr double kTimestampToMs =
 // This ssrc is used to fulfill the current API but will be removed
 // after the API has been changed.
 constexpr uint32_t kFixedSsrc = 0;
+constexpr int kRateWindowMs = 150;
+
 }  // namespace
 
 namespace webrtc {
+DelayBasedBwe::BitrateEstimator::BitrateEstimator()
+    : sum_(0),
+      count_(0),
+      current_win_ms_(0),
+      prev_time_ms_(-1),
+      bitrate_estimate_(300.0f),
+      bitrate_estimate_std_(2000.0f) {}
+
+void DelayBasedBwe::BitrateEstimator::Update(int64_t now_ms, int bytes) {
+  std::pair<float, int> bitrate_sample = UpdateWindow(now_ms, bytes);

[terelius, 2016/10/25 12:51:19]

Are we using the bitrate_sample.second anywhere?

[stefan-webrtc, 2016/10/26 11:23:17]

Yes, line 57 :)

[terelius, 2016/10/26 13:05:02]

Acknowledged.

+  if (bitrate_sample.first <= 0.0f)
+    return;
+  // Define the sample uncertainty as a function of how far away it is from the
+  // current estimate, and how many payloads it is based on.
+  float sample_uncertainty = std::max(5 * (5 - bitrate_sample.second), 1) *
+                             (bitrate_estimate_ - bitrate_sample.first);
+  float sample_var = std::max(sample_uncertainty * sample_uncertainty, 1.0f);
+  // Update a bayesian estimate of the rate, weighting it lower if the sample
+  // uncertainty is large.
+  // The bitrate estimate uncertainty is increased with each update to model
+  // the possibility that the bitrate can change over time.
+  float bitrate_estimate_std = bitrate_estimate_std_ + 60.0f;
+  float bitrate_estimate_var = bitrate_estimate_std * bitrate_estimate_std;
+  float denom = 1.0f / sample_var + 1.0f / bitrate_estimate_var;
+  bitrate_estimate_std_ = sqrt(1.0f / denom);

[terelius, 2016/10/25 11:42:14]

Maybe we could skip the sqrt and the denom computation, and do
bitrate_estimate_var = sample_var*bitrate_estimate_var /
(sample_var+bitrate_estimate_var);

WDYT? 

[stefan-webrtc, 2016/10/26 11:23:17]

Done.

+  bitrate_estimate_ = (sample_var * bitrate_estimate_ +
+                       bitrate_estimate_var * bitrate_sample.first) /
+                      (sample_var + bitrate_estimate_var);

[terelius, 2016/10/25 11:42:13]

I think this is supposed to be the old estimate variance (before you update it)

[terelius, 2016/10/25 12:51:19]

Nvm, it is based on the old variance.

+}
+
+std::pair<float, int> DelayBasedBwe::BitrateEstimator::UpdateWindow(
+    int64_t now_ms,
+    int bytes) {
+  // Reset if time moves backwards.
+  if (now_ms < prev_time_ms_) {
+    prev_time_ms_ = -1;
+    sum_ = 0;
+    count_ = 0;
+    current_win_ms_ = 0;
+  }
+  if (prev_time_ms_ >= 0)
+    current_win_ms_ += now_ms - prev_time_ms_;
+  std::pair<float, int> bitrate_sample(-1.0f, count_);
+  if (current_win_ms_ >= kRateWindowMs) {

[terelius, 2016/10/25 12:51:19]

If we receive packets at 1Mbps and then receive nothing for a time much longer
than kRateWindowMs, then the next time we get a packet it will still report a
bitrate 1Mbps?

[stefan-webrtc, 2016/10/26 11:23:17]

Yes, you are right. I guess the option would be to update twice in the case
where an acked packet results in both the current window and the next window
being filled?

The way it works now the second update will come one packet later.

Not sure what I prefer, but the current approach is at least simpler. WDYT?

[terelius, 2016/10/26 13:05:02]

Maybe current_win_ms_ %= kRateWindowMs instead of current_win_ms_ -=
kRateWindowMs?

+    bitrate_sample.first = 8.0f * sum_ / static_cast<float>(kRateWindowMs);
+    current_win_ms_ -= kRateWindowMs;
+    sum_ = 0;
+    count_ = 0;
+  }
+  sum_ += bytes;
+  ++count_;
+  prev_time_ms_ = now_ms;
+  return bitrate_sample;
+}
+
+int DelayBasedBwe::BitrateEstimator::bitrate_bps() const {
+  return bitrate_estimate_ * 1000;
+}
 
 DelayBasedBwe::DelayBasedBwe(Clock* clock)
     : clock_(clock),
       inter_arrival_(),
       estimator_(),
       detector_(OverUseDetectorOptions()),
-      receiver_incoming_bitrate_(kBitrateWindowMs, 8000),
+      receiver_incoming_bitrate_(),
       last_update_ms_(-1),
       last_seen_packet_ms_(-1),
       uma_recorded_(false) {
@@ -73,7 +133,7 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
     const PacketInfo& info) {
   int64_t now_ms = clock_->TimeInMilliseconds();
 
-  receiver_incoming_bitrate_.Update(info.payload_size, info.arrival_time_ms);
+  receiver_incoming_bitrate_.Update(info.arrival_time_ms, info.payload_size);
   Result result;
   // Reset if the stream has timed out.
   if (last_seen_packet_ms_ == -1 ||
@@ -113,29 +173,28 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
     probing_bps = probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(info);
   }
 
+  int acked_bitrate_bps = receiver_incoming_bitrate_.bitrate_bps();
   // Currently overusing the bandwidth.
   if (detector_.State() == kBwOverusing) {
-    rtc::Optional<uint32_t> incoming_rate =
-        receiver_incoming_bitrate_.Rate(info.arrival_time_ms);
-    if (incoming_rate &&
-        rate_control_.TimeToReduceFurther(now_ms, *incoming_rate)) {
-      result.updated = UpdateEstimate(info.arrival_time_ms, now_ms,
-                                      &result.target_bitrate_bps);
+    if (rate_control_.TimeToReduceFurther(now_ms, acked_bitrate_bps)) {
+      result.updated =
+          UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
+                         &result.target_bitrate_bps);
     }
   } else if (probing_bps > 0) {
     // No overuse, but probing measured a bitrate.
     rate_control_.SetEstimate(probing_bps, info.arrival_time_ms);
     result.probe = true;
-    result.updated = UpdateEstimate(info.arrival_time_ms, now_ms,
-                                    &result.target_bitrate_bps);
+    result.updated =
+        UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
+                       &result.target_bitrate_bps);
   }
-  rtc::Optional<uint32_t> incoming_rate =
-      receiver_incoming_bitrate_.Rate(info.arrival_time_ms);
   if (!result.updated &&
       (last_update_ms_ == -1 ||
        now_ms - last_update_ms_ > rate_control_.GetFeedbackInterval())) {
-    result.updated = UpdateEstimate(info.arrival_time_ms, now_ms,
-                                    &result.target_bitrate_bps);
+    result.updated =
+        UpdateEstimate(info.arrival_time_ms, now_ms, acked_bitrate_bps,
+                       &result.target_bitrate_bps);
   }
   if (result.updated)
     last_update_ms_ = now_ms;
@@ -145,12 +204,12 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketInfo(
 
 bool DelayBasedBwe::UpdateEstimate(int64_t arrival_time_ms,
                                    int64_t now_ms,
+                                   int acked_bitrate_bps,
                                    uint32_t* target_bitrate_bps) {
-  // The first overuse should immediately trigger a new estimate.
-  // We also have to update the estimate immediately if we are overusing
-  // and the target bitrate is too high compared to what we are receiving.
+  if (acked_bitrate_bps <= 0)
+    return false;
   const RateControlInput input(detector_.State(),
-                               receiver_incoming_bitrate_.Rate(arrival_time_ms),
+                               rtc::Optional<uint32_t>(acked_bitrate_bps),
                                estimator_->var_noise());
   rate_control_.Update(&input, now_ms);
   *target_bitrate_bps = rate_control_.UpdateBandwidthEstimate(now_ms);