Reland "Moved congestion controller to goog_cc folder."
This is a reland of e6cefdf9c572cdce55ff0497ad6e516c76132ee8.
Original change's description:
> Moved congestion controller to goog_cc folder.
>
> Bug: webrtc:8415
> Change-Id: I2070da0cacf1dbfc4b6a89285af3e68fd03497ab
> Reviewed-on: https://webrtc-review.googlesource.com/43841
> Commit-Queue: Sebastian Jansson <srte@webrtc.org>
> Reviewed-by: Björn Terelius <terelius@webrtc.org>
> Reviewed-by: Stefan Holmer <stefan@webrtc.org>
> Cr-Commit-Position: refs/heads/master@{#21928}
Bug: webrtc:8415
Change-Id: Ib5cf8641466655d64ac80f720561817f4cab49a9
Reviewed-on: https://webrtc-review.googlesource.com/53062
Commit-Queue: Sebastian Jansson <srte@webrtc.org>
Reviewed-by: Björn Terelius <terelius@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#22244}diff --git a/modules/congestion_controller/goog_cc/BUILD.gn b/modules/congestion_controller/goog_cc/BUILD.gn
new file mode 100644
index 0000000..bc17af1
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/BUILD.gn
@@ -0,0 +1,164 @@
+# Copyright (c) 2018 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.
+
+import("../../../webrtc.gni")
+
+config("bwe_test_logging") {
+ if (rtc_enable_bwe_test_logging) {
+ defines = [ "BWE_TEST_LOGGING_COMPILE_TIME_ENABLE=1" ]
+ } else {
+ defines = [ "BWE_TEST_LOGGING_COMPILE_TIME_ENABLE=0" ]
+ }
+}
+
+rtc_static_library("goog_cc") {
+ configs += [ ":bwe_test_logging" ]
+ sources = [
+ "alr_detector.cc",
+ "alr_detector.h",
+ "goog_cc_factory.cc",
+ "goog_cc_network_control.cc",
+ "goog_cc_network_control.h",
+ "include/goog_cc_factory.h",
+ "probe_controller.cc",
+ "probe_controller.h",
+ ]
+
+ # TODO(jschuh): Bug 1348: fix this warning.
+ configs += [ "//build/config/compiler:no_size_t_to_int_warning" ]
+
+ if (!build_with_chromium && is_clang) {
+ # Suppress warnings from the Chromium Clang plugin (bugs.webrtc.org/163).
+ suppressed_configs += [ "//build/config/clang:find_bad_constructs" ]
+ }
+
+ deps = [
+ ":delay_based_bwe",
+ ":estimators",
+ "../..:module_api",
+ "../../..:webrtc_common",
+ "../../../:typedefs",
+ "../../../api:optional",
+ "../../../logging:rtc_event_log_api",
+ "../../../logging:rtc_event_pacing",
+ "../../../rtc_base:checks",
+ "../../../rtc_base:rtc_base_approved",
+ "../../../rtc_base/experiments:alr_experiment",
+ "../../../system_wrappers",
+ "../../../system_wrappers:field_trial_api",
+ "../../../system_wrappers:metrics_api",
+ "../../bitrate_controller",
+ "../../pacing",
+ "../../remote_bitrate_estimator",
+ "../../rtp_rtcp:rtp_rtcp_format",
+ "../network_control",
+ ]
+}
+
+rtc_source_set("estimators") {
+ configs += [ ":bwe_test_logging" ]
+ sources = [
+ "acknowledged_bitrate_estimator.cc",
+ "acknowledged_bitrate_estimator.h",
+ "bitrate_estimator.cc",
+ "bitrate_estimator.h",
+ "delay_increase_detector_interface.h",
+ "median_slope_estimator.cc",
+ "median_slope_estimator.h",
+ "probe_bitrate_estimator.cc",
+ "probe_bitrate_estimator.h",
+ "trendline_estimator.cc",
+ "trendline_estimator.h",
+ ]
+
+ # TODO(jschuh): Bug 1348: fix this warning.
+ configs += [ "//build/config/compiler:no_size_t_to_int_warning" ]
+
+ if (!build_with_chromium && is_clang) {
+ # Suppress warnings from the Chromium Clang plugin (bugs.webrtc.org/163).
+ suppressed_configs += [ "//build/config/clang:find_bad_constructs" ]
+ }
+
+ deps = [
+ "../../../api:optional",
+ "../../../logging:rtc_event_bwe",
+ "../../../logging:rtc_event_log_api",
+ "../../../rtc_base:checks",
+ "../../../rtc_base:rtc_base_approved",
+ "../../../rtc_base:rtc_numerics",
+ "../../../system_wrappers:field_trial_api",
+ "../../../system_wrappers:metrics_api",
+ "../../remote_bitrate_estimator",
+ "../../rtp_rtcp:rtp_rtcp_format",
+ ]
+}
+
+rtc_source_set("delay_based_bwe") {
+ configs += [ ":bwe_test_logging" ]
+ sources = [
+ "delay_based_bwe.cc",
+ "delay_based_bwe.h",
+ ]
+
+ deps = [
+ ":estimators",
+ "../../../:typedefs",
+ "../../../logging:rtc_event_bwe",
+ "../../../logging:rtc_event_log_api",
+ "../../../rtc_base:checks",
+ "../../../rtc_base:rtc_base_approved",
+ "../../../system_wrappers:field_trial_api",
+ "../../../system_wrappers:metrics_api",
+ "../../pacing",
+ "../../remote_bitrate_estimator",
+ ]
+
+ if (!build_with_chromium && is_clang) {
+ # Suppress warnings from the Chromium Clang plugin (bugs.webrtc.org/163).
+ suppressed_configs += [ "//build/config/clang:find_bad_constructs" ]
+ }
+}
+
+if (rtc_include_tests) {
+ rtc_source_set("goog_cc_unittests") {
+ testonly = true
+
+ sources = [
+ "acknowledged_bitrate_estimator_unittest.cc",
+ "alr_detector_unittest.cc",
+ "delay_based_bwe_unittest.cc",
+ "delay_based_bwe_unittest_helper.cc",
+ "delay_based_bwe_unittest_helper.h",
+ "median_slope_estimator_unittest.cc",
+ "probe_bitrate_estimator_unittest.cc",
+ "probe_controller_unittest.cc",
+ "trendline_estimator_unittest.cc",
+ ]
+ deps = [
+ ":delay_based_bwe",
+ ":estimators",
+ ":goog_cc",
+ "../../../rtc_base:checks",
+ "../../../rtc_base:rtc_base_approved",
+ "../../../rtc_base:rtc_base_tests_utils",
+ "../../../rtc_base/experiments:alr_experiment",
+ "../../../system_wrappers",
+ "../../../test:field_trial",
+ "../../../test:test_support",
+ "../../pacing",
+ "../../remote_bitrate_estimator",
+ "../../rtp_rtcp:rtp_rtcp_format",
+ "../network_control",
+ "//testing/gmock",
+ ]
+ if (!build_with_chromium && is_clang) {
+ # Suppress warnings from the Chromium Clang plugin (bugs.webrtc.org/163).
+ suppressed_configs += [ "//build/config/clang:find_bad_constructs" ]
+ }
+ }
+}
diff --git a/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.cc b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.cc
new file mode 100644
index 0000000..7e1855d
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.cc
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2017 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 "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h"
+
+#include <utility>
+
+#include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
+#include "rtc_base/numerics/safe_conversions.h"
+#include "rtc_base/ptr_util.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+bool IsInSendTimeHistory(const PacketFeedback& packet) {
+ return packet.send_time_ms != PacketFeedback::kNoSendTime;
+}
+} // namespace
+
+AcknowledgedBitrateEstimator::AcknowledgedBitrateEstimator()
+ : AcknowledgedBitrateEstimator(rtc::MakeUnique<BitrateEstimator>()) {}
+
+AcknowledgedBitrateEstimator::~AcknowledgedBitrateEstimator() {}
+
+AcknowledgedBitrateEstimator::AcknowledgedBitrateEstimator(
+ std::unique_ptr<BitrateEstimator> bitrate_estimator)
+ : bitrate_estimator_(std::move(bitrate_estimator)) {}
+
+void AcknowledgedBitrateEstimator::IncomingPacketFeedbackVector(
+ const std::vector<PacketFeedback>& packet_feedback_vector) {
+ RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(),
+ packet_feedback_vector.end(),
+ PacketFeedbackComparator()));
+ for (const auto& packet : packet_feedback_vector) {
+ if (IsInSendTimeHistory(packet)) {
+ MaybeExpectFastRateChange(packet.send_time_ms);
+ bitrate_estimator_->Update(packet.arrival_time_ms,
+ rtc::dchecked_cast<int>(packet.payload_size));
+ }
+ }
+}
+
+rtc::Optional<uint32_t> AcknowledgedBitrateEstimator::bitrate_bps() const {
+ return bitrate_estimator_->bitrate_bps();
+}
+
+void AcknowledgedBitrateEstimator::SetAlrEndedTimeMs(
+ int64_t alr_ended_time_ms) {
+ alr_ended_time_ms_.emplace(alr_ended_time_ms);
+}
+
+void AcknowledgedBitrateEstimator::MaybeExpectFastRateChange(
+ int64_t packet_send_time_ms) {
+ if (alr_ended_time_ms_ && packet_send_time_ms > *alr_ended_time_ms_) {
+ bitrate_estimator_->ExpectFastRateChange();
+ alr_ended_time_ms_.reset();
+ }
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h
new file mode 100644
index 0000000..f584792
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_ACKNOWLEDGED_BITRATE_ESTIMATOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_ACKNOWLEDGED_BITRATE_ESTIMATOR_H_
+
+#include <memory>
+#include <vector>
+
+#include "api/optional.h"
+#include "modules/congestion_controller/goog_cc/bitrate_estimator.h"
+
+namespace webrtc {
+
+struct PacketFeedback;
+
+namespace webrtc_cc {
+
+class AcknowledgedBitrateEstimator {
+ public:
+ explicit AcknowledgedBitrateEstimator(
+ std::unique_ptr<BitrateEstimator> bitrate_estimator);
+
+ AcknowledgedBitrateEstimator();
+ ~AcknowledgedBitrateEstimator();
+
+ void IncomingPacketFeedbackVector(
+ const std::vector<PacketFeedback>& packet_feedback_vector);
+ rtc::Optional<uint32_t> bitrate_bps() const;
+ void SetAlrEndedTimeMs(int64_t alr_ended_time_ms);
+
+ private:
+ void MaybeExpectFastRateChange(int64_t packet_arrival_time_ms);
+ rtc::Optional<int64_t> alr_ended_time_ms_;
+ std::unique_ptr<BitrateEstimator> bitrate_estimator_;
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_ACKNOWLEDGED_BITRATE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator_unittest.cc b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator_unittest.cc
new file mode 100644
index 0000000..f8f5025
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator_unittest.cc
@@ -0,0 +1,136 @@
+/*
+ * Copyright (c) 2017 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 "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h"
+
+#include <utility>
+
+#include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
+#include "rtc_base/fakeclock.h"
+#include "rtc_base/ptr_util.h"
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+using testing::_;
+using testing::NiceMock;
+using testing::InSequence;
+using testing::Return;
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+
+constexpr int64_t kFirstArrivalTimeMs = 10;
+constexpr int64_t kFirstSendTimeMs = 10;
+constexpr uint16_t kSequenceNumber = 1;
+constexpr size_t kPayloadSize = 10;
+
+class MockBitrateEstimator : public BitrateEstimator {
+ public:
+ MOCK_METHOD2(Update, void(int64_t now_ms, int bytes));
+ MOCK_CONST_METHOD0(bitrate_bps, rtc::Optional<uint32_t>());
+ MOCK_METHOD0(ExpectFastRateChange, void());
+};
+
+struct AcknowledgedBitrateEstimatorTestStates {
+ std::unique_ptr<AcknowledgedBitrateEstimator> acknowledged_bitrate_estimator;
+ MockBitrateEstimator* mock_bitrate_estimator;
+};
+
+AcknowledgedBitrateEstimatorTestStates CreateTestStates() {
+ AcknowledgedBitrateEstimatorTestStates states;
+ auto mock_bitrate_estimator = rtc::MakeUnique<MockBitrateEstimator>();
+ states.mock_bitrate_estimator = mock_bitrate_estimator.get();
+ states.acknowledged_bitrate_estimator =
+ rtc::MakeUnique<AcknowledgedBitrateEstimator>(
+ std::move(mock_bitrate_estimator));
+ return states;
+}
+
+std::vector<PacketFeedback> CreateFeedbackVector() {
+ std::vector<PacketFeedback> packet_feedback_vector;
+ const PacedPacketInfo pacing_info;
+ packet_feedback_vector.push_back(
+ PacketFeedback(kFirstArrivalTimeMs, kFirstSendTimeMs, kSequenceNumber,
+ kPayloadSize, pacing_info));
+ packet_feedback_vector.push_back(
+ PacketFeedback(kFirstArrivalTimeMs + 10, kFirstSendTimeMs + 10,
+ kSequenceNumber, kPayloadSize + 10, pacing_info));
+ return packet_feedback_vector;
+}
+
+} // anonymous namespace
+
+TEST(TestAcknowledgedBitrateEstimator, DontAddPacketsWhichAreNotInSendHistory) {
+ auto states = CreateTestStates();
+ std::vector<PacketFeedback> packet_feedback_vector;
+ packet_feedback_vector.push_back(
+ PacketFeedback(kFirstArrivalTimeMs, kSequenceNumber));
+ EXPECT_CALL(*states.mock_bitrate_estimator, Update(_, _)).Times(0);
+ states.acknowledged_bitrate_estimator->IncomingPacketFeedbackVector(
+ packet_feedback_vector);
+}
+
+TEST(TestAcknowledgedBitrateEstimator, UpdateBandwith) {
+ auto states = CreateTestStates();
+ auto packet_feedback_vector = CreateFeedbackVector();
+ {
+ InSequence dummy;
+ EXPECT_CALL(
+ *states.mock_bitrate_estimator,
+ Update(packet_feedback_vector[0].arrival_time_ms,
+ static_cast<int>(packet_feedback_vector[0].payload_size)))
+ .Times(1);
+ EXPECT_CALL(
+ *states.mock_bitrate_estimator,
+ Update(packet_feedback_vector[1].arrival_time_ms,
+ static_cast<int>(packet_feedback_vector[1].payload_size)))
+ .Times(1);
+ }
+ states.acknowledged_bitrate_estimator->IncomingPacketFeedbackVector(
+ packet_feedback_vector);
+}
+
+TEST(TestAcknowledgedBitrateEstimator, ExpectFastRateChangeWhenLeftAlr) {
+ auto states = CreateTestStates();
+ auto packet_feedback_vector = CreateFeedbackVector();
+ {
+ InSequence dummy;
+ EXPECT_CALL(
+ *states.mock_bitrate_estimator,
+ Update(packet_feedback_vector[0].arrival_time_ms,
+ static_cast<int>(packet_feedback_vector[0].payload_size)))
+ .Times(1);
+ EXPECT_CALL(*states.mock_bitrate_estimator, ExpectFastRateChange())
+ .Times(1);
+ EXPECT_CALL(
+ *states.mock_bitrate_estimator,
+ Update(packet_feedback_vector[1].arrival_time_ms,
+ static_cast<int>(packet_feedback_vector[1].payload_size)))
+ .Times(1);
+ }
+ states.acknowledged_bitrate_estimator->SetAlrEndedTimeMs(kFirstArrivalTimeMs +
+ 1);
+ states.acknowledged_bitrate_estimator->IncomingPacketFeedbackVector(
+ packet_feedback_vector);
+}
+
+TEST(TestAcknowledgedBitrateEstimator, ReturnBitrate) {
+ auto states = CreateTestStates();
+ rtc::Optional<uint32_t> return_value(42);
+ EXPECT_CALL(*states.mock_bitrate_estimator, bitrate_bps())
+ .Times(1)
+ .WillOnce(Return(return_value));
+ EXPECT_EQ(return_value, states.acknowledged_bitrate_estimator->bitrate_bps());
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc*/
diff --git a/modules/congestion_controller/goog_cc/alr_detector.cc b/modules/congestion_controller/goog_cc/alr_detector.cc
new file mode 100644
index 0000000..f36b1f9
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/alr_detector.cc
@@ -0,0 +1,97 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/alr_detector.h"
+
+#include <algorithm>
+#include <cstdio>
+#include <string>
+
+#include "logging/rtc_event_log/events/rtc_event_alr_state.h"
+#include "logging/rtc_event_log/rtc_event_log.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/experiments/alr_experiment.h"
+#include "rtc_base/format_macros.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/ptr_util.h"
+#include "rtc_base/timeutils.h"
+#include "system_wrappers/include/field_trial.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+AlrDetector::AlrDetector() : AlrDetector(nullptr) {}
+
+AlrDetector::AlrDetector(RtcEventLog* event_log)
+ : bandwidth_usage_percent_(kDefaultAlrBandwidthUsagePercent),
+ alr_start_budget_level_percent_(kDefaultAlrStartBudgetLevelPercent),
+ alr_stop_budget_level_percent_(kDefaultAlrStopBudgetLevelPercent),
+ alr_budget_(0, true),
+ event_log_(event_log) {
+ RTC_CHECK(AlrExperimentSettings::MaxOneFieldTrialEnabled());
+ rtc::Optional<AlrExperimentSettings> experiment_settings =
+ AlrExperimentSettings::CreateFromFieldTrial(
+ AlrExperimentSettings::kScreenshareProbingBweExperimentName);
+ if (!experiment_settings) {
+ experiment_settings = AlrExperimentSettings::CreateFromFieldTrial(
+ AlrExperimentSettings::kStrictPacingAndProbingExperimentName);
+ }
+ if (experiment_settings) {
+ alr_stop_budget_level_percent_ =
+ experiment_settings->alr_stop_budget_level_percent;
+ alr_start_budget_level_percent_ =
+ experiment_settings->alr_start_budget_level_percent;
+ bandwidth_usage_percent_ = experiment_settings->alr_bandwidth_usage_percent;
+ }
+}
+
+AlrDetector::~AlrDetector() {}
+
+void AlrDetector::OnBytesSent(size_t bytes_sent, int64_t send_time_ms) {
+ if (!last_send_time_ms_.has_value()) {
+ last_send_time_ms_ = send_time_ms;
+ // Since the duration for sending the bytes is unknwon, return without
+ // updating alr state.
+ return;
+ }
+ int64_t delta_time_ms = send_time_ms - *last_send_time_ms_;
+ last_send_time_ms_ = send_time_ms;
+
+ alr_budget_.UseBudget(bytes_sent);
+ alr_budget_.IncreaseBudget(delta_time_ms);
+ bool state_changed = false;
+ if (alr_budget_.budget_level_percent() > alr_start_budget_level_percent_ &&
+ !alr_started_time_ms_) {
+ alr_started_time_ms_.emplace(rtc::TimeMillis());
+ state_changed = true;
+ } else if (alr_budget_.budget_level_percent() <
+ alr_stop_budget_level_percent_ &&
+ alr_started_time_ms_) {
+ state_changed = true;
+ alr_started_time_ms_.reset();
+ }
+ if (event_log_ && state_changed) {
+ event_log_->Log(
+ rtc::MakeUnique<RtcEventAlrState>(alr_started_time_ms_.has_value()));
+ }
+}
+
+void AlrDetector::SetEstimatedBitrate(int bitrate_bps) {
+ RTC_DCHECK(bitrate_bps);
+ const auto target_rate_kbps = static_cast<int64_t>(bitrate_bps) *
+ bandwidth_usage_percent_ / (1000 * 100);
+ alr_budget_.set_target_rate_kbps(rtc::dchecked_cast<int>(target_rate_kbps));
+}
+
+rtc::Optional<int64_t> AlrDetector::GetApplicationLimitedRegionStartTime()
+ const {
+ return alr_started_time_ms_;
+}
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/alr_detector.h b/modules/congestion_controller/goog_cc/alr_detector.h
new file mode 100644
index 0000000..98293a7
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/alr_detector.h
@@ -0,0 +1,77 @@
+/*
+ * 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_ALR_DETECTOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_ALR_DETECTOR_H_
+
+#include "api/optional.h"
+#include "common_types.h" // NOLINT(build/include)
+#include "modules/pacing/interval_budget.h"
+#include "modules/pacing/paced_sender.h"
+#include "rtc_base/rate_statistics.h"
+#include "typedefs.h" // NOLINT(build/include)
+
+namespace webrtc {
+
+class RtcEventLog;
+
+namespace webrtc_cc {
+
+// Application limited region detector is a class that utilizes signals of
+// elapsed time and bytes sent to estimate whether network traffic is
+// currently limited by the application's ability to generate traffic.
+//
+// AlrDetector provides a signal that can be utilized to adjust
+// estimate bandwidth.
+// Note: This class is not thread-safe.
+class AlrDetector {
+ public:
+ AlrDetector();
+ explicit AlrDetector(RtcEventLog* event_log);
+ ~AlrDetector();
+
+ void OnBytesSent(size_t bytes_sent, int64_t send_time_ms);
+
+ // Set current estimated bandwidth.
+ void SetEstimatedBitrate(int bitrate_bps);
+
+ // Returns time in milliseconds when the current application-limited region
+ // started or empty result if the sender is currently not application-limited.
+ rtc::Optional<int64_t> GetApplicationLimitedRegionStartTime() const;
+
+ // Sent traffic percentage as a function of network capacity used to determine
+ // application-limited region. ALR region start when bandwidth usage drops
+ // below kAlrStartUsagePercent and ends when it raises above
+ // kAlrEndUsagePercent. NOTE: This is intentionally conservative at the moment
+ // until BW adjustments of application limited region is fine tuned.
+ static constexpr int kDefaultAlrBandwidthUsagePercent = 65;
+ static constexpr int kDefaultAlrStartBudgetLevelPercent = 80;
+ static constexpr int kDefaultAlrStopBudgetLevelPercent = 50;
+
+ void UpdateBudgetWithElapsedTime(int64_t delta_time_ms);
+ void UpdateBudgetWithBytesSent(size_t bytes_sent);
+
+ private:
+ int bandwidth_usage_percent_;
+ int alr_start_budget_level_percent_;
+ int alr_stop_budget_level_percent_;
+
+ rtc::Optional<int64_t> last_send_time_ms_;
+
+ IntervalBudget alr_budget_;
+ rtc::Optional<int64_t> alr_started_time_ms_;
+
+ RtcEventLog* event_log_;
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_ALR_DETECTOR_H_
diff --git a/modules/congestion_controller/goog_cc/alr_detector_unittest.cc b/modules/congestion_controller/goog_cc/alr_detector_unittest.cc
new file mode 100644
index 0000000..9aeab51
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/alr_detector_unittest.cc
@@ -0,0 +1,177 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/alr_detector.h"
+
+#include "rtc_base/experiments/alr_experiment.h"
+#include "test/field_trial.h"
+#include "test/gtest.h"
+
+namespace {
+
+constexpr int kEstimatedBitrateBps = 300000;
+
+} // namespace
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+class SimulateOutgoingTrafficIn {
+ public:
+ explicit SimulateOutgoingTrafficIn(AlrDetector* alr_detector,
+ int64_t* timestamp_ms)
+ : alr_detector_(alr_detector), timestamp_ms_(timestamp_ms) {
+ RTC_CHECK(alr_detector_);
+ }
+
+ SimulateOutgoingTrafficIn& ForTimeMs(int time_ms) {
+ interval_ms_ = time_ms;
+ ProduceTraffic();
+ return *this;
+ }
+
+ SimulateOutgoingTrafficIn& AtPercentOfEstimatedBitrate(int usage_percentage) {
+ usage_percentage_.emplace(usage_percentage);
+ ProduceTraffic();
+ return *this;
+ }
+
+ private:
+ void ProduceTraffic() {
+ if (!interval_ms_ || !usage_percentage_)
+ return;
+ const int kTimeStepMs = 10;
+ for (int t = 0; t < *interval_ms_; t += kTimeStepMs) {
+ *timestamp_ms_ += kTimeStepMs;
+ alr_detector_->OnBytesSent(kEstimatedBitrateBps * *usage_percentage_ *
+ kTimeStepMs / (8 * 100 * 1000),
+ *timestamp_ms_);
+ }
+ int remainder_ms = *interval_ms_ % kTimeStepMs;
+ if (remainder_ms > 0) {
+ *timestamp_ms_ += kTimeStepMs;
+ alr_detector_->OnBytesSent(kEstimatedBitrateBps * *usage_percentage_ *
+ remainder_ms / (8 * 100 * 1000),
+ *timestamp_ms_);
+ }
+ }
+ AlrDetector* const alr_detector_;
+ int64_t* timestamp_ms_;
+ rtc::Optional<int> interval_ms_;
+ rtc::Optional<int> usage_percentage_;
+};
+} // namespace
+
+class AlrDetectorTest : public testing::Test {
+ public:
+ void SetUp() override {
+ alr_detector_.SetEstimatedBitrate(kEstimatedBitrateBps);
+ }
+
+ protected:
+ AlrDetector alr_detector_;
+ int64_t timestamp_ms_ = 1000;
+};
+
+TEST_F(AlrDetectorTest, AlrDetection) {
+ // Start in non-ALR state.
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // Stay in non-ALR state when usage is close to 100%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(1000)
+ .AtPercentOfEstimatedBitrate(90);
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // Verify that we ALR starts when bitrate drops below 20%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(1500)
+ .AtPercentOfEstimatedBitrate(20);
+ EXPECT_TRUE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // Verify that ALR ends when usage is above 65%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(4000)
+ .AtPercentOfEstimatedBitrate(100);
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+}
+
+TEST_F(AlrDetectorTest, ShortSpike) {
+ // Start in non-ALR state.
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // Verify that we ALR starts when bitrate drops below 20%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(1000)
+ .AtPercentOfEstimatedBitrate(20);
+ EXPECT_TRUE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // Verify that we stay in ALR region even after a short bitrate spike.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(100)
+ .AtPercentOfEstimatedBitrate(150);
+ EXPECT_TRUE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // ALR ends when usage is above 65%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(3000)
+ .AtPercentOfEstimatedBitrate(100);
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+}
+
+TEST_F(AlrDetectorTest, BandwidthEstimateChanges) {
+ // Start in non-ALR state.
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // ALR starts when bitrate drops below 20%.
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(1000)
+ .AtPercentOfEstimatedBitrate(20);
+ EXPECT_TRUE(alr_detector_.GetApplicationLimitedRegionStartTime());
+
+ // When bandwidth estimate drops the detector should stay in ALR mode and quit
+ // it shortly afterwards as the sender continues sending the same amount of
+ // traffic. This is necessary to ensure that ProbeController can still react
+ // to the BWE drop by initiating a new probe.
+ alr_detector_.SetEstimatedBitrate(kEstimatedBitrateBps / 5);
+ EXPECT_TRUE(alr_detector_.GetApplicationLimitedRegionStartTime());
+ SimulateOutgoingTrafficIn(&alr_detector_, ×tamp_ms_)
+ .ForTimeMs(1000)
+ .AtPercentOfEstimatedBitrate(50);
+ EXPECT_FALSE(alr_detector_.GetApplicationLimitedRegionStartTime());
+}
+
+TEST_F(AlrDetectorTest, ParseControlFieldTrial) {
+ webrtc::test::ScopedFieldTrials field_trial(
+ "WebRTC-ProbingScreenshareBwe/Control/");
+ rtc::Optional<AlrExperimentSettings> parsed_params =
+ AlrExperimentSettings::CreateFromFieldTrial(
+ "WebRTC-ProbingScreenshareBwe");
+ EXPECT_FALSE(static_cast<bool>(parsed_params));
+}
+
+TEST_F(AlrDetectorTest, ParseActiveFieldTrial) {
+ webrtc::test::ScopedFieldTrials field_trial(
+ "WebRTC-ProbingScreenshareBwe/1.1,2875,85,20,-20,1/");
+ rtc::Optional<AlrExperimentSettings> parsed_params =
+ AlrExperimentSettings::CreateFromFieldTrial(
+ "WebRTC-ProbingScreenshareBwe");
+ ASSERT_TRUE(static_cast<bool>(parsed_params));
+ EXPECT_EQ(1.1f, parsed_params->pacing_factor);
+ EXPECT_EQ(2875, parsed_params->max_paced_queue_time);
+ EXPECT_EQ(85, parsed_params->alr_bandwidth_usage_percent);
+ EXPECT_EQ(20, parsed_params->alr_start_budget_level_percent);
+ EXPECT_EQ(-20, parsed_params->alr_stop_budget_level_percent);
+ EXPECT_EQ(1, parsed_params->group_id);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/bitrate_estimator.cc b/modules/congestion_controller/goog_cc/bitrate_estimator.cc
new file mode 100644
index 0000000..2cd5331
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/bitrate_estimator.cc
@@ -0,0 +1,109 @@
+/*
+ * Copyright (c) 2017 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 "modules/congestion_controller/goog_cc/bitrate_estimator.h"
+
+#include <cmath>
+
+#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+#include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+constexpr int kInitialRateWindowMs = 500;
+constexpr int kRateWindowMs = 150;
+} // namespace
+
+BitrateEstimator::BitrateEstimator()
+ : sum_(0),
+ current_win_ms_(0),
+ prev_time_ms_(-1),
+ bitrate_estimate_(-1.0f),
+ bitrate_estimate_var_(50.0f) {}
+
+BitrateEstimator::~BitrateEstimator() = default;
+
+void BitrateEstimator::Update(int64_t now_ms, int bytes) {
+ int rate_window_ms = kRateWindowMs;
+ // We use a larger window at the beginning to get a more stable sample that
+ // we can use to initialize the estimate.
+ if (bitrate_estimate_ < 0.f)
+ rate_window_ms = kInitialRateWindowMs;
+ float bitrate_sample = UpdateWindow(now_ms, bytes, rate_window_ms);
+ if (bitrate_sample < 0.0f)
+ return;
+ if (bitrate_estimate_ < 0.0f) {
+ // This is the very first sample we get. Use it to initialize the estimate.
+ bitrate_estimate_ = bitrate_sample;
+ return;
+ }
+ // Define the sample uncertainty as a function of how far away it is from the
+ // current estimate.
+ float sample_uncertainty =
+ 10.0f * std::abs(bitrate_estimate_ - bitrate_sample) / bitrate_estimate_;
+ float sample_var = sample_uncertainty * sample_uncertainty;
+ // Update a bayesian estimate of the rate, weighting it lower if the sample
+ // uncertainty is large.
+ // The bitrate estimate uncertainty is increased with each update to model
+ // that the bitrate changes over time.
+ float pred_bitrate_estimate_var = bitrate_estimate_var_ + 5.f;
+ bitrate_estimate_ = (sample_var * bitrate_estimate_ +
+ pred_bitrate_estimate_var * bitrate_sample) /
+ (sample_var + pred_bitrate_estimate_var);
+ bitrate_estimate_var_ = sample_var * pred_bitrate_estimate_var /
+ (sample_var + pred_bitrate_estimate_var);
+ BWE_TEST_LOGGING_PLOT(1, "acknowledged_bitrate", now_ms,
+ bitrate_estimate_ * 1000);
+}
+
+float BitrateEstimator::UpdateWindow(int64_t now_ms,
+ int bytes,
+ int rate_window_ms) {
+ // Reset if time moves backwards.
+ if (now_ms < prev_time_ms_) {
+ prev_time_ms_ = -1;
+ sum_ = 0;
+ current_win_ms_ = 0;
+ }
+ if (prev_time_ms_ >= 0) {
+ current_win_ms_ += now_ms - prev_time_ms_;
+ // Reset if nothing has been received for more than a full window.
+ if (now_ms - prev_time_ms_ > rate_window_ms) {
+ sum_ = 0;
+ current_win_ms_ %= rate_window_ms;
+ }
+ }
+ prev_time_ms_ = now_ms;
+ float bitrate_sample = -1.0f;
+ if (current_win_ms_ >= rate_window_ms) {
+ bitrate_sample = 8.0f * sum_ / static_cast<float>(rate_window_ms);
+ current_win_ms_ -= rate_window_ms;
+ sum_ = 0;
+ }
+ sum_ += bytes;
+ return bitrate_sample;
+}
+
+rtc::Optional<uint32_t> BitrateEstimator::bitrate_bps() const {
+ if (bitrate_estimate_ < 0.f)
+ return rtc::nullopt;
+ return bitrate_estimate_ * 1000;
+}
+
+void BitrateEstimator::ExpectFastRateChange() {
+ // By setting the bitrate-estimate variance to a higher value we allow the
+ // bitrate to change fast for the next few samples.
+ bitrate_estimate_var_ += 200;
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/bitrate_estimator.h b/modules/congestion_controller/goog_cc/bitrate_estimator.h
new file mode 100644
index 0000000..ca5a40e
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/bitrate_estimator.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_BITRATE_ESTIMATOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_BITRATE_ESTIMATOR_H_
+
+#include <vector>
+
+#include "api/optional.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+// Computes a bayesian estimate of the throughput given acks containing
+// the arrival time and payload size. Samples which are far from the current
+// estimate or are based on few packets are given a smaller weight, as they
+// are considered to be more likely to have been caused by, e.g., delay spikes
+// unrelated to congestion.
+class BitrateEstimator {
+ public:
+ BitrateEstimator();
+ virtual ~BitrateEstimator();
+ virtual void Update(int64_t now_ms, int bytes);
+
+ virtual rtc::Optional<uint32_t> bitrate_bps() const;
+
+ virtual void ExpectFastRateChange();
+
+ private:
+ float UpdateWindow(int64_t now_ms, int bytes, int rate_window_ms);
+ int sum_;
+ int64_t current_win_ms_;
+ int64_t prev_time_ms_;
+ float bitrate_estimate_;
+ float bitrate_estimate_var_;
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_BITRATE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/goog_cc/delay_based_bwe.cc b/modules/congestion_controller/goog_cc/delay_based_bwe.cc
new file mode 100644
index 0000000..fea5a66
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_based_bwe.cc
@@ -0,0 +1,331 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/delay_based_bwe.h"
+
+#include <algorithm>
+#include <cmath>
+#include <cstdio>
+#include <string>
+
+#include "logging/rtc_event_log/events/rtc_event_bwe_update_delay_based.h"
+#include "logging/rtc_event_log/rtc_event_log.h"
+#include "modules/congestion_controller/goog_cc/trendline_estimator.h"
+#include "modules/pacing/paced_sender.h"
+#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/constructormagic.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/ptr_util.h"
+#include "rtc_base/thread_annotations.h"
+#include "system_wrappers/include/field_trial.h"
+#include "system_wrappers/include/metrics.h"
+#include "typedefs.h" // NOLINT(build/include)
+
+namespace {
+constexpr int kTimestampGroupLengthMs = 5;
+constexpr int kAbsSendTimeFraction = 18;
+constexpr int kAbsSendTimeInterArrivalUpshift = 8;
+constexpr int kInterArrivalShift =
+ kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift;
+constexpr double kTimestampToMs =
+ 1000.0 / static_cast<double>(1 << kInterArrivalShift);
+// This ssrc is used to fulfill the current API but will be removed
+// after the API has been changed.
+constexpr uint32_t kFixedSsrc = 0;
+
+// Parameters for linear least squares fit of regression line to noisy data.
+constexpr size_t kDefaultTrendlineWindowSize = 20;
+constexpr double kDefaultTrendlineSmoothingCoeff = 0.9;
+constexpr double kDefaultTrendlineThresholdGain = 4.0;
+
+constexpr int kMaxConsecutiveFailedLookups = 5;
+
+const char kBweWindowSizeInPacketsExperiment[] =
+ "WebRTC-BweWindowSizeInPackets";
+
+size_t ReadTrendlineFilterWindowSize() {
+ std::string experiment_string =
+ webrtc::field_trial::FindFullName(kBweWindowSizeInPacketsExperiment);
+ size_t window_size;
+ int parsed_values =
+ sscanf(experiment_string.c_str(), "Enabled-%zu", &window_size);
+ if (parsed_values == 1) {
+ if (window_size > 1)
+ return window_size;
+ RTC_LOG(WARNING) << "Window size must be greater than 1.";
+ }
+ RTC_LOG(LS_WARNING) << "Failed to parse parameters for BweTrendlineFilter "
+ "experiment from field trial string. Using default.";
+ return kDefaultTrendlineWindowSize;
+}
+} // namespace
+
+namespace webrtc {
+namespace webrtc_cc {
+
+DelayBasedBwe::Result::Result()
+ : updated(false),
+ probe(false),
+ target_bitrate_bps(0),
+ recovered_from_overuse(false) {}
+
+DelayBasedBwe::Result::Result(bool probe, uint32_t target_bitrate_bps)
+ : updated(true),
+ probe(probe),
+ target_bitrate_bps(target_bitrate_bps),
+ recovered_from_overuse(false) {}
+
+DelayBasedBwe::Result::~Result() {}
+
+DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log)
+ : event_log_(event_log),
+ inter_arrival_(),
+ delay_detector_(),
+ last_seen_packet_ms_(-1),
+ uma_recorded_(false),
+ probe_bitrate_estimator_(event_log),
+ trendline_window_size_(
+ webrtc::field_trial::IsEnabled(kBweWindowSizeInPacketsExperiment)
+ ? ReadTrendlineFilterWindowSize()
+ : kDefaultTrendlineWindowSize),
+ trendline_smoothing_coeff_(kDefaultTrendlineSmoothingCoeff),
+ trendline_threshold_gain_(kDefaultTrendlineThresholdGain),
+ consecutive_delayed_feedbacks_(0),
+ prev_bitrate_(0),
+ prev_state_(BandwidthUsage::kBwNormal) {
+ RTC_LOG(LS_INFO)
+ << "Using Trendline filter for delay change estimation with window size "
+ << trendline_window_size_;
+ delay_detector_.reset(new TrendlineEstimator(trendline_window_size_,
+ trendline_smoothing_coeff_,
+ trendline_threshold_gain_));
+}
+
+DelayBasedBwe::~DelayBasedBwe() {}
+
+DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
+ const std::vector<PacketFeedback>& packet_feedback_vector,
+ rtc::Optional<uint32_t> acked_bitrate_bps,
+ int64_t at_time_ms) {
+ RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(),
+ packet_feedback_vector.end(),
+ PacketFeedbackComparator()));
+ RTC_DCHECK_RUNS_SERIALIZED(&network_race_);
+
+ // TOOD(holmer): An empty feedback vector here likely means that
+ // all acks were too late and that the send time history had
+ // timed out. We should reduce the rate when this occurs.
+ if (packet_feedback_vector.empty()) {
+ RTC_LOG(LS_WARNING) << "Very late feedback received.";
+ return DelayBasedBwe::Result();
+ }
+
+ if (!uma_recorded_) {
+ RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram,
+ BweNames::kSendSideTransportSeqNum,
+ BweNames::kBweNamesMax);
+ uma_recorded_ = true;
+ }
+ bool delayed_feedback = true;
+ bool recovered_from_overuse = false;
+ BandwidthUsage prev_detector_state = delay_detector_->State();
+ for (const auto& packet_feedback : packet_feedback_vector) {
+ if (packet_feedback.send_time_ms < 0)
+ continue;
+ delayed_feedback = false;
+ IncomingPacketFeedback(packet_feedback, at_time_ms);
+ if (prev_detector_state == BandwidthUsage::kBwUnderusing &&
+ delay_detector_->State() == BandwidthUsage::kBwNormal) {
+ recovered_from_overuse = true;
+ }
+ prev_detector_state = delay_detector_->State();
+ }
+
+ if (delayed_feedback) {
+ ++consecutive_delayed_feedbacks_;
+ if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) {
+ consecutive_delayed_feedbacks_ = 0;
+ return OnLongFeedbackDelay(packet_feedback_vector.back().arrival_time_ms);
+ }
+ } else {
+ consecutive_delayed_feedbacks_ = 0;
+ return MaybeUpdateEstimate(acked_bitrate_bps, recovered_from_overuse,
+ at_time_ms);
+ }
+ return Result();
+}
+
+DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay(
+ int64_t arrival_time_ms) {
+ // Estimate should always be valid since a start bitrate always is set in the
+ // Call constructor. An alternative would be to return an empty Result here,
+ // or to estimate the throughput based on the feedback we received.
+ RTC_DCHECK(rate_control_.ValidEstimate());
+ rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2,
+ arrival_time_ms);
+ Result result;
+ result.updated = true;
+ result.probe = false;
+ result.target_bitrate_bps = rate_control_.LatestEstimate();
+ RTC_LOG(LS_WARNING) << "Long feedback delay detected, reducing BWE to "
+ << result.target_bitrate_bps;
+ return result;
+}
+
+void DelayBasedBwe::IncomingPacketFeedback(
+ const PacketFeedback& packet_feedback,
+ int64_t at_time_ms) {
+ int64_t now_ms = at_time_ms;
+ // Reset if the stream has timed out.
+ if (last_seen_packet_ms_ == -1 ||
+ now_ms - last_seen_packet_ms_ > kStreamTimeOutMs) {
+ inter_arrival_.reset(
+ new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
+ kTimestampToMs, true));
+ delay_detector_.reset(new TrendlineEstimator(trendline_window_size_,
+ trendline_smoothing_coeff_,
+ trendline_threshold_gain_));
+ }
+ last_seen_packet_ms_ = now_ms;
+
+ uint32_t send_time_24bits =
+ static_cast<uint32_t>(
+ ((static_cast<uint64_t>(packet_feedback.send_time_ms)
+ << kAbsSendTimeFraction) +
+ 500) /
+ 1000) &
+ 0x00FFFFFF;
+ // Shift up send time to use the full 32 bits that inter_arrival works with,
+ // so wrapping works properly.
+ uint32_t timestamp = send_time_24bits << kAbsSendTimeInterArrivalUpshift;
+
+ uint32_t ts_delta = 0;
+ int64_t t_delta = 0;
+ int size_delta = 0;
+ if (inter_arrival_->ComputeDeltas(timestamp, packet_feedback.arrival_time_ms,
+ now_ms, packet_feedback.payload_size,
+ &ts_delta, &t_delta, &size_delta)) {
+ double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
+ delay_detector_->Update(t_delta, ts_delta_ms,
+ packet_feedback.arrival_time_ms);
+ }
+ if (packet_feedback.pacing_info.probe_cluster_id !=
+ PacedPacketInfo::kNotAProbe) {
+ probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback);
+ }
+}
+
+DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate(
+ rtc::Optional<uint32_t> acked_bitrate_bps,
+ bool recovered_from_overuse,
+ int64_t at_time_ms) {
+ Result result;
+ int64_t now_ms = at_time_ms;
+
+ rtc::Optional<int> probe_bitrate_bps =
+ probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps();
+ // Currently overusing the bandwidth.
+ if (delay_detector_->State() == BandwidthUsage::kBwOverusing) {
+ if (acked_bitrate_bps &&
+ rate_control_.TimeToReduceFurther(now_ms, *acked_bitrate_bps)) {
+ result.updated =
+ UpdateEstimate(now_ms, acked_bitrate_bps, &result.target_bitrate_bps);
+ } else if (!acked_bitrate_bps && rate_control_.ValidEstimate() &&
+ rate_control_.TimeToReduceFurther(
+ now_ms, rate_control_.LatestEstimate() / 2 - 1)) {
+ // Overusing before we have a measured acknowledged bitrate. We check
+ // TimeToReduceFurther (with a fake acknowledged bitrate) to avoid
+ // reducing too often.
+ // TODO(tschumim): Improve this and/or the acknowledged bitrate estimator
+ // so that we (almost) always have a bitrate estimate.
+ rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, now_ms);
+ result.updated = true;
+ result.probe = false;
+ result.target_bitrate_bps = rate_control_.LatestEstimate();
+ }
+ } else {
+ if (probe_bitrate_bps) {
+ result.probe = true;
+ result.updated = true;
+ result.target_bitrate_bps = *probe_bitrate_bps;
+ rate_control_.SetEstimate(*probe_bitrate_bps, now_ms);
+ } else {
+ result.updated =
+ UpdateEstimate(now_ms, acked_bitrate_bps, &result.target_bitrate_bps);
+ result.recovered_from_overuse = recovered_from_overuse;
+ }
+ }
+ BandwidthUsage detector_state = delay_detector_->State();
+ if ((result.updated && prev_bitrate_ != result.target_bitrate_bps) ||
+ detector_state != prev_state_) {
+ uint32_t bitrate_bps =
+ result.updated ? result.target_bitrate_bps : prev_bitrate_;
+
+ BWE_TEST_LOGGING_PLOT(1, "target_bitrate_bps", now_ms, bitrate_bps);
+
+ if (event_log_) {
+ event_log_->Log(rtc::MakeUnique<RtcEventBweUpdateDelayBased>(
+ bitrate_bps, detector_state));
+ }
+
+ prev_bitrate_ = bitrate_bps;
+ prev_state_ = detector_state;
+ }
+ return result;
+}
+
+bool DelayBasedBwe::UpdateEstimate(int64_t now_ms,
+ rtc::Optional<uint32_t> acked_bitrate_bps,
+ uint32_t* target_bitrate_bps) {
+ // TODO(terelius): RateControlInput::noise_var is deprecated and will be
+ // removed. In the meantime, we set it to zero.
+ const RateControlInput input(delay_detector_->State(), acked_bitrate_bps, 0);
+ *target_bitrate_bps = rate_control_.Update(&input, now_ms);
+ return rate_control_.ValidEstimate();
+}
+
+void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms) {
+ rate_control_.SetRtt(avg_rtt_ms);
+}
+
+bool DelayBasedBwe::LatestEstimate(std::vector<uint32_t>* ssrcs,
+ uint32_t* bitrate_bps) const {
+ // Currently accessed from both the process thread (see
+ // ModuleRtpRtcpImpl::Process()) and the configuration thread (see
+ // Call::GetStats()). Should in the future only be accessed from a single
+ // thread.
+ RTC_DCHECK(ssrcs);
+ RTC_DCHECK(bitrate_bps);
+ if (!rate_control_.ValidEstimate())
+ return false;
+
+ *ssrcs = {kFixedSsrc};
+ *bitrate_bps = rate_control_.LatestEstimate();
+ return true;
+}
+
+void DelayBasedBwe::SetStartBitrate(int start_bitrate_bps) {
+ RTC_LOG(LS_WARNING) << "BWE Setting start bitrate to: " << start_bitrate_bps;
+ rate_control_.SetStartBitrate(start_bitrate_bps);
+}
+
+void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) {
+ // Called from both the configuration thread and the network thread. Shouldn't
+ // be called from the network thread in the future.
+ rate_control_.SetMinBitrate(min_bitrate_bps);
+}
+
+int64_t DelayBasedBwe::GetExpectedBwePeriodMs() const {
+ return rate_control_.GetExpectedBandwidthPeriodMs();
+}
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/delay_based_bwe.h b/modules/congestion_controller/goog_cc/delay_based_bwe.h
new file mode 100644
index 0000000..485f687
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_based_bwe.h
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_H_
+
+#include <memory>
+#include <utility>
+#include <vector>
+
+#include "modules/congestion_controller/goog_cc/delay_increase_detector_interface.h"
+#include "modules/congestion_controller/goog_cc/probe_bitrate_estimator.h"
+#include "modules/remote_bitrate_estimator/aimd_rate_control.h"
+#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "modules/remote_bitrate_estimator/inter_arrival.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/constructormagic.h"
+#include "rtc_base/race_checker.h"
+
+namespace webrtc {
+class RtcEventLog;
+
+namespace webrtc_cc {
+
+class DelayBasedBwe {
+ public:
+ static const int64_t kStreamTimeOutMs = 2000;
+
+ struct Result {
+ Result();
+ Result(bool probe, uint32_t target_bitrate_bps);
+ ~Result();
+ bool updated;
+ bool probe;
+ uint32_t target_bitrate_bps;
+ bool recovered_from_overuse;
+ };
+
+ explicit DelayBasedBwe(RtcEventLog* event_log);
+ virtual ~DelayBasedBwe();
+
+ Result IncomingPacketFeedbackVector(
+ const std::vector<PacketFeedback>& packet_feedback_vector,
+ rtc::Optional<uint32_t> acked_bitrate_bps,
+ int64_t at_time_ms);
+ void OnRttUpdate(int64_t avg_rtt_ms);
+ bool LatestEstimate(std::vector<uint32_t>* ssrcs,
+ uint32_t* bitrate_bps) const;
+ void SetStartBitrate(int start_bitrate_bps);
+ void SetMinBitrate(int min_bitrate_bps);
+ int64_t GetExpectedBwePeriodMs() const;
+
+ private:
+ void IncomingPacketFeedback(const PacketFeedback& packet_feedback,
+ int64_t at_time_ms);
+ Result OnLongFeedbackDelay(int64_t arrival_time_ms);
+ Result MaybeUpdateEstimate(rtc::Optional<uint32_t> acked_bitrate_bps,
+ bool request_probe,
+ int64_t at_time_ms);
+ // Updates the current remote rate estimate and returns true if a valid
+ // estimate exists.
+ bool UpdateEstimate(int64_t now_ms,
+ rtc::Optional<uint32_t> acked_bitrate_bps,
+ uint32_t* target_bitrate_bps);
+
+ rtc::RaceChecker network_race_;
+ RtcEventLog* const event_log_;
+ std::unique_ptr<InterArrival> inter_arrival_;
+ std::unique_ptr<DelayIncreaseDetectorInterface> delay_detector_;
+ int64_t last_seen_packet_ms_;
+ bool uma_recorded_;
+ AimdRateControl rate_control_;
+ ProbeBitrateEstimator probe_bitrate_estimator_;
+ size_t trendline_window_size_;
+ double trendline_smoothing_coeff_;
+ double trendline_threshold_gain_;
+ int consecutive_delayed_feedbacks_;
+ uint32_t prev_bitrate_;
+ BandwidthUsage prev_state_;
+
+ RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(DelayBasedBwe);
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_H_
diff --git a/modules/congestion_controller/goog_cc/delay_based_bwe_unittest.cc b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest.cc
new file mode 100644
index 0000000..b19e8f9
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest.cc
@@ -0,0 +1,239 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/delay_based_bwe.h"
+#include "modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.h"
+#include "modules/pacing/paced_sender.h"
+#include "rtc_base/constructormagic.h"
+#include "system_wrappers/include/clock.h"
+#include "test/field_trial.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+constexpr int kNumProbesCluster0 = 5;
+constexpr int kNumProbesCluster1 = 8;
+const PacedPacketInfo kPacingInfo0(0, kNumProbesCluster0, 2000);
+const PacedPacketInfo kPacingInfo1(1, kNumProbesCluster1, 4000);
+constexpr float kTargetUtilizationFraction = 0.95f;
+constexpr int64_t kDummyTimestamp = 1000;
+} // namespace
+
+TEST_F(DelayBasedBweTest, NoCrashEmptyFeedback) {
+ std::vector<PacketFeedback> packet_feedback_vector;
+ bitrate_estimator_->IncomingPacketFeedbackVector(
+ packet_feedback_vector, rtc::nullopt, kDummyTimestamp);
+}
+
+TEST_F(DelayBasedBweTest, NoCrashOnlyLostFeedback) {
+ std::vector<PacketFeedback> packet_feedback_vector;
+ packet_feedback_vector.push_back(PacketFeedback(PacketFeedback::kNotReceived,
+ PacketFeedback::kNoSendTime,
+ 0, 1500, PacedPacketInfo()));
+ packet_feedback_vector.push_back(PacketFeedback(PacketFeedback::kNotReceived,
+ PacketFeedback::kNoSendTime,
+ 1, 1500, PacedPacketInfo()));
+ bitrate_estimator_->IncomingPacketFeedbackVector(
+ packet_feedback_vector, rtc::nullopt, kDummyTimestamp);
+}
+
+TEST_F(DelayBasedBweTest, ProbeDetection) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ uint16_t seq_num = 0;
+
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ for (int i = 0; i < kNumProbesCluster0; ++i) {
+ clock_.AdvanceTimeMilliseconds(10);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, now_ms, seq_num++, 1000, kPacingInfo0);
+ }
+ EXPECT_TRUE(bitrate_observer_.updated());
+
+ // Second burst sent at 8 * 1000 / 5 = 1600 kbps.
+ for (int i = 0; i < kNumProbesCluster1; ++i) {
+ clock_.AdvanceTimeMilliseconds(5);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, now_ms, seq_num++, 1000, kPacingInfo1);
+ }
+
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_GT(bitrate_observer_.latest_bitrate(), 1500000u);
+}
+
+TEST_F(DelayBasedBweTest, ProbeDetectionNonPacedPackets) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ uint16_t seq_num = 0;
+ // First burst sent at 8 * 1000 / 10 = 800 kbps, but with every other packet
+ // not being paced which could mess things up.
+ for (int i = 0; i < kNumProbesCluster0; ++i) {
+ clock_.AdvanceTimeMilliseconds(5);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, now_ms, seq_num++, 1000, kPacingInfo0);
+ // Non-paced packet, arriving 5 ms after.
+ clock_.AdvanceTimeMilliseconds(5);
+ IncomingFeedback(now_ms, now_ms, seq_num++, 100, PacedPacketInfo());
+ }
+
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_GT(bitrate_observer_.latest_bitrate(), 800000u);
+}
+
+TEST_F(DelayBasedBweTest, ProbeDetectionFasterArrival) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ uint16_t seq_num = 0;
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ // Arriving at 8 * 1000 / 5 = 1600 kbps.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbesCluster0; ++i) {
+ clock_.AdvanceTimeMilliseconds(1);
+ send_time_ms += 10;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, send_time_ms, seq_num++, 1000, kPacingInfo0);
+ }
+
+ EXPECT_FALSE(bitrate_observer_.updated());
+}
+
+TEST_F(DelayBasedBweTest, ProbeDetectionSlowerArrival) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ uint16_t seq_num = 0;
+ // First burst sent at 8 * 1000 / 5 = 1600 kbps.
+ // Arriving at 8 * 1000 / 7 = 1142 kbps.
+ // Since the receive rate is significantly below the send rate, we expect to
+ // use 95% of the estimated capacity.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbesCluster1; ++i) {
+ clock_.AdvanceTimeMilliseconds(7);
+ send_time_ms += 5;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, send_time_ms, seq_num++, 1000, kPacingInfo1);
+ }
+
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_NEAR(bitrate_observer_.latest_bitrate(),
+ kTargetUtilizationFraction * 1140000u, 10000u);
+}
+
+TEST_F(DelayBasedBweTest, ProbeDetectionSlowerArrivalHighBitrate) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ uint16_t seq_num = 0;
+ // Burst sent at 8 * 1000 / 1 = 8000 kbps.
+ // Arriving at 8 * 1000 / 2 = 4000 kbps.
+ // Since the receive rate is significantly below the send rate, we expect to
+ // use 95% of the estimated capacity.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbesCluster1; ++i) {
+ clock_.AdvanceTimeMilliseconds(2);
+ send_time_ms += 1;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingFeedback(now_ms, send_time_ms, seq_num++, 1000, kPacingInfo1);
+ }
+
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_NEAR(bitrate_observer_.latest_bitrate(),
+ kTargetUtilizationFraction * 4000000u, 10000u);
+}
+
+TEST_F(DelayBasedBweTest, GetExpectedBwePeriodMs) {
+ int64_t default_interval_ms = bitrate_estimator_->GetExpectedBwePeriodMs();
+ EXPECT_GT(default_interval_ms, 0);
+ CapacityDropTestHelper(1, true, 333, 0);
+ int64_t interval_ms = bitrate_estimator_->GetExpectedBwePeriodMs();
+ EXPECT_GT(interval_ms, 0);
+ EXPECT_NE(interval_ms, default_interval_ms);
+}
+
+TEST_F(DelayBasedBweTest, InitialBehavior) {
+ InitialBehaviorTestHelper(730000);
+}
+
+TEST_F(DelayBasedBweTest, RateIncreaseReordering) {
+ RateIncreaseReorderingTestHelper(730000);
+}
+TEST_F(DelayBasedBweTest, RateIncreaseRtpTimestamps) {
+ RateIncreaseRtpTimestampsTestHelper(627);
+}
+
+TEST_F(DelayBasedBweTest, CapacityDropOneStream) {
+ CapacityDropTestHelper(1, false, 300, 0);
+}
+
+TEST_F(DelayBasedBweTest, CapacityDropPosOffsetChange) {
+ CapacityDropTestHelper(1, false, 867, 30000);
+}
+
+TEST_F(DelayBasedBweTest, CapacityDropNegOffsetChange) {
+ CapacityDropTestHelper(1, false, 933, -30000);
+}
+
+TEST_F(DelayBasedBweTest, CapacityDropOneStreamWrap) {
+ CapacityDropTestHelper(1, true, 333, 0);
+}
+
+TEST_F(DelayBasedBweTest, TestTimestampGrouping) {
+ TestTimestampGroupingTestHelper();
+}
+
+TEST_F(DelayBasedBweTest, TestShortTimeoutAndWrap) {
+ // Simulate a client leaving and rejoining the call after 35 seconds. This
+ // will make abs send time wrap, so if streams aren't timed out properly
+ // the next 30 seconds of packets will be out of order.
+ TestWrappingHelper(35);
+}
+
+TEST_F(DelayBasedBweTest, TestLongTimeoutAndWrap) {
+ // Simulate a client leaving and rejoining the call after some multiple of
+ // 64 seconds later. This will cause a zero difference in abs send times due
+ // to the wrap, but a big difference in arrival time, if streams aren't
+ // properly timed out.
+ TestWrappingHelper(10 * 64);
+}
+
+TEST_F(DelayBasedBweTest, TestInitialOveruse) {
+ const uint32_t kStartBitrate = 300e3;
+ const uint32_t kInitialCapacityBps = 200e3;
+ const uint32_t kDummySsrc = 0;
+ // High FPS to ensure that we send a lot of packets in a short time.
+ const int kFps = 90;
+
+ stream_generator_->AddStream(new test::RtpStream(kFps, kStartBitrate));
+ stream_generator_->set_capacity_bps(kInitialCapacityBps);
+
+ // Needed to initialize the AimdRateControl.
+ bitrate_estimator_->SetStartBitrate(kStartBitrate);
+
+ // Produce 30 frames (in 1/3 second) and give them to the estimator.
+ uint32_t bitrate_bps = kStartBitrate;
+ bool seen_overuse = false;
+ for (int i = 0; i < 30; ++i) {
+ bool overuse = GenerateAndProcessFrame(kDummySsrc, bitrate_bps);
+ // The purpose of this test is to ensure that we back down even if we don't
+ // have any acknowledged bitrate estimate yet. Hence, if the test works
+ // as expected, we should not have a measured bitrate yet.
+ EXPECT_FALSE(acknowledged_bitrate_estimator_->bitrate_bps().has_value());
+ if (overuse) {
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_NEAR(bitrate_observer_.latest_bitrate(), kStartBitrate / 2, 15000);
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ seen_overuse = true;
+ break;
+ } else if (bitrate_observer_.updated()) {
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ bitrate_observer_.Reset();
+ }
+ }
+ EXPECT_TRUE(seen_overuse);
+ EXPECT_NEAR(bitrate_observer_.latest_bitrate(), kStartBitrate / 2, 15000);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.cc b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.cc
new file mode 100644
index 0000000..35019b0
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.cc
@@ -0,0 +1,517 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.h"
+
+#include <algorithm>
+#include <limits>
+#include <utility>
+
+#include "modules/congestion_controller/goog_cc/delay_based_bwe.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/ptr_util.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+constexpr size_t kMtu = 1200;
+constexpr uint32_t kAcceptedBitrateErrorBps = 50000;
+
+// Number of packets needed before we have a valid estimate.
+constexpr int kNumInitialPackets = 2;
+
+constexpr int kInitialProbingPackets = 5;
+
+namespace test {
+
+void TestBitrateObserver::OnReceiveBitrateChanged(
+ const std::vector<uint32_t>& ssrcs,
+ uint32_t bitrate) {
+ latest_bitrate_ = bitrate;
+ updated_ = true;
+}
+
+RtpStream::RtpStream(int fps, int bitrate_bps)
+ : fps_(fps),
+ bitrate_bps_(bitrate_bps),
+ next_rtp_time_(0),
+ sequence_number_(0) {
+ RTC_CHECK_GT(fps_, 0);
+}
+
+// Generates a new frame for this stream. If called too soon after the
+// previous frame, no frame will be generated. The frame is split into
+// packets.
+int64_t RtpStream::GenerateFrame(int64_t time_now_us,
+ std::vector<PacketFeedback>* packets) {
+ if (time_now_us < next_rtp_time_) {
+ return next_rtp_time_;
+ }
+ RTC_CHECK(packets != NULL);
+ size_t bits_per_frame = (bitrate_bps_ + fps_ / 2) / fps_;
+ size_t n_packets =
+ std::max<size_t>((bits_per_frame + 4 * kMtu) / (8 * kMtu), 1u);
+ size_t payload_size = (bits_per_frame + 4 * n_packets) / (8 * n_packets);
+ for (size_t i = 0; i < n_packets; ++i) {
+ PacketFeedback packet(-1, sequence_number_++);
+ packet.send_time_ms = (time_now_us + kSendSideOffsetUs) / 1000;
+ packet.payload_size = payload_size;
+ packets->push_back(packet);
+ }
+ next_rtp_time_ = time_now_us + (1000000 + fps_ / 2) / fps_;
+ return next_rtp_time_;
+}
+
+// The send-side time when the next frame can be generated.
+int64_t RtpStream::next_rtp_time() const {
+ return next_rtp_time_;
+}
+
+void RtpStream::set_bitrate_bps(int bitrate_bps) {
+ ASSERT_GE(bitrate_bps, 0);
+ bitrate_bps_ = bitrate_bps;
+}
+
+int RtpStream::bitrate_bps() const {
+ return bitrate_bps_;
+}
+
+bool RtpStream::Compare(const std::unique_ptr<RtpStream>& lhs,
+ const std::unique_ptr<RtpStream>& rhs) {
+ return lhs->next_rtp_time_ < rhs->next_rtp_time_;
+}
+
+StreamGenerator::StreamGenerator(int capacity, int64_t time_now)
+ : capacity_(capacity), prev_arrival_time_us_(time_now) {}
+
+// Add a new stream.
+void StreamGenerator::AddStream(RtpStream* stream) {
+ streams_.push_back(std::unique_ptr<RtpStream>(stream));
+}
+
+// Set the link capacity.
+void StreamGenerator::set_capacity_bps(int capacity_bps) {
+ ASSERT_GT(capacity_bps, 0);
+ capacity_ = capacity_bps;
+}
+
+// Divides |bitrate_bps| among all streams. The allocated bitrate per stream
+// is decided by the current allocation ratios.
+void StreamGenerator::SetBitrateBps(int bitrate_bps) {
+ ASSERT_GE(streams_.size(), 0u);
+ int total_bitrate_before = 0;
+ for (const auto& stream : streams_) {
+ total_bitrate_before += stream->bitrate_bps();
+ }
+ int64_t bitrate_before = 0;
+ int total_bitrate_after = 0;
+ for (const auto& stream : streams_) {
+ bitrate_before += stream->bitrate_bps();
+ int64_t bitrate_after =
+ (bitrate_before * bitrate_bps + total_bitrate_before / 2) /
+ total_bitrate_before;
+ stream->set_bitrate_bps(bitrate_after - total_bitrate_after);
+ total_bitrate_after += stream->bitrate_bps();
+ }
+ ASSERT_EQ(bitrate_before, total_bitrate_before);
+ EXPECT_EQ(total_bitrate_after, bitrate_bps);
+}
+
+// TODO(holmer): Break out the channel simulation part from this class to make
+// it possible to simulate different types of channels.
+int64_t StreamGenerator::GenerateFrame(std::vector<PacketFeedback>* packets,
+ int64_t time_now_us) {
+ RTC_CHECK(packets != NULL);
+ RTC_CHECK(packets->empty());
+ RTC_CHECK_GT(capacity_, 0);
+ auto it =
+ std::min_element(streams_.begin(), streams_.end(), RtpStream::Compare);
+ (*it)->GenerateFrame(time_now_us, packets);
+ int i = 0;
+ for (PacketFeedback& packet : *packets) {
+ int capacity_bpus = capacity_ / 1000;
+ int64_t required_network_time_us =
+ (8 * 1000 * packet.payload_size + capacity_bpus / 2) / capacity_bpus;
+ prev_arrival_time_us_ =
+ std::max(time_now_us + required_network_time_us,
+ prev_arrival_time_us_ + required_network_time_us);
+ packet.arrival_time_ms = prev_arrival_time_us_ / 1000;
+ ++i;
+ }
+ it = std::min_element(streams_.begin(), streams_.end(), RtpStream::Compare);
+ return std::max((*it)->next_rtp_time(), time_now_us);
+}
+} // namespace test
+
+DelayBasedBweTest::DelayBasedBweTest()
+ : clock_(100000000),
+ acknowledged_bitrate_estimator_(
+ rtc::MakeUnique<AcknowledgedBitrateEstimator>()),
+ bitrate_estimator_(new DelayBasedBwe(nullptr)),
+ stream_generator_(new test::StreamGenerator(1e6, // Capacity.
+ clock_.TimeInMicroseconds())),
+ arrival_time_offset_ms_(0),
+ first_update_(true) {}
+
+DelayBasedBweTest::~DelayBasedBweTest() {}
+
+void DelayBasedBweTest::AddDefaultStream() {
+ stream_generator_->AddStream(new test::RtpStream(30, 3e5));
+}
+
+const uint32_t DelayBasedBweTest::kDefaultSsrc = 0;
+
+void DelayBasedBweTest::IncomingFeedback(int64_t arrival_time_ms,
+ int64_t send_time_ms,
+ uint16_t sequence_number,
+ size_t payload_size) {
+ IncomingFeedback(arrival_time_ms, send_time_ms, sequence_number, payload_size,
+ PacedPacketInfo());
+}
+
+void DelayBasedBweTest::IncomingFeedback(int64_t arrival_time_ms,
+ int64_t send_time_ms,
+ uint16_t sequence_number,
+ size_t payload_size,
+ const PacedPacketInfo& pacing_info) {
+ RTC_CHECK_GE(arrival_time_ms + arrival_time_offset_ms_, 0);
+ PacketFeedback packet(arrival_time_ms + arrival_time_offset_ms_, send_time_ms,
+ sequence_number, payload_size, pacing_info);
+ std::vector<PacketFeedback> packets;
+ packets.push_back(packet);
+ acknowledged_bitrate_estimator_->IncomingPacketFeedbackVector(packets);
+ DelayBasedBwe::Result result =
+ bitrate_estimator_->IncomingPacketFeedbackVector(
+ packets, acknowledged_bitrate_estimator_->bitrate_bps(),
+ clock_.TimeInMilliseconds());
+ const uint32_t kDummySsrc = 0;
+ if (result.updated) {
+ bitrate_observer_.OnReceiveBitrateChanged({kDummySsrc},
+ result.target_bitrate_bps);
+ }
+}
+
+// Generates a frame of packets belonging to a stream at a given bitrate and
+// with a given ssrc. The stream is pushed through a very simple simulated
+// network, and is then given to the receive-side bandwidth estimator.
+// Returns true if an over-use was seen, false otherwise.
+// The StreamGenerator::updated() should be used to check for any changes in
+// target bitrate after the call to this function.
+bool DelayBasedBweTest::GenerateAndProcessFrame(uint32_t ssrc,
+ uint32_t bitrate_bps) {
+ stream_generator_->SetBitrateBps(bitrate_bps);
+ std::vector<PacketFeedback> packets;
+ int64_t next_time_us =
+ stream_generator_->GenerateFrame(&packets, clock_.TimeInMicroseconds());
+ if (packets.empty())
+ return false;
+
+ bool overuse = false;
+ bitrate_observer_.Reset();
+ clock_.AdvanceTimeMicroseconds(1000 * packets.back().arrival_time_ms -
+ clock_.TimeInMicroseconds());
+ for (auto& packet : packets) {
+ RTC_CHECK_GE(packet.arrival_time_ms + arrival_time_offset_ms_, 0);
+ packet.arrival_time_ms += arrival_time_offset_ms_;
+ }
+
+ acknowledged_bitrate_estimator_->IncomingPacketFeedbackVector(packets);
+ DelayBasedBwe::Result result =
+ bitrate_estimator_->IncomingPacketFeedbackVector(
+ packets, acknowledged_bitrate_estimator_->bitrate_bps(),
+ clock_.TimeInMilliseconds());
+ const uint32_t kDummySsrc = 0;
+ if (result.updated) {
+ bitrate_observer_.OnReceiveBitrateChanged({kDummySsrc},
+ result.target_bitrate_bps);
+ if (!first_update_ && result.target_bitrate_bps < bitrate_bps)
+ overuse = true;
+ first_update_ = false;
+ }
+
+ clock_.AdvanceTimeMicroseconds(next_time_us - clock_.TimeInMicroseconds());
+ return overuse;
+}
+
+// Run the bandwidth estimator with a stream of |number_of_frames| frames, or
+// until it reaches |target_bitrate|.
+// Can for instance be used to run the estimator for some time to get it
+// into a steady state.
+uint32_t DelayBasedBweTest::SteadyStateRun(uint32_t ssrc,
+ int max_number_of_frames,
+ uint32_t start_bitrate,
+ uint32_t min_bitrate,
+ uint32_t max_bitrate,
+ uint32_t target_bitrate) {
+ uint32_t bitrate_bps = start_bitrate;
+ bool bitrate_update_seen = false;
+ // Produce |number_of_frames| frames and give them to the estimator.
+ for (int i = 0; i < max_number_of_frames; ++i) {
+ bool overuse = GenerateAndProcessFrame(ssrc, bitrate_bps);
+ if (overuse) {
+ EXPECT_LT(bitrate_observer_.latest_bitrate(), max_bitrate);
+ EXPECT_GT(bitrate_observer_.latest_bitrate(), min_bitrate);
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ bitrate_update_seen = true;
+ } else if (bitrate_observer_.updated()) {
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ bitrate_observer_.Reset();
+ }
+ if (bitrate_update_seen && bitrate_bps > target_bitrate) {
+ break;
+ }
+ }
+ EXPECT_TRUE(bitrate_update_seen);
+ return bitrate_bps;
+}
+
+void DelayBasedBweTest::InitialBehaviorTestHelper(
+ uint32_t expected_converge_bitrate) {
+ const int kFramerate = 50; // 50 fps to avoid rounding errors.
+ const int kFrameIntervalMs = 1000 / kFramerate;
+ const PacedPacketInfo kPacingInfo(0, 5, 5000);
+ uint32_t bitrate_bps = 0;
+ int64_t send_time_ms = 0;
+ uint16_t sequence_number = 0;
+ std::vector<uint32_t> ssrcs;
+ EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps));
+ EXPECT_EQ(0u, ssrcs.size());
+ clock_.AdvanceTimeMilliseconds(1000);
+ EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps));
+ EXPECT_FALSE(bitrate_observer_.updated());
+ bitrate_observer_.Reset();
+ clock_.AdvanceTimeMilliseconds(1000);
+ // Inserting packets for 5 seconds to get a valid estimate.
+ for (int i = 0; i < 5 * kFramerate + 1 + kNumInitialPackets; ++i) {
+ // NOTE!!! If the following line is moved under the if case then this test
+ // wont work on windows realease bots.
+ PacedPacketInfo pacing_info =
+ i < kInitialProbingPackets ? kPacingInfo : PacedPacketInfo();
+
+ if (i == kNumInitialPackets) {
+ EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps));
+ EXPECT_EQ(0u, ssrcs.size());
+ EXPECT_FALSE(bitrate_observer_.updated());
+ bitrate_observer_.Reset();
+ }
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, kMtu, pacing_info);
+ clock_.AdvanceTimeMilliseconds(1000 / kFramerate);
+ send_time_ms += kFrameIntervalMs;
+ }
+ EXPECT_TRUE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps));
+ ASSERT_EQ(1u, ssrcs.size());
+ EXPECT_EQ(kDefaultSsrc, ssrcs.front());
+ EXPECT_NEAR(expected_converge_bitrate, bitrate_bps, kAcceptedBitrateErrorBps);
+ EXPECT_TRUE(bitrate_observer_.updated());
+ bitrate_observer_.Reset();
+ EXPECT_EQ(bitrate_observer_.latest_bitrate(), bitrate_bps);
+}
+
+void DelayBasedBweTest::RateIncreaseReorderingTestHelper(
+ uint32_t expected_bitrate_bps) {
+ const int kFramerate = 50; // 50 fps to avoid rounding errors.
+ const int kFrameIntervalMs = 1000 / kFramerate;
+ const PacedPacketInfo kPacingInfo(0, 5, 5000);
+ int64_t send_time_ms = 0;
+ uint16_t sequence_number = 0;
+ // Inserting packets for five seconds to get a valid estimate.
+ for (int i = 0; i < 5 * kFramerate + 1 + kNumInitialPackets; ++i) {
+ // NOTE!!! If the following line is moved under the if case then this test
+ // wont work on windows realease bots.
+ PacedPacketInfo pacing_info =
+ i < kInitialProbingPackets ? kPacingInfo : PacedPacketInfo();
+
+ // TODO(sprang): Remove this hack once the single stream estimator is gone,
+ // as it doesn't do anything in Process().
+ if (i == kNumInitialPackets) {
+ // Process after we have enough frames to get a valid input rate estimate.
+
+ EXPECT_FALSE(bitrate_observer_.updated()); // No valid estimate.
+ }
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, kMtu, pacing_info);
+ clock_.AdvanceTimeMilliseconds(kFrameIntervalMs);
+ send_time_ms += kFrameIntervalMs;
+ }
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_NEAR(expected_bitrate_bps, bitrate_observer_.latest_bitrate(),
+ kAcceptedBitrateErrorBps);
+ for (int i = 0; i < 10; ++i) {
+ clock_.AdvanceTimeMilliseconds(2 * kFrameIntervalMs);
+ send_time_ms += 2 * kFrameIntervalMs;
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number + 2, 1000);
+ IncomingFeedback(clock_.TimeInMilliseconds(),
+ send_time_ms - kFrameIntervalMs, sequence_number + 1,
+ 1000);
+ sequence_number += 2;
+ }
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_NEAR(expected_bitrate_bps, bitrate_observer_.latest_bitrate(),
+ kAcceptedBitrateErrorBps);
+}
+
+// Make sure we initially increase the bitrate as expected.
+void DelayBasedBweTest::RateIncreaseRtpTimestampsTestHelper(
+ int expected_iterations) {
+ // This threshold corresponds approximately to increasing linearly with
+ // bitrate(i) = 1.04 * bitrate(i-1) + 1000
+ // until bitrate(i) > 500000, with bitrate(1) ~= 30000.
+ uint32_t bitrate_bps = 30000;
+ int iterations = 0;
+ AddDefaultStream();
+ // Feed the estimator with a stream of packets and verify that it reaches
+ // 500 kbps at the expected time.
+ while (bitrate_bps < 5e5) {
+ bool overuse = GenerateAndProcessFrame(kDefaultSsrc, bitrate_bps);
+ if (overuse) {
+ EXPECT_GT(bitrate_observer_.latest_bitrate(), bitrate_bps);
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ bitrate_observer_.Reset();
+ } else if (bitrate_observer_.updated()) {
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ bitrate_observer_.Reset();
+ }
+ ++iterations;
+ }
+ ASSERT_EQ(expected_iterations, iterations);
+}
+
+void DelayBasedBweTest::CapacityDropTestHelper(
+ int number_of_streams,
+ bool wrap_time_stamp,
+ uint32_t expected_bitrate_drop_delta,
+ int64_t receiver_clock_offset_change_ms) {
+ const int kFramerate = 30;
+ const int kStartBitrate = 900e3;
+ const int kMinExpectedBitrate = 800e3;
+ const int kMaxExpectedBitrate = 1100e3;
+ const uint32_t kInitialCapacityBps = 1000e3;
+ const uint32_t kReducedCapacityBps = 500e3;
+
+ int steady_state_time = 0;
+ if (number_of_streams <= 1) {
+ steady_state_time = 10;
+ AddDefaultStream();
+ } else {
+ steady_state_time = 10 * number_of_streams;
+ int bitrate_sum = 0;
+ int kBitrateDenom = number_of_streams * (number_of_streams - 1);
+ for (int i = 0; i < number_of_streams; i++) {
+ // First stream gets half available bitrate, while the rest share the
+ // remaining half i.e.: 1/2 = Sum[n/(N*(N-1))] for n=1..N-1 (rounded up)
+ int bitrate = kStartBitrate / 2;
+ if (i > 0) {
+ bitrate = (kStartBitrate * i + kBitrateDenom / 2) / kBitrateDenom;
+ }
+ stream_generator_->AddStream(new test::RtpStream(kFramerate, bitrate));
+ bitrate_sum += bitrate;
+ }
+ ASSERT_EQ(bitrate_sum, kStartBitrate);
+ }
+
+ // Run in steady state to make the estimator converge.
+ stream_generator_->set_capacity_bps(kInitialCapacityBps);
+ uint32_t bitrate_bps = SteadyStateRun(
+ kDefaultSsrc, steady_state_time * kFramerate, kStartBitrate,
+ kMinExpectedBitrate, kMaxExpectedBitrate, kInitialCapacityBps);
+ EXPECT_NEAR(kInitialCapacityBps, bitrate_bps, 180000u);
+ bitrate_observer_.Reset();
+
+ // Add an offset to make sure the BWE can handle it.
+ arrival_time_offset_ms_ += receiver_clock_offset_change_ms;
+
+ // Reduce the capacity and verify the decrease time.
+ stream_generator_->set_capacity_bps(kReducedCapacityBps);
+ int64_t overuse_start_time = clock_.TimeInMilliseconds();
+ int64_t bitrate_drop_time = -1;
+ for (int i = 0; i < 100 * number_of_streams; ++i) {
+ GenerateAndProcessFrame(kDefaultSsrc, bitrate_bps);
+ if (bitrate_drop_time == -1 &&
+ bitrate_observer_.latest_bitrate() <= kReducedCapacityBps) {
+ bitrate_drop_time = clock_.TimeInMilliseconds();
+ }
+ if (bitrate_observer_.updated())
+ bitrate_bps = bitrate_observer_.latest_bitrate();
+ }
+
+ EXPECT_NEAR(expected_bitrate_drop_delta,
+ bitrate_drop_time - overuse_start_time, 33);
+}
+
+void DelayBasedBweTest::TestTimestampGroupingTestHelper() {
+ const int kFramerate = 50; // 50 fps to avoid rounding errors.
+ const int kFrameIntervalMs = 1000 / kFramerate;
+ int64_t send_time_ms = 0;
+ uint16_t sequence_number = 0;
+ // Initial set of frames to increase the bitrate. 6 seconds to have enough
+ // time for the first estimate to be generated and for Process() to be called.
+ for (int i = 0; i <= 6 * kFramerate; ++i) {
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, 1000);
+
+ clock_.AdvanceTimeMilliseconds(kFrameIntervalMs);
+ send_time_ms += kFrameIntervalMs;
+ }
+ EXPECT_TRUE(bitrate_observer_.updated());
+ EXPECT_GE(bitrate_observer_.latest_bitrate(), 400000u);
+
+ // Insert batches of frames which were sent very close in time. Also simulate
+ // capacity over-use to see that we back off correctly.
+ const int kTimestampGroupLength = 15;
+ for (int i = 0; i < 100; ++i) {
+ for (int j = 0; j < kTimestampGroupLength; ++j) {
+ // Insert |kTimestampGroupLength| frames with just 1 timestamp ticks in
+ // between. Should be treated as part of the same group by the estimator.
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, 100);
+ clock_.AdvanceTimeMilliseconds(kFrameIntervalMs / kTimestampGroupLength);
+ send_time_ms += 1;
+ }
+ // Increase time until next batch to simulate over-use.
+ clock_.AdvanceTimeMilliseconds(10);
+ send_time_ms += kFrameIntervalMs - kTimestampGroupLength;
+ }
+ EXPECT_TRUE(bitrate_observer_.updated());
+ // Should have reduced the estimate.
+ EXPECT_LT(bitrate_observer_.latest_bitrate(), 400000u);
+}
+
+void DelayBasedBweTest::TestWrappingHelper(int silence_time_s) {
+ const int kFramerate = 100;
+ const int kFrameIntervalMs = 1000 / kFramerate;
+ int64_t send_time_ms = 0;
+ uint16_t sequence_number = 0;
+
+ for (size_t i = 0; i < 3000; ++i) {
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, 1000);
+ clock_.AdvanceTimeMilliseconds(kFrameIntervalMs);
+ send_time_ms += kFrameIntervalMs;
+ }
+ uint32_t bitrate_before = 0;
+ std::vector<uint32_t> ssrcs;
+ bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_before);
+
+ clock_.AdvanceTimeMilliseconds(silence_time_s * 1000);
+ send_time_ms += silence_time_s * 1000;
+
+ for (size_t i = 0; i < 24; ++i) {
+ IncomingFeedback(clock_.TimeInMilliseconds(), send_time_ms,
+ sequence_number++, 1000);
+ clock_.AdvanceTimeMilliseconds(2 * kFrameIntervalMs);
+ send_time_ms += kFrameIntervalMs;
+ }
+ uint32_t bitrate_after = 0;
+ bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_after);
+ EXPECT_LT(bitrate_after, bitrate_before);
+}
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.h b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.h
new file mode 100644
index 0000000..4ccf228
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_based_bwe_unittest_helper.h
@@ -0,0 +1,180 @@
+/*
+ * 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_UNITTEST_HELPER_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_UNITTEST_HELPER_H_
+
+#include <list>
+#include <map>
+#include <memory>
+#include <utility>
+#include <vector>
+
+#include "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h"
+#include "modules/congestion_controller/goog_cc/delay_based_bwe.h"
+#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "rtc_base/constructormagic.h"
+#include "system_wrappers/include/clock.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+namespace test {
+
+class TestBitrateObserver : public RemoteBitrateObserver {
+ public:
+ TestBitrateObserver() : updated_(false), latest_bitrate_(0) {}
+ virtual ~TestBitrateObserver() {}
+
+ void OnReceiveBitrateChanged(const std::vector<uint32_t>& ssrcs,
+ uint32_t bitrate) override;
+
+ void Reset() { updated_ = false; }
+
+ bool updated() const { return updated_; }
+
+ uint32_t latest_bitrate() const { return latest_bitrate_; }
+
+ private:
+ bool updated_;
+ uint32_t latest_bitrate_;
+};
+
+class RtpStream {
+ public:
+ enum { kSendSideOffsetUs = 1000000 };
+
+ RtpStream(int fps, int bitrate_bps);
+
+ // Generates a new frame for this stream. If called too soon after the
+ // previous frame, no frame will be generated. The frame is split into
+ // packets.
+ int64_t GenerateFrame(int64_t time_now_us,
+ std::vector<PacketFeedback>* packets);
+
+ // The send-side time when the next frame can be generated.
+ int64_t next_rtp_time() const;
+
+ void set_bitrate_bps(int bitrate_bps);
+
+ int bitrate_bps() const;
+
+ static bool Compare(const std::unique_ptr<RtpStream>& lhs,
+ const std::unique_ptr<RtpStream>& rhs);
+
+ private:
+ int fps_;
+ int bitrate_bps_;
+ int64_t next_rtp_time_;
+ uint16_t sequence_number_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(RtpStream);
+};
+
+class StreamGenerator {
+ public:
+ StreamGenerator(int capacity, int64_t time_now);
+
+ // Add a new stream.
+ void AddStream(RtpStream* stream);
+
+ // Set the link capacity.
+ void set_capacity_bps(int capacity_bps);
+
+ // Divides |bitrate_bps| among all streams. The allocated bitrate per stream
+ // is decided by the initial allocation ratios.
+ void SetBitrateBps(int bitrate_bps);
+
+ // Set the RTP timestamp offset for the stream identified by |ssrc|.
+ void set_rtp_timestamp_offset(uint32_t ssrc, uint32_t offset);
+
+ // TODO(holmer): Break out the channel simulation part from this class to make
+ // it possible to simulate different types of channels.
+ int64_t GenerateFrame(std::vector<PacketFeedback>* packets,
+ int64_t time_now_us);
+
+ private:
+ // Capacity of the simulated channel in bits per second.
+ int capacity_;
+ // The time when the last packet arrived.
+ int64_t prev_arrival_time_us_;
+ // All streams being transmitted on this simulated channel.
+ std::vector<std::unique_ptr<RtpStream>> streams_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(StreamGenerator);
+};
+} // namespace test
+
+class DelayBasedBweTest : public ::testing::Test {
+ public:
+ DelayBasedBweTest();
+ virtual ~DelayBasedBweTest();
+
+ protected:
+ void AddDefaultStream();
+
+ // Helpers to insert a single packet into the delay-based BWE.
+ void IncomingFeedback(int64_t arrival_time_ms,
+ int64_t send_time_ms,
+ uint16_t sequence_number,
+ size_t payload_size);
+ void IncomingFeedback(int64_t arrival_time_ms,
+ int64_t send_time_ms,
+ uint16_t sequence_number,
+ size_t payload_size,
+ const PacedPacketInfo& pacing_info);
+
+ // Generates a frame of packets belonging to a stream at a given bitrate and
+ // with a given ssrc. The stream is pushed through a very simple simulated
+ // network, and is then given to the receive-side bandwidth estimator.
+ // Returns true if an over-use was seen, false otherwise.
+ // The StreamGenerator::updated() should be used to check for any changes in
+ // target bitrate after the call to this function.
+ bool GenerateAndProcessFrame(uint32_t ssrc, uint32_t bitrate_bps);
+
+ // Run the bandwidth estimator with a stream of |number_of_frames| frames, or
+ // until it reaches |target_bitrate|.
+ // Can for instance be used to run the estimator for some time to get it
+ // into a steady state.
+ uint32_t SteadyStateRun(uint32_t ssrc,
+ int number_of_frames,
+ uint32_t start_bitrate,
+ uint32_t min_bitrate,
+ uint32_t max_bitrate,
+ uint32_t target_bitrate);
+
+ void TestTimestampGroupingTestHelper();
+
+ void TestWrappingHelper(int silence_time_s);
+
+ void InitialBehaviorTestHelper(uint32_t expected_converge_bitrate);
+ void RateIncreaseReorderingTestHelper(uint32_t expected_bitrate);
+ void RateIncreaseRtpTimestampsTestHelper(int expected_iterations);
+ void CapacityDropTestHelper(int number_of_streams,
+ bool wrap_time_stamp,
+ uint32_t expected_bitrate_drop_delta,
+ int64_t receiver_clock_offset_change_ms);
+
+ static const uint32_t kDefaultSsrc;
+
+ SimulatedClock clock_; // Time at the receiver.
+ test::TestBitrateObserver bitrate_observer_;
+ std::unique_ptr<AcknowledgedBitrateEstimator> acknowledged_bitrate_estimator_;
+ std::unique_ptr<DelayBasedBwe> bitrate_estimator_;
+ std::unique_ptr<test::StreamGenerator> stream_generator_;
+ int64_t arrival_time_offset_ms_;
+ bool first_update_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(DelayBasedBweTest);
+};
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_BASED_BWE_UNITTEST_HELPER_H_
diff --git a/modules/congestion_controller/goog_cc/delay_increase_detector_interface.h b/modules/congestion_controller/goog_cc/delay_increase_detector_interface.h
new file mode 100644
index 0000000..d748c28
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/delay_increase_detector_interface.h
@@ -0,0 +1,39 @@
+/*
+ * Copyright (c) 2018 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.
+ */
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_INCREASE_DETECTOR_INTERFACE_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_INCREASE_DETECTOR_INTERFACE_H_
+
+#include <stdint.h>
+
+#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
+#include "rtc_base/constructormagic.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+class DelayIncreaseDetectorInterface {
+ public:
+ DelayIncreaseDetectorInterface() {}
+ virtual ~DelayIncreaseDetectorInterface() {}
+
+ // Update the detector with a new sample. The deltas should represent deltas
+ // between timestamp groups as defined by the InterArrival class.
+ virtual void Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms) = 0;
+
+ virtual BandwidthUsage State() const = 0;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(DelayIncreaseDetectorInterface);
+};
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_DELAY_INCREASE_DETECTOR_INTERFACE_H_
diff --git a/modules/congestion_controller/goog_cc/goog_cc_factory.cc b/modules/congestion_controller/goog_cc/goog_cc_factory.cc
new file mode 100644
index 0000000..ad230bc
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/goog_cc_factory.cc
@@ -0,0 +1,30 @@
+/*
+ * Copyright (c) 2018 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 "modules/congestion_controller/goog_cc/include/goog_cc_factory.h"
+
+#include "modules/congestion_controller/goog_cc/goog_cc_network_control.h"
+#include "rtc_base/ptr_util.h"
+namespace webrtc {
+GoogCcNetworkControllerFactory::GoogCcNetworkControllerFactory(
+ RtcEventLog* event_log)
+ : event_log_(event_log) {}
+
+NetworkControllerInterface::uptr GoogCcNetworkControllerFactory::Create(
+ NetworkControllerObserver* observer) {
+ return rtc::MakeUnique<webrtc_cc::GoogCcNetworkController>(event_log_,
+ observer);
+}
+
+TimeDelta GoogCcNetworkControllerFactory::GetProcessInterval() const {
+ const int64_t kUpdateIntervalMs = 25;
+ return TimeDelta::ms(kUpdateIntervalMs);
+}
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/goog_cc_network_control.cc b/modules/congestion_controller/goog_cc/goog_cc_network_control.cc
new file mode 100644
index 0000000..a360e9c
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/goog_cc_network_control.cc
@@ -0,0 +1,413 @@
+/*
+ * Copyright (c) 2018 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 "modules/congestion_controller/goog_cc/goog_cc_network_control.h"
+
+#include <algorithm>
+#include <functional>
+#include <limits>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h"
+#include "modules/congestion_controller/goog_cc/alr_detector.h"
+#include "modules/congestion_controller/goog_cc/include/goog_cc_factory.h"
+#include "modules/congestion_controller/goog_cc/probe_controller.h"
+#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
+#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/format_macros.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/ptr_util.h"
+#include "rtc_base/timeutils.h"
+#include "system_wrappers/include/field_trial.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+namespace {
+
+const char kCwndExperiment[] = "WebRTC-CwndExperiment";
+const int64_t kDefaultAcceptedQueueMs = 250;
+
+// Pacing-rate relative to our target send rate.
+// Multiplicative factor that is applied to the target bitrate to calculate
+// the number of bytes that can be transmitted per interval.
+// Increasing this factor will result in lower delays in cases of bitrate
+// overshoots from the encoder.
+const float kDefaultPaceMultiplier = 2.5f;
+
+bool CwndExperimentEnabled() {
+ std::string experiment_string =
+ webrtc::field_trial::FindFullName(kCwndExperiment);
+ // The experiment is enabled iff the field trial string begins with "Enabled".
+ return experiment_string.find("Enabled") == 0;
+}
+
+bool ReadCwndExperimentParameter(int64_t* accepted_queue_ms) {
+ RTC_DCHECK(accepted_queue_ms);
+ std::string experiment_string =
+ webrtc::field_trial::FindFullName(kCwndExperiment);
+ int parsed_values =
+ sscanf(experiment_string.c_str(), "Enabled-%" PRId64, accepted_queue_ms);
+ if (parsed_values == 1) {
+ RTC_CHECK_GE(*accepted_queue_ms, 0)
+ << "Accepted must be greater than or equal to 0.";
+ return true;
+ }
+ return false;
+}
+
+// Makes sure that the bitrate and the min, max values are in valid range.
+static void ClampBitrates(int64_t* bitrate_bps,
+ int64_t* min_bitrate_bps,
+ int64_t* max_bitrate_bps) {
+ // TODO(holmer): We should make sure the default bitrates are set to 10 kbps,
+ // and that we don't try to set the min bitrate to 0 from any applications.
+ // The congestion controller should allow a min bitrate of 0.
+ if (*min_bitrate_bps < congestion_controller::GetMinBitrateBps())
+ *min_bitrate_bps = congestion_controller::GetMinBitrateBps();
+ if (*max_bitrate_bps > 0)
+ *max_bitrate_bps = std::max(*min_bitrate_bps, *max_bitrate_bps);
+ if (*bitrate_bps > 0)
+ *bitrate_bps = std::max(*min_bitrate_bps, *bitrate_bps);
+}
+
+std::vector<PacketFeedback> ReceivedPacketsFeedbackAsRtp(
+ const TransportPacketsFeedback report) {
+ std::vector<PacketFeedback> packet_feedback_vector;
+ for (auto& fb : report.PacketsWithFeedback()) {
+ if (fb.receive_time.IsFinite()) {
+ PacketFeedback pf(fb.receive_time.ms(), 0);
+ pf.creation_time_ms = report.feedback_time.ms();
+ if (fb.sent_packet.has_value()) {
+ pf.payload_size = fb.sent_packet->size.bytes();
+ pf.pacing_info = fb.sent_packet->pacing_info;
+ pf.send_time_ms = fb.sent_packet->send_time.ms();
+ } else {
+ pf.send_time_ms = PacketFeedback::kNoSendTime;
+ }
+ packet_feedback_vector.push_back(pf);
+ }
+ }
+ return packet_feedback_vector;
+}
+
+} // namespace
+
+GoogCcNetworkController::GoogCcNetworkController(
+ RtcEventLog* event_log,
+ NetworkControllerObserver* observer)
+ : event_log_(event_log),
+ observer_(observer),
+ probe_controller_(new ProbeController(observer_)),
+ bandwidth_estimation_(
+ rtc::MakeUnique<SendSideBandwidthEstimation>(event_log_)),
+ alr_detector_(rtc::MakeUnique<AlrDetector>()),
+ delay_based_bwe_(new DelayBasedBwe(event_log_)),
+ acknowledged_bitrate_estimator_(
+ rtc::MakeUnique<AcknowledgedBitrateEstimator>()),
+ pacing_factor_(kDefaultPaceMultiplier),
+ min_pacing_rate_(DataRate::Zero()),
+ max_padding_rate_(DataRate::Zero()),
+ in_cwnd_experiment_(CwndExperimentEnabled()),
+ accepted_queue_ms_(kDefaultAcceptedQueueMs) {
+ delay_based_bwe_->SetMinBitrate(congestion_controller::GetMinBitrateBps());
+ if (in_cwnd_experiment_ &&
+ !ReadCwndExperimentParameter(&accepted_queue_ms_)) {
+ RTC_LOG(LS_WARNING) << "Failed to parse parameters for CwndExperiment "
+ "from field trial string. Experiment disabled.";
+ in_cwnd_experiment_ = false;
+ }
+}
+
+GoogCcNetworkController::~GoogCcNetworkController() {}
+
+void GoogCcNetworkController::OnNetworkAvailability(NetworkAvailability msg) {
+ probe_controller_->OnNetworkAvailability(msg);
+}
+
+void GoogCcNetworkController::OnNetworkRouteChange(NetworkRouteChange msg) {
+ int64_t min_bitrate_bps = msg.constraints.min_data_rate.bps();
+ int64_t max_bitrate_bps = -1;
+ int64_t start_bitrate_bps = -1;
+
+ if (msg.constraints.max_data_rate.IsFinite())
+ max_bitrate_bps = msg.constraints.max_data_rate.bps();
+ if (msg.constraints.starting_rate.IsFinite())
+ start_bitrate_bps = msg.constraints.starting_rate.bps();
+
+ ClampBitrates(&start_bitrate_bps, &min_bitrate_bps, &max_bitrate_bps);
+
+ bandwidth_estimation_ =
+ rtc::MakeUnique<SendSideBandwidthEstimation>(event_log_);
+ bandwidth_estimation_->SetBitrates(start_bitrate_bps, min_bitrate_bps,
+ max_bitrate_bps);
+ delay_based_bwe_.reset(new DelayBasedBwe(event_log_));
+ acknowledged_bitrate_estimator_.reset(new AcknowledgedBitrateEstimator());
+ delay_based_bwe_->SetStartBitrate(start_bitrate_bps);
+ delay_based_bwe_->SetMinBitrate(min_bitrate_bps);
+
+ probe_controller_->Reset(msg.at_time.ms());
+ probe_controller_->SetBitrates(min_bitrate_bps, start_bitrate_bps,
+ max_bitrate_bps, msg.at_time.ms());
+
+ MaybeTriggerOnNetworkChanged(msg.at_time);
+}
+
+void GoogCcNetworkController::OnProcessInterval(ProcessInterval msg) {
+ bandwidth_estimation_->UpdateEstimate(msg.at_time.ms());
+ rtc::Optional<int64_t> start_time_ms =
+ alr_detector_->GetApplicationLimitedRegionStartTime();
+ probe_controller_->SetAlrStartTimeMs(start_time_ms);
+ probe_controller_->Process(msg.at_time.ms());
+ MaybeTriggerOnNetworkChanged(msg.at_time);
+}
+
+void GoogCcNetworkController::OnRemoteBitrateReport(RemoteBitrateReport msg) {
+ bandwidth_estimation_->UpdateReceiverEstimate(msg.receive_time.ms(),
+ msg.bandwidth.bps());
+ BWE_TEST_LOGGING_PLOT(1, "REMB_kbps", msg.receive_time.ms(),
+ msg.bandwidth.bps() / 1000);
+}
+
+void GoogCcNetworkController::OnRoundTripTimeUpdate(RoundTripTimeUpdate msg) {
+ if (msg.smoothed) {
+ delay_based_bwe_->OnRttUpdate(msg.round_trip_time.ms());
+ } else {
+ bandwidth_estimation_->UpdateRtt(msg.round_trip_time.ms(),
+ msg.receive_time.ms());
+ }
+}
+
+void GoogCcNetworkController::OnSentPacket(SentPacket sent_packet) {
+ alr_detector_->OnBytesSent(sent_packet.size.bytes(),
+ sent_packet.send_time.ms());
+}
+
+void GoogCcNetworkController::OnStreamsConfig(StreamsConfig msg) {
+ probe_controller_->EnablePeriodicAlrProbing(msg.requests_alr_probing);
+
+ bool pacing_changed = false;
+ if (msg.pacing_factor && *msg.pacing_factor != pacing_factor_) {
+ pacing_factor_ = *msg.pacing_factor;
+ pacing_changed = true;
+ }
+ if (msg.min_pacing_rate && *msg.min_pacing_rate != min_pacing_rate_) {
+ min_pacing_rate_ = *msg.min_pacing_rate;
+ pacing_changed = true;
+ }
+ if (msg.max_padding_rate && *msg.max_padding_rate != max_padding_rate_) {
+ max_padding_rate_ = *msg.max_padding_rate;
+ pacing_changed = true;
+ }
+ if (pacing_changed)
+ UpdatePacingRates(msg.at_time);
+}
+
+void GoogCcNetworkController::OnTargetRateConstraints(
+ TargetRateConstraints constraints) {
+ int64_t min_bitrate_bps = constraints.min_data_rate.bps();
+ int64_t max_bitrate_bps = -1;
+ int64_t start_bitrate_bps = -1;
+
+ if (constraints.max_data_rate.IsFinite())
+ max_bitrate_bps = constraints.max_data_rate.bps();
+ if (constraints.starting_rate.IsFinite())
+ start_bitrate_bps = constraints.starting_rate.bps();
+
+ ClampBitrates(&start_bitrate_bps, &min_bitrate_bps, &max_bitrate_bps);
+
+ probe_controller_->SetBitrates(min_bitrate_bps, start_bitrate_bps,
+ max_bitrate_bps, constraints.at_time.ms());
+
+ bandwidth_estimation_->SetBitrates(start_bitrate_bps, min_bitrate_bps,
+ max_bitrate_bps);
+ if (start_bitrate_bps > 0)
+ delay_based_bwe_->SetStartBitrate(start_bitrate_bps);
+ delay_based_bwe_->SetMinBitrate(min_bitrate_bps);
+
+ MaybeTriggerOnNetworkChanged(constraints.at_time);
+}
+
+void GoogCcNetworkController::OnTransportLossReport(TransportLossReport msg) {
+ int64_t total_packets_delta =
+ msg.packets_received_delta + msg.packets_lost_delta;
+ bandwidth_estimation_->UpdatePacketsLost(
+ msg.packets_lost_delta, total_packets_delta, msg.receive_time.ms());
+}
+
+void GoogCcNetworkController::OnTransportPacketsFeedback(
+ TransportPacketsFeedback report) {
+ int64_t feedback_rtt = -1;
+ for (const auto& packet_feedback : report.PacketsWithFeedback()) {
+ if (packet_feedback.sent_packet.has_value() &&
+ packet_feedback.receive_time.IsFinite()) {
+ int64_t rtt = report.feedback_time.ms() -
+ packet_feedback.sent_packet->send_time.ms();
+ // max() is used to account for feedback being delayed by the
+ // receiver.
+ feedback_rtt = std::max(rtt, feedback_rtt);
+ }
+ }
+ if (feedback_rtt > -1) {
+ feedback_rtts_.push_back(feedback_rtt);
+ const size_t kFeedbackRttWindow = 32;
+ if (feedback_rtts_.size() > kFeedbackRttWindow)
+ feedback_rtts_.pop_front();
+ min_feedback_rtt_ms_.emplace(
+ *std::min_element(feedback_rtts_.begin(), feedback_rtts_.end()));
+ }
+
+ std::vector<PacketFeedback> received_feedback_vector =
+ ReceivedPacketsFeedbackAsRtp(report);
+
+ rtc::Optional<int64_t> alr_start_time =
+ alr_detector_->GetApplicationLimitedRegionStartTime();
+
+ if (previously_in_alr && !alr_start_time.has_value()) {
+ int64_t now_ms = report.feedback_time.ms();
+ acknowledged_bitrate_estimator_->SetAlrEndedTimeMs(now_ms);
+ probe_controller_->SetAlrEndedTimeMs(now_ms);
+ }
+ previously_in_alr = alr_start_time.has_value();
+ acknowledged_bitrate_estimator_->IncomingPacketFeedbackVector(
+ received_feedback_vector);
+ DelayBasedBwe::Result result;
+ result = delay_based_bwe_->IncomingPacketFeedbackVector(
+ received_feedback_vector, acknowledged_bitrate_estimator_->bitrate_bps(),
+ report.feedback_time.ms());
+ if (result.updated) {
+ if (result.probe) {
+ bandwidth_estimation_->SetSendBitrate(result.target_bitrate_bps);
+ }
+ // Since SetSendBitrate now resets the delay-based estimate, we have to call
+ // UpdateDelayBasedEstimate after SetSendBitrate.
+ bandwidth_estimation_->UpdateDelayBasedEstimate(report.feedback_time.ms(),
+ result.target_bitrate_bps);
+ // Update the estimate in the ProbeController, in case we want to probe.
+ MaybeTriggerOnNetworkChanged(report.feedback_time);
+ }
+ if (result.recovered_from_overuse) {
+ probe_controller_->SetAlrStartTimeMs(alr_start_time);
+ probe_controller_->RequestProbe(report.feedback_time.ms());
+ }
+ MaybeUpdateCongestionWindow();
+}
+
+void GoogCcNetworkController::MaybeUpdateCongestionWindow() {
+ if (!in_cwnd_experiment_)
+ return;
+ // No valid RTT. Could be because send-side BWE isn't used, in which case
+ // we don't try to limit the outstanding packets.
+ if (!min_feedback_rtt_ms_)
+ return;
+ if (!last_estimate_.has_value())
+ return;
+ const DataSize kMinCwnd = DataSize::bytes(2 * 1500);
+ TimeDelta time_window =
+ TimeDelta::ms(*min_feedback_rtt_ms_ + accepted_queue_ms_);
+ DataSize data_window = last_estimate_->bandwidth * time_window;
+ CongestionWindow msg;
+ msg.enabled = true;
+ msg.data_window = std::max(kMinCwnd, data_window);
+ observer_->OnCongestionWindow(msg);
+ RTC_LOG(LS_INFO) << "Feedback rtt: " << *min_feedback_rtt_ms_
+ << " Bitrate: " << last_estimate_->bandwidth.bps();
+}
+
+void GoogCcNetworkController::MaybeTriggerOnNetworkChanged(Timestamp at_time) {
+ int32_t estimated_bitrate_bps;
+ uint8_t fraction_loss;
+ int64_t rtt_ms;
+
+ bool estimate_changed = GetNetworkParameters(
+ &estimated_bitrate_bps, &fraction_loss, &rtt_ms, at_time);
+ if (estimate_changed) {
+ TimeDelta bwe_period =
+ TimeDelta::ms(delay_based_bwe_->GetExpectedBwePeriodMs());
+
+ NetworkEstimate new_estimate;
+ new_estimate.at_time = at_time;
+ new_estimate.round_trip_time = TimeDelta::ms(rtt_ms);
+ new_estimate.bandwidth = DataRate::bps(estimated_bitrate_bps);
+ new_estimate.loss_rate_ratio = fraction_loss / 255.0f;
+ new_estimate.bwe_period = bwe_period;
+ new_estimate.changed = true;
+ last_estimate_ = new_estimate;
+ OnNetworkEstimate(new_estimate);
+ }
+}
+
+bool GoogCcNetworkController::GetNetworkParameters(
+ int32_t* estimated_bitrate_bps,
+ uint8_t* fraction_loss,
+ int64_t* rtt_ms,
+ Timestamp at_time) {
+ bandwidth_estimation_->CurrentEstimate(estimated_bitrate_bps, fraction_loss,
+ rtt_ms);
+ *estimated_bitrate_bps = std::max<int32_t>(
+ *estimated_bitrate_bps, bandwidth_estimation_->GetMinBitrate());
+
+ bool estimate_changed = false;
+ if ((*estimated_bitrate_bps != last_estimated_bitrate_bps_) ||
+ (*fraction_loss != last_estimated_fraction_loss_) ||
+ (*rtt_ms != last_estimated_rtt_ms_)) {
+ last_estimated_bitrate_bps_ = *estimated_bitrate_bps;
+ last_estimated_fraction_loss_ = *fraction_loss;
+ last_estimated_rtt_ms_ = *rtt_ms;
+ estimate_changed = true;
+ }
+
+ BWE_TEST_LOGGING_PLOT(1, "fraction_loss_%", at_time.ms(),
+ (*fraction_loss * 100) / 256);
+ BWE_TEST_LOGGING_PLOT(1, "rtt_ms", at_time.ms(), *rtt_ms);
+ BWE_TEST_LOGGING_PLOT(1, "Target_bitrate_kbps", at_time.ms(),
+ *estimated_bitrate_bps / 1000);
+
+ return estimate_changed;
+}
+
+void GoogCcNetworkController::OnNetworkEstimate(NetworkEstimate estimate) {
+ if (!estimate.changed)
+ return;
+
+ UpdatePacingRates(estimate.at_time);
+ alr_detector_->SetEstimatedBitrate(estimate.bandwidth.bps());
+ probe_controller_->SetEstimatedBitrate(estimate.bandwidth.bps(),
+ estimate.at_time.ms());
+
+ TargetTransferRate target_rate;
+ target_rate.at_time = estimate.at_time;
+ // Set the target rate to the full estimated bandwidth since the estimation
+ // for legacy reasons includes target rate constraints.
+ target_rate.target_rate = estimate.bandwidth;
+ target_rate.network_estimate = estimate;
+ observer_->OnTargetTransferRate(target_rate);
+}
+
+void GoogCcNetworkController::UpdatePacingRates(Timestamp at_time) {
+ if (!last_estimate_)
+ return;
+ DataRate pacing_rate =
+ std::max(min_pacing_rate_, last_estimate_->bandwidth) * pacing_factor_;
+ DataRate padding_rate =
+ std::min(max_padding_rate_, last_estimate_->bandwidth);
+ PacerConfig msg;
+ msg.at_time = at_time;
+ msg.time_window = TimeDelta::s(1);
+ msg.data_window = pacing_rate * msg.time_window;
+ msg.pad_window = padding_rate * msg.time_window;
+ observer_->OnPacerConfig(msg);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/goog_cc_network_control.h b/modules/congestion_controller/goog_cc/goog_cc_network_control.h
new file mode 100644
index 0000000..47ae084
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/goog_cc_network_control.h
@@ -0,0 +1,94 @@
+/*
+ * Copyright (c) 2018 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_GOOG_CC_NETWORK_CONTROL_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_GOOG_CC_NETWORK_CONTROL_H_
+
+#include <stdint.h>
+#include <deque>
+#include <memory>
+#include <vector>
+
+#include "api/optional.h"
+#include "logging/rtc_event_log/rtc_event_log.h"
+#include "modules/bitrate_controller/send_side_bandwidth_estimation.h"
+#include "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator.h"
+#include "modules/congestion_controller/goog_cc/alr_detector.h"
+#include "modules/congestion_controller/goog_cc/delay_based_bwe.h"
+#include "modules/congestion_controller/goog_cc/probe_controller.h"
+#include "modules/congestion_controller/network_control/include/network_control.h"
+#include "rtc_base/constructormagic.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+class GoogCcNetworkController : public NetworkControllerInterface {
+ public:
+ GoogCcNetworkController(RtcEventLog* event_log,
+ NetworkControllerObserver* observer);
+ ~GoogCcNetworkController() override;
+
+ // NetworkControllerInterface
+ void OnNetworkAvailability(NetworkAvailability msg) override;
+ void OnNetworkRouteChange(NetworkRouteChange msg) override;
+ void OnProcessInterval(ProcessInterval msg) override;
+ void OnRemoteBitrateReport(RemoteBitrateReport msg) override;
+ void OnRoundTripTimeUpdate(RoundTripTimeUpdate msg) override;
+ void OnSentPacket(SentPacket msg) override;
+ void OnStreamsConfig(StreamsConfig msg) override;
+ void OnTargetRateConstraints(TargetRateConstraints msg) override;
+ void OnTransportLossReport(TransportLossReport msg) override;
+ void OnTransportPacketsFeedback(TransportPacketsFeedback msg) override;
+
+ private:
+ void MaybeUpdateCongestionWindow();
+ void MaybeTriggerOnNetworkChanged(Timestamp at_time);
+ bool GetNetworkParameters(int32_t* estimated_bitrate_bps,
+ uint8_t* fraction_loss,
+ int64_t* rtt_ms,
+ Timestamp at_time);
+ void OnNetworkEstimate(NetworkEstimate msg);
+ void UpdatePacingRates(Timestamp at_time);
+
+ RtcEventLog* const event_log_;
+ NetworkControllerObserver* const observer_;
+
+ const std::unique_ptr<ProbeController> probe_controller_;
+
+ std::unique_ptr<SendSideBandwidthEstimation> bandwidth_estimation_;
+ std::unique_ptr<AlrDetector> alr_detector_;
+ std::unique_ptr<DelayBasedBwe> delay_based_bwe_;
+ std::unique_ptr<AcknowledgedBitrateEstimator> acknowledged_bitrate_estimator_;
+
+ std::deque<int64_t> feedback_rtts_;
+ rtc::Optional<int64_t> min_feedback_rtt_ms_;
+
+ rtc::Optional<NetworkEstimate> last_estimate_;
+ rtc::Optional<TargetTransferRate> last_target_rate_;
+
+ int32_t last_estimated_bitrate_bps_ = 0;
+ uint8_t last_estimated_fraction_loss_ = 0;
+ int64_t last_estimated_rtt_ms_ = 0;
+
+ double pacing_factor_;
+ DataRate min_pacing_rate_;
+ DataRate max_padding_rate_;
+
+ bool in_cwnd_experiment_;
+ int64_t accepted_queue_ms_;
+ bool previously_in_alr = false;
+
+ RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(GoogCcNetworkController);
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_GOOG_CC_NETWORK_CONTROL_H_
diff --git a/modules/congestion_controller/goog_cc/include/goog_cc_factory.h b/modules/congestion_controller/goog_cc/include/goog_cc_factory.h
new file mode 100644
index 0000000..20717f9
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/include/goog_cc_factory.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright (c) 2018 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_INCLUDE_GOOG_CC_FACTORY_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_INCLUDE_GOOG_CC_FACTORY_H_
+#include "modules/congestion_controller/network_control/include/network_control.h"
+
+namespace webrtc {
+class Clock;
+class RtcEventLog;
+
+class GoogCcNetworkControllerFactory
+ : public NetworkControllerFactoryInterface {
+ public:
+ explicit GoogCcNetworkControllerFactory(RtcEventLog*);
+ NetworkControllerInterface::uptr Create(
+ NetworkControllerObserver* observer) override;
+ TimeDelta GetProcessInterval() const override;
+
+ private:
+ RtcEventLog* const event_log_;
+};
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_INCLUDE_GOOG_CC_FACTORY_H_
diff --git a/modules/congestion_controller/goog_cc/median_slope_estimator.cc b/modules/congestion_controller/goog_cc/median_slope_estimator.cc
new file mode 100644
index 0000000..3ad5e3f
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/median_slope_estimator.cc
@@ -0,0 +1,95 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/median_slope_estimator.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
+#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+constexpr unsigned int kDeltaCounterMax = 1000;
+
+MedianSlopeEstimator::MedianSlopeEstimator(size_t window_size,
+ double threshold_gain)
+ : window_size_(window_size),
+ threshold_gain_(threshold_gain),
+ num_of_deltas_(0),
+ accumulated_delay_(0),
+ delay_hist_(),
+ median_filter_(0.5),
+ trendline_(0) {}
+
+MedianSlopeEstimator::~MedianSlopeEstimator() {}
+
+MedianSlopeEstimator::DelayInfo::DelayInfo(int64_t time,
+ double delay,
+ size_t slope_count)
+ : time(time), delay(delay) {
+ slopes.reserve(slope_count);
+}
+
+MedianSlopeEstimator::DelayInfo::~DelayInfo() = default;
+
+void MedianSlopeEstimator::Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms) {
+ const double delta_ms = recv_delta_ms - send_delta_ms;
+ ++num_of_deltas_;
+ if (num_of_deltas_ > kDeltaCounterMax)
+ num_of_deltas_ = kDeltaCounterMax;
+
+ accumulated_delay_ += delta_ms;
+ BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", arrival_time_ms,
+ accumulated_delay_);
+
+ // If the window is full, remove the |window_size_| - 1 slopes that belong to
+ // the oldest point.
+ if (delay_hist_.size() == window_size_) {
+ for (double slope : delay_hist_.front().slopes) {
+ const bool success = median_filter_.Erase(slope);
+ RTC_CHECK(success);
+ }
+ delay_hist_.pop_front();
+ }
+ // Add |window_size_| - 1 new slopes.
+ for (auto& old_delay : delay_hist_) {
+ if (arrival_time_ms - old_delay.time != 0) {
+ // The C99 standard explicitly states that casts and assignments must
+ // perform the associated conversions. This means that |slope| will be
+ // a 64-bit double even if the division is computed using, e.g., 80-bit
+ // extended precision. I believe this also holds in C++ even though the
+ // C++11 standard isn't as explicit. Furthermore, there are good reasons
+ // to believe that compilers couldn't perform optimizations that break
+ // this assumption even if they wanted to.
+ double slope = (accumulated_delay_ - old_delay.delay) /
+ static_cast<double>(arrival_time_ms - old_delay.time);
+ median_filter_.Insert(slope);
+ // We want to avoid issues with different rounding mode / precision
+ // which we might get if we recomputed the slope when we remove it.
+ old_delay.slopes.push_back(slope);
+ }
+ }
+ delay_hist_.emplace_back(arrival_time_ms, accumulated_delay_,
+ window_size_ - 1);
+ // Recompute the median slope.
+ if (delay_hist_.size() == window_size_)
+ trendline_ = median_filter_.GetPercentileValue();
+
+ BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trendline_);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/median_slope_estimator.h b/modules/congestion_controller/goog_cc/median_slope_estimator.h
new file mode 100644
index 0000000..acac830
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/median_slope_estimator.h
@@ -0,0 +1,74 @@
+/*
+ * 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.
+ */
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_MEDIAN_SLOPE_ESTIMATOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_MEDIAN_SLOPE_ESTIMATOR_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <deque>
+#include <vector>
+
+#include "rtc_base/constructormagic.h"
+#include "rtc_base/numerics/percentile_filter.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+class MedianSlopeEstimator {
+ public:
+ // |window_size| is the number of points required to compute a trend line.
+ // |threshold_gain| is used to scale the trendline slope for comparison to
+ // the old threshold. Once the old estimator has been removed (or the
+ // thresholds been merged into the estimators), we can just set the
+ // threshold instead of setting a gain.
+ MedianSlopeEstimator(size_t window_size, double threshold_gain);
+ ~MedianSlopeEstimator();
+
+ // Update the estimator with a new sample. The deltas should represent deltas
+ // between timestamp groups as defined by the InterArrival class.
+ void Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms);
+
+ // Returns the estimated trend k multiplied by some gain.
+ // 0 < k < 1 -> the delay increases, queues are filling up
+ // k == 0 -> the delay does not change
+ // k < 0 -> the delay decreases, queues are being emptied
+ double trendline_slope() const { return trendline_ * threshold_gain_; }
+
+ // Returns the number of deltas which the current estimator state is based on.
+ unsigned int num_of_deltas() const { return num_of_deltas_; }
+
+ private:
+ struct DelayInfo {
+ DelayInfo(int64_t time, double delay, size_t slope_count);
+ ~DelayInfo();
+ int64_t time;
+ double delay;
+ std::vector<double> slopes;
+ };
+ // Parameters.
+ const size_t window_size_;
+ const double threshold_gain_;
+ // Used by the existing threshold.
+ unsigned int num_of_deltas_;
+ // Theil-Sen robust line fitting
+ double accumulated_delay_;
+ std::deque<DelayInfo> delay_hist_;
+ PercentileFilter<double> median_filter_;
+ double trendline_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(MedianSlopeEstimator);
+};
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_MEDIAN_SLOPE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/goog_cc/median_slope_estimator_unittest.cc b/modules/congestion_controller/goog_cc/median_slope_estimator_unittest.cc
new file mode 100644
index 0000000..c1ead91
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/median_slope_estimator_unittest.cc
@@ -0,0 +1,74 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/median_slope_estimator.h"
+#include "rtc_base/random.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+constexpr size_t kWindowSize = 20;
+constexpr double kGain = 1;
+constexpr int64_t kAvgTimeBetweenPackets = 10;
+constexpr size_t kPacketCount = 2 * kWindowSize + 1;
+
+void TestEstimator(double slope, double jitter_stddev, double tolerance) {
+ MedianSlopeEstimator estimator(kWindowSize, kGain);
+ Random random(0x1234567);
+ int64_t send_times[kPacketCount];
+ int64_t recv_times[kPacketCount];
+ int64_t send_start_time = random.Rand(1000000);
+ int64_t recv_start_time = random.Rand(1000000);
+ for (size_t i = 0; i < kPacketCount; ++i) {
+ send_times[i] = send_start_time + i * kAvgTimeBetweenPackets;
+ double latency = i * kAvgTimeBetweenPackets / (1 - slope);
+ double jitter = random.Gaussian(0, jitter_stddev);
+ recv_times[i] = recv_start_time + latency + jitter;
+ }
+ for (size_t i = 1; i < kPacketCount; ++i) {
+ double recv_delta = recv_times[i] - recv_times[i - 1];
+ double send_delta = send_times[i] - send_times[i - 1];
+ estimator.Update(recv_delta, send_delta, recv_times[i]);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), slope, tolerance);
+ }
+}
+} // namespace
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeOneHalf) {
+ TestEstimator(0.5, 0, 0.001);
+}
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeMinusOne) {
+ TestEstimator(-1, 0, 0.001);
+}
+
+TEST(MedianSlopeEstimator, PerfectLineSlopeZero) {
+ TestEstimator(0, 0, 0.001);
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeOneHalf) {
+ TestEstimator(0.5, kAvgTimeBetweenPackets / 3.0, 0.01);
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeMinusOne) {
+ TestEstimator(-1, kAvgTimeBetweenPackets / 3.0, 0.05);
+}
+
+TEST(MedianSlopeEstimator, JitteryLineSlopeZero) {
+ TestEstimator(0, kAvgTimeBetweenPackets / 3.0, 0.02);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/probe_bitrate_estimator.cc b/modules/congestion_controller/goog_cc/probe_bitrate_estimator.cc
new file mode 100644
index 0000000..5effa2f
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_bitrate_estimator.cc
@@ -0,0 +1,191 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/probe_bitrate_estimator.h"
+
+#include <algorithm>
+
+#include "logging/rtc_event_log/events/rtc_event_probe_result_failure.h"
+#include "logging/rtc_event_log/events/rtc_event_probe_result_success.h"
+#include "logging/rtc_event_log/rtc_event_log.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/numerics/safe_conversions.h"
+#include "rtc_base/ptr_util.h"
+
+namespace {
+// The minumum number of probes we need to receive feedback about in percent
+// in order to have a valid estimate.
+constexpr int kMinReceivedProbesPercent = 80;
+
+// The minumum number of bytes we need to receive feedback about in percent
+// in order to have a valid estimate.
+constexpr int kMinReceivedBytesPercent = 80;
+
+// The maximum |receive rate| / |send rate| ratio for a valid estimate.
+constexpr float kMaxValidRatio = 2.0f;
+
+// The minimum |receive rate| / |send rate| ratio assuming that the link is
+// not saturated, i.e. we assume that we will receive at least
+// kMinRatioForUnsaturatedLink * |send rate| if |send rate| is less than the
+// link capacity.
+constexpr float kMinRatioForUnsaturatedLink = 0.9f;
+
+// The target utilization of the link. If we know true link capacity
+// we'd like to send at 95% of that rate.
+constexpr float kTargetUtilizationFraction = 0.95f;
+
+// The maximum time period over 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 kMaxClusterHistoryMs = 1000;
+
+// 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 kMaxProbeIntervalMs = 1000;
+} // namespace
+
+namespace webrtc {
+namespace webrtc_cc {
+
+ProbeBitrateEstimator::ProbeBitrateEstimator(RtcEventLog* event_log)
+ : event_log_(event_log) {}
+
+ProbeBitrateEstimator::~ProbeBitrateEstimator() = default;
+
+int ProbeBitrateEstimator::HandleProbeAndEstimateBitrate(
+ const PacketFeedback& packet_feedback) {
+ int cluster_id = packet_feedback.pacing_info.probe_cluster_id;
+ RTC_DCHECK_NE(cluster_id, PacedPacketInfo::kNotAProbe);
+
+ EraseOldClusters(packet_feedback.arrival_time_ms - kMaxClusterHistoryMs);
+
+ int payload_size_bits =
+ rtc::dchecked_cast<int>(packet_feedback.payload_size * 8);
+ AggregatedCluster* cluster = &clusters_[cluster_id];
+
+ if (packet_feedback.send_time_ms < cluster->first_send_ms) {
+ cluster->first_send_ms = packet_feedback.send_time_ms;
+ }
+ if (packet_feedback.send_time_ms > cluster->last_send_ms) {
+ cluster->last_send_ms = packet_feedback.send_time_ms;
+ cluster->size_last_send = payload_size_bits;
+ }
+ if (packet_feedback.arrival_time_ms < cluster->first_receive_ms) {
+ cluster->first_receive_ms = packet_feedback.arrival_time_ms;
+ cluster->size_first_receive = payload_size_bits;
+ }
+ if (packet_feedback.arrival_time_ms > cluster->last_receive_ms) {
+ cluster->last_receive_ms = packet_feedback.arrival_time_ms;
+ }
+ cluster->size_total += payload_size_bits;
+ cluster->num_probes += 1;
+
+ RTC_DCHECK_GT(packet_feedback.pacing_info.probe_cluster_min_probes, 0);
+ RTC_DCHECK_GT(packet_feedback.pacing_info.probe_cluster_min_bytes, 0);
+
+ int min_probes = packet_feedback.pacing_info.probe_cluster_min_probes *
+ kMinReceivedProbesPercent / 100;
+ int min_bytes = packet_feedback.pacing_info.probe_cluster_min_bytes *
+ kMinReceivedBytesPercent / 100;
+ if (cluster->num_probes < min_probes || cluster->size_total < min_bytes * 8)
+ return -1;
+
+ float send_interval_ms = cluster->last_send_ms - cluster->first_send_ms;
+ float receive_interval_ms =
+ cluster->last_receive_ms - cluster->first_receive_ms;
+
+ if (send_interval_ms <= 0 || send_interval_ms > kMaxProbeIntervalMs ||
+ receive_interval_ms <= 0 || receive_interval_ms > kMaxProbeIntervalMs) {
+ RTC_LOG(LS_INFO) << "Probing unsuccessful, invalid send/receive interval"
+ << " [cluster id: " << cluster_id
+ << "] [send interval: " << send_interval_ms << " ms]"
+ << " [receive interval: " << receive_interval_ms << " ms]";
+ if (event_log_) {
+ event_log_->Log(rtc::MakeUnique<RtcEventProbeResultFailure>(
+ cluster_id, ProbeFailureReason::kInvalidSendReceiveInterval));
+ }
+ return -1;
+ }
+ // Since the |send_interval_ms| does not include the time it takes to actually
+ // send the last packet the size of the last sent packet should not be
+ // included when calculating the send bitrate.
+ RTC_DCHECK_GT(cluster->size_total, cluster->size_last_send);
+ float send_size = cluster->size_total - cluster->size_last_send;
+ float send_bps = send_size / send_interval_ms * 1000;
+
+ // Since the |receive_interval_ms| does not include the time it takes to
+ // actually receive the first packet the size of the first received packet
+ // should not be included when calculating the receive bitrate.
+ RTC_DCHECK_GT(cluster->size_total, cluster->size_first_receive);
+ float receive_size = cluster->size_total - cluster->size_first_receive;
+ float receive_bps = receive_size / receive_interval_ms * 1000;
+
+ float ratio = receive_bps / send_bps;
+ if (ratio > kMaxValidRatio) {
+ RTC_LOG(LS_INFO) << "Probing unsuccessful, receive/send ratio too high"
+ << " [cluster id: " << cluster_id
+ << "] [send: " << send_size << " bytes / "
+ << send_interval_ms << " ms = " << send_bps / 1000
+ << " kb/s]"
+ << " [receive: " << receive_size << " bytes / "
+ << receive_interval_ms << " ms = " << receive_bps / 1000
+ << " kb/s]"
+ << " [ratio: " << receive_bps / 1000 << " / "
+ << send_bps / 1000 << " = " << ratio
+ << " > kMaxValidRatio (" << kMaxValidRatio << ")]";
+ if (event_log_) {
+ event_log_->Log(rtc::MakeUnique<RtcEventProbeResultFailure>(
+ cluster_id, ProbeFailureReason::kInvalidSendReceiveRatio));
+ }
+ return -1;
+ }
+ RTC_LOG(LS_INFO) << "Probing successful"
+ << " [cluster id: " << cluster_id << "] [send: " << send_size
+ << " bytes / " << send_interval_ms
+ << " ms = " << send_bps / 1000 << " kb/s]"
+ << " [receive: " << receive_size << " bytes / "
+ << receive_interval_ms << " ms = " << receive_bps / 1000
+ << " kb/s]";
+
+ float res = std::min(send_bps, receive_bps);
+ // If we're receiving at significantly lower bitrate than we were sending at,
+ // it suggests that we've found the true capacity of the link. In this case,
+ // set the target bitrate slightly lower to not immediately overuse.
+ if (receive_bps < kMinRatioForUnsaturatedLink * send_bps) {
+ RTC_DCHECK_GT(send_bps, receive_bps);
+ res = kTargetUtilizationFraction * receive_bps;
+ }
+ if (event_log_) {
+ event_log_->Log(
+ rtc::MakeUnique<RtcEventProbeResultSuccess>(cluster_id, res));
+ }
+ estimated_bitrate_bps_ = res;
+ return *estimated_bitrate_bps_;
+}
+
+rtc::Optional<int>
+ProbeBitrateEstimator::FetchAndResetLastEstimatedBitrateBps() {
+ rtc::Optional<int> estimated_bitrate_bps = estimated_bitrate_bps_;
+ estimated_bitrate_bps_.reset();
+ return estimated_bitrate_bps;
+}
+
+void ProbeBitrateEstimator::EraseOldClusters(int64_t timestamp_ms) {
+ for (auto it = clusters_.begin(); it != clusters_.end();) {
+ if (it->second.last_receive_ms < timestamp_ms) {
+ it = clusters_.erase(it);
+ } else {
+ ++it;
+ }
+ }
+}
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/probe_bitrate_estimator.h b/modules/congestion_controller/goog_cc/probe_bitrate_estimator.h
new file mode 100644
index 0000000..23d61ee
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_bitrate_estimator.h
@@ -0,0 +1,57 @@
+/*
+ * 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_BITRATE_ESTIMATOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_BITRATE_ESTIMATOR_H_
+
+#include <limits>
+#include <map>
+
+#include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
+
+namespace webrtc {
+class RtcEventLog;
+namespace webrtc_cc {
+
+class ProbeBitrateEstimator {
+ public:
+ explicit ProbeBitrateEstimator(RtcEventLog* event_log);
+ ~ProbeBitrateEstimator();
+
+ // Should be called for every probe packet we receive feedback about.
+ // Returns the estimated bitrate if the probe completes a valid cluster.
+ int HandleProbeAndEstimateBitrate(const PacketFeedback& packet_feedback);
+
+ rtc::Optional<int> FetchAndResetLastEstimatedBitrateBps();
+
+ private:
+ struct AggregatedCluster {
+ int num_probes = 0;
+ int64_t first_send_ms = std::numeric_limits<int64_t>::max();
+ int64_t last_send_ms = 0;
+ int64_t first_receive_ms = std::numeric_limits<int64_t>::max();
+ int64_t last_receive_ms = 0;
+ int size_last_send = 0;
+ int size_first_receive = 0;
+ int size_total = 0;
+ };
+
+ // Erases old cluster data that was seen before |timestamp_ms|.
+ void EraseOldClusters(int64_t timestamp_ms);
+
+ std::map<int, AggregatedCluster> clusters_;
+ RtcEventLog* const event_log_;
+ rtc::Optional<int> estimated_bitrate_bps_;
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_BITRATE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/goog_cc/probe_bitrate_estimator_unittest.cc b/modules/congestion_controller/goog_cc/probe_bitrate_estimator_unittest.cc
new file mode 100644
index 0000000..4a74778
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_bitrate_estimator_unittest.cc
@@ -0,0 +1,223 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/probe_bitrate_estimator.h"
+
+#include <utility>
+#include <vector>
+
+#include "modules/remote_bitrate_estimator/aimd_rate_control.h"
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+constexpr int kInvalidBitrate = -1;
+constexpr int kDefaultMinProbes = 5;
+constexpr int kDefaultMinBytes = 5000;
+constexpr float kTargetUtilizationFraction = 0.95f;
+} // anonymous namespace
+
+class TestProbeBitrateEstimator : public ::testing::Test {
+ public:
+ TestProbeBitrateEstimator() : probe_bitrate_estimator_(nullptr) {}
+
+ // TODO(philipel): Use PacedPacketInfo when ProbeBitrateEstimator is rewritten
+ // to use that information.
+ void AddPacketFeedback(int probe_cluster_id,
+ size_t size_bytes,
+ int64_t send_time_ms,
+ int64_t arrival_time_ms,
+ int min_probes = kDefaultMinProbes,
+ int min_bytes = kDefaultMinBytes) {
+ PacedPacketInfo pacing_info(probe_cluster_id, min_probes, min_bytes);
+ PacketFeedback packet_feedback(arrival_time_ms, send_time_ms, 0, size_bytes,
+ pacing_info);
+ measured_bps_ =
+ probe_bitrate_estimator_.HandleProbeAndEstimateBitrate(packet_feedback);
+ }
+
+ protected:
+ int measured_bps_ = kInvalidBitrate;
+ ProbeBitrateEstimator probe_bitrate_estimator_;
+};
+
+TEST_F(TestProbeBitrateEstimator, OneCluster) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+ AddPacketFeedback(0, 1000, 30, 40);
+
+ EXPECT_NEAR(measured_bps_, 800000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, OneClusterTooFewProbes) {
+ AddPacketFeedback(0, 2000, 0, 10);
+ AddPacketFeedback(0, 2000, 10, 20);
+ AddPacketFeedback(0, 2000, 20, 30);
+
+ EXPECT_EQ(kInvalidBitrate, measured_bps_);
+}
+
+TEST_F(TestProbeBitrateEstimator, OneClusterTooFewBytes) {
+ const int kMinBytes = 6000;
+ AddPacketFeedback(0, 800, 0, 10, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 800, 10, 20, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 800, 20, 30, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 800, 30, 40, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 800, 40, 50, kDefaultMinProbes, kMinBytes);
+
+ EXPECT_EQ(kInvalidBitrate, measured_bps_);
+}
+
+TEST_F(TestProbeBitrateEstimator, SmallCluster) {
+ const int kMinBytes = 1000;
+ AddPacketFeedback(0, 150, 0, 10, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 150, 10, 20, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 150, 20, 30, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 150, 30, 40, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 150, 40, 50, kDefaultMinProbes, kMinBytes);
+ AddPacketFeedback(0, 150, 50, 60, kDefaultMinProbes, kMinBytes);
+ EXPECT_NEAR(measured_bps_, 120000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, LargeCluster) {
+ const int kMinProbes = 30;
+ const int kMinBytes = 312500;
+
+ int64_t send_time = 0;
+ int64_t receive_time = 5;
+ for (int i = 0; i < 25; ++i) {
+ AddPacketFeedback(0, 12500, send_time, receive_time, kMinProbes, kMinBytes);
+ ++send_time;
+ ++receive_time;
+ }
+ EXPECT_NEAR(measured_bps_, 100000000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, FastReceive) {
+ AddPacketFeedback(0, 1000, 0, 15);
+ AddPacketFeedback(0, 1000, 10, 30);
+ AddPacketFeedback(0, 1000, 20, 35);
+ AddPacketFeedback(0, 1000, 30, 40);
+
+ EXPECT_NEAR(measured_bps_, 800000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, TooFastReceive) {
+ AddPacketFeedback(0, 1000, 0, 19);
+ AddPacketFeedback(0, 1000, 10, 22);
+ AddPacketFeedback(0, 1000, 20, 25);
+ AddPacketFeedback(0, 1000, 40, 27);
+
+ EXPECT_EQ(measured_bps_, kInvalidBitrate);
+}
+
+TEST_F(TestProbeBitrateEstimator, SlowReceive) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 40);
+ AddPacketFeedback(0, 1000, 20, 70);
+ AddPacketFeedback(0, 1000, 30, 85);
+ // Expected send rate = 800 kbps, expected receive rate = 320 kbps.
+
+ EXPECT_NEAR(measured_bps_, kTargetUtilizationFraction * 320000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, BurstReceive) {
+ AddPacketFeedback(0, 1000, 0, 50);
+ AddPacketFeedback(0, 1000, 10, 50);
+ AddPacketFeedback(0, 1000, 20, 50);
+ AddPacketFeedback(0, 1000, 40, 50);
+
+ EXPECT_EQ(measured_bps_, kInvalidBitrate);
+}
+
+TEST_F(TestProbeBitrateEstimator, MultipleClusters) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+ AddPacketFeedback(0, 1000, 40, 60);
+ // Expected send rate = 600 kbps, expected receive rate = 480 kbps.
+ EXPECT_NEAR(measured_bps_, kTargetUtilizationFraction * 480000, 10);
+
+ AddPacketFeedback(0, 1000, 50, 60);
+ // Expected send rate = 640 kbps, expected receive rate = 640 kbps.
+ EXPECT_NEAR(measured_bps_, 640000, 10);
+
+ AddPacketFeedback(1, 1000, 60, 70);
+ AddPacketFeedback(1, 1000, 65, 77);
+ AddPacketFeedback(1, 1000, 70, 84);
+ AddPacketFeedback(1, 1000, 75, 90);
+ // Expected send rate = 1600 kbps, expected receive rate = 1200 kbps.
+
+ EXPECT_NEAR(measured_bps_, kTargetUtilizationFraction * 1200000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, IgnoreOldClusters) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+
+ AddPacketFeedback(1, 1000, 60, 70);
+ AddPacketFeedback(1, 1000, 65, 77);
+ AddPacketFeedback(1, 1000, 70, 84);
+ AddPacketFeedback(1, 1000, 75, 90);
+ // Expected send rate = 1600 kbps, expected receive rate = 1200 kbps.
+
+ EXPECT_NEAR(measured_bps_, kTargetUtilizationFraction * 1200000, 10);
+
+ // Coming in 6s later
+ AddPacketFeedback(0, 1000, 40 + 6000, 60 + 6000);
+
+ EXPECT_EQ(measured_bps_, kInvalidBitrate);
+}
+
+TEST_F(TestProbeBitrateEstimator, IgnoreSizeLastSendPacket) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+ AddPacketFeedback(0, 1000, 30, 40);
+ AddPacketFeedback(0, 1500, 40, 50);
+ // Expected send rate = 800 kbps, expected receive rate = 900 kbps.
+
+ EXPECT_NEAR(measured_bps_, 800000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, IgnoreSizeFirstReceivePacket) {
+ AddPacketFeedback(0, 1500, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+ AddPacketFeedback(0, 1000, 30, 40);
+ // Expected send rate = 933 kbps, expected receive rate = 800 kbps.
+
+ EXPECT_NEAR(measured_bps_, kTargetUtilizationFraction * 800000, 10);
+}
+
+TEST_F(TestProbeBitrateEstimator, NoLastEstimatedBitrateBps) {
+ EXPECT_FALSE(probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps());
+}
+
+TEST_F(TestProbeBitrateEstimator, FetchLastEstimatedBitrateBps) {
+ AddPacketFeedback(0, 1000, 0, 10);
+ AddPacketFeedback(0, 1000, 10, 20);
+ AddPacketFeedback(0, 1000, 20, 30);
+ AddPacketFeedback(0, 1000, 30, 40);
+
+ auto estimated_bitrate_bps =
+ probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps();
+ EXPECT_TRUE(estimated_bitrate_bps);
+ EXPECT_NEAR(*estimated_bitrate_bps, 800000, 10);
+ EXPECT_FALSE(probe_bitrate_estimator_.FetchAndResetLastEstimatedBitrateBps());
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/probe_controller.cc b/modules/congestion_controller/goog_cc/probe_controller.cc
new file mode 100644
index 0000000..b257032
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_controller.cc
@@ -0,0 +1,310 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/probe_controller.h"
+
+#include <algorithm>
+#include <initializer_list>
+
+#include "rtc_base/logging.h"
+#include "rtc_base/numerics/safe_conversions.h"
+#include "system_wrappers/include/field_trial.h"
+#include "system_wrappers/include/metrics.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+// The minimum number probing packets used.
+constexpr int kMinProbePacketsSent = 5;
+
+// The minimum probing duration in ms.
+constexpr int kMinProbeDurationMs = 15;
+
+// Maximum waiting time from the time of initiating probing to getting
+// the measured results back.
+constexpr int64_t kMaxWaitingTimeForProbingResultMs = 1000;
+
+// Value of |min_bitrate_to_probe_further_bps_| that indicates
+// further probing is disabled.
+constexpr int kExponentialProbingDisabled = 0;
+
+// Default probing bitrate limit. Applied only when the application didn't
+// specify max bitrate.
+constexpr int64_t kDefaultMaxProbingBitrateBps = 5000000;
+
+// Interval between probes when ALR periodic probing is enabled.
+constexpr int64_t kAlrPeriodicProbingIntervalMs = 5000;
+
+// Minimum probe bitrate percentage to probe further for repeated probes,
+// relative to the previous probe. For example, if 1Mbps probe results in
+// 80kbps, then we'll probe again at 1.6Mbps. In that case second probe won't be
+// sent if we get 600kbps from the first one.
+constexpr int kRepeatedProbeMinPercentage = 70;
+
+// If the bitrate drops to a factor |kBitrateDropThreshold| or lower
+// and we recover within |kBitrateDropTimeoutMs|, then we'll send
+// a probe at a fraction |kProbeFractionAfterDrop| of the original bitrate.
+constexpr double kBitrateDropThreshold = 0.66;
+constexpr int kBitrateDropTimeoutMs = 5000;
+constexpr double kProbeFractionAfterDrop = 0.85;
+
+// Timeout for probing after leaving ALR. If the bitrate drops significantly,
+// (as determined by the delay based estimator) and we leave ALR, then we will
+// send a probe if we recover within |kLeftAlrTimeoutMs| ms.
+constexpr int kAlrEndedTimeoutMs = 3000;
+
+// The expected uncertainty of probe result (as a fraction of the target probe
+// This is a limit on how often probing can be done when there is a BW
+// drop detected in ALR.
+constexpr int64_t kMinTimeBetweenAlrProbesMs = 5000;
+
+// bitrate). Used to avoid probing if the probe bitrate is close to our current
+// estimate.
+constexpr double kProbeUncertainty = 0.05;
+
+// Use probing to recover faster after large bitrate estimate drops.
+constexpr char kBweRapidRecoveryExperiment[] =
+ "WebRTC-BweRapidRecoveryExperiment";
+
+} // namespace
+
+ProbeController::ProbeController(NetworkControllerObserver* observer)
+ : observer_(observer), enable_periodic_alr_probing_(false) {
+ Reset(0);
+ in_rapid_recovery_experiment_ = webrtc::field_trial::FindFullName(
+ kBweRapidRecoveryExperiment) == "Enabled";
+}
+
+ProbeController::~ProbeController() {}
+
+void ProbeController::SetBitrates(int64_t min_bitrate_bps,
+ int64_t start_bitrate_bps,
+ int64_t max_bitrate_bps,
+ int64_t at_time_ms) {
+ if (start_bitrate_bps > 0) {
+ start_bitrate_bps_ = start_bitrate_bps;
+ estimated_bitrate_bps_ = start_bitrate_bps;
+ } else if (start_bitrate_bps_ == 0) {
+ start_bitrate_bps_ = min_bitrate_bps;
+ }
+
+ // The reason we use the variable |old_max_bitrate_pbs| is because we
+ // need to set |max_bitrate_bps_| before we call InitiateProbing.
+ int64_t old_max_bitrate_bps = max_bitrate_bps_;
+ max_bitrate_bps_ = max_bitrate_bps;
+
+ switch (state_) {
+ case State::kInit:
+ if (network_available_)
+ InitiateExponentialProbing(at_time_ms);
+ break;
+
+ case State::kWaitingForProbingResult:
+ break;
+
+ case State::kProbingComplete:
+ // If the new max bitrate is higher than the old max bitrate and the
+ // estimate is lower than the new max bitrate then initiate probing.
+ if (estimated_bitrate_bps_ != 0 &&
+ old_max_bitrate_bps < max_bitrate_bps_ &&
+ estimated_bitrate_bps_ < max_bitrate_bps_) {
+ // The assumption is that if we jump more than 20% in the bandwidth
+ // estimate or if the bandwidth estimate is within 90% of the new
+ // max bitrate then the probing attempt was successful.
+ mid_call_probing_succcess_threshold_ =
+ std::min(estimated_bitrate_bps_ * 1.2, max_bitrate_bps_ * 0.9);
+ mid_call_probing_waiting_for_result_ = true;
+ mid_call_probing_bitrate_bps_ = max_bitrate_bps_;
+
+ RTC_HISTOGRAM_COUNTS_10000("WebRTC.BWE.MidCallProbing.Initiated",
+ max_bitrate_bps_ / 1000);
+
+ InitiateProbing(at_time_ms, {max_bitrate_bps}, false);
+ }
+ break;
+ }
+}
+
+void ProbeController::OnNetworkAvailability(NetworkAvailability msg) {
+ network_available_ = msg.network_available;
+ if (network_available_ && state_ == State::kInit && start_bitrate_bps_ > 0)
+ InitiateExponentialProbing(msg.at_time.ms());
+}
+
+void ProbeController::InitiateExponentialProbing(int64_t at_time_ms) {
+ RTC_DCHECK(network_available_);
+ RTC_DCHECK(state_ == State::kInit);
+ RTC_DCHECK_GT(start_bitrate_bps_, 0);
+
+ // When probing at 1.8 Mbps ( 6x 300), this represents a threshold of
+ // 1.2 Mbps to continue probing.
+ InitiateProbing(at_time_ms, {3 * start_bitrate_bps_, 6 * start_bitrate_bps_},
+ true);
+}
+
+void ProbeController::SetEstimatedBitrate(int64_t bitrate_bps,
+ int64_t at_time_ms) {
+ int64_t now_ms = at_time_ms;
+
+ if (mid_call_probing_waiting_for_result_ &&
+ bitrate_bps >= mid_call_probing_succcess_threshold_) {
+ RTC_HISTOGRAM_COUNTS_10000("WebRTC.BWE.MidCallProbing.Success",
+ mid_call_probing_bitrate_bps_ / 1000);
+ RTC_HISTOGRAM_COUNTS_10000("WebRTC.BWE.MidCallProbing.ProbedKbps",
+ bitrate_bps / 1000);
+ mid_call_probing_waiting_for_result_ = false;
+ }
+
+ if (state_ == State::kWaitingForProbingResult) {
+ // Continue probing if probing results indicate channel has greater
+ // capacity.
+ RTC_LOG(LS_INFO) << "Measured bitrate: " << bitrate_bps
+ << " Minimum to probe further: "
+ << min_bitrate_to_probe_further_bps_;
+
+ if (min_bitrate_to_probe_further_bps_ != kExponentialProbingDisabled &&
+ bitrate_bps > min_bitrate_to_probe_further_bps_) {
+ // Double the probing bitrate.
+ InitiateProbing(now_ms, {2 * bitrate_bps}, true);
+ }
+ }
+
+ if (bitrate_bps < kBitrateDropThreshold * estimated_bitrate_bps_) {
+ time_of_last_large_drop_ms_ = now_ms;
+ bitrate_before_last_large_drop_bps_ = estimated_bitrate_bps_;
+ }
+
+ estimated_bitrate_bps_ = bitrate_bps;
+}
+
+void ProbeController::EnablePeriodicAlrProbing(bool enable) {
+ enable_periodic_alr_probing_ = enable;
+}
+
+void ProbeController::SetAlrStartTimeMs(
+ rtc::Optional<int64_t> alr_start_time_ms) {
+ alr_start_time_ms_ = alr_start_time_ms;
+}
+void ProbeController::SetAlrEndedTimeMs(int64_t alr_end_time_ms) {
+ alr_end_time_ms_.emplace(alr_end_time_ms);
+}
+
+void ProbeController::RequestProbe(int64_t at_time_ms) {
+ // Called once we have returned to normal state after a large drop in
+ // estimated bandwidth. The current response is to initiate a single probe
+ // session (if not already probing) at the previous bitrate.
+ //
+ // If the probe session fails, the assumption is that this drop was a
+ // real one from a competing flow or a network change.
+ bool in_alr = alr_start_time_ms_.has_value();
+ bool alr_ended_recently =
+ (alr_end_time_ms_.has_value() &&
+ at_time_ms - alr_end_time_ms_.value() < kAlrEndedTimeoutMs);
+ if (in_alr || alr_ended_recently || in_rapid_recovery_experiment_) {
+ if (state_ == State::kProbingComplete) {
+ uint32_t suggested_probe_bps =
+ kProbeFractionAfterDrop * bitrate_before_last_large_drop_bps_;
+ uint32_t min_expected_probe_result_bps =
+ (1 - kProbeUncertainty) * suggested_probe_bps;
+ int64_t time_since_drop_ms = at_time_ms - time_of_last_large_drop_ms_;
+ int64_t time_since_probe_ms = at_time_ms - last_bwe_drop_probing_time_ms_;
+ if (min_expected_probe_result_bps > estimated_bitrate_bps_ &&
+ time_since_drop_ms < kBitrateDropTimeoutMs &&
+ time_since_probe_ms > kMinTimeBetweenAlrProbesMs) {
+ RTC_LOG(LS_INFO) << "Detected big bandwidth drop, start probing.";
+ // Track how often we probe in response to bandwidth drop in ALR.
+ RTC_HISTOGRAM_COUNTS_10000(
+ "WebRTC.BWE.BweDropProbingIntervalInS",
+ (at_time_ms - last_bwe_drop_probing_time_ms_) / 1000);
+ InitiateProbing(at_time_ms, {suggested_probe_bps}, false);
+ last_bwe_drop_probing_time_ms_ = at_time_ms;
+ }
+ }
+ }
+}
+
+void ProbeController::Reset(int64_t at_time_ms) {
+ network_available_ = true;
+ state_ = State::kInit;
+ min_bitrate_to_probe_further_bps_ = kExponentialProbingDisabled;
+ time_last_probing_initiated_ms_ = 0;
+ estimated_bitrate_bps_ = 0;
+ start_bitrate_bps_ = 0;
+ max_bitrate_bps_ = 0;
+ int64_t now_ms = at_time_ms;
+ last_bwe_drop_probing_time_ms_ = now_ms;
+ alr_end_time_ms_.reset();
+ mid_call_probing_waiting_for_result_ = false;
+ time_of_last_large_drop_ms_ = now_ms;
+ bitrate_before_last_large_drop_bps_ = 0;
+}
+
+void ProbeController::Process(int64_t at_time_ms) {
+ int64_t now_ms = at_time_ms;
+
+ if (now_ms - time_last_probing_initiated_ms_ >
+ kMaxWaitingTimeForProbingResultMs) {
+ mid_call_probing_waiting_for_result_ = false;
+
+ if (state_ == State::kWaitingForProbingResult) {
+ RTC_LOG(LS_INFO) << "kWaitingForProbingResult: timeout";
+ state_ = State::kProbingComplete;
+ min_bitrate_to_probe_further_bps_ = kExponentialProbingDisabled;
+ }
+ }
+
+ if (state_ != State::kProbingComplete || !enable_periodic_alr_probing_)
+ return;
+
+ // Probe bandwidth periodically when in ALR state.
+ if (alr_start_time_ms_ && estimated_bitrate_bps_ > 0) {
+ int64_t next_probe_time_ms =
+ std::max(*alr_start_time_ms_, time_last_probing_initiated_ms_) +
+ kAlrPeriodicProbingIntervalMs;
+ if (now_ms >= next_probe_time_ms) {
+ InitiateProbing(now_ms, {estimated_bitrate_bps_ * 2}, true);
+ }
+ }
+}
+
+void ProbeController::InitiateProbing(
+ int64_t now_ms,
+ std::initializer_list<int64_t> bitrates_to_probe,
+ bool probe_further) {
+ for (int64_t bitrate : bitrates_to_probe) {
+ RTC_DCHECK_GT(bitrate, 0);
+ int64_t max_probe_bitrate_bps =
+ max_bitrate_bps_ > 0 ? max_bitrate_bps_ : kDefaultMaxProbingBitrateBps;
+ if (bitrate > max_probe_bitrate_bps) {
+ bitrate = max_probe_bitrate_bps;
+ probe_further = false;
+ }
+
+ ProbeClusterConfig config;
+ config.at_time = Timestamp::ms(now_ms);
+ config.target_data_rate = DataRate::bps(rtc::dchecked_cast<int>(bitrate));
+ config.target_duration = TimeDelta::ms(kMinProbeDurationMs);
+ config.target_probe_count = kMinProbePacketsSent;
+ observer_->OnProbeClusterConfig(config);
+ }
+ time_last_probing_initiated_ms_ = now_ms;
+ if (probe_further) {
+ state_ = State::kWaitingForProbingResult;
+ min_bitrate_to_probe_further_bps_ =
+ (*(bitrates_to_probe.end() - 1)) * kRepeatedProbeMinPercentage / 100;
+ } else {
+ state_ = State::kProbingComplete;
+ min_bitrate_to_probe_further_bps_ = kExponentialProbingDisabled;
+ }
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/probe_controller.h b/modules/congestion_controller/goog_cc/probe_controller.h
new file mode 100644
index 0000000..23fc4f7
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_controller.h
@@ -0,0 +1,100 @@
+/*
+ * 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.
+ */
+
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_CONTROLLER_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_CONTROLLER_H_
+
+#include <stdint.h>
+
+#include <initializer_list>
+
+#include "api/optional.h"
+#include "modules/congestion_controller/network_control/include/network_control.h"
+
+namespace webrtc {
+
+class Clock;
+
+namespace webrtc_cc {
+
+// This class controls initiation of probing to estimate initial channel
+// capacity. There is also support for probing during a session when max
+// bitrate is adjusted by an application.
+class ProbeController {
+ public:
+ explicit ProbeController(NetworkControllerObserver* observer);
+ ~ProbeController();
+
+ void SetBitrates(int64_t min_bitrate_bps,
+ int64_t start_bitrate_bps,
+ int64_t max_bitrate_bps,
+ int64_t at_time_ms);
+
+ void OnNetworkAvailability(NetworkAvailability msg);
+
+ void SetEstimatedBitrate(int64_t bitrate_bps, int64_t at_time_ms);
+
+ void EnablePeriodicAlrProbing(bool enable);
+
+ void SetAlrStartTimeMs(rtc::Optional<int64_t> alr_start_time);
+ void SetAlrEndedTimeMs(int64_t alr_end_time);
+
+ void RequestProbe(int64_t at_time_ms);
+
+ // Resets the ProbeController to a state equivalent to as if it was just
+ // created EXCEPT for |enable_periodic_alr_probing_|.
+ void Reset(int64_t at_time_ms);
+
+ void Process(int64_t at_time_ms);
+
+ private:
+ enum class State {
+ // Initial state where no probing has been triggered yet.
+ kInit,
+ // Waiting for probing results to continue further probing.
+ kWaitingForProbingResult,
+ // Probing is complete.
+ kProbingComplete,
+ };
+
+ void InitiateExponentialProbing(int64_t at_time_ms);
+ void InitiateProbing(int64_t now_ms,
+ std::initializer_list<int64_t> bitrates_to_probe,
+ bool probe_further);
+
+ NetworkControllerObserver* const observer_;
+
+ bool network_available_;
+ State state_;
+ int64_t min_bitrate_to_probe_further_bps_;
+ int64_t time_last_probing_initiated_ms_;
+ int64_t estimated_bitrate_bps_;
+ int64_t start_bitrate_bps_;
+ int64_t max_bitrate_bps_;
+ int64_t last_bwe_drop_probing_time_ms_;
+ rtc::Optional<int64_t> alr_start_time_ms_;
+ rtc::Optional<int64_t> alr_end_time_ms_;
+ bool enable_periodic_alr_probing_;
+ int64_t time_of_last_large_drop_ms_;
+ int64_t bitrate_before_last_large_drop_bps_;
+
+ bool in_rapid_recovery_experiment_;
+ // For WebRTC.BWE.MidCallProbing.* metric.
+ bool mid_call_probing_waiting_for_result_;
+ int64_t mid_call_probing_bitrate_bps_;
+ int64_t mid_call_probing_succcess_threshold_;
+
+ RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(ProbeController);
+};
+
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_PROBE_CONTROLLER_H_
diff --git a/modules/congestion_controller/goog_cc/probe_controller_unittest.cc b/modules/congestion_controller/goog_cc/probe_controller_unittest.cc
new file mode 100644
index 0000000..7ac6b3f
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/probe_controller_unittest.cc
@@ -0,0 +1,292 @@
+/*
+ * 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 <memory>
+
+#include "modules/congestion_controller/goog_cc/probe_controller.h"
+#include "modules/congestion_controller/network_control/include/network_types.h"
+#include "rtc_base/logging.h"
+#include "system_wrappers/include/clock.h"
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+using testing::_;
+using testing::AtLeast;
+using testing::Field;
+using testing::Matcher;
+using testing::NiceMock;
+using testing::Return;
+
+namespace webrtc {
+namespace webrtc_cc {
+namespace test {
+
+namespace {
+
+constexpr int kMinBitrateBps = 100;
+constexpr int kStartBitrateBps = 300;
+constexpr int kMaxBitrateBps = 10000;
+
+constexpr int kExponentialProbingTimeoutMs = 5000;
+
+constexpr int kAlrProbeInterval = 5000;
+constexpr int kAlrEndedTimeoutMs = 3000;
+constexpr int kBitrateDropTimeoutMs = 5000;
+
+inline Matcher<ProbeClusterConfig> DataRateEqBps(int bps) {
+ return Field(&ProbeClusterConfig::target_data_rate, DataRate::bps(bps));
+}
+class MockNetworkControllerObserver : public NetworkControllerObserver {
+ public:
+ MOCK_METHOD1(OnCongestionWindow, void(CongestionWindow));
+ MOCK_METHOD1(OnPacerConfig, void(PacerConfig));
+ MOCK_METHOD1(OnProbeClusterConfig, void(ProbeClusterConfig));
+ MOCK_METHOD1(OnTargetTransferRate, void(TargetTransferRate));
+};
+} // namespace
+
+class ProbeControllerTest : public ::testing::Test {
+ protected:
+ ProbeControllerTest() : clock_(100000000L) {
+ probe_controller_.reset(new ProbeController(&cluster_handler_));
+ }
+ ~ProbeControllerTest() override {}
+
+ void SetNetworkAvailable(bool available) {
+ NetworkAvailability msg;
+ msg.at_time = Timestamp::ms(NowMs());
+ msg.network_available = available;
+ probe_controller_->OnNetworkAvailability(msg);
+ }
+
+ int64_t NowMs() { return clock_.TimeInMilliseconds(); }
+
+ SimulatedClock clock_;
+ NiceMock<MockNetworkControllerObserver> cluster_handler_;
+ std::unique_ptr<ProbeController> probe_controller_;
+};
+
+TEST_F(ProbeControllerTest, InitiatesProbingAtStart) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(AtLeast(2));
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+}
+
+TEST_F(ProbeControllerTest, ProbeOnlyWhenNetworkIsUp) {
+ SetNetworkAvailable(false);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(AtLeast(2));
+ SetNetworkAvailable(true);
+}
+
+TEST_F(ProbeControllerTest, InitiatesProbingOnMaxBitrateIncrease) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(AtLeast(2));
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ // Long enough to time out exponential probing.
+ clock_.AdvanceTimeMilliseconds(kExponentialProbingTimeoutMs);
+ probe_controller_->SetEstimatedBitrate(kStartBitrateBps, NowMs());
+ probe_controller_->Process(NowMs());
+
+ EXPECT_CALL(cluster_handler_,
+ OnProbeClusterConfig(DataRateEqBps(kMaxBitrateBps + 100)));
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps + 100, NowMs());
+}
+
+TEST_F(ProbeControllerTest, InitiatesProbingOnMaxBitrateIncreaseAtMaxBitrate) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(AtLeast(2));
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ // Long enough to time out exponential probing.
+ clock_.AdvanceTimeMilliseconds(kExponentialProbingTimeoutMs);
+ probe_controller_->SetEstimatedBitrate(kStartBitrateBps, NowMs());
+ probe_controller_->Process(NowMs());
+
+ probe_controller_->SetEstimatedBitrate(kMaxBitrateBps, NowMs());
+ EXPECT_CALL(cluster_handler_,
+ OnProbeClusterConfig(DataRateEqBps(kMaxBitrateBps + 100)));
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps + 100, NowMs());
+}
+
+TEST_F(ProbeControllerTest, TestExponentialProbing) {
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+
+ // Repeated probe should only be sent when estimated bitrate climbs above
+ // 0.7 * 6 * kStartBitrateBps = 1260.
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetEstimatedBitrate(1000, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(DataRateEqBps(2 * 1800)));
+ probe_controller_->SetEstimatedBitrate(1800, NowMs());
+}
+
+TEST_F(ProbeControllerTest, TestExponentialProbingTimeout) {
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+
+ // Advance far enough to cause a time out in waiting for probing result.
+ clock_.AdvanceTimeMilliseconds(kExponentialProbingTimeoutMs);
+ probe_controller_->Process(NowMs());
+
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetEstimatedBitrate(1800, NowMs());
+}
+
+TEST_F(ProbeControllerTest, RequestProbeInAlr) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(DataRateEqBps(0.85 * 500)))
+ .Times(1);
+ probe_controller_->SetAlrStartTimeMs(clock_.TimeInMilliseconds());
+ clock_.AdvanceTimeMilliseconds(kAlrProbeInterval + 1);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(250, NowMs());
+ probe_controller_->RequestProbe(NowMs());
+}
+
+TEST_F(ProbeControllerTest, RequestProbeWhenAlrEndedRecently) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(DataRateEqBps(0.85 * 500)))
+ .Times(1);
+ probe_controller_->SetAlrStartTimeMs(rtc::nullopt);
+ clock_.AdvanceTimeMilliseconds(kAlrProbeInterval + 1);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(250, NowMs());
+ probe_controller_->SetAlrEndedTimeMs(clock_.TimeInMilliseconds());
+ clock_.AdvanceTimeMilliseconds(kAlrEndedTimeoutMs - 1);
+ probe_controller_->RequestProbe(NowMs());
+}
+
+TEST_F(ProbeControllerTest, RequestProbeWhenAlrNotEndedRecently) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetAlrStartTimeMs(rtc::nullopt);
+ clock_.AdvanceTimeMilliseconds(kAlrProbeInterval + 1);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(250, NowMs());
+ probe_controller_->SetAlrEndedTimeMs(clock_.TimeInMilliseconds());
+ clock_.AdvanceTimeMilliseconds(kAlrEndedTimeoutMs + 1);
+ probe_controller_->RequestProbe(NowMs());
+}
+
+TEST_F(ProbeControllerTest, RequestProbeWhenBweDropNotRecent) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetAlrStartTimeMs(clock_.TimeInMilliseconds());
+ clock_.AdvanceTimeMilliseconds(kAlrProbeInterval + 1);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(250, NowMs());
+ clock_.AdvanceTimeMilliseconds(kBitrateDropTimeoutMs + 1);
+ probe_controller_->RequestProbe(NowMs());
+}
+
+TEST_F(ProbeControllerTest, PeriodicProbing) {
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->EnablePeriodicAlrProbing(true);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+
+ int64_t start_time = clock_.TimeInMilliseconds();
+
+ // Expect the controller to send a new probe after 5s has passed.
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(DataRateEqBps(1000)))
+ .Times(1);
+ probe_controller_->SetAlrStartTimeMs(start_time);
+ clock_.AdvanceTimeMilliseconds(5000);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+
+ // The following probe should be sent at 10s into ALR.
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetAlrStartTimeMs(start_time);
+ clock_.AdvanceTimeMilliseconds(4000);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(1);
+ probe_controller_->SetAlrStartTimeMs(start_time);
+ clock_.AdvanceTimeMilliseconds(1000);
+ probe_controller_->Process(NowMs());
+ probe_controller_->SetEstimatedBitrate(500, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+}
+
+TEST_F(ProbeControllerTest, PeriodicProbingAfterReset) {
+ NiceMock<MockNetworkControllerObserver> local_handler;
+ probe_controller_.reset(new ProbeController(&local_handler));
+ int64_t alr_start_time = clock_.TimeInMilliseconds();
+
+ probe_controller_->SetAlrStartTimeMs(alr_start_time);
+ EXPECT_CALL(local_handler, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->EnablePeriodicAlrProbing(true);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+ probe_controller_->Reset(NowMs());
+
+ clock_.AdvanceTimeMilliseconds(10000);
+ probe_controller_->Process(NowMs());
+
+ EXPECT_CALL(local_handler, OnProbeClusterConfig(_)).Times(2);
+ probe_controller_->SetBitrates(kMinBitrateBps, kStartBitrateBps,
+ kMaxBitrateBps, NowMs());
+
+ // Make sure we use |kStartBitrateBps| as the estimated bitrate
+ // until SetEstimatedBitrate is called with an updated estimate.
+ clock_.AdvanceTimeMilliseconds(10000);
+ EXPECT_CALL(local_handler,
+ OnProbeClusterConfig(DataRateEqBps(kStartBitrateBps * 2)));
+ probe_controller_->Process(NowMs());
+}
+
+TEST_F(ProbeControllerTest, TestExponentialProbingOverflow) {
+ const int64_t kMbpsMultiplier = 1000000;
+ probe_controller_->SetBitrates(kMinBitrateBps, 10 * kMbpsMultiplier,
+ 100 * kMbpsMultiplier, NowMs());
+
+ // Verify that probe bitrate is capped at the specified max bitrate.
+ EXPECT_CALL(cluster_handler_,
+ OnProbeClusterConfig(DataRateEqBps(100 * kMbpsMultiplier)));
+ probe_controller_->SetEstimatedBitrate(60 * kMbpsMultiplier, NowMs());
+ testing::Mock::VerifyAndClearExpectations(&cluster_handler_);
+
+ // Verify that repeated probes aren't sent.
+ EXPECT_CALL(cluster_handler_, OnProbeClusterConfig(_)).Times(0);
+ probe_controller_->SetEstimatedBitrate(100 * kMbpsMultiplier, NowMs());
+}
+
+} // namespace test
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/trendline_estimator.cc b/modules/congestion_controller/goog_cc/trendline_estimator.cc
new file mode 100644
index 0000000..0dfa822
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/trendline_estimator.cc
@@ -0,0 +1,185 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/trendline_estimator.h"
+
+#include <math.h>
+
+#include <algorithm>
+
+#include "api/optional.h"
+#include "modules/remote_bitrate_estimator/test/bwe_test_logging.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/safe_minmax.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+rtc::Optional<double> LinearFitSlope(
+ const std::deque<std::pair<double, double>>& points) {
+ RTC_DCHECK(points.size() >= 2);
+ // Compute the "center of mass".
+ double sum_x = 0;
+ double sum_y = 0;
+ for (const auto& point : points) {
+ sum_x += point.first;
+ sum_y += point.second;
+ }
+ double x_avg = sum_x / points.size();
+ double y_avg = sum_y / points.size();
+ // Compute the slope k = \sum (x_i-x_avg)(y_i-y_avg) / \sum (x_i-x_avg)^2
+ double numerator = 0;
+ double denominator = 0;
+ for (const auto& point : points) {
+ numerator += (point.first - x_avg) * (point.second - y_avg);
+ denominator += (point.first - x_avg) * (point.first - x_avg);
+ }
+ if (denominator == 0)
+ return rtc::nullopt;
+ return numerator / denominator;
+}
+
+constexpr double kMaxAdaptOffsetMs = 15.0;
+constexpr double kOverUsingTimeThreshold = 10;
+constexpr int kMinNumDeltas = 60;
+
+} // namespace
+
+enum { kDeltaCounterMax = 1000 };
+
+TrendlineEstimator::TrendlineEstimator(size_t window_size,
+ double smoothing_coef,
+ double threshold_gain)
+ : window_size_(window_size),
+ smoothing_coef_(smoothing_coef),
+ threshold_gain_(threshold_gain),
+ num_of_deltas_(0),
+ first_arrival_time_ms_(-1),
+ accumulated_delay_(0),
+ smoothed_delay_(0),
+ delay_hist_(),
+ trendline_(0),
+ k_up_(0.0087),
+ k_down_(0.039),
+ overusing_time_threshold_(kOverUsingTimeThreshold),
+ threshold_(12.5),
+ last_update_ms_(-1),
+ prev_offset_(0.0),
+ time_over_using_(-1),
+ overuse_counter_(0),
+ hypothesis_(BandwidthUsage::kBwNormal) {}
+
+TrendlineEstimator::~TrendlineEstimator() {}
+
+void TrendlineEstimator::Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms) {
+ const double delta_ms = recv_delta_ms - send_delta_ms;
+ ++num_of_deltas_;
+ if (num_of_deltas_ > kDeltaCounterMax)
+ num_of_deltas_ = kDeltaCounterMax;
+ if (first_arrival_time_ms_ == -1)
+ first_arrival_time_ms_ = arrival_time_ms;
+
+ // Exponential backoff filter.
+ accumulated_delay_ += delta_ms;
+ BWE_TEST_LOGGING_PLOT(1, "accumulated_delay_ms", arrival_time_ms,
+ accumulated_delay_);
+ smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
+ (1 - smoothing_coef_) * accumulated_delay_;
+ BWE_TEST_LOGGING_PLOT(1, "smoothed_delay_ms", arrival_time_ms,
+ smoothed_delay_);
+
+ // Simple linear regression.
+ delay_hist_.push_back(std::make_pair(
+ static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
+ smoothed_delay_));
+ if (delay_hist_.size() > window_size_)
+ delay_hist_.pop_front();
+ if (delay_hist_.size() == window_size_) {
+ // Only update trendline_ if it is possible to fit a line to the data.
+ trendline_ = LinearFitSlope(delay_hist_).value_or(trendline_);
+ }
+
+ BWE_TEST_LOGGING_PLOT(1, "trendline_slope", arrival_time_ms, trendline_);
+
+ Detect(trendline_slope(), send_delta_ms, num_of_deltas(), arrival_time_ms);
+}
+
+BandwidthUsage TrendlineEstimator::State() const {
+ return hypothesis_;
+}
+
+void TrendlineEstimator::Detect(double offset,
+ double ts_delta,
+ int num_of_deltas,
+ int64_t now_ms) {
+ if (num_of_deltas < 2) {
+ hypothesis_ = BandwidthUsage::kBwNormal;
+ return;
+ }
+ const double T = std::min(num_of_deltas, kMinNumDeltas) * offset;
+ BWE_TEST_LOGGING_PLOT(1, "T", now_ms, T);
+ BWE_TEST_LOGGING_PLOT(1, "threshold", now_ms, threshold_);
+ if (T > threshold_) {
+ if (time_over_using_ == -1) {
+ // Initialize the timer. Assume that we've been
+ // over-using half of the time since the previous
+ // sample.
+ time_over_using_ = ts_delta / 2;
+ } else {
+ // Increment timer
+ time_over_using_ += ts_delta;
+ }
+ overuse_counter_++;
+ if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
+ if (offset >= prev_offset_) {
+ time_over_using_ = 0;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwOverusing;
+ }
+ }
+ } else if (T < -threshold_) {
+ time_over_using_ = -1;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwUnderusing;
+ } else {
+ time_over_using_ = -1;
+ overuse_counter_ = 0;
+ hypothesis_ = BandwidthUsage::kBwNormal;
+ }
+ prev_offset_ = offset;
+
+ UpdateThreshold(T, now_ms);
+}
+
+void TrendlineEstimator::UpdateThreshold(double modified_offset,
+ int64_t now_ms) {
+ if (last_update_ms_ == -1)
+ last_update_ms_ = now_ms;
+
+ if (fabs(modified_offset) > threshold_ + kMaxAdaptOffsetMs) {
+ // Avoid adapting the threshold to big latency spikes, caused e.g.,
+ // by a sudden capacity drop.
+ last_update_ms_ = now_ms;
+ return;
+ }
+
+ const double k = fabs(modified_offset) < threshold_ ? k_down_ : k_up_;
+ const int64_t kMaxTimeDeltaMs = 100;
+ int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
+ threshold_ += k * (fabs(modified_offset) - threshold_) * time_delta_ms;
+ threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
+ last_update_ms_ = now_ms;
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc
diff --git a/modules/congestion_controller/goog_cc/trendline_estimator.h b/modules/congestion_controller/goog_cc/trendline_estimator.h
new file mode 100644
index 0000000..162c174
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/trendline_estimator.h
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+#ifndef MODULES_CONGESTION_CONTROLLER_GOOG_CC_TRENDLINE_ESTIMATOR_H_
+#define MODULES_CONGESTION_CONTROLLER_GOOG_CC_TRENDLINE_ESTIMATOR_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <deque>
+#include <utility>
+
+#include "modules/congestion_controller/goog_cc/delay_increase_detector_interface.h"
+#include "rtc_base/constructormagic.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+class TrendlineEstimator : public DelayIncreaseDetectorInterface {
+ public:
+ // |window_size| is the number of points required to compute a trend line.
+ // |smoothing_coef| controls how much we smooth out the delay before fitting
+ // the trend line. |threshold_gain| is used to scale the trendline slope for
+ // comparison to the old threshold. Once the old estimator has been removed
+ // (or the thresholds been merged into the estimators), we can just set the
+ // threshold instead of setting a gain.
+ TrendlineEstimator(size_t window_size,
+ double smoothing_coef,
+ double threshold_gain);
+
+ ~TrendlineEstimator() override;
+
+ // Update the estimator with a new sample. The deltas should represent deltas
+ // between timestamp groups as defined by the InterArrival class.
+ void Update(double recv_delta_ms,
+ double send_delta_ms,
+ int64_t arrival_time_ms) override;
+
+ BandwidthUsage State() const override;
+
+ // Returns the estimated trend k multiplied by some gain.
+ // 0 < k < 1 -> the delay increases, queues are filling up
+ // k == 0 -> the delay does not change
+ // k < 0 -> the delay decreases, queues are being emptied
+ double trendline_slope() const { return trendline_ * threshold_gain_; }
+
+ // Returns the number of deltas which the current estimator state is based on.
+ unsigned int num_of_deltas() const { return num_of_deltas_; }
+
+ private:
+ void Detect(double offset,
+ double ts_delta,
+ int num_of_deltas,
+ int64_t now_ms);
+
+ void UpdateThreshold(double modified_offset, int64_t now_ms);
+
+ // Parameters.
+ const size_t window_size_;
+ const double smoothing_coef_;
+ const double threshold_gain_;
+ // Used by the existing threshold.
+ unsigned int num_of_deltas_;
+ // Keep the arrival times small by using the change from the first packet.
+ int64_t first_arrival_time_ms_;
+ // Exponential backoff filtering.
+ double accumulated_delay_;
+ double smoothed_delay_;
+ // Linear least squares regression.
+ std::deque<std::pair<double, double>> delay_hist_;
+ double trendline_;
+
+ const double k_up_;
+ const double k_down_;
+ double overusing_time_threshold_;
+ double threshold_;
+ int64_t last_update_ms_;
+ double prev_offset_;
+ double time_over_using_;
+ int overuse_counter_;
+ BandwidthUsage hypothesis_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(TrendlineEstimator);
+};
+} // namespace webrtc_cc
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_GOOG_CC_TRENDLINE_ESTIMATOR_H_
diff --git a/modules/congestion_controller/goog_cc/trendline_estimator_unittest.cc b/modules/congestion_controller/goog_cc/trendline_estimator_unittest.cc
new file mode 100644
index 0000000..376f277
--- /dev/null
+++ b/modules/congestion_controller/goog_cc/trendline_estimator_unittest.cc
@@ -0,0 +1,75 @@
+/*
+ * 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 "modules/congestion_controller/goog_cc/trendline_estimator.h"
+#include "rtc_base/random.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace webrtc_cc {
+
+namespace {
+constexpr size_t kWindowSize = 20;
+constexpr double kSmoothing = 0.0;
+constexpr double kGain = 1;
+constexpr int64_t kAvgTimeBetweenPackets = 10;
+constexpr size_t kPacketCount = 2 * kWindowSize + 1;
+
+void TestEstimator(double slope, double jitter_stddev, double tolerance) {
+ TrendlineEstimator estimator(kWindowSize, kSmoothing, kGain);
+ Random random(0x1234567);
+ int64_t send_times[kPacketCount];
+ int64_t recv_times[kPacketCount];
+ int64_t send_start_time = random.Rand(1000000);
+ int64_t recv_start_time = random.Rand(1000000);
+ for (size_t i = 0; i < kPacketCount; ++i) {
+ send_times[i] = send_start_time + i * kAvgTimeBetweenPackets;
+ double latency = i * kAvgTimeBetweenPackets / (1 - slope);
+ double jitter = random.Gaussian(0, jitter_stddev);
+ recv_times[i] = recv_start_time + latency + jitter;
+ }
+ for (size_t i = 1; i < kPacketCount; ++i) {
+ double recv_delta = recv_times[i] - recv_times[i - 1];
+ double send_delta = send_times[i] - send_times[i - 1];
+ estimator.Update(recv_delta, send_delta, recv_times[i]);
+ if (i < kWindowSize)
+ EXPECT_NEAR(estimator.trendline_slope(), 0, 0.001);
+ else
+ EXPECT_NEAR(estimator.trendline_slope(), slope, tolerance);
+ }
+}
+} // namespace
+
+TEST(TrendlineEstimator, PerfectLineSlopeOneHalf) {
+ TestEstimator(0.5, 0, 0.001);
+}
+
+TEST(TrendlineEstimator, PerfectLineSlopeMinusOne) {
+ TestEstimator(-1, 0, 0.001);
+}
+
+TEST(TrendlineEstimator, PerfectLineSlopeZero) {
+ TestEstimator(0, 0, 0.001);
+}
+
+TEST(TrendlineEstimator, JitteryLineSlopeOneHalf) {
+ TestEstimator(0.5, kAvgTimeBetweenPackets / 3.0, 0.01);
+}
+
+TEST(TrendlineEstimator, JitteryLineSlopeMinusOne) {
+ TestEstimator(-1, kAvgTimeBetweenPackets / 3.0, 0.075);
+}
+
+TEST(TrendlineEstimator, JitteryLineSlopeZero) {
+ TestEstimator(0, kAvgTimeBetweenPackets / 3.0, 0.02);
+}
+
+} // namespace webrtc_cc
+} // namespace webrtc