Use bayesian estimate of acked bitrate.

webrtc/modules/congestion_controller/delay_based_bwe.cc

 /*
  *  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/delay_based_bwe.h"
 
-#include <math.h>
-
 #include <algorithm>
+#include <cmath>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/base/constructormagic.h"
 #include "webrtc/base/logging.h"
 #include "webrtc/base/thread_annotations.h"
 #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/system_wrappers/include/metrics.h"
 #include "webrtc/typedefs.h"
 
 namespace {
 constexpr int kTimestampGroupLengthMs = 5;
 constexpr int kAbsSendTimeFraction = 18;
 constexpr int kAbsSendTimeInterArrivalUpshift = 8;
 constexpr int kInterArrivalShift =
     kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift;
 constexpr double kTimestampToMs =
     1000.0 / static_cast<double>(1 << kInterArrivalShift);
 // 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_var_(4e6) {}
+
+void DelayBasedBwe::BitrateEstimator::Update(int64_t now_ms, int bytes) {
+  std::pair<float, int> bitrate_sample = UpdateWindow(now_ms, bytes);
+  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(std::max(5 * (5 - bitrate_sample.second), 1) *
+                   std::abs(bitrate_estimate_ - bitrate_sample.first),
+               1.0f);
+  float sample_var = sample_uncertainty * sample_uncertainty;
+  // 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
+  // that the bitrate changes over time.
+  float pred_bitrate_estimate_var = bitrate_estimate_var_ + 20000.0f;
+  bitrate_estimate_ = (sample_var * bitrate_estimate_ +
+                       pred_bitrate_estimate_var * bitrate_sample.first) /
+                      (sample_var + pred_bitrate_estimate_var);
+  bitrate_estimate_var_ = sample_var * pred_bitrate_estimate_var /
+                          (sample_var + pred_bitrate_estimate_var);
+}
+
+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_;
+    // Reset if nothing has been received for more than a full window.
+    if (now_ms - prev_time_ms_ > kRateWindowMs) {
+      sum_ = 0;
+      count_ = 0;
+      current_win_ms_ %= kRateWindowMs;
+    }
+  }
+  prev_time_ms_ = now_ms;
+  std::pair<float, int> bitrate_sample(-1.0f, count_);
+  if (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_;
+  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) {
   network_thread_.DetachFromThread();
 }
 
 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
     const std::vector<PacketInfo>& packet_feedback_vector) {
   RTC_DCHECK(network_thread_.CalledOnValidThread());
   if (!uma_recorded_) {
     RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram,
                               BweNames::kSendSideTransportSeqNum,
                               BweNames::kBweNamesMax);
     uma_recorded_ = true;
   }
   Result aggregated_result;
   for (const auto& packet_info : packet_feedback_vector) {
     Result result = IncomingPacketInfo(packet_info);
     if (result.updated)
       aggregated_result = result;
   }
   return aggregated_result;
 }
 
 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 ||
       now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) {
     inter_arrival_.reset(
         new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
                          kTimestampToMs, true));
     estimator_.reset(new OveruseEstimator(OverUseDetectorOptions()));
   }
   last_seen_packet_ms_ = now_ms;
@@ skipping 19 matching lines @@
                        info.arrival_time_ms);
     detector_.Detect(estimator_->offset(), ts_delta_ms,
                      estimator_->num_of_deltas(), info.arrival_time_ms);
   }
 
   int probing_bps = 0;
   if (info.probe_cluster_id != PacketInfo::kNotAProbe) {
     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);
   }
   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;
 
   return result;
 }
 
 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);
   return rate_control_.ValidEstimate();
 }
 
 void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) {
   rate_control_.SetRtt(avg_rtt_ms);
 }
 
@@ skipping 12 matching lines @@
   *bitrate_bps = rate_control_.LatestEstimate();
   return true;
 }
 
 void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) {
   // Called from both the configuration thread and the network thread. Shouldn't
   // be called from the network thread in the future.
   rate_control_.SetMinBitrate(min_bitrate_bps);
 }
 }  // namespace webrtc