Probing: Add support for exponential startup probing

webrtc/modules/pacing/bitrate_prober.cc

Index: webrtc/modules/pacing/bitrate_prober.cc
diff --git a/webrtc/modules/pacing/bitrate_prober.cc b/webrtc/modules/pacing/bitrate_prober.cc
index aba108d37e136e9949cc0e0043677f572596d546..4b61c7e5e652c4c7d43f009aa8d30d02ef8eb22d 100644
--- a/webrtc/modules/pacing/bitrate_prober.cc
+++ b/webrtc/modules/pacing/bitrate_prober.cc
@@ -23,6 +23,19 @@ namespace {
 // Inactivity threshold above which probing is restarted.
 constexpr int kInactivityThresholdMs = 5000;
 
+// Number of deltas between probes per cluster. On the very first cluster,
+// we will need kProbeDeltasPerCluster + 1 probes, but on a cluster following
+// another, we need kProbeDeltasPerCluster probes.
+constexpr int kProbeDeltasPerCluster = 5;
+
+// Maximum waiting time from the time of sending last probe to getting
+// the measured results back.
+constexpr int64_t kMaxWaitingTimeForProbingResultMs = 1000;
+
+// Value of |min_bitrate_to_probe_further_| that indicates
+// further probing is disabled.
+constexpr int kDisableExponentialProbing = 0;
+
 int ComputeDeltaFromBitrate(size_t packet_size, int bitrate_bps) {
   RTC_CHECK_GT(bitrate_bps, 0);
   // Compute the time delta needed to send packet_size bytes at bitrate_bps
@@ -32,40 +45,95 @@ int ComputeDeltaFromBitrate(size_t packet_size, int bitrate_bps) {
 }  // namespace
 
 BitrateProber::BitrateProber()
-    : probing_state_(ProbingState::kDisabled),
+    : probing_state_(State::kInit),
       packet_size_last_sent_(0),
       time_last_probe_sent_ms_(-1),
-      next_cluster_id_(0) {
-  SetEnabled(true);
+      next_cluster_id_(0),
+      min_bitrate_to_probe_further_(kDisableExponentialProbing),
+      estimated_bitrate_bps_(0) {}
+
+bool BitrateProber::IsProbing() const {
+  return probing_state_ == State::kSending;
 }
 
 void BitrateProber::SetEnabled(bool enable) {
   if (enable) {
-    if (probing_state_ == ProbingState::kDisabled) {
-      probing_state_ = ProbingState::kInactive;
-      LOG(LS_INFO) << "Bandwidth probing enabled, set to inactive";
+    if (probing_state_ == State::kDisabled) {
+      probing_state_ = State::kInit;
+      LOG(LS_INFO) << "Bandwidth probing enabled";
     }
   } else {
-    probing_state_ = ProbingState::kDisabled;
+    probing_state_ = State::kDisabled;
     LOG(LS_INFO) << "Bandwidth probing disabled";
   }
 }
 
-bool BitrateProber::IsProbing() const {
-  return probing_state_ == ProbingState::kActive;
+bool BitrateProber::IsExpectingProbingResults() const {
+  // We would like to hear of probe results the moment we start sending
+  // probes.
+  return probing_state_ == State::kSending ||
+         probing_state_ == State::kWaitForResult;
 }
 
-void BitrateProber::OnIncomingPacket(size_t packet_size) {
-  // Don't initialize probing unless we have something large enough to start
-  // probing.
-  if (probing_state_ == ProbingState::kInactive &&
-      !clusters_.empty() &&
-      packet_size >= PacedSender::kMinProbePacketSize) {
-    probing_state_ = ProbingState::kActive;
+void BitrateProber::SetEstimatedBitrate(int bitrate_bps) {

[philipel, 2016/08/25 10:39:56]

In order to make the bitrate prober more general I would suggest we move the
logic to perform exponential probing to the congestion controller (now that the
delay based bwe takes a congestion controller instead of a remote bitrate
observer).

[stefan-webrtc, 2016/09/02 13:10:22]

Do you mean that the CongestionController should be calling CreateProbeCluster()
with exponentially increasing bitrates?

I don't want to spread out the logic too much, but at the same time it would be
good to don't make too many assumptions in this class, so if the amount of
probing code needed in CongestionController is small I think that might be a
good idea.

[philipel, 2016/09/02 13:32:50]

To me it looks like this could be implemented either in
CongestionController::Process or in
CongestionController::MaybeTriggerOnNetworkChanged.

I think it's important to keep the "lego blocks" clean so they are both easy to
understand but also to avoid having to refactor even the most basic components
in the case of anyone wanting to change the probing behavior.

+  switch (probing_state_) {
+    // We could have a result before we finish sending probe clusters
+    // completely.
+    case State::kSending:
+    case State::kWaitForResult:
+      LOG(LS_INFO) << "SetEstimatedBitrate " << bitrate_bps;
+      if (min_bitrate_to_probe_further_ &&

[philipel, 2016/08/25 10:39:56]

min_bitrate_to_probe_further != kDisableExponentialProbing

+          bitrate_bps > min_bitrate_to_probe_further_) {
+        // Reset before new probe session.
+        ResetState();
+        CreateProbeCluster(2 * bitrate_bps, kProbeDeltasPerCluster + 1);
+        // A minimum of 25% gain to continue.
+        min_bitrate_to_probe_further_ = 1.25 * bitrate_bps;
+        LOG(LS_INFO) << " min_bitrate_to_probe_further_  "
+                     << min_bitrate_to_probe_further_;
+      }
+      break;
+    default:
+      break;
+  }
+  estimated_bitrate_bps_ = bitrate_bps;
+}
+
+void BitrateProber::OnIncomingPacket(int64_t now_ms, size_t packet_size) {
+  switch (probing_state_) {
+    case State::kInit:
+      // Don't initialize probing unless we have something large enough to start
+      // probing.
+      if (packet_size >= PacedSender::kMinProbePacketSize &&
+          estimated_bitrate_bps_ > 0) {
+        LOG(LS_INFO) << "kInit: initialize probing";
+        // Ensure state is initialized before starting probing.
+        ResetState();
+        CreateProbeCluster(900000, kProbeDeltasPerCluster + 1);

[philipel, 2016/08/25 10:39:56]

Why move the creation of initial probe clusters here?

+        CreateProbeCluster(1800000, kProbeDeltasPerCluster);
+        // When probing at 1.8 Mbps ( 6x 300), this represents a threshold of
+        // 1.2 Mbps to continue probing.
+        min_bitrate_to_probe_further_ = 4 * estimated_bitrate_bps_;

[danilchap, 2016/08/23 17:59:29]

it probably make more sense to derive this value from just added probe, not
estimated_bitrate_bps_, Or derive probe bitrate from estimated_bitrate_bps_ too.
e.g.
const int kStartProbeBps = 1800000;
CreateProbeCluster(kStartProbeBps / 2,...);
CreateProbeCluster(kStartProbeBps,...);
min_bitrate_to_probe_further_ = kStartProbeBps * 2 / 3;

+        LOG(LS_INFO) << " min_bitrate_to_probe_further_  "
+                     << min_bitrate_to_probe_further_;
+      }
+      break;
+    case State::kWaitForResult:
+      if ((now_ms - time_last_probe_sent_ms_) >

[danilchap, 2016/08/23 17:59:29]

this check has nothing to do with IncomingPacket (a new media packet created to
be paced).
The kInit block uses only packet_size,
The kWaitForResult block uses only now_ms.
i.e. this two blocks of code feel too unrelated to be in same function.

May be move this block into own function and call it from PacedSender::Process?

[philipel, 2016/08/25 10:39:56]

I don't think this will ever occur. If we don't have packets to send we send
padding instead and PacketSent is still called. 

+          kMaxWaitingTimeForProbingResultMs) {
+        probing_state_ = State::kComplete;
+        LOG(LS_INFO) << "kWaitForResult: timeout";
+      }
+      break;
+    case State::kSending:
+    case State::kComplete:
+    case State::kDisabled:
+      break;
   }
 }
 
 void BitrateProber::CreateProbeCluster(int bitrate_bps, int num_packets) {
+  RTC_DCHECK(probing_state_ != State::kDisabled);
   ProbeCluster cluster;
   cluster.max_probe_packets = num_packets;
   cluster.probe_bitrate_bps = bitrate_bps;
@@ -74,8 +142,8 @@ void BitrateProber::CreateProbeCluster(int bitrate_bps, int num_packets) {
   LOG(LS_INFO) << "Probe cluster (bitrate:packets): ("
                << cluster.probe_bitrate_bps << ":" << cluster.max_probe_packets
                << ") ";
-  if (probing_state_ != ProbingState::kActive)
-    probing_state_ = ProbingState::kInactive;
+  probing_state_ = State::kSending;
+  min_bitrate_to_probe_further_ = kDisableExponentialProbing;
 }
 
 void BitrateProber::ResetState() {
@@ -90,14 +158,11 @@ void BitrateProber::ResetState() {
                        clusters.front().max_probe_packets);
     clusters.pop();
   }
-  // If its enabled, reset to inactive.
-  if (probing_state_ != ProbingState::kDisabled)
-    probing_state_ = ProbingState::kInactive;
 }
 
 int BitrateProber::TimeUntilNextProbe(int64_t now_ms) {
-  // Probing is not active or probing is already complete.
-  if (probing_state_ != ProbingState::kActive || clusters_.empty())
+  // Proceed only if we are in kSending state.
+  if (probing_state_ != State::kSending)
     return -1;
   // time_last_probe_sent_ms_ of -1 indicates no probes have yet been sent.
   int64_t elapsed_time_ms;
@@ -115,7 +180,7 @@ int BitrateProber::TimeUntilNextProbe(int64_t now_ms) {
   // We will send the first probe packet immediately if no packet has been
   // sent before.
   int time_until_probe_ms = 0;
-  if (packet_size_last_sent_ != 0 && probing_state_ == ProbingState::kActive) {
+  if (packet_size_last_sent_ != 0) {
     int next_delta_ms = ComputeDeltaFromBitrate(
         packet_size_last_sent_, clusters_.front().probe_bitrate_bps);
     time_until_probe_ms = next_delta_ms - elapsed_time_ms;
@@ -127,7 +192,7 @@ int BitrateProber::TimeUntilNextProbe(int64_t now_ms) {
     const int kMaxProbeDelayMs = 3;
     if (next_delta_ms < kMinProbeDeltaMs ||
         time_until_probe_ms < -kMaxProbeDelayMs) {
-      probing_state_ = ProbingState::kSuspended;
+      probing_state_ = State::kComplete;
       LOG(LS_INFO) << "Delta too small or missed probing accurately, suspend";
       time_until_probe_ms = 0;
     }
@@ -137,7 +202,7 @@ int BitrateProber::TimeUntilNextProbe(int64_t now_ms) {
 
 int BitrateProber::CurrentClusterId() const {
   RTC_DCHECK(!clusters_.empty());
-  RTC_DCHECK(ProbingState::kActive == probing_state_);
+  RTC_DCHECK(probing_state_ == State::kSending);
   return clusters_.front().id;
 }
 
@@ -147,11 +212,11 @@ size_t BitrateProber::RecommendedPacketSize() const {
 
 void BitrateProber::PacketSent(int64_t now_ms, size_t packet_size) {
   assert(packet_size > 0);
+  RTC_DCHECK(probing_state_ == State::kSending);
+
   if (packet_size < PacedSender::kMinProbePacketSize)
     return;
   packet_size_last_sent_ = packet_size;
-  if (probing_state_ != ProbingState::kActive)
-    return;
   time_last_probe_sent_ms_ = now_ms;
   if (!clusters_.empty()) {
     ProbeCluster* cluster = &clusters_.front();
@@ -159,7 +224,7 @@ void BitrateProber::PacketSent(int64_t now_ms, size_t packet_size) {
     if (cluster->sent_probe_packets == cluster->max_probe_packets)
       clusters_.pop();
     if (clusters_.empty())
-      probing_state_ = ProbingState::kSuspended;
+      probing_state_ = State::kWaitForResult;
   }
 }
 }  // namespace webrtc