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.
  */
 
@@ skipping 17 matching lines @@
 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_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) {
   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);
   }
-  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;
 
   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