Probing: Add support for exponential startup probing

webrtc/modules/pacing/bitrate_prober.cc

 /*
  *  Copyright (c) 2014 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/pacing/bitrate_prober.h"
 
 #include <algorithm>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/base/logging.h"
 #include "webrtc/modules/pacing/paced_sender.h"
 
 namespace webrtc {
 
 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
   // bps. Result is in milliseconds.
   return static_cast<int>((1000ll * packet_size * 8) / 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;
   cluster.id = next_cluster_id_++;
   clusters_.push(cluster);
   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() {
   time_last_probe_sent_ms_ = -1;
   packet_size_last_sent_ = 0;
 
   // Recreate all probing clusters.
   std::queue<ProbeCluster> clusters;
   clusters.swap(clusters_);
   while (!clusters.empty()) {
     CreateProbeCluster(clusters.front().probe_bitrate_bps,
                        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;
   if (time_last_probe_sent_ms_ == -1) {
     elapsed_time_ms = 0;
   } else {
     elapsed_time_ms = now_ms - time_last_probe_sent_ms_;
   }
   // If no probes have been sent for a while, abort current probing and
   // reset.
   if (elapsed_time_ms > kInactivityThresholdMs) {
     ResetState();
     return -1;
   }
   // 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;
     // There is no point in trying to probe with less than 1 ms between packets
     // as it essentially means trying to probe at infinite bandwidth.
     const int kMinProbeDeltaMs = 1;
     // If we have waited more than 3 ms for a new packet to probe with we will
     // consider this probing session over.
     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;
     }
   }
   return std::max(time_until_probe_ms, 0);
 }
 
 int BitrateProber::CurrentClusterId() const {
   RTC_DCHECK(!clusters_.empty());
-  RTC_DCHECK(ProbingState::kActive == probing_state_);
+  RTC_DCHECK(probing_state_ == State::kSending);
   return clusters_.front().id;
 }
 
 size_t BitrateProber::RecommendedPacketSize() const {
   return packet_size_last_sent_;
 }
 
 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();
     ++cluster->sent_probe_packets;
     if (cluster->sent_probe_packets == cluster->max_probe_packets)
       clusters_.pop();
     if (clusters_.empty())
-      probing_state_ = ProbingState::kSuspended;
+      probing_state_ = State::kWaitForResult;
   }
 }
 }  // namespace webrtc