Changing the bitrate clamping in BitrateControllerImpl

This CL implements an alternative to the bitrate clamping that is done
in BitrateControllerImpl. The default behavior is unchanged, but if
the new algorithm is enabled the behavior is as follows:
When the new bitrate is lower than the sum of min bitrates, the
algorithm will give each observer up to its min bitrate, one
observer at a time, until the bitrate budget is depleted. Thus,
with this change, some observers may get less than their min bitrate,
or even zero.

Unit tests are implemented.

Also fixing two old lint warnings in the affected files.

This change is related to the auto-muter feature.

BUG=2436
R=stefan@webrtc.org

Review URL: https://webrtc-codereview.appspot.com/2439005

git-svn-id: http://webrtc.googlecode.com/svn/trunk/webrtc@5007 4adac7df-926f-26a2-2b94-8c16560cd09d

4 files changed, 155 insertions, 20 deletions

diff --git a/modules/bitrate_controller/bitrate_controller_impl.cc b/modules/bitrate_controller/bitrate_controller_impl.cc
index 20cc3ace..11c36c09 100644
--- a/modules/bitrate_controller/bitrate_controller_impl.cc
+++ b/modules/bitrate_controller/bitrate_controller_impl.cc
@@ -11,6 +11,7 @@
 
 #include "webrtc/modules/bitrate_controller/bitrate_controller_impl.h"
 
+#include <algorithm>
 #include <utility>
 
 #include "webrtc/modules/rtp_rtcp/interface/rtp_rtcp_defines.h"
@@ -69,13 +70,58 @@ class RtcpBandwidthObserverImpl : public RtcpBandwidthObserver {
     owner_->OnReceivedRtcpReceiverReport(fraction_lost_aggregate, rtt,
                                          total_number_of_packets, now_ms);
   }
+
  private:
   std::map<uint32_t, uint32_t> ssrc_to_last_received_extended_high_seq_num_;
   BitrateControllerImpl* owner_;
 };
 
-BitrateController* BitrateController::CreateBitrateController() {
-  return new BitrateControllerImpl();
+class BitrateControllerEnforceMinRate : public BitrateControllerImpl {
+ private:
+  void LowRateAllocation(uint32_t bitrate,
+                         uint8_t fraction_loss,
+                         uint32_t rtt,
+                         uint32_t sum_min_bitrates) {
+    // Min bitrate to all observers.
+    BitrateObserverConfList::iterator it;
+    for (it = bitrate_observers_.begin(); it != bitrate_observers_.end();
+        ++it) {
+      it->first->OnNetworkChanged(it->second->min_bitrate_, fraction_loss,
+                                  rtt);
+    }
+    // Set sum of min to current send bitrate.
+    bandwidth_estimation_.SetSendBitrate(sum_min_bitrates);
+  }
+};
+
+class BitrateControllerNoEnforceMinRate : public BitrateControllerImpl {
+ private:
+  void LowRateAllocation(uint32_t bitrate,
+                         uint8_t fraction_loss,
+                         uint32_t rtt,
+                         uint32_t sum_min_bitrates) {
+    // Allocate up to |min_bitrate_| to one observer at a time, until
+    // |bitrate| is depleted.
+    uint32_t remainder = bitrate;
+    BitrateObserverConfList::iterator it;
+    for (it = bitrate_observers_.begin(); it != bitrate_observers_.end();
+        ++it) {
+      uint32_t allocation = std::min(remainder, it->second->min_bitrate_);
+      it->first->OnNetworkChanged(allocation, fraction_loss, rtt);
+      remainder -= allocation;
+    }
+    // Set |bitrate| to current send bitrate.
+    bandwidth_estimation_.SetSendBitrate(bitrate);
+  }
+};
+
+BitrateController* BitrateController::CreateBitrateController(
+    bool enforce_min_bitrate) {
+  if (enforce_min_bitrate) {
+    return new BitrateControllerEnforceMinRate();
+  } else {
+    return new BitrateControllerNoEnforceMinRate();
+  }
 }
 
 BitrateControllerImpl::BitrateControllerImpl()
@@ -201,15 +247,7 @@ void BitrateControllerImpl::OnNetworkChanged(const uint32_t bitrate,
     sum_min_bitrates += it->second->min_bitrate_;
   }
   if (bitrate <= sum_min_bitrates) {
-    // Min bitrate to all observers.
-    for (it = bitrate_observers_.begin(); it != bitrate_observers_.end();
-        ++it) {
-      it->first->OnNetworkChanged(it->second->min_bitrate_, fraction_loss,
-                                  rtt);
-    }
-    // Set sum of min to current send bitrate.
-    bandwidth_estimation_.SetSendBitrate(sum_min_bitrates);
-    return;
+    return LowRateAllocation(bitrate, fraction_loss, rtt, sum_min_bitrates);
   }
   uint32_t bitrate_per_observer = (bitrate - sum_min_bitrates) /
       number_of_observers;
@@ -248,4 +286,5 @@ void BitrateControllerImpl::OnNetworkChanged(const uint32_t bitrate,
 bool BitrateControllerImpl::AvailableBandwidth(uint32_t* bandwidth) const {
   return bandwidth_estimation_.AvailableBandwidth(bandwidth);
 }
+
 }  // namespace webrtc
diff --git a/modules/bitrate_controller/bitrate_controller_impl.h b/modules/bitrate_controller/bitrate_controller_impl.h
index 4c891d9d..5e56607c 100644
--- a/modules/bitrate_controller/bitrate_controller_impl.h
+++ b/modules/bitrate_controller/bitrate_controller_impl.h
@@ -19,6 +19,7 @@
 
 #include <list>
 #include <map>
+#include <utility>
 
 #include "webrtc/modules/bitrate_controller/send_side_bandwidth_estimation.h"
 #include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
@@ -67,6 +68,9 @@ class BitrateControllerImpl : public BitrateController {
     BitrateObserver* observer_;
     uint32_t min_bitrate_;
   };
+  typedef std::pair<BitrateObserver*, BitrateConfiguration*>
+      BitrateObserverConfiguration;
+  typedef std::list<BitrateObserverConfiguration> BitrateObserverConfList;
 
   // Called by BitrateObserver's direct from the RTCP module.
   void OnReceivedEstimatedBitrate(const uint32_t bitrate);
@@ -76,21 +80,24 @@ class BitrateControllerImpl : public BitrateController {
                                     const int number_of_packets,
                                     const uint32_t now_ms);
 
+  SendSideBandwidthEstimation bandwidth_estimation_;
+  BitrateObserverConfList bitrate_observers_;
+
  private:
   typedef std::multimap<uint32_t, ObserverConfiguration*> ObserverSortingMap;
-  typedef std::pair<BitrateObserver*, BitrateConfiguration*>
-      BitrateObserverConfiguration;
-  typedef std::list<BitrateObserverConfiguration> BitrateObserverConfList;
 
   BitrateObserverConfList::iterator
       FindObserverConfigurationPair(const BitrateObserver* observer);
   void OnNetworkChanged(const uint32_t bitrate,
                         const uint8_t fraction_loss,  // 0 - 255.
                         const uint32_t rtt);
+  // Derived classes must implement this strategy method.
+  virtual void LowRateAllocation(uint32_t bitrate,
+                                 uint8_t fraction_loss,
+                                 uint32_t rtt,
+                                 uint32_t sum_min_bitrates) = 0;
 
   CriticalSectionWrapper* critsect_;
-  SendSideBandwidthEstimation bandwidth_estimation_;
-  BitrateObserverConfList bitrate_observers_;
 };
 }  // namespace webrtc
 #endif  // WEBRTC_MODULES_BITRATE_CONTROLLER_BITRATE_CONTROLLER_IMPL_H_
