diff options
Diffstat (limited to 'third_party/libwebrtc/modules/congestion_controller/pcc')
18 files changed, 2157 insertions, 0 deletions
diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/BUILD.gn b/third_party/libwebrtc/modules/congestion_controller/pcc/BUILD.gn new file mode 100644 index 0000000000..85b12b3771 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/BUILD.gn @@ -0,0 +1,123 @@ +# 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") + +rtc_library("pcc") { + sources = [ + "pcc_factory.cc", + "pcc_factory.h", + ] + deps = [ + ":pcc_controller", + "../../../api/transport:network_control", + "../../../api/units:time_delta", + ] +} + +rtc_library("pcc_controller") { + sources = [ + "pcc_network_controller.cc", + "pcc_network_controller.h", + ] + deps = [ + ":bitrate_controller", + ":monitor_interval", + ":rtt_tracker", + "../../../api/transport:network_control", + "../../../api/units:data_rate", + "../../../api/units:data_size", + "../../../api/units:time_delta", + "../../../api/units:timestamp", + "../../../rtc_base:checks", + "../../../rtc_base:random", + ] + absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] +} + +rtc_library("monitor_interval") { + sources = [ + "monitor_interval.cc", + "monitor_interval.h", + ] + deps = [ + "../../../api/transport:network_control", + "../../../api/units:data_rate", + "../../../api/units:data_size", + "../../../api/units:time_delta", + "../../../api/units:timestamp", + "../../../rtc_base:logging", + ] +} + +rtc_library("rtt_tracker") { + sources = [ + "rtt_tracker.cc", + "rtt_tracker.h", + ] + deps = [ + "../../../api/transport:network_control", + "../../../api/units:time_delta", + "../../../api/units:timestamp", + ] +} + +rtc_library("utility_function") { + sources = [ + "utility_function.cc", + "utility_function.h", + ] + deps = [ + ":monitor_interval", + "../../../api/transport:network_control", + "../../../api/units:data_rate", + "../../../rtc_base:checks", + ] +} + +rtc_library("bitrate_controller") { + sources = [ + "bitrate_controller.cc", + "bitrate_controller.h", + ] + deps = [ + ":monitor_interval", + ":utility_function", + "../../../api/transport:network_control", + "../../../api/units:data_rate", + ] + absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] +} + +if (rtc_include_tests && !build_with_chromium) { + rtc_library("pcc_unittests") { + testonly = true + sources = [ + "bitrate_controller_unittest.cc", + "monitor_interval_unittest.cc", + "pcc_network_controller_unittest.cc", + "rtt_tracker_unittest.cc", + "utility_function_unittest.cc", + ] + deps = [ + ":bitrate_controller", + ":monitor_interval", + ":pcc", + ":pcc_controller", + ":rtt_tracker", + ":utility_function", + "../../../api/transport:network_control", + "../../../api/units:data_rate", + "../../../api/units:data_size", + "../../../api/units:time_delta", + "../../../api/units:timestamp", + "../../../test:test_support", + "../../../test/scenario", + ] + } +} diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.cc new file mode 100644 index 0000000000..1a9cddb519 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.cc @@ -0,0 +1,138 @@ +/* + * 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/pcc/bitrate_controller.h" + +#include <algorithm> +#include <cmath> +#include <cstdlib> +#include <memory> +#include <utility> +#include <vector> + +namespace webrtc { +namespace pcc { + +PccBitrateController::PccBitrateController(double initial_conversion_factor, + double initial_dynamic_boundary, + double dynamic_boundary_increment, + double rtt_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double rtt_gradient_threshold, + double delay_gradient_negative_bound) + : PccBitrateController(initial_conversion_factor, + initial_dynamic_boundary, + dynamic_boundary_increment, + std::make_unique<ModifiedVivaceUtilityFunction>( + rtt_gradient_coefficient, + loss_coefficient, + throughput_coefficient, + throughput_power, + rtt_gradient_threshold, + delay_gradient_negative_bound)) {} + +PccBitrateController::PccBitrateController( + double initial_conversion_factor, + double initial_dynamic_boundary, + double dynamic_boundary_increment, + std::unique_ptr<PccUtilityFunctionInterface> utility_function) + : consecutive_boundary_adjustments_number_(0), + initial_dynamic_boundary_(initial_dynamic_boundary), + dynamic_boundary_increment_(dynamic_boundary_increment), + utility_function_(std::move(utility_function)), + step_size_adjustments_number_(0), + initial_conversion_factor_(initial_conversion_factor) {} + +PccBitrateController::~PccBitrateController() = default; + +double PccBitrateController::ComputeStepSize(double utility_gradient) { + // Computes number of consecutive step size adjustments. + if (utility_gradient > 0) { + step_size_adjustments_number_ = + std::max<int64_t>(step_size_adjustments_number_ + 1, 1); + } else if (utility_gradient < 0) { + step_size_adjustments_number_ = + std::min<int64_t>(step_size_adjustments_number_ - 1, -1); + } else { + step_size_adjustments_number_ = 0; + } + // Computes step size amplifier. + int64_t step_size_amplifier = 1; + if (std::abs(step_size_adjustments_number_) <= 3) { + step_size_amplifier = + std::max<int64_t>(std::abs(step_size_adjustments_number_), 1); + } else { + step_size_amplifier = 2 * std::abs(step_size_adjustments_number_) - 3; + } + return step_size_amplifier * initial_conversion_factor_; +} + +double PccBitrateController::ApplyDynamicBoundary(double rate_change, + double bitrate) { + double rate_change_abs = std::abs(rate_change); + int64_t rate_change_sign = (rate_change > 0) ? 1 : -1; + if (consecutive_boundary_adjustments_number_ * rate_change_sign < 0) { + consecutive_boundary_adjustments_number_ = 0; + } + double dynamic_change_boundary = + initial_dynamic_boundary_ + + std::abs(consecutive_boundary_adjustments_number_) * + dynamic_boundary_increment_; + double boundary = bitrate * dynamic_change_boundary; + if (rate_change_abs > boundary) { + consecutive_boundary_adjustments_number_ += rate_change_sign; + return boundary * rate_change_sign; + } + // Rate change smaller than boundary. Reset boundary to the smallest possible + // that would allow the change. + while (rate_change_abs <= boundary && + consecutive_boundary_adjustments_number_ * rate_change_sign > 0) { + consecutive_boundary_adjustments_number_ -= rate_change_sign; + dynamic_change_boundary = + initial_dynamic_boundary_ + + std::abs(consecutive_boundary_adjustments_number_) * + dynamic_boundary_increment_; + boundary = bitrate * dynamic_change_boundary; + } + consecutive_boundary_adjustments_number_ += rate_change_sign; + return rate_change; +} + +absl::optional<DataRate> +PccBitrateController::ComputeRateUpdateForSlowStartMode( + const PccMonitorInterval& monitor_interval) { + double utility_value = utility_function_->Compute(monitor_interval); + if (previous_utility_.has_value() && utility_value <= previous_utility_) { + return absl::nullopt; + } + previous_utility_ = utility_value; + return monitor_interval.GetTargetSendingRate(); +} + +DataRate PccBitrateController::ComputeRateUpdateForOnlineLearningMode( + const std::vector<PccMonitorInterval>& intervals, + DataRate bandwith_estimate) { + double first_utility = utility_function_->Compute(intervals[0]); + double second_utility = utility_function_->Compute(intervals[1]); + double first_bitrate_bps = intervals[0].GetTargetSendingRate().bps(); + double second_bitrate_bps = intervals[1].GetTargetSendingRate().bps(); + double gradient = (first_utility - second_utility) / + (first_bitrate_bps - second_bitrate_bps); + double rate_change_bps = gradient * ComputeStepSize(gradient); // delta_r + rate_change_bps = + ApplyDynamicBoundary(rate_change_bps, bandwith_estimate.bps()); + return DataRate::BitsPerSec( + std::max(0.0, bandwith_estimate.bps() + rate_change_bps)); +} + +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.h b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.h new file mode 100644 index 0000000000..fadeea1b55 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller.h @@ -0,0 +1,74 @@ +/* + * 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_PCC_BITRATE_CONTROLLER_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_BITRATE_CONTROLLER_H_ + +#include <stdint.h> + +#include <memory> +#include <vector> + +#include "absl/types/optional.h" +#include "api/units/data_rate.h" +#include "modules/congestion_controller/pcc/monitor_interval.h" +#include "modules/congestion_controller/pcc/utility_function.h" + +namespace webrtc { +namespace pcc { + +class PccBitrateController { + public: + PccBitrateController(double initial_conversion_factor, + double initial_dynamic_boundary, + double dynamic_boundary_increment, + double rtt_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double rtt_gradient_threshold, + double delay_gradient_negative_bound); + + PccBitrateController( + double initial_conversion_factor, + double initial_dynamic_boundary, + double dynamic_boundary_increment, + std::unique_ptr<PccUtilityFunctionInterface> utility_function); + + absl::optional<DataRate> ComputeRateUpdateForSlowStartMode( + const PccMonitorInterval& monitor_interval); + + DataRate ComputeRateUpdateForOnlineLearningMode( + const std::vector<PccMonitorInterval>& block, + DataRate bandwidth_estimate); + + ~PccBitrateController(); + + private: + double ApplyDynamicBoundary(double rate_change, double bitrate); + double ComputeStepSize(double utility_gradient); + + // Dynamic boundary variables: + int64_t consecutive_boundary_adjustments_number_; + const double initial_dynamic_boundary_; + const double dynamic_boundary_increment_; + + const std::unique_ptr<PccUtilityFunctionInterface> utility_function_; + // Step Size variables: + int64_t step_size_adjustments_number_; + const double initial_conversion_factor_; + + absl::optional<double> previous_utility_; +}; + +} // namespace pcc +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_BITRATE_CONTROLLER_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller_unittest.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller_unittest.cc new file mode 100644 index 0000000000..957d99b1de --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/bitrate_controller_unittest.cc @@ -0,0 +1,303 @@ +/* + * 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/pcc/bitrate_controller.h" + +#include <memory> +#include <utility> + +#include "modules/congestion_controller/pcc/monitor_interval.h" +#include "test/gmock.h" +#include "test/gtest.h" + +namespace webrtc { +namespace pcc { +namespace test { +namespace { +constexpr double kInitialConversionFactor = 1; +constexpr double kInitialDynamicBoundary = 0.05; +constexpr double kDynamicBoundaryIncrement = 0.1; + +constexpr double kDelayGradientCoefficient = 900; +constexpr double kLossCoefficient = 11.35; +constexpr double kThroughputCoefficient = 500 * 1000; +constexpr double kThroughputPower = 0.99; +constexpr double kDelayGradientThreshold = 0.01; +constexpr double kDelayGradientNegativeBound = 10; + +const DataRate kTargetSendingRate = DataRate::KilobitsPerSec(300); +const double kEpsilon = 0.05; +const Timestamp kStartTime = Timestamp::Micros(0); +const TimeDelta kPacketsDelta = TimeDelta::Millis(1); +const TimeDelta kIntervalDuration = TimeDelta::Millis(1000); +const TimeDelta kDefaultRtt = TimeDelta::Millis(1000); +const DataSize kDefaultDataSize = DataSize::Bytes(100); + +std::vector<PacketResult> CreatePacketResults( + const std::vector<Timestamp>& packets_send_times, + const std::vector<Timestamp>& packets_received_times = {}, + const std::vector<DataSize>& packets_sizes = {}) { + std::vector<PacketResult> packet_results; + PacketResult packet_result; + SentPacket sent_packet; + for (size_t i = 0; i < packets_send_times.size(); ++i) { + sent_packet.send_time = packets_send_times[i]; + if (packets_sizes.empty()) { + sent_packet.size = kDefaultDataSize; + } else { + sent_packet.size = packets_sizes[i]; + } + packet_result.sent_packet = sent_packet; + if (packets_received_times.empty()) { + packet_result.receive_time = packets_send_times[i] + kDefaultRtt; + } else { + packet_result.receive_time = packets_received_times[i]; + } + packet_results.push_back(packet_result); + } + return packet_results; +} + +class MockUtilityFunction : public PccUtilityFunctionInterface { + public: + MOCK_METHOD(double, + Compute, + (const PccMonitorInterval& monitor_interval), + (const, override)); +}; + +} // namespace + +TEST(PccBitrateControllerTest, IncreaseRateWhenNoChangesForTestBitrates) { + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, kDelayGradientCoefficient, kLossCoefficient, + kThroughputCoefficient, kThroughputPower, kDelayGradientThreshold, + kDelayGradientNegativeBound); + VivaceUtilityFunction utility_function( + kDelayGradientCoefficient, kLossCoefficient, kThroughputCoefficient, + kThroughputPower, kDelayGradientThreshold, kDelayGradientNegativeBound); + std::vector<PccMonitorInterval> monitor_block{ + PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime, + kIntervalDuration), + PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon), + kStartTime + kIntervalDuration, kIntervalDuration)}; + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + kPacketsDelta, + kStartTime + kIntervalDuration + kPacketsDelta, + kStartTime + 3 * kIntervalDuration}, + {}, {})); + monitor_block[1].OnPacketsFeedback( + CreatePacketResults({kStartTime + kPacketsDelta, + kStartTime + kIntervalDuration + kPacketsDelta, + kStartTime + 3 * kIntervalDuration}, + {}, {})); + // For both of the monitor intervals there were no change in rtt gradient + // and in packet loss. Since the only difference is in the sending rate, + // the higher sending rate should be chosen by congestion controller. + EXPECT_GT(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps()); +} + +TEST(PccBitrateControllerTest, NoChangesWhenUtilityFunctionDoesntChange) { + std::unique_ptr<MockUtilityFunction> mock_utility_function = + std::make_unique<MockUtilityFunction>(); + EXPECT_CALL(*mock_utility_function, Compute(::testing::_)) + .Times(2) + .WillOnce(::testing::Return(100)) + .WillOnce(::testing::Return(100)); + + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, std::move(mock_utility_function)); + std::vector<PccMonitorInterval> monitor_block{ + PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime, + kIntervalDuration), + PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon), + kStartTime + kIntervalDuration, kIntervalDuration)}; + // To complete collecting feedback within monitor intervals. + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + monitor_block[1].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + // Because we don't have any packets inside of monitor intervals, utility + // function should be zero for both of them and the sending rate should not + // change. + EXPECT_EQ(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps()); +} + +TEST(PccBitrateControllerTest, NoBoundaryWhenSmallGradient) { + std::unique_ptr<MockUtilityFunction> mock_utility_function = + std::make_unique<MockUtilityFunction>(); + constexpr double kFirstMonitorIntervalUtility = 0; + const double kSecondMonitorIntervalUtility = + 2 * kTargetSendingRate.bps() * kEpsilon; + + EXPECT_CALL(*mock_utility_function, Compute(::testing::_)) + .Times(2) + .WillOnce(::testing::Return(kFirstMonitorIntervalUtility)) + .WillOnce(::testing::Return(kSecondMonitorIntervalUtility)); + + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, std::move(mock_utility_function)); + std::vector<PccMonitorInterval> monitor_block{ + PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime, + kIntervalDuration), + PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon), + kStartTime + kIntervalDuration, kIntervalDuration)}; + // To complete collecting feedback within monitor intervals. + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + monitor_block[1].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + + double gradient = + (kFirstMonitorIntervalUtility - kSecondMonitorIntervalUtility) / + (kTargetSendingRate.bps() * 2 * kEpsilon); + // When the gradient is small we don't hit the dynamic boundary. + EXPECT_EQ(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps() + kInitialConversionFactor * gradient); +} + +TEST(PccBitrateControllerTest, FaceBoundaryWhenLargeGradient) { + std::unique_ptr<MockUtilityFunction> mock_utility_function = + std::make_unique<MockUtilityFunction>(); + constexpr double kFirstMonitorIntervalUtility = 0; + const double kSecondMonitorIntervalUtility = + 10 * kInitialDynamicBoundary * kTargetSendingRate.bps() * 2 * + kTargetSendingRate.bps() * kEpsilon; + + EXPECT_CALL(*mock_utility_function, Compute(::testing::_)) + .Times(4) + .WillOnce(::testing::Return(kFirstMonitorIntervalUtility)) + .WillOnce(::testing::Return(kSecondMonitorIntervalUtility)) + .WillOnce(::testing::Return(kFirstMonitorIntervalUtility)) + .WillOnce(::testing::Return(kSecondMonitorIntervalUtility)); + + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, std::move(mock_utility_function)); + std::vector<PccMonitorInterval> monitor_block{ + PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime, + kIntervalDuration), + PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon), + kStartTime + kIntervalDuration, kIntervalDuration)}; + // To complete collecting feedback within monitor intervals. + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + monitor_block[1].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + // The utility function gradient is too big and we hit the dynamic boundary. + EXPECT_EQ(bitrate_controller.ComputeRateUpdateForOnlineLearningMode( + monitor_block, kTargetSendingRate), + kTargetSendingRate * (1 - kInitialDynamicBoundary)); + // For the second time we hit the dynamic boundary in the same direction, the + // boundary should increase. + EXPECT_EQ(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps() * + (1 - kInitialDynamicBoundary - kDynamicBoundaryIncrement)); +} + +TEST(PccBitrateControllerTest, SlowStartMode) { + std::unique_ptr<MockUtilityFunction> mock_utility_function = + std::make_unique<MockUtilityFunction>(); + constexpr double kFirstUtilityFunction = 1000; + EXPECT_CALL(*mock_utility_function, Compute(::testing::_)) + .Times(4) + // For first 3 calls we expect to stay in the SLOW_START mode and double + // the sending rate since the utility function increases its value. For + // the last call utility function decreases its value, this means that + // we should not double the sending rate and exit SLOW_START mode. + .WillOnce(::testing::Return(kFirstUtilityFunction)) + .WillOnce(::testing::Return(kFirstUtilityFunction + 1)) + .WillOnce(::testing::Return(kFirstUtilityFunction + 2)) + .WillOnce(::testing::Return(kFirstUtilityFunction + 1)); + + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, std::move(mock_utility_function)); + std::vector<PccMonitorInterval> monitor_block{PccMonitorInterval( + 2 * kTargetSendingRate, kStartTime, kIntervalDuration)}; + // To complete collecting feedback within monitor intervals. + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + EXPECT_EQ( + bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]), + kTargetSendingRate * 2); + EXPECT_EQ( + bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]), + kTargetSendingRate * 2); + EXPECT_EQ( + bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]), + kTargetSendingRate * 2); + EXPECT_EQ( + bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]), + absl::nullopt); +} + +TEST(PccBitrateControllerTest, StepSizeIncrease) { + std::unique_ptr<MockUtilityFunction> mock_utility_function = + std::make_unique<MockUtilityFunction>(); + constexpr double kFirstMiUtilityFunction = 0; + const double kSecondMiUtilityFunction = + 2 * kTargetSendingRate.bps() * kEpsilon; + + EXPECT_CALL(*mock_utility_function, Compute(::testing::_)) + .Times(4) + .WillOnce(::testing::Return(kFirstMiUtilityFunction)) + .WillOnce(::testing::Return(kSecondMiUtilityFunction)) + .WillOnce(::testing::Return(kFirstMiUtilityFunction)) + .WillOnce(::testing::Return(kSecondMiUtilityFunction)); + std::vector<PccMonitorInterval> monitor_block{ + PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime, + kIntervalDuration), + PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon), + kStartTime + kIntervalDuration, kIntervalDuration)}; + // To complete collecting feedback within monitor intervals. + monitor_block[0].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + monitor_block[1].OnPacketsFeedback( + CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {})); + + double gradient = (kFirstMiUtilityFunction - kSecondMiUtilityFunction) / + (kTargetSendingRate.bps() * 2 * kEpsilon); + PccBitrateController bitrate_controller( + kInitialConversionFactor, kInitialDynamicBoundary, + kDynamicBoundaryIncrement, std::move(mock_utility_function)); + // If we are moving in the same direction - the step size should increase. + EXPECT_EQ(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps() + kInitialConversionFactor * gradient); + EXPECT_EQ(bitrate_controller + .ComputeRateUpdateForOnlineLearningMode(monitor_block, + kTargetSendingRate) + .bps(), + kTargetSendingRate.bps() + 2 * kInitialConversionFactor * gradient); +} + +} // namespace test +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.cc new file mode 100644 index 0000000000..de1e2d5e69 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.cc @@ -0,0 +1,135 @@ +/* + * 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/pcc/monitor_interval.h" + +#include <stddef.h> + +#include <cmath> + +#include "rtc_base/logging.h" + +namespace webrtc { +namespace pcc { + +PccMonitorInterval::PccMonitorInterval(DataRate target_sending_rate, + Timestamp start_time, + TimeDelta duration) + : target_sending_rate_(target_sending_rate), + start_time_(start_time), + interval_duration_(duration), + received_packets_size_(DataSize::Zero()), + feedback_collection_done_(false) {} + +PccMonitorInterval::~PccMonitorInterval() = default; + +PccMonitorInterval::PccMonitorInterval(const PccMonitorInterval& other) = + default; + +void PccMonitorInterval::OnPacketsFeedback( + const std::vector<PacketResult>& packets_results) { + for (const PacketResult& packet_result : packets_results) { + if (packet_result.sent_packet.send_time <= start_time_) { + continue; + } + // Here we assume that if some packets are reordered with packets sent + // after the end of the monitor interval, then they are lost. (Otherwise + // it is not clear how long should we wait for packets feedback to arrive). + if (packet_result.sent_packet.send_time > + start_time_ + interval_duration_) { + feedback_collection_done_ = true; + return; + } + if (!packet_result.IsReceived()) { + lost_packets_sent_time_.push_back(packet_result.sent_packet.send_time); + } else { + received_packets_.push_back( + {packet_result.receive_time - packet_result.sent_packet.send_time, + packet_result.sent_packet.send_time}); + received_packets_size_ += packet_result.sent_packet.size; + } + } +} + +// For the formula used in computations see formula for "slope" in the second +// method: +// https://www.johndcook.com/blog/2008/10/20/comparing-two-ways-to-fit-a-line-to-data/ +double PccMonitorInterval::ComputeDelayGradient( + double delay_gradient_threshold) const { + // Early return to prevent division by 0 in case all packets are sent at the + // same time. + if (received_packets_.empty() || received_packets_.front().sent_time == + received_packets_.back().sent_time) { + return 0; + } + double sum_times = 0; + for (const ReceivedPacket& packet : received_packets_) { + double time_delta_us = + (packet.sent_time - received_packets_[0].sent_time).us(); + sum_times += time_delta_us; + } + double sum_squared_scaled_time_deltas = 0; + double sum_scaled_time_delta_dot_delay = 0; + for (const ReceivedPacket& packet : received_packets_) { + double time_delta_us = + (packet.sent_time - received_packets_[0].sent_time).us(); + double delay = packet.delay.us(); + double scaled_time_delta_us = + time_delta_us - sum_times / received_packets_.size(); + sum_squared_scaled_time_deltas += + scaled_time_delta_us * scaled_time_delta_us; + sum_scaled_time_delta_dot_delay += scaled_time_delta_us * delay; + } + double rtt_gradient = + sum_scaled_time_delta_dot_delay / sum_squared_scaled_time_deltas; + if (std::abs(rtt_gradient) < delay_gradient_threshold) + rtt_gradient = 0; + return rtt_gradient; +} + +bool PccMonitorInterval::IsFeedbackCollectionDone() const { + return feedback_collection_done_; +} + +Timestamp PccMonitorInterval::GetEndTime() const { + return start_time_ + interval_duration_; +} + +double PccMonitorInterval::GetLossRate() const { + size_t packets_lost = lost_packets_sent_time_.size(); + size_t packets_received = received_packets_.size(); + if (packets_lost == 0) + return 0; + return static_cast<double>(packets_lost) / (packets_lost + packets_received); +} + +DataRate PccMonitorInterval::GetTargetSendingRate() const { + return target_sending_rate_; +} + +DataRate PccMonitorInterval::GetTransmittedPacketsRate() const { + if (received_packets_.empty()) { + return target_sending_rate_; + } + Timestamp receive_time_of_first_packet = + received_packets_.front().sent_time + received_packets_.front().delay; + Timestamp receive_time_of_last_packet = + received_packets_.back().sent_time + received_packets_.back().delay; + if (receive_time_of_first_packet == receive_time_of_last_packet) { + RTC_LOG(LS_WARNING) + << "All packets in monitor interval were received at the same time."; + return target_sending_rate_; + } + return received_packets_size_ / + (receive_time_of_last_packet - receive_time_of_first_packet); +} + +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.h b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.h new file mode 100644 index 0000000000..51bd0f068a --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval.h @@ -0,0 +1,71 @@ +/* + * 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_PCC_MONITOR_INTERVAL_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_MONITOR_INTERVAL_H_ + +#include <vector> + +#include "api/transport/network_types.h" +#include "api/units/data_rate.h" +#include "api/units/data_size.h" +#include "api/units/time_delta.h" +#include "api/units/timestamp.h" + +namespace webrtc { +namespace pcc { + +// PCC divides time into consecutive monitor intervals which are used to test +// consequences for performance of sending at a certain rate. +class PccMonitorInterval { + public: + PccMonitorInterval(DataRate target_sending_rate, + Timestamp start_time, + TimeDelta duration); + ~PccMonitorInterval(); + PccMonitorInterval(const PccMonitorInterval& other); + void OnPacketsFeedback(const std::vector<PacketResult>& packets_results); + // Returns true if got complete information about packets. + // Notice, this only happens when received feedback about the first packet + // which were sent after the end of the monitor interval. If such event + // doesn't occur, we don't mind anyway and stay in the same state. + bool IsFeedbackCollectionDone() const; + Timestamp GetEndTime() const; + + double GetLossRate() const; + // Estimates the gradient using linear regression on the 2-dimensional + // dataset (sampled packets delay, time of sampling). + double ComputeDelayGradient(double delay_gradient_threshold) const; + DataRate GetTargetSendingRate() const; + // How fast receiving side gets packets. + DataRate GetTransmittedPacketsRate() const; + + private: + struct ReceivedPacket { + TimeDelta delay; + Timestamp sent_time; + }; + // Target bitrate used to generate and pace the outgoing packets. + // Actually sent bitrate might not match the target exactly. + DataRate target_sending_rate_; + // Start time is not included into interval while end time is included. + Timestamp start_time_; + TimeDelta interval_duration_; + // Vectors below updates while receiving feedback. + std::vector<ReceivedPacket> received_packets_; + std::vector<Timestamp> lost_packets_sent_time_; + DataSize received_packets_size_; + bool feedback_collection_done_; +}; + +} // namespace pcc +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_MONITOR_INTERVAL_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval_unittest.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval_unittest.cc new file mode 100644 index 0000000000..aaff57bd2a --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/monitor_interval_unittest.cc @@ -0,0 +1,190 @@ +/* + * 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/pcc/monitor_interval.h" + +#include <stddef.h> + +#include "test/gtest.h" + +namespace webrtc { +namespace pcc { +namespace test { +namespace { +const DataRate kTargetSendingRate = DataRate::KilobitsPerSec(300); +const Timestamp kStartTime = Timestamp::Micros(0); +const TimeDelta kPacketsDelta = TimeDelta::Millis(1); +const TimeDelta kIntervalDuration = TimeDelta::Millis(100); +const TimeDelta kDefaultDelay = TimeDelta::Millis(100); +const DataSize kDefaultPacketSize = DataSize::Bytes(100); +constexpr double kDelayGradientThreshold = 0.01; + +std::vector<PacketResult> CreatePacketResults( + const std::vector<Timestamp>& packets_send_times, + const std::vector<Timestamp>& packets_received_times = {}, + const std::vector<DataSize>& packets_sizes = {}) { + std::vector<PacketResult> packet_results; + for (size_t i = 0; i < packets_send_times.size(); ++i) { + SentPacket sent_packet; + sent_packet.send_time = packets_send_times[i]; + if (packets_sizes.empty()) { + sent_packet.size = kDefaultPacketSize; + } else { + sent_packet.size = packets_sizes[i]; + } + PacketResult packet_result; + packet_result.sent_packet = sent_packet; + if (packets_received_times.empty()) { + packet_result.receive_time = packets_send_times[i] + kDefaultDelay; + } else { + packet_result.receive_time = packets_received_times[i]; + } + packet_results.push_back(packet_result); + } + return packet_results; +} + +} // namespace + +TEST(PccMonitorIntervalTest, InitialValuesAreEqualToOnesSetInConstructor) { + PccMonitorInterval interval{kTargetSendingRate, kStartTime, + kIntervalDuration}; + EXPECT_EQ(interval.IsFeedbackCollectionDone(), false); + EXPECT_EQ(interval.GetEndTime(), kStartTime + kIntervalDuration); + EXPECT_EQ(interval.GetTargetSendingRate(), kTargetSendingRate); +} + +TEST(PccMonitorIntervalTest, IndicatesDoneWhenFeedbackReceivedAfterInterval) { + PccMonitorInterval interval{kTargetSendingRate, kStartTime, + kIntervalDuration}; + interval.OnPacketsFeedback(CreatePacketResults({kStartTime})); + EXPECT_EQ(interval.IsFeedbackCollectionDone(), false); + interval.OnPacketsFeedback( + CreatePacketResults({kStartTime, kStartTime + kIntervalDuration})); + EXPECT_EQ(interval.IsFeedbackCollectionDone(), false); + interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kIntervalDuration, kStartTime + 2 * kIntervalDuration})); + EXPECT_EQ(interval.IsFeedbackCollectionDone(), true); +} + +TEST(PccMonitorIntervalTest, LossRateIsOneThirdIfLostOnePacketOutOfThree) { + PccMonitorInterval interval{kTargetSendingRate, kStartTime, + kIntervalDuration}; + std::vector<Timestamp> start_times = { + kStartTime, kStartTime + 0.1 * kIntervalDuration, + kStartTime + 0.5 * kIntervalDuration, kStartTime + kIntervalDuration, + kStartTime + 2 * kIntervalDuration}; + std::vector<Timestamp> end_times = { + kStartTime + 2 * kIntervalDuration, kStartTime + 2 * kIntervalDuration, + Timestamp::PlusInfinity(), kStartTime + 2 * kIntervalDuration, + kStartTime + 4 * kIntervalDuration}; + std::vector<DataSize> packet_sizes = { + kDefaultPacketSize, 2 * kDefaultPacketSize, 3 * kDefaultPacketSize, + 4 * kDefaultPacketSize, 5 * kDefaultPacketSize}; + std::vector<PacketResult> packet_results = + CreatePacketResults(start_times, end_times, packet_sizes); + interval.OnPacketsFeedback(packet_results); + EXPECT_EQ(interval.IsFeedbackCollectionDone(), true); + + EXPECT_DOUBLE_EQ(interval.GetLossRate(), 1. / 3); +} + +TEST(PccMonitorIntervalTest, DelayGradientIsZeroIfNoChangeInPacketDelay) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kPacketsDelta, + kStartTime + 3 * kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay + 2 * kPacketsDelta, + Timestamp::PlusInfinity()}, + {})); + // Delay gradient should be zero, because both received packets have the + // same one way delay. + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), 0); +} + +TEST(PccMonitorIntervalTest, + DelayGradientIsZeroWhenOnePacketSentInMonitorInterval) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, kStartTime + 3 * kIntervalDuration}, {})); + // Only one received packet belongs to the monitor_interval, delay gradient + // should be zero in this case. + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), 0); +} + +TEST(PccMonitorIntervalTest, DelayGradientIsOne) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kPacketsDelta, + kStartTime + 3 * kPacketsDelta, kStartTime + 3 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + 4 * kPacketsDelta + kDefaultDelay, + kStartTime + 3 * kIntervalDuration}, + {})); + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), 1); +} + +TEST(PccMonitorIntervalTest, DelayGradientIsMinusOne) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kPacketsDelta, + kStartTime + 5 * kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay, kStartTime + 3 * kIntervalDuration}, + {})); + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), -1); +} + +TEST(PccMonitorIntervalTest, + DelayGradientIsZeroIfItSmallerWhenGradientThreshold) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + kPacketsDelta, + kStartTime + 102 * kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay + kPacketsDelta, + kStartTime + 3 * kIntervalDuration}, + {})); + // Delay gradient is less than 0.01 hence should be treated as zero. + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), 0); +} + +TEST(PccMonitorIntervalTest, + DelayGradientIsZeroWhenAllPacketsSentAtTheSameTime) { + PccMonitorInterval monitor_interval(kTargetSendingRate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + kPacketsDelta, + kStartTime + kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay + kPacketsDelta, + kStartTime + 3 * kIntervalDuration}, + {})); + // If all packets were sent at the same time, then delay gradient should be + // zero. + EXPECT_DOUBLE_EQ( + monitor_interval.ComputeDelayGradient(kDelayGradientThreshold), 0); +} + +} // namespace test +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_factory.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_factory.cc new file mode 100644 index 0000000000..c35c6e8ab2 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_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/pcc/pcc_factory.h" + +#include <memory> + +#include "modules/congestion_controller/pcc/pcc_network_controller.h" + +namespace webrtc { + +PccNetworkControllerFactory::PccNetworkControllerFactory() {} + +std::unique_ptr<NetworkControllerInterface> PccNetworkControllerFactory::Create( + NetworkControllerConfig config) { + return std::make_unique<pcc::PccNetworkController>(config); +} + +TimeDelta PccNetworkControllerFactory::GetProcessInterval() const { + return TimeDelta::PlusInfinity(); +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_factory.h b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_factory.h new file mode 100644 index 0000000000..bb70d7a499 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_factory.h @@ -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. + */ + +#ifndef MODULES_CONGESTION_CONTROLLER_PCC_PCC_FACTORY_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_PCC_FACTORY_H_ + +#include <memory> + +#include "api/transport/network_control.h" +#include "api/units/time_delta.h" + +namespace webrtc { + +class PccNetworkControllerFactory : public NetworkControllerFactoryInterface { + public: + PccNetworkControllerFactory(); + std::unique_ptr<NetworkControllerInterface> Create( + NetworkControllerConfig config) override; + TimeDelta GetProcessInterval() const override; +}; +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_PCC_FACTORY_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.cc new file mode 100644 index 0000000000..8653470955 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.cc @@ -0,0 +1,391 @@ +/* + * 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/pcc/pcc_network_controller.h" + +#include <algorithm> + +#include "absl/types/optional.h" +#include "api/units/data_size.h" +#include "rtc_base/checks.h" + +namespace webrtc { +namespace pcc { +namespace { +constexpr int64_t kInitialRttMs = 200; +constexpr int64_t kInitialBandwidthKbps = 300; +constexpr double kMonitorIntervalDurationRatio = 1; +constexpr double kDefaultSamplingStep = 0.05; +constexpr double kTimeoutRatio = 2; +constexpr double kAlphaForRtt = 0.9; +constexpr double kSlowStartModeIncrease = 1.5; + +constexpr double kAlphaForPacketInterval = 0.9; +constexpr int64_t kMinPacketsNumberPerInterval = 20; +const TimeDelta kMinDurationOfMonitorInterval = TimeDelta::Millis(50); +const TimeDelta kStartupDuration = TimeDelta::Millis(500); +constexpr double kMinRateChangeBps = 4000; +constexpr DataRate kMinRateHaveMultiplicativeRateChange = DataRate::BitsPerSec( + static_cast<int64_t>(kMinRateChangeBps / kDefaultSamplingStep)); + +// Bitrate controller constants. +constexpr double kInitialConversionFactor = 5; +constexpr double kInitialDynamicBoundary = 0.1; +constexpr double kDynamicBoundaryIncrement = 0.1; +// Utility function parameters. +constexpr double kRttGradientCoefficientBps = 0.005; +constexpr double kLossCoefficientBps = 10; +constexpr double kThroughputCoefficient = 0.001; +constexpr double kThroughputPower = 0.9; +constexpr double kRttGradientThreshold = 0.01; +constexpr double kDelayGradientNegativeBound = 0.1; + +constexpr int64_t kNumberOfPacketsToKeep = 20; +const uint64_t kRandomSeed = 100; +} // namespace + +PccNetworkController::PccNetworkController(NetworkControllerConfig config) + : start_time_(Timestamp::PlusInfinity()), + last_sent_packet_time_(Timestamp::PlusInfinity()), + smoothed_packets_sending_interval_(TimeDelta::Zero()), + mode_(Mode::kStartup), + default_bandwidth_(DataRate::KilobitsPerSec(kInitialBandwidthKbps)), + bandwidth_estimate_(default_bandwidth_), + rtt_tracker_(TimeDelta::Millis(kInitialRttMs), kAlphaForRtt), + monitor_interval_timeout_(TimeDelta::Millis(kInitialRttMs) * + kTimeoutRatio), + monitor_interval_length_strategy_(MonitorIntervalLengthStrategy::kFixed), + monitor_interval_duration_ratio_(kMonitorIntervalDurationRatio), + sampling_step_(kDefaultSamplingStep), + monitor_interval_timeout_ratio_(kTimeoutRatio), + min_packets_number_per_interval_(kMinPacketsNumberPerInterval), + bitrate_controller_(kInitialConversionFactor, + kInitialDynamicBoundary, + kDynamicBoundaryIncrement, + kRttGradientCoefficientBps, + kLossCoefficientBps, + kThroughputCoefficient, + kThroughputPower, + kRttGradientThreshold, + kDelayGradientNegativeBound), + monitor_intervals_duration_(TimeDelta::Zero()), + complete_feedback_monitor_interval_number_(0), + random_generator_(kRandomSeed) { + if (config.constraints.starting_rate) { + default_bandwidth_ = *config.constraints.starting_rate; + bandwidth_estimate_ = default_bandwidth_; + } +} + +PccNetworkController::~PccNetworkController() {} + +NetworkControlUpdate PccNetworkController::CreateRateUpdate( + Timestamp at_time) const { + DataRate sending_rate = DataRate::Zero(); + if (monitor_intervals_.empty() || + (monitor_intervals_.size() >= monitor_intervals_bitrates_.size() && + at_time >= monitor_intervals_.back().GetEndTime())) { + sending_rate = bandwidth_estimate_; + } else { + sending_rate = monitor_intervals_.back().GetTargetSendingRate(); + } + // Set up config when sending rate is computed. + NetworkControlUpdate update; + + // Set up target rate to encoder. + TargetTransferRate target_rate_msg; + target_rate_msg.at_time = at_time; + target_rate_msg.network_estimate.at_time = at_time; + target_rate_msg.network_estimate.round_trip_time = rtt_tracker_.GetRtt(); + // TODO(koloskova): Add correct estimate. + target_rate_msg.network_estimate.loss_rate_ratio = 0; + target_rate_msg.network_estimate.bwe_period = + monitor_interval_duration_ratio_ * rtt_tracker_.GetRtt(); + + target_rate_msg.target_rate = sending_rate; + update.target_rate = target_rate_msg; + + // Set up pacing/padding target rate. + PacerConfig pacer_config; + pacer_config.at_time = at_time; + pacer_config.time_window = TimeDelta::Millis(1); + pacer_config.data_window = sending_rate * pacer_config.time_window; + pacer_config.pad_window = sending_rate * pacer_config.time_window; + + update.pacer_config = pacer_config; + return update; +} + +NetworkControlUpdate PccNetworkController::OnSentPacket(SentPacket msg) { + // Start new monitor interval if previous has finished. + // Monitor interval is initialized in OnProcessInterval function. + if (start_time_.IsInfinite()) { + start_time_ = msg.send_time; + monitor_intervals_duration_ = kStartupDuration; + monitor_intervals_bitrates_ = {bandwidth_estimate_}; + monitor_intervals_.emplace_back(bandwidth_estimate_, msg.send_time, + monitor_intervals_duration_); + complete_feedback_monitor_interval_number_ = 0; + } + if (last_sent_packet_time_.IsFinite()) { + smoothed_packets_sending_interval_ = + (msg.send_time - last_sent_packet_time_) * kAlphaForPacketInterval + + (1 - kAlphaForPacketInterval) * smoothed_packets_sending_interval_; + } + last_sent_packet_time_ = msg.send_time; + if (!monitor_intervals_.empty() && + msg.send_time >= monitor_intervals_.back().GetEndTime() && + monitor_intervals_bitrates_.size() > monitor_intervals_.size()) { + // Start new monitor interval. + monitor_intervals_.emplace_back( + monitor_intervals_bitrates_[monitor_intervals_.size()], msg.send_time, + monitor_intervals_duration_); + } + if (IsTimeoutExpired(msg.send_time)) { + DataSize received_size = DataSize::Zero(); + for (size_t i = 1; i < last_received_packets_.size(); ++i) { + received_size += last_received_packets_[i].sent_packet.size; + } + TimeDelta sending_time = TimeDelta::Zero(); + if (last_received_packets_.size() > 0) + sending_time = last_received_packets_.back().receive_time - + last_received_packets_.front().receive_time; + DataRate receiving_rate = bandwidth_estimate_; + if (sending_time > TimeDelta::Zero()) + receiving_rate = received_size / sending_time; + bandwidth_estimate_ = + std::min<DataRate>(bandwidth_estimate_ * 0.5, receiving_rate); + if (mode_ == Mode::kSlowStart) + mode_ = Mode::kOnlineLearning; + } + if (mode_ == Mode::kStartup && + msg.send_time - start_time_ >= kStartupDuration) { + DataSize received_size = DataSize::Zero(); + for (size_t i = 1; i < last_received_packets_.size(); ++i) { + received_size += last_received_packets_[i].sent_packet.size; + } + TimeDelta sending_time = TimeDelta::Zero(); + if (last_received_packets_.size() > 0) + sending_time = last_received_packets_.back().receive_time - + last_received_packets_.front().receive_time; + DataRate receiving_rate = bandwidth_estimate_; + if (sending_time > TimeDelta::Zero()) + receiving_rate = received_size / sending_time; + bandwidth_estimate_ = receiving_rate; + monitor_intervals_.clear(); + mode_ = Mode::kSlowStart; + monitor_intervals_duration_ = ComputeMonitorIntervalsDuration(); + monitor_intervals_bitrates_ = {bandwidth_estimate_}; + monitor_intervals_.emplace_back(bandwidth_estimate_, msg.send_time, + monitor_intervals_duration_); + bandwidth_estimate_ = bandwidth_estimate_ * (1 / kSlowStartModeIncrease); + complete_feedback_monitor_interval_number_ = 0; + return CreateRateUpdate(msg.send_time); + } + if (IsFeedbackCollectionDone() || IsTimeoutExpired(msg.send_time)) { + // Creating new monitor intervals. + monitor_intervals_.clear(); + monitor_interval_timeout_ = + rtt_tracker_.GetRtt() * monitor_interval_timeout_ratio_; + monitor_intervals_duration_ = ComputeMonitorIntervalsDuration(); + complete_feedback_monitor_interval_number_ = 0; + // Compute bitrates and start first monitor interval. + if (mode_ == Mode::kSlowStart) { + monitor_intervals_bitrates_ = {kSlowStartModeIncrease * + bandwidth_estimate_}; + monitor_intervals_.emplace_back( + kSlowStartModeIncrease * bandwidth_estimate_, msg.send_time, + monitor_intervals_duration_); + } else { + RTC_DCHECK(mode_ == Mode::kOnlineLearning || mode_ == Mode::kDoubleCheck); + monitor_intervals_.clear(); + int64_t sign = 2 * (random_generator_.Rand(0, 1) % 2) - 1; + RTC_DCHECK_GE(sign, -1); + RTC_DCHECK_LE(sign, 1); + if (bandwidth_estimate_ >= kMinRateHaveMultiplicativeRateChange) { + monitor_intervals_bitrates_ = { + bandwidth_estimate_ * (1 + sign * sampling_step_), + bandwidth_estimate_ * (1 - sign * sampling_step_)}; + } else { + monitor_intervals_bitrates_ = { + DataRate::BitsPerSec(std::max<double>( + bandwidth_estimate_.bps() + sign * kMinRateChangeBps, 0)), + DataRate::BitsPerSec(std::max<double>( + bandwidth_estimate_.bps() - sign * kMinRateChangeBps, 0))}; + } + monitor_intervals_.emplace_back(monitor_intervals_bitrates_[0], + msg.send_time, + monitor_intervals_duration_); + } + } + return CreateRateUpdate(msg.send_time); +} + +TimeDelta PccNetworkController::ComputeMonitorIntervalsDuration() const { + TimeDelta monitor_intervals_duration = TimeDelta::Zero(); + if (monitor_interval_length_strategy_ == + MonitorIntervalLengthStrategy::kAdaptive) { + monitor_intervals_duration = std::max( + rtt_tracker_.GetRtt() * monitor_interval_duration_ratio_, + smoothed_packets_sending_interval_ * min_packets_number_per_interval_); + } else { + RTC_DCHECK(monitor_interval_length_strategy_ == + MonitorIntervalLengthStrategy::kFixed); + monitor_intervals_duration = + smoothed_packets_sending_interval_ * min_packets_number_per_interval_; + } + monitor_intervals_duration = + std::max(kMinDurationOfMonitorInterval, monitor_intervals_duration); + return monitor_intervals_duration; +} + +bool PccNetworkController::IsTimeoutExpired(Timestamp current_time) const { + if (complete_feedback_monitor_interval_number_ >= monitor_intervals_.size()) { + return false; + } + return current_time - + monitor_intervals_[complete_feedback_monitor_interval_number_] + .GetEndTime() >= + monitor_interval_timeout_; +} + +bool PccNetworkController::IsFeedbackCollectionDone() const { + return complete_feedback_monitor_interval_number_ >= + monitor_intervals_bitrates_.size(); +} + +NetworkControlUpdate PccNetworkController::OnTransportPacketsFeedback( + TransportPacketsFeedback msg) { + if (msg.packet_feedbacks.empty()) + return NetworkControlUpdate(); + // Save packets to last_received_packets_ array. + for (const PacketResult& packet_result : msg.ReceivedWithSendInfo()) { + last_received_packets_.push_back(packet_result); + } + while (last_received_packets_.size() > kNumberOfPacketsToKeep) { + last_received_packets_.pop_front(); + } + rtt_tracker_.OnPacketsFeedback(msg.PacketsWithFeedback(), msg.feedback_time); + // Skip rate update in case when online learning mode just started, but + // corresponding monitor intervals were not started yet. + if (mode_ == Mode::kOnlineLearning && + monitor_intervals_bitrates_.size() < 2) { + return NetworkControlUpdate(); + } + if (!IsFeedbackCollectionDone() && !monitor_intervals_.empty()) { + while (complete_feedback_monitor_interval_number_ < + monitor_intervals_.size()) { + monitor_intervals_[complete_feedback_monitor_interval_number_] + .OnPacketsFeedback(msg.PacketsWithFeedback()); + if (!monitor_intervals_[complete_feedback_monitor_interval_number_] + .IsFeedbackCollectionDone()) + break; + ++complete_feedback_monitor_interval_number_; + } + } + if (IsFeedbackCollectionDone()) { + if (mode_ == Mode::kDoubleCheck) { + mode_ = Mode::kOnlineLearning; + } else if (NeedDoubleCheckMeasurments()) { + mode_ = Mode::kDoubleCheck; + } + if (mode_ != Mode::kDoubleCheck) + UpdateSendingRateAndMode(); + } + return NetworkControlUpdate(); +} + +bool PccNetworkController::NeedDoubleCheckMeasurments() const { + if (mode_ == Mode::kSlowStart) { + return false; + } + double first_loss_rate = monitor_intervals_[0].GetLossRate(); + double second_loss_rate = monitor_intervals_[1].GetLossRate(); + DataRate first_bitrate = monitor_intervals_[0].GetTargetSendingRate(); + DataRate second_bitrate = monitor_intervals_[1].GetTargetSendingRate(); + if ((first_bitrate.bps() - second_bitrate.bps()) * + (first_loss_rate - second_loss_rate) < + 0) { + return true; + } + return false; +} + +void PccNetworkController::UpdateSendingRateAndMode() { + if (monitor_intervals_.empty() || !IsFeedbackCollectionDone()) { + return; + } + if (mode_ == Mode::kSlowStart) { + DataRate old_bandwidth_estimate = bandwidth_estimate_; + bandwidth_estimate_ = + bitrate_controller_ + .ComputeRateUpdateForSlowStartMode(monitor_intervals_[0]) + .value_or(bandwidth_estimate_); + if (bandwidth_estimate_ <= old_bandwidth_estimate) + mode_ = Mode::kOnlineLearning; + } else { + RTC_DCHECK(mode_ == Mode::kOnlineLearning); + bandwidth_estimate_ = + bitrate_controller_.ComputeRateUpdateForOnlineLearningMode( + monitor_intervals_, bandwidth_estimate_); + } +} + +NetworkControlUpdate PccNetworkController::OnNetworkAvailability( + NetworkAvailability msg) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnNetworkRouteChange( + NetworkRouteChange msg) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnProcessInterval( + ProcessInterval msg) { + return CreateRateUpdate(msg.at_time); +} + +NetworkControlUpdate PccNetworkController::OnTargetRateConstraints( + TargetRateConstraints msg) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnRemoteBitrateReport( + RemoteBitrateReport) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnRoundTripTimeUpdate( + RoundTripTimeUpdate) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnTransportLossReport( + TransportLossReport) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnStreamsConfig(StreamsConfig msg) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnReceivedPacket( + ReceivedPacket msg) { + return NetworkControlUpdate(); +} + +NetworkControlUpdate PccNetworkController::OnNetworkStateEstimate( + NetworkStateEstimate msg) { + return NetworkControlUpdate(); +} + +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.h b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.h new file mode 100644 index 0000000000..e5f65dd7d9 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller.h @@ -0,0 +1,125 @@ +/* + * 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_PCC_PCC_NETWORK_CONTROLLER_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_PCC_NETWORK_CONTROLLER_H_ + +#include <stddef.h> +#include <stdint.h> + +#include <deque> +#include <vector> + +#include "api/transport/network_control.h" +#include "api/transport/network_types.h" +#include "api/units/data_rate.h" +#include "api/units/time_delta.h" +#include "api/units/timestamp.h" +#include "modules/congestion_controller/pcc/bitrate_controller.h" +#include "modules/congestion_controller/pcc/monitor_interval.h" +#include "modules/congestion_controller/pcc/rtt_tracker.h" +#include "rtc_base/random.h" + +namespace webrtc { +namespace pcc { + +// PCC (Performance-oriented Congestion Control) Vivace is a congestion +// control algorithm based on online (convex) optimization in machine learning. +// It divides time into consecutive Monitor Intervals (MI) to test sending +// rates r(1 + eps), r(1 - eps) for the current sending rate r. +// At the end of each MI it computes utility function to transform the +// performance statistics into a numerical value. Then it updates current +// sending rate using gradient ascent to maximize utility function. +class PccNetworkController : public NetworkControllerInterface { + public: + enum class Mode { + kStartup, + // Slow start phase of PCC doubles sending rate each monitor interval. + kSlowStart, + // After getting the first decrease in utility function PCC exits slow start + // and enters the online learning phase. + kOnlineLearning, + // If we got that sending with the lower rate resulted in higher packet + // loss, then the measurements are unreliable and we need to double check + // them. + kDoubleCheck + }; + + enum class MonitorIntervalLengthStrategy { + // Monitor interval length adaptive when it is proportional to packets RTT. + kAdaptive, + // Monitor interval length is fixed when it is equal to the time of sending + // predefined amount of packets (kMinPacketsNumberPerInterval). + kFixed + }; + + explicit PccNetworkController(NetworkControllerConfig config); + ~PccNetworkController() override; + + // NetworkControllerInterface + NetworkControlUpdate OnNetworkAvailability(NetworkAvailability msg) override; + NetworkControlUpdate OnNetworkRouteChange(NetworkRouteChange msg) override; + NetworkControlUpdate OnProcessInterval(ProcessInterval msg) override; + NetworkControlUpdate OnSentPacket(SentPacket msg) override; + NetworkControlUpdate OnTargetRateConstraints( + TargetRateConstraints msg) override; + NetworkControlUpdate OnTransportPacketsFeedback( + TransportPacketsFeedback msg) override; + + // Part of remote bitrate estimation api, not implemented for PCC + NetworkControlUpdate OnStreamsConfig(StreamsConfig msg) override; + NetworkControlUpdate OnRemoteBitrateReport(RemoteBitrateReport msg) override; + NetworkControlUpdate OnRoundTripTimeUpdate(RoundTripTimeUpdate msg) override; + NetworkControlUpdate OnTransportLossReport(TransportLossReport msg) override; + NetworkControlUpdate OnReceivedPacket(ReceivedPacket msg) override; + NetworkControlUpdate OnNetworkStateEstimate( + NetworkStateEstimate msg) override; + + private: + void UpdateSendingRateAndMode(); + NetworkControlUpdate CreateRateUpdate(Timestamp at_time) const; + TimeDelta ComputeMonitorIntervalsDuration() const; + bool NeedDoubleCheckMeasurments() const; + bool IsTimeoutExpired(Timestamp current_time) const; + bool IsFeedbackCollectionDone() const; + + Timestamp start_time_; + Timestamp last_sent_packet_time_; + TimeDelta smoothed_packets_sending_interval_; + Mode mode_; + + // Default value used for initializing bandwidth. + DataRate default_bandwidth_; + // Current estimate r. + DataRate bandwidth_estimate_; + + RttTracker rtt_tracker_; + TimeDelta monitor_interval_timeout_; + const MonitorIntervalLengthStrategy monitor_interval_length_strategy_; + const double monitor_interval_duration_ratio_; + const double sampling_step_; // Epsilon. + const double monitor_interval_timeout_ratio_; + const int64_t min_packets_number_per_interval_; + + PccBitrateController bitrate_controller_; + + std::vector<PccMonitorInterval> monitor_intervals_; + std::vector<DataRate> monitor_intervals_bitrates_; + TimeDelta monitor_intervals_duration_; + size_t complete_feedback_monitor_interval_number_; + + webrtc::Random random_generator_; + std::deque<PacketResult> last_received_packets_; +}; + +} // namespace pcc +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_PCC_NETWORK_CONTROLLER_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller_unittest.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller_unittest.cc new file mode 100644 index 0000000000..31bc13f824 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/pcc_network_controller_unittest.cc @@ -0,0 +1,119 @@ +/* + * 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/pcc/pcc_network_controller.h" + +#include <memory> + +#include "modules/congestion_controller/pcc/pcc_factory.h" +#include "test/gmock.h" +#include "test/gtest.h" +#include "test/scenario/scenario.h" + +using ::testing::AllOf; +using ::testing::Field; +using ::testing::Ge; +using ::testing::Le; +using ::testing::Matcher; +using ::testing::Property; + +namespace webrtc { +namespace test { +namespace { + +const DataRate kInitialBitrate = DataRate::KilobitsPerSec(60); +const Timestamp kDefaultStartTime = Timestamp::Millis(10000000); + +constexpr double kDataRateMargin = 0.20; +constexpr double kMinDataRateFactor = 1 - kDataRateMargin; +constexpr double kMaxDataRateFactor = 1 + kDataRateMargin; +inline Matcher<TargetTransferRate> TargetRateCloseTo(DataRate rate) { + DataRate min_data_rate = rate * kMinDataRateFactor; + DataRate max_data_rate = rate * kMaxDataRateFactor; + return Field(&TargetTransferRate::target_rate, + AllOf(Ge(min_data_rate), Le(max_data_rate))); +} + +NetworkControllerConfig InitialConfig( + int starting_bandwidth_kbps = kInitialBitrate.kbps(), + int min_data_rate_kbps = 0, + int max_data_rate_kbps = 5 * kInitialBitrate.kbps()) { + NetworkControllerConfig config; + config.constraints.at_time = kDefaultStartTime; + config.constraints.min_data_rate = + DataRate::KilobitsPerSec(min_data_rate_kbps); + config.constraints.max_data_rate = + DataRate::KilobitsPerSec(max_data_rate_kbps); + config.constraints.starting_rate = + DataRate::KilobitsPerSec(starting_bandwidth_kbps); + return config; +} + +ProcessInterval InitialProcessInterval() { + ProcessInterval process_interval; + process_interval.at_time = kDefaultStartTime; + return process_interval; +} + +} // namespace + +TEST(PccNetworkControllerTest, SendsConfigurationOnFirstProcess) { + std::unique_ptr<NetworkControllerInterface> controller_; + controller_.reset(new pcc::PccNetworkController(InitialConfig())); + + NetworkControlUpdate update = + controller_->OnProcessInterval(InitialProcessInterval()); + EXPECT_THAT(*update.target_rate, TargetRateCloseTo(kInitialBitrate)); + EXPECT_THAT(*update.pacer_config, + Property(&PacerConfig::data_rate, Ge(kInitialBitrate))); +} + +TEST(PccNetworkControllerTest, UpdatesTargetSendRate) { + PccNetworkControllerFactory factory; + Scenario s("pcc_unit/updates_rate", false); + CallClientConfig config; + config.transport.cc_factory = &factory; + config.transport.rates.min_rate = DataRate::KilobitsPerSec(10); + config.transport.rates.max_rate = DataRate::KilobitsPerSec(1500); + config.transport.rates.start_rate = DataRate::KilobitsPerSec(300); + auto send_net = s.CreateMutableSimulationNode([](NetworkSimulationConfig* c) { + c->bandwidth = DataRate::KilobitsPerSec(500); + c->delay = TimeDelta::Millis(100); + }); + auto ret_net = s.CreateMutableSimulationNode( + [](NetworkSimulationConfig* c) { c->delay = TimeDelta::Millis(100); }); + + auto* client = s.CreateClient("send", config); + auto* route = s.CreateRoutes(client, {send_net->node()}, + s.CreateClient("return", CallClientConfig()), + {ret_net->node()}); + VideoStreamConfig video; + video.stream.use_rtx = false; + s.CreateVideoStream(route->forward(), video); + s.RunFor(TimeDelta::Seconds(30)); + EXPECT_NEAR(client->target_rate().kbps(), 450, 100); + send_net->UpdateConfig([](NetworkSimulationConfig* c) { + c->bandwidth = DataRate::KilobitsPerSec(800); + c->delay = TimeDelta::Millis(100); + }); + s.RunFor(TimeDelta::Seconds(40)); + EXPECT_NEAR(client->target_rate().kbps(), 750, 150); + send_net->UpdateConfig([](NetworkSimulationConfig* c) { + c->bandwidth = DataRate::KilobitsPerSec(200); + c->delay = TimeDelta::Millis(200); + }); + ret_net->UpdateConfig( + [](NetworkSimulationConfig* c) { c->delay = TimeDelta::Millis(200); }); + s.RunFor(TimeDelta::Seconds(35)); + EXPECT_NEAR(client->target_rate().kbps(), 170, 50); +} + +} // namespace test +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.cc new file mode 100644 index 0000000000..af9dc8f11b --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.cc @@ -0,0 +1,41 @@ +/* + * 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/pcc/rtt_tracker.h" + +#include <algorithm> + +namespace webrtc { +namespace pcc { + +RttTracker::RttTracker(TimeDelta initial_rtt, double alpha) + : rtt_estimate_(initial_rtt), alpha_(alpha) {} + +void RttTracker::OnPacketsFeedback( + const std::vector<PacketResult>& packet_feedbacks, + Timestamp feedback_received_time) { + TimeDelta packet_rtt = TimeDelta::MinusInfinity(); + for (const PacketResult& packet_result : packet_feedbacks) { + if (!packet_result.IsReceived()) + continue; + packet_rtt = std::max<TimeDelta>( + packet_rtt, + feedback_received_time - packet_result.sent_packet.send_time); + } + if (packet_rtt.IsFinite()) + rtt_estimate_ = (1 - alpha_) * rtt_estimate_ + alpha_ * packet_rtt; +} + +TimeDelta RttTracker::GetRtt() const { + return rtt_estimate_; +} + +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.h b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.h new file mode 100644 index 0000000000..94033cd511 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker.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_PCC_RTT_TRACKER_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_RTT_TRACKER_H_ + +#include <vector> + +#include "api/transport/network_types.h" +#include "api/units/time_delta.h" +#include "api/units/timestamp.h" + +namespace webrtc { +namespace pcc { + +class RttTracker { + public: + RttTracker(TimeDelta initial_rtt, double alpha); + // Updates RTT estimate. + void OnPacketsFeedback(const std::vector<PacketResult>& packet_feedbacks, + Timestamp feedback_received_time); + TimeDelta GetRtt() const; + + private: + TimeDelta rtt_estimate_; + double alpha_; +}; + +} // namespace pcc +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_RTT_TRACKER_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker_unittest.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker_unittest.cc new file mode 100644 index 0000000000..7d90e86822 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/rtt_tracker_unittest.cc @@ -0,0 +1,71 @@ +/* + * 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/pcc/rtt_tracker.h" + +#include "test/gtest.h" + +namespace webrtc { +namespace pcc { +namespace test { +namespace { +const TimeDelta kInitialRtt = TimeDelta::Micros(10); +constexpr double kAlpha = 0.9; +const Timestamp kStartTime = Timestamp::Seconds(0); + +PacketResult GetPacketWithRtt(TimeDelta rtt) { + SentPacket packet; + packet.send_time = kStartTime; + PacketResult packet_result; + packet_result.sent_packet = packet; + if (rtt.IsFinite()) { + packet_result.receive_time = kStartTime + rtt; + } else { + packet_result.receive_time = Timestamp::PlusInfinity(); + } + return packet_result; +} +} // namespace + +TEST(PccRttTrackerTest, InitialValue) { + RttTracker tracker{kInitialRtt, kAlpha}; + EXPECT_EQ(kInitialRtt, tracker.GetRtt()); + for (int i = 0; i < 100; ++i) { + tracker.OnPacketsFeedback({GetPacketWithRtt(kInitialRtt)}, + kStartTime + kInitialRtt); + } + EXPECT_EQ(kInitialRtt, tracker.GetRtt()); +} + +TEST(PccRttTrackerTest, DoNothingWhenPacketIsLost) { + RttTracker tracker{kInitialRtt, kAlpha}; + tracker.OnPacketsFeedback({GetPacketWithRtt(TimeDelta::PlusInfinity())}, + kStartTime + kInitialRtt); + EXPECT_EQ(tracker.GetRtt(), kInitialRtt); +} + +TEST(PccRttTrackerTest, ChangeInRtt) { + RttTracker tracker{kInitialRtt, kAlpha}; + const TimeDelta kNewRtt = TimeDelta::Micros(100); + tracker.OnPacketsFeedback({GetPacketWithRtt(kNewRtt)}, kStartTime + kNewRtt); + EXPECT_GT(tracker.GetRtt(), kInitialRtt); + EXPECT_LE(tracker.GetRtt(), kNewRtt); + for (int i = 0; i < 100; ++i) { + tracker.OnPacketsFeedback({GetPacketWithRtt(kNewRtt)}, + kStartTime + kNewRtt); + } + const TimeDelta absolute_error = TimeDelta::Micros(1); + EXPECT_NEAR(tracker.GetRtt().us(), kNewRtt.us(), absolute_error.us()); + EXPECT_LE(tracker.GetRtt(), kNewRtt); +} + +} // namespace test +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.cc new file mode 100644 index 0000000000..006a2fccd9 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.cc @@ -0,0 +1,86 @@ +/* + * 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/pcc/utility_function.h" + +#include <algorithm> +#include <cmath> + +#include "api/units/data_rate.h" +#include "rtc_base/checks.h" + +namespace webrtc { +namespace pcc { + +VivaceUtilityFunction::VivaceUtilityFunction( + double delay_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double delay_gradient_threshold, + double delay_gradient_negative_bound) + : delay_gradient_coefficient_(delay_gradient_coefficient), + loss_coefficient_(loss_coefficient), + throughput_power_(throughput_power), + throughput_coefficient_(throughput_coefficient), + delay_gradient_threshold_(delay_gradient_threshold), + delay_gradient_negative_bound_(delay_gradient_negative_bound) { + RTC_DCHECK_GE(delay_gradient_negative_bound_, 0); +} + +double VivaceUtilityFunction::Compute( + const PccMonitorInterval& monitor_interval) const { + RTC_DCHECK(monitor_interval.IsFeedbackCollectionDone()); + double bitrate = monitor_interval.GetTargetSendingRate().bps(); + double loss_rate = monitor_interval.GetLossRate(); + double rtt_gradient = + monitor_interval.ComputeDelayGradient(delay_gradient_threshold_); + rtt_gradient = std::max(rtt_gradient, -delay_gradient_negative_bound_); + return (throughput_coefficient_ * std::pow(bitrate, throughput_power_)) - + (delay_gradient_coefficient_ * bitrate * rtt_gradient) - + (loss_coefficient_ * bitrate * loss_rate); +} + +VivaceUtilityFunction::~VivaceUtilityFunction() = default; + +ModifiedVivaceUtilityFunction::ModifiedVivaceUtilityFunction( + double delay_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double delay_gradient_threshold, + double delay_gradient_negative_bound) + : delay_gradient_coefficient_(delay_gradient_coefficient), + loss_coefficient_(loss_coefficient), + throughput_power_(throughput_power), + throughput_coefficient_(throughput_coefficient), + delay_gradient_threshold_(delay_gradient_threshold), + delay_gradient_negative_bound_(delay_gradient_negative_bound) { + RTC_DCHECK_GE(delay_gradient_negative_bound_, 0); +} + +double ModifiedVivaceUtilityFunction::Compute( + const PccMonitorInterval& monitor_interval) const { + RTC_DCHECK(monitor_interval.IsFeedbackCollectionDone()); + double bitrate = monitor_interval.GetTargetSendingRate().bps(); + double loss_rate = monitor_interval.GetLossRate(); + double rtt_gradient = + monitor_interval.ComputeDelayGradient(delay_gradient_threshold_); + rtt_gradient = std::max(rtt_gradient, -delay_gradient_negative_bound_); + return (throughput_coefficient_ * std::pow(bitrate, throughput_power_) * + bitrate) - + (delay_gradient_coefficient_ * bitrate * bitrate * rtt_gradient) - + (loss_coefficient_ * bitrate * bitrate * loss_rate); +} + +ModifiedVivaceUtilityFunction::~ModifiedVivaceUtilityFunction() = default; + +} // namespace pcc +} // namespace webrtc diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.h b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.h new file mode 100644 index 0000000000..98bb0744c1 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function.h @@ -0,0 +1,78 @@ +/* + * 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_PCC_UTILITY_FUNCTION_H_ +#define MODULES_CONGESTION_CONTROLLER_PCC_UTILITY_FUNCTION_H_ + +#include "modules/congestion_controller/pcc/monitor_interval.h" + +namespace webrtc { +namespace pcc { + +// Utility function is used by PCC to transform the performance statistics +// (sending rate, loss rate, packets latency) gathered at one monitor interval +// into a numerical value. +// https://www.usenix.org/conference/nsdi18/presentation/dong +class PccUtilityFunctionInterface { + public: + virtual double Compute(const PccMonitorInterval& monitor_interval) const = 0; + virtual ~PccUtilityFunctionInterface() = default; +}; + +// Vivace utility function were suggested in the paper "PCC Vivace: +// Online-Learning Congestion Control", Mo Dong et all. +class VivaceUtilityFunction : public PccUtilityFunctionInterface { + public: + VivaceUtilityFunction(double delay_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double delay_gradient_threshold, + double delay_gradient_negative_bound); + double Compute(const PccMonitorInterval& monitor_interval) const override; + ~VivaceUtilityFunction() override; + + private: + const double delay_gradient_coefficient_; + const double loss_coefficient_; + const double throughput_power_; + const double throughput_coefficient_; + const double delay_gradient_threshold_; + const double delay_gradient_negative_bound_; +}; + +// This utility function were obtained by tuning Vivace utility function. +// The main difference is that gradient of modified utilify funtion (as well as +// rate updates) scales proportionally to the sending rate which leads to +// better performance in case of single sender. +class ModifiedVivaceUtilityFunction : public PccUtilityFunctionInterface { + public: + ModifiedVivaceUtilityFunction(double delay_gradient_coefficient, + double loss_coefficient, + double throughput_coefficient, + double throughput_power, + double delay_gradient_threshold, + double delay_gradient_negative_bound); + double Compute(const PccMonitorInterval& monitor_interval) const override; + ~ModifiedVivaceUtilityFunction() override; + + private: + const double delay_gradient_coefficient_; + const double loss_coefficient_; + const double throughput_power_; + const double throughput_coefficient_; + const double delay_gradient_threshold_; + const double delay_gradient_negative_bound_; +}; + +} // namespace pcc +} // namespace webrtc + +#endif // MODULES_CONGESTION_CONTROLLER_PCC_UTILITY_FUNCTION_H_ diff --git a/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function_unittest.cc b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function_unittest.cc new file mode 100644 index 0000000000..19b2d15920 --- /dev/null +++ b/third_party/libwebrtc/modules/congestion_controller/pcc/utility_function_unittest.cc @@ -0,0 +1,113 @@ +/* + * 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/pcc/utility_function.h" + +#include <stddef.h> + +#include <cmath> +#include <type_traits> +#include <vector> + +#include "api/transport/network_types.h" +#include "api/units/data_rate.h" +#include "api/units/data_size.h" +#include "api/units/time_delta.h" +#include "api/units/timestamp.h" +#include "test/gtest.h" + +namespace webrtc { +namespace pcc { +namespace test { +namespace { +constexpr double kLossCoefficient = 11.35; +constexpr double kThroughputPower = 0.9; +constexpr double kThroughputCoefficient = 1; +constexpr double kDelayGradientNegativeBound = 10; + +const Timestamp kStartTime = Timestamp::Micros(0); +const TimeDelta kPacketsDelta = TimeDelta::Millis(1); +const TimeDelta kIntervalDuration = TimeDelta::Millis(100); +const DataRate kSendingBitrate = DataRate::BitsPerSec(1000); + +const DataSize kDefaultDataSize = DataSize::Bytes(100); +const TimeDelta kDefaultDelay = TimeDelta::Millis(100); + +std::vector<PacketResult> CreatePacketResults( + const std::vector<Timestamp>& packets_send_times, + const std::vector<Timestamp>& packets_received_times = {}, + const std::vector<DataSize>& packets_sizes = {}) { + std::vector<PacketResult> packet_results; + PacketResult packet_result; + SentPacket sent_packet; + for (size_t i = 0; i < packets_send_times.size(); ++i) { + sent_packet.send_time = packets_send_times[i]; + if (packets_sizes.empty()) { + sent_packet.size = kDefaultDataSize; + } else { + sent_packet.size = packets_sizes[i]; + } + packet_result.sent_packet = sent_packet; + if (packets_received_times.empty()) { + packet_result.receive_time = packets_send_times[i] + kDefaultDelay; + } else { + packet_result.receive_time = packets_received_times[i]; + } + packet_results.push_back(packet_result); + } + return packet_results; +} + +} // namespace + +TEST(PccVivaceUtilityFunctionTest, + UtilityIsThroughputTermIfAllRestCoefficientsAreZero) { + VivaceUtilityFunction utility_function(0, 0, kThroughputCoefficient, + kThroughputPower, 0, + kDelayGradientNegativeBound); + PccMonitorInterval monitor_interval(kSendingBitrate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kPacketsDelta, + kStartTime + 3 * kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kPacketsDelta + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay + 3 * kPacketsDelta, + Timestamp::PlusInfinity()}, + {kDefaultDataSize, kDefaultDataSize, kDefaultDataSize, + kDefaultDataSize})); + EXPECT_DOUBLE_EQ(utility_function.Compute(monitor_interval), + kThroughputCoefficient * + std::pow(kSendingBitrate.bps(), kThroughputPower)); +} + +TEST(PccVivaceUtilityFunctionTest, + LossTermIsNonZeroIfLossCoefficientIsNonZero) { + VivaceUtilityFunction utility_function( + 0, kLossCoefficient, kThroughputCoefficient, kThroughputPower, 0, + kDelayGradientNegativeBound); + PccMonitorInterval monitor_interval(kSendingBitrate, kStartTime, + kIntervalDuration); + monitor_interval.OnPacketsFeedback(CreatePacketResults( + {kStartTime + kPacketsDelta, kStartTime + 2 * kPacketsDelta, + kStartTime + 5 * kPacketsDelta, kStartTime + 2 * kIntervalDuration}, + {kStartTime + kDefaultDelay, Timestamp::PlusInfinity(), + kStartTime + kDefaultDelay, kStartTime + 3 * kIntervalDuration}, + {})); + // The second packet was lost. + EXPECT_DOUBLE_EQ(utility_function.Compute(monitor_interval), + kThroughputCoefficient * + std::pow(kSendingBitrate.bps(), kThroughputPower) - + kLossCoefficient * kSendingBitrate.bps() * + monitor_interval.GetLossRate()); +} + +} // namespace test +} // namespace pcc +} // namespace webrtc |