ProbingEstimator: Erase history based on time threshold

webrtc/modules/congestion_controller/probe_bitrate_estimator.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/probe_bitrate_estimator.h"
 
 #include <algorithm>
 
+#include "webrtc/base/checks.h"
 #include "webrtc/base/logging.h"
 
 namespace {
-// Max number of saved clusters.
-constexpr size_t kMaxNumSavedClusters = 5;
-
 // The minumum number of probes we need for a valid cluster.
 constexpr int kMinNumProbesValidCluster = 4;
 
 // The maximum (receive rate)/(send rate) ratio for a valid estimate.
 constexpr float kValidRatio = 1.2f;
+
+// The maximum time period of which the cluster history is retained.
+// This is also the maximum time period beyond which a probing burst is not
+// expected to last.
+constexpr int kMaxClusterHistoryInMs = 5000;
+
+// The maximum time interval between first and the last probe on a cluster
+// on the side side as well as the receive side.

[stefan-webrtc, 2016/08/13 10:05:10]

sender side

[Irfan, 2016/08/15 07:00:07]

Done.

+constexpr int kMaxProbeIntervalInMs = 1000;
 }
 
 namespace webrtc {
 
-ProbingResult::ProbingResult() : bps(kNoEstimate), timestamp(0) {}
+ProbeBitrateEstimator::ProbeBitrateEstimator() {}
 
-ProbingResult::ProbingResult(int bps, int64_t timestamp)
-    : bps(bps), timestamp(timestamp) {}
-
-bool ProbingResult::valid() const {
-  return bps != kNoEstimate;
-}
-
-ProbeBitrateEstimator::ProbeBitrateEstimator() : last_valid_cluster_id_(0) {}
-
-ProbingResult ProbeBitrateEstimator::PacketFeedback(
-    const PacketInfo& packet_info) {
-  // If this is not a probing packet or if this probing packet
-  // belongs to an old cluster, do nothing.
-  if (packet_info.probe_cluster_id == PacketInfo::kNotAProbe ||
-      packet_info.probe_cluster_id < last_valid_cluster_id_) {
-    return ProbingResult();
-  }
+int ProbeBitrateEstimator::HandleProbeAndEstimateBitrate(
+    const PacketInfo& packet_info,
+    int min_clusters) {
+  RTC_DCHECK(packet_info.probe_cluster_id != PacketInfo::kNotAProbe);
 
   AggregatedCluster* cluster = &clusters_[packet_info.probe_cluster_id];
   cluster->first_send_ms =
       std::min(cluster->first_send_ms, packet_info.send_time_ms);
   cluster->last_send_ms =
       std::max(cluster->last_send_ms, packet_info.send_time_ms);
   cluster->first_receive_ms =
       std::min(cluster->first_receive_ms, packet_info.arrival_time_ms);
   cluster->last_receive_ms =
       std::max(cluster->last_receive_ms, packet_info.arrival_time_ms);
   cluster->size += packet_info.payload_size * 8;
-  cluster->num_probes += 1;
-
-  // Clean up old clusters.
-  while (clusters_.size() > kMaxNumSavedClusters)
-    clusters_.erase(clusters_.begin());
+  cluster->num_probes++;

[stefan-webrtc, 2016/08/13 10:05:10]

++cluster...;

[Irfan, 2016/08/15 07:00:07]

Done.

 
   if (cluster->num_probes < kMinNumProbesValidCluster)
-    return ProbingResult();
+    return -1;
+
+  // The first time a cluster meets minimum requirement.
+  if (cluster->num_probes == kMinNumProbesValidCluster)
+    valid_clusters_++;
+
+  if (valid_clusters_ < min_clusters)
+    return -1;
+
+  EraseOldClusters(packet_info.arrival_time_ms - kMaxClusterHistoryInMs);
 
   float send_interval_ms = cluster->last_send_ms - cluster->first_send_ms;
   float receive_interval_ms =
       cluster->last_receive_ms - cluster->first_receive_ms;
 
   // Since the send/receive interval does not include the send/receive time of
   // the last/first packet we expand the interval by the average inverval
   // between the probing packets.
   float interval_correction =
       static_cast<float>(cluster->num_probes) / (cluster->num_probes - 1);
   send_interval_ms *= interval_correction;
   receive_interval_ms *= interval_correction;
 
-  if (send_interval_ms == 0 || receive_interval_ms == 0) {
+  if (send_interval_ms <= 0 || receive_interval_ms <= 0 ||
+      send_interval_ms > kMaxProbeIntervalInMs ||
+      receive_interval_ms > kMaxProbeIntervalInMs) {
     LOG(LS_INFO) << "Probing unsuccessful, invalid send/receive interval"
                  << " [cluster id: " << packet_info.probe_cluster_id
                  << "] [send interval: " << send_interval_ms << " ms]"
                  << " [receive interval: " << receive_interval_ms << " ms]";
-
-    return ProbingResult();
+    return -1;
   }
   float send_bps = static_cast<float>(cluster->size) / send_interval_ms * 1000;
   float receive_bps =
       static_cast<float>(cluster->size) / receive_interval_ms * 1000;
   float ratio = receive_bps / send_bps;
   if (ratio > kValidRatio) {
     LOG(LS_INFO) << "Probing unsuccessful, receive/send ratio too high"
                  << " [cluster id: " << packet_info.probe_cluster_id
                  << "] [send: " << cluster->size << " bytes / "
                  << send_interval_ms << " ms = " << send_bps / 1000 << " kb/s]"
                  << " [receive: " << cluster->size << " bytes / "
                  << receive_interval_ms << " ms = " << receive_bps / 1000
                  << " kb/s]"
                  << " [ratio: " << receive_bps / 1000 << " / "
                  << send_bps / 1000 << " = " << ratio << " > kValidRatio ("
                  << kValidRatio << ")]";
-
-    return ProbingResult();
+    return -1;
   }
-  // We have a valid estimate.
-  int result_bps = std::min(send_bps, receive_bps);
-  last_valid_cluster_id_ = packet_info.probe_cluster_id;
   LOG(LS_INFO) << "Probing successful"
                << " [cluster id: " << packet_info.probe_cluster_id
                << "] [send: " << cluster->size << " bytes / "
                << send_interval_ms << " ms = " << send_bps / 1000 << " kb/s]"
                << " [receive: " << cluster->size << " bytes / "
                << receive_interval_ms << " ms = " << receive_bps / 1000
                << " kb/s]";
+  cluster->bps = std::min(send_bps, receive_bps);
+  return HighestBitrateOnClusters();
+}
 
-  return ProbingResult(result_bps, packet_info.arrival_time_ms);
+void ProbeBitrateEstimator::EraseOldClusters(int64_t timestamp_ms) {
+  for (auto it = clusters_.begin(); it != clusters_.end();) {
+    if (it->second.last_receive_ms < timestamp_ms) {
+      if (it->second.num_probes >= kMinNumProbesValidCluster)
+        valid_clusters_--;

[stefan-webrtc, 2016/08/13 10:05:11]

--valid_clusters_;

[Irfan, 2016/08/15 07:00:07]

Done.

+      it = clusters_.erase(it);
+    } else {
+      ++it;
+    }
+  }
 }
+
+int ProbeBitrateEstimator::HighestBitrateOnClusters() {

[stefan-webrtc, 2016/08/13 10:05:11]

Our previous reasoning has been that if a probe cluster at, say, 1000 kbps fails
and the next cluster at 2000 kbps succeeds, both are considered failures. This
could perhaps be a too cautious decision. What's the rationale for accepting the
higher bitrate probes as we do with this change?

[Irfan, 2016/08/15 07:00:07]

Given that probing uses 5 samples to get a quick idea of the BW, a failure (we
discard measured data for several reasons) indicates that the probing was
unsuccessful. A success at a higher bitrate does indicate that the bottleneck on
the end-to-end path can handle that particular bitrate and the measured bitrate
should be useful as a starting point. Also, the overuse/underuse signals stay
active during probing to handle a real issue. Happy to chat more over VC on
this.

+  int highest_bps = 0;
+  for (const auto& kv : clusters_) {
+    if (kv.second.bps > highest_bps)
+      highest_bps = kv.second.bps;
+  }
+  return highest_bps;
+}
+
 }  // namespace webrtc