diff --git a/modules/bitrate_controller/bitrate_controller_unittest.cc b/modules/bitrate_controller/bitrate_controller_unittest.cc
index 7abe71b5..30f85a81 100644
--- a/modules/bitrate_controller/bitrate_controller_unittest.cc
+++ b/modules/bitrate_controller/bitrate_controller_unittest.cc
@@ -57,12 +57,12 @@ class TestBitrateObserver: public BitrateObserver {
 
 class BitrateControllerTest : public ::testing::Test {
  protected:
-  BitrateControllerTest() {
-  }
+  BitrateControllerTest() : enforce_min_bitrate_(true) {}
   ~BitrateControllerTest() {}
 
   virtual void SetUp() {
-    controller_ = BitrateController::CreateBitrateController();
+    controller_ =
+        BitrateController::CreateBitrateController(enforce_min_bitrate_);
     bandwidth_observer_ = controller_->CreateRtcpBandwidthObserver();
   }
 
@@ -70,6 +70,7 @@ class BitrateControllerTest : public ::testing::Test {
     delete bandwidth_observer_;
     delete controller_;
   }
+  bool enforce_min_bitrate_;
   BitrateController* controller_;
   RtcpBandwidthObserver* bandwidth_observer_;
 };
@@ -414,3 +415,86 @@ TEST_F(BitrateControllerTest, TwoBitrateObserversOneRtcpObserver) {
   controller_->RemoveBitrateObserver(&bitrate_observer_1);
   controller_->RemoveBitrateObserver(&bitrate_observer_2);
 }
+
+class BitrateControllerTestNoEnforceMin : public BitrateControllerTest {
+ protected:
+  BitrateControllerTestNoEnforceMin() : BitrateControllerTest() {
+    enforce_min_bitrate_ = false;
+  }
+};
+
+// The following three tests verify that the EnforceMinBitrate() method works
+// as intended.
+TEST_F(BitrateControllerTestNoEnforceMin, OneBitrateObserver) {
+  TestBitrateObserver bitrate_observer_1;
+  controller_->SetBitrateObserver(&bitrate_observer_1, 200000, 100000, 400000);
+
+  // High REMB.
+  bandwidth_observer_->OnReceivedEstimatedBitrate(150000);
+  EXPECT_EQ(150000u, bitrate_observer_1.last_bitrate_);
+
+  // Low REMB.
+  bandwidth_observer_->OnReceivedEstimatedBitrate(1000);
+  EXPECT_EQ(1000u, bitrate_observer_1.last_bitrate_);
+
+  controller_->RemoveBitrateObserver(&bitrate_observer_1);
+}
+
+TEST_F(BitrateControllerTestNoEnforceMin, ThreeBitrateObservers) {
+  TestBitrateObserver bitrate_observer_1;
+  TestBitrateObserver bitrate_observer_2;
+  TestBitrateObserver bitrate_observer_3;
+  // Set up the observers with min bitrates at 100000, 200000, and 300000.
+  // Note: The start bitrate of bitrate_observer_1 (700000) is used as the
+  // overall start bitrate.
+  controller_->SetBitrateObserver(&bitrate_observer_1, 700000, 100000, 400000);
+  controller_->SetBitrateObserver(&bitrate_observer_2, 200000, 200000, 400000);
+  controller_->SetBitrateObserver(&bitrate_observer_3, 200000, 300000, 400000);
+
+  // High REMB. Make sure the controllers get a fair share of the surplus
+  // (i.e., what is left after each controller gets its min rate).
+  bandwidth_observer_->OnReceivedEstimatedBitrate(690000);
+  // Verify that each observer gets its min rate (sum of min rates is 600000),
+  // and that the remaining 90000 is divided equally among the three.
+  EXPECT_EQ(130000u, bitrate_observer_1.last_bitrate_);
+  EXPECT_EQ(230000u, bitrate_observer_2.last_bitrate_);
+  EXPECT_EQ(330000u, bitrate_observer_3.last_bitrate_);
+
+  // High REMB, but below the sum of min bitrates.
+  bandwidth_observer_->OnReceivedEstimatedBitrate(500000);
+  // Verify that the first and second observers get their min bitrates, and the
+  // third gets the remainder.
+  EXPECT_EQ(100000u, bitrate_observer_1.last_bitrate_);  // Min bitrate.
+  EXPECT_EQ(200000u, bitrate_observer_2.last_bitrate_);  // Min bitrate.
+  EXPECT_EQ(200000u, bitrate_observer_3.last_bitrate_);  // Remainder.
+
+  // Low REMB.
+  bandwidth_observer_->OnReceivedEstimatedBitrate(1000);
+  // Verify that the first observer gets all the rate, and the rest get zero.
+  EXPECT_EQ(1000u, bitrate_observer_1.last_bitrate_);
+  EXPECT_EQ(0u, bitrate_observer_2.last_bitrate_);
+  EXPECT_EQ(0u, bitrate_observer_3.last_bitrate_);
+
+  controller_->RemoveBitrateObserver(&bitrate_observer_1);
+  controller_->RemoveBitrateObserver(&bitrate_observer_2);
+  controller_->RemoveBitrateObserver(&bitrate_observer_3);
+}
+
+TEST_F(BitrateControllerTest, ThreeBitrateObserversLowRembEnforceMin) {
+  TestBitrateObserver bitrate_observer_1;
+  TestBitrateObserver bitrate_observer_2;
+  TestBitrateObserver bitrate_observer_3;
+  controller_->SetBitrateObserver(&bitrate_observer_1, 200000, 100000, 300000);
+  controller_->SetBitrateObserver(&bitrate_observer_2, 200000, 200000, 300000);
+  controller_->SetBitrateObserver(&bitrate_observer_3, 200000, 300000, 300000);
+
+  // Low REMB. Verify that all observers still get their respective min bitrate.
+  bandwidth_observer_->OnReceivedEstimatedBitrate(1000);
+  EXPECT_EQ(100000u, bitrate_observer_1.last_bitrate_);  // Min cap.
+  EXPECT_EQ(200000u, bitrate_observer_2.last_bitrate_);  // Min cap.
+  EXPECT_EQ(300000u, bitrate_observer_3.last_bitrate_);  // Min cap.
+
+  controller_->RemoveBitrateObserver(&bitrate_observer_1);
+  controller_->RemoveBitrateObserver(&bitrate_observer_2);
+  controller_->RemoveBitrateObserver(&bitrate_observer_3);
+}
diff --git a/modules/bitrate_controller/include/bitrate_controller.h b/modules/bitrate_controller/include/bitrate_controller.h
index d74be169..ec03a141 100644
--- a/modules/bitrate_controller/include/bitrate_controller.h
+++ b/modules/bitrate_controller/include/bitrate_controller.h
@@ -43,7 +43,12 @@ class BitrateController {
  * BitrateObservers.
  */
  public:
-  static BitrateController* CreateBitrateController();
+  // The argument |enforce_min_bitrate| controls the behavior when the available
+  // bitrate is lower than the minimum bitrate, or the sum of minimum bitrates.
+  // When true, the bitrate will never be set lower than the minimum bitrate(s).
+  // When false, the bitrate observers will be allocated rates up to their
+  // respective minimum bitrate, satisfying one observer after the other.
+  static BitrateController* CreateBitrateController(bool enforce_min_bitrate);
   virtual ~BitrateController() {}
 
   virtual RtcpBandwidthObserver* CreateRtcpBandwidthObserver() = 0;