ProbingEstimator: Erase history based on time threshold

webrtc/modules/congestion_controller/probe_bitrate_estimator.cc

Index: webrtc/modules/congestion_controller/probe_bitrate_estimator.cc
diff --git a/webrtc/modules/congestion_controller/probe_bitrate_estimator.cc b/webrtc/modules/congestion_controller/probe_bitrate_estimator.cc
index 561fde939180b74e0cad8b606952487c984eabbd..111dc8d6751baaf93f328fa4a2d87d3c6f523a51 100644
--- a/webrtc/modules/congestion_controller/probe_bitrate_estimator.cc
+++ b/webrtc/modules/congestion_controller/probe_bitrate_estimator.cc
@@ -12,40 +12,34 @@
 
 #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;
-}
 
-namespace webrtc {
+// 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;

[Irfan, 2016/08/16 17:02:10]

This may be to high if we want to do probing more often in some scenarios.

I am planning to reduce to 1s. lmk if you feel strongly on a value here.

 
-ProbingResult::ProbingResult() : bps(kNoEstimate), timestamp(0) {}
+// The maximum time interval between first and the last probe on a cluster
+// on the sender side as well as the receive side.
+constexpr int kMaxProbeIntervalInMs = 1000;
+}  // namespace
 
-ProbingResult::ProbingResult(int bps, int64_t timestamp)
-    : bps(bps), timestamp(timestamp) {}
-
-bool ProbingResult::valid() const {
-  return bps != kNoEstimate;
-}
+namespace webrtc {
 
-ProbeBitrateEstimator::ProbeBitrateEstimator() : last_valid_cluster_id_(0) {}
+ProbeBitrateEstimator::ProbeBitrateEstimator() {}
 
-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 =
@@ -57,14 +51,19 @@ ProbingResult ProbeBitrateEstimator::PacketFeedback(
   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;
 
   if (cluster->num_probes < kMinNumProbesValidCluster)
-    return ProbingResult();
+    return -1;
+
+  // The first time a cluster meets minimum requirement.
+  if (cluster->num_probes == kMinNumProbesValidCluster)
+    ++valid_clusters_;

[philipel, 2016/08/16 15:21:06]

At this point we don't know if this is a valid cluster or not, move to line 89.

[Irfan, 2016/08/16 17:02:10]

valid cluster indicates that we have received enough probes
(kMinNumProbesValidCluster) to evaluate it.

We have this to allow waiting on probes to be received on multiple clusters (3x
+ 6x scenario at init) before evaluating bitrate and reporting back
paced_sender.

Moving this down at line 89 would mean that if the first cluster had an
unsuccessful probing (due to timing issues), we would not even look at the
second cluster at all at line 56. And we do want to evaluate even if one cluster
has successful probing.

[philipel, 2016/08/19 13:41:31]

This can still cause us to ignore the second probe cluster if we don't receive
enough feedback about the first probe cluster.

I would suggest that we either keep the old logic that only report results about
the current or newer probing attempt, or, we expand the ProbeResult class with
more information about the probing cluster (like cluster id or maybe
send/receive timestamps) so that the decision can be made somewhere else.

+
+  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 =
@@ -78,13 +77,14 @@ ProbingResult ProbeBitrateEstimator::PacketFeedback(
   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 =
@@ -101,12 +101,8 @@ ProbingResult ProbeBitrateEstimator::PacketFeedback(
                  << " [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 / "
@@ -114,7 +110,29 @@ ProbingResult ProbeBitrateEstimator::PacketFeedback(
                << " [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_;
+      it = clusters_.erase(it);
+    } else {
+      ++it;
+    }
+  }
 }
+
+int ProbeBitrateEstimator::HighestBitrateOnClusters() {

[philipel, 2016/08/16 15:21:06]

Shouldn't this iterate over only the last |min_clusters| from
HandleProbeAndEstimateBitrate?

[Irfan, 2016/08/16 17:02:10]

The |min_clusters| indicates minimum number of clusters we want to look at. We
could also turn it into an exact requirement (instead of min) and in that case
look at that many clusters, but do you see an issue with this ?

On a related note, am considering to reduce the max cluster history to 1 second.

+  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