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 = 250;
+
 }  // namespace
 
 namespace webrtc {
+DelayBasedBwe::RateEstimator::RateEstimator()
+    : sum_(0),
+      count_(0),
+      bitrate_estimate_(300.0f),
+      bitrate_estimate_std_(2000.0f) {}
+
+void DelayBasedBwe::RateEstimator::Update(int64_t now_ms, int bytes) {
+  UpdateWindow(now_ms, bytes);
+  RTC_DCHECK_GE(sum_, 0);
+  RTC_DCHECK_GE(count_, 0);
+  float bitrate_sample = 8.0f * sum_ / static_cast<float>(kRateWindowMs);
+  // Define the sample uncertainty as a function of how far away it is from the
+  // current estimate, and how many payloads it based on.

[terelius, 2016/10/21 10:15:52]

nit: it is based on

[stefan-webrtc, 2016/10/24 10:55:14]

Done.

+  float sample_uncertainty =

[terelius, 2016/10/21 10:15:52]

This essentially means that we make smaller changes to the estimate if the
difference between the estimate and the measured value is large.
Shouldn't the sample uncertainty be based on the spread of recently measured
values instead? For example
sample_var = 1/N \sum (x_i - x)^2   where x = 1/N \sum x_i

[stefan-webrtc, 2016/10/24 10:55:14]

Yes, maybe. I'm worried that the window would have to be too large, which is why
I went with this approach. I can run some tests with your suggestion though. It
should in theory have similar properties, but I'm afraid that the averaging may
mean that a single deviating sample won't be suppressed as much as we'd like?

[terelius, 2016/10/24 11:20:38]

Maybe it is difficult to do what I suggested since it would require a list of
recent bitrate measurements, whereas the current window holds a list of packets
which only gives us a single bitrate. Feel free to disregard my original comment
if you want.

+      std::max(5 * (5 - count_), 1) * (bitrate_estimate_ - bitrate_sample);
+  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.
+  // TODO(holmer): Consider increasing the uncertainty every N milliseconds
+  // instead of every update.
+  float bitrate_estimate_std = bitrate_estimate_std_ + 25.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);
+  bitrate_estimate_ =

[terelius, 2016/10/21 10:15:52]

I believe that the reason we are slow to recover from a delay spike is that we
weight the measurement and the previous estimate differently, and the weights
changes during the execution. Since this update is similar, we should monitor
the variances to ensure that we don't get the same problem here.

[stefan-webrtc, 2016/10/24 10:55:14]

Good point. The problem would occur if for instance the bitrate temporarily
increases to something very large, and then decreases to something very small.
In that case it may take us a longer time to adapt.

I'm not entirely sure about this approach, so let me know if you have
suggestions. I experimented a bit with a max filter too, which could be an
alternative, and perhaps a bit simpler. A max filter relies more on the window
being correctly chosen though...

+      (bitrate_estimate_ / bitrate_estimate_var + bitrate_sample / sample_var) *
+      bitrate_estimate_std_ * bitrate_estimate_std_;

[terelius, 2016/10/21 10:15:52]

This update could alternatively be written as

estimate = (estimate*(sample-estimate)^2 + sample*old_estimate_std^2) /
           ((sample-estimate)^2 + old_estimate_std^2)
           

[stefan-webrtc, 2016/10/24 10:55:14]

Do you prefer that?

[terelius, 2016/10/24 11:20:38]

I think I'd prefer
estimate = (sample_var * estimate + old_estimate_var * sample) / (sample_var +
old_estimate_var)

AFAIK, that's the most common form for the bayesian update, and it is
independent of how we estimate the variances. It also makes it clear that we are
taking a weighted average (i.e. that the coefficients sum to 1).

[stefan-webrtc, 2016/10/25 11:04:33]

Yes, the sums to 1 is a nice thing to show clearly.

+}
+
+void DelayBasedBwe::RateEstimator::UpdateWindow(int64_t now_ms, int bytes) {
+  // Reset if time moves backwards.
+  if (!payloads_.empty() && payloads_.back().first > now_ms) {
+    payloads_.clear();
+    sum_ = 0;
+  }
+  payloads_.push_back(std::make_pair(now_ms, bytes));
+  sum_ += bytes;
+  ++count_;
+  while (!payloads_.empty()) {
+    auto oldest = payloads_.front();
+    if (oldest.first > now_ms - kRateWindowMs)
+      break;
+    sum_ -= oldest.second;
+    payloads_.pop_front();
+    --count_;
+  }
+}
+
+int DelayBasedBwe::RateEstimator::bitrate_estimate() const {
+  return bitrate_estimate_ * 1000;

[terelius, 2016/10/21 10:15:52]

Why multiply by 1000?

[stefan-webrtc, 2016/10/24 10:55:14]

I wanted the returned value to be bits/s. Should probably change to bits/s
everywhere instead though.

[terelius, 2016/10/24 11:20:38]

Oh, right. It would have been bits/ms otherwise.

+}
 
 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_estimate();
   // 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