1 /*
2  *  Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
3  *
4  *  Use of this source code is governed by a BSD-style license
5  *  that can be found in the LICENSE file in the root of the source
6  *  tree. An additional intellectual property rights grant can be found
7  *  in the file PATENTS.  All contributing project authors may
8  *  be found in the AUTHORS file in the root of the source tree.
9  */
10 
11 #include "modules/congestion_controller/pcc/bitrate_controller.h"
12 
13 #include <memory>
14 #include <utility>
15 
16 #include "modules/congestion_controller/pcc/monitor_interval.h"
17 #include "test/gmock.h"
18 #include "test/gtest.h"
19 
20 namespace webrtc {
21 namespace pcc {
22 namespace test {
23 namespace {
24 constexpr double kInitialConversionFactor = 1;
25 constexpr double kInitialDynamicBoundary = 0.05;
26 constexpr double kDynamicBoundaryIncrement = 0.1;
27 
28 constexpr double kDelayGradientCoefficient = 900;
29 constexpr double kLossCoefficient = 11.35;
30 constexpr double kThroughputCoefficient = 500 * 1000;
31 constexpr double kThroughputPower = 0.99;
32 constexpr double kDelayGradientThreshold = 0.01;
33 constexpr double kDelayGradientNegativeBound = 10;
34 
35 const DataRate kTargetSendingRate = DataRate::KilobitsPerSec(300);
36 const double kEpsilon = 0.05;
37 const Timestamp kStartTime = Timestamp::Micros(0);
38 const TimeDelta kPacketsDelta = TimeDelta::Millis(1);
39 const TimeDelta kIntervalDuration = TimeDelta::Millis(1000);
40 const TimeDelta kDefaultRtt = TimeDelta::Millis(1000);
41 const DataSize kDefaultDataSize = DataSize::Bytes(100);
42 
CreatePacketResults(const std::vector<Timestamp> & packets_send_times,const std::vector<Timestamp> & packets_received_times={},const std::vector<DataSize> & packets_sizes={})43 std::vector<PacketResult> CreatePacketResults(
44     const std::vector<Timestamp>& packets_send_times,
45     const std::vector<Timestamp>& packets_received_times = {},
46     const std::vector<DataSize>& packets_sizes = {}) {
47   std::vector<PacketResult> packet_results;
48   PacketResult packet_result;
49   SentPacket sent_packet;
50   for (size_t i = 0; i < packets_send_times.size(); ++i) {
51     sent_packet.send_time = packets_send_times[i];
52     if (packets_sizes.empty()) {
53       sent_packet.size = kDefaultDataSize;
54     } else {
55       sent_packet.size = packets_sizes[i];
56     }
57     packet_result.sent_packet = sent_packet;
58     if (packets_received_times.empty()) {
59       packet_result.receive_time = packets_send_times[i] + kDefaultRtt;
60     } else {
61       packet_result.receive_time = packets_received_times[i];
62     }
63     packet_results.push_back(packet_result);
64   }
65   return packet_results;
66 }
67 
68 class MockUtilityFunction : public PccUtilityFunctionInterface {
69  public:
70   MOCK_METHOD(double,
71               Compute,
72               (const PccMonitorInterval& monitor_interval),
73               (const, override));
74 };
75 
76 }  // namespace
77 
TEST(PccBitrateControllerTest,IncreaseRateWhenNoChangesForTestBitrates)78 TEST(PccBitrateControllerTest, IncreaseRateWhenNoChangesForTestBitrates) {
79   PccBitrateController bitrate_controller(
80       kInitialConversionFactor, kInitialDynamicBoundary,
81       kDynamicBoundaryIncrement, kDelayGradientCoefficient, kLossCoefficient,
82       kThroughputCoefficient, kThroughputPower, kDelayGradientThreshold,
83       kDelayGradientNegativeBound);
84   VivaceUtilityFunction utility_function(
85       kDelayGradientCoefficient, kLossCoefficient, kThroughputCoefficient,
86       kThroughputPower, kDelayGradientThreshold, kDelayGradientNegativeBound);
87   std::vector<PccMonitorInterval> monitor_block{
88       PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime,
89                          kIntervalDuration),
90       PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon),
91                          kStartTime + kIntervalDuration, kIntervalDuration)};
92   monitor_block[0].OnPacketsFeedback(
93       CreatePacketResults({kStartTime + kPacketsDelta,
94                            kStartTime + kIntervalDuration + kPacketsDelta,
95                            kStartTime + 3 * kIntervalDuration},
96                           {}, {}));
97   monitor_block[1].OnPacketsFeedback(
98       CreatePacketResults({kStartTime + kPacketsDelta,
99                            kStartTime + kIntervalDuration + kPacketsDelta,
100                            kStartTime + 3 * kIntervalDuration},
101                           {}, {}));
102   // For both of the monitor intervals there were no change in rtt gradient
103   // and in packet loss. Since the only difference is in the sending rate,
104   // the higher sending rate should be chosen by congestion controller.
105   EXPECT_GT(bitrate_controller
106                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
107                                                         kTargetSendingRate)
108                 .bps(),
109             kTargetSendingRate.bps());
110 }
111 
TEST(PccBitrateControllerTest,NoChangesWhenUtilityFunctionDoesntChange)112 TEST(PccBitrateControllerTest, NoChangesWhenUtilityFunctionDoesntChange) {
113   std::unique_ptr<MockUtilityFunction> mock_utility_function =
114       std::make_unique<MockUtilityFunction>();
115   EXPECT_CALL(*mock_utility_function, Compute(::testing::_))
116       .Times(2)
117       .WillOnce(::testing::Return(100))
118       .WillOnce(::testing::Return(100));
119 
120   PccBitrateController bitrate_controller(
121       kInitialConversionFactor, kInitialDynamicBoundary,
122       kDynamicBoundaryIncrement, std::move(mock_utility_function));
123   std::vector<PccMonitorInterval> monitor_block{
124       PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime,
125                          kIntervalDuration),
126       PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon),
127                          kStartTime + kIntervalDuration, kIntervalDuration)};
128   // To complete collecting feedback within monitor intervals.
129   monitor_block[0].OnPacketsFeedback(
130       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
131   monitor_block[1].OnPacketsFeedback(
132       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
133   // Because we don't have any packets inside of monitor intervals, utility
134   // function should be zero for both of them and the sending rate should not
135   // change.
136   EXPECT_EQ(bitrate_controller
137                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
138                                                         kTargetSendingRate)
139                 .bps(),
140             kTargetSendingRate.bps());
141 }
142 
TEST(PccBitrateControllerTest,NoBoundaryWhenSmallGradient)143 TEST(PccBitrateControllerTest, NoBoundaryWhenSmallGradient) {
144   std::unique_ptr<MockUtilityFunction> mock_utility_function =
145       std::make_unique<MockUtilityFunction>();
146   constexpr double kFirstMonitorIntervalUtility = 0;
147   const double kSecondMonitorIntervalUtility =
148       2 * kTargetSendingRate.bps() * kEpsilon;
149 
150   EXPECT_CALL(*mock_utility_function, Compute(::testing::_))
151       .Times(2)
152       .WillOnce(::testing::Return(kFirstMonitorIntervalUtility))
153       .WillOnce(::testing::Return(kSecondMonitorIntervalUtility));
154 
155   PccBitrateController bitrate_controller(
156       kInitialConversionFactor, kInitialDynamicBoundary,
157       kDynamicBoundaryIncrement, std::move(mock_utility_function));
158   std::vector<PccMonitorInterval> monitor_block{
159       PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime,
160                          kIntervalDuration),
161       PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon),
162                          kStartTime + kIntervalDuration, kIntervalDuration)};
163   // To complete collecting feedback within monitor intervals.
164   monitor_block[0].OnPacketsFeedback(
165       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
166   monitor_block[1].OnPacketsFeedback(
167       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
168 
169   double gradient =
170       (kFirstMonitorIntervalUtility - kSecondMonitorIntervalUtility) /
171       (kTargetSendingRate.bps() * 2 * kEpsilon);
172   // When the gradient is small we don't hit the dynamic boundary.
173   EXPECT_EQ(bitrate_controller
174                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
175                                                         kTargetSendingRate)
176                 .bps(),
177             kTargetSendingRate.bps() + kInitialConversionFactor * gradient);
178 }
179 
TEST(PccBitrateControllerTest,FaceBoundaryWhenLargeGradient)180 TEST(PccBitrateControllerTest, FaceBoundaryWhenLargeGradient) {
181   std::unique_ptr<MockUtilityFunction> mock_utility_function =
182       std::make_unique<MockUtilityFunction>();
183   constexpr double kFirstMonitorIntervalUtility = 0;
184   const double kSecondMonitorIntervalUtility =
185       10 * kInitialDynamicBoundary * kTargetSendingRate.bps() * 2 *
186       kTargetSendingRate.bps() * kEpsilon;
187 
188   EXPECT_CALL(*mock_utility_function, Compute(::testing::_))
189       .Times(4)
190       .WillOnce(::testing::Return(kFirstMonitorIntervalUtility))
191       .WillOnce(::testing::Return(kSecondMonitorIntervalUtility))
192       .WillOnce(::testing::Return(kFirstMonitorIntervalUtility))
193       .WillOnce(::testing::Return(kSecondMonitorIntervalUtility));
194 
195   PccBitrateController bitrate_controller(
196       kInitialConversionFactor, kInitialDynamicBoundary,
197       kDynamicBoundaryIncrement, std::move(mock_utility_function));
198   std::vector<PccMonitorInterval> monitor_block{
199       PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime,
200                          kIntervalDuration),
201       PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon),
202                          kStartTime + kIntervalDuration, kIntervalDuration)};
203   // To complete collecting feedback within monitor intervals.
204   monitor_block[0].OnPacketsFeedback(
205       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
206   monitor_block[1].OnPacketsFeedback(
207       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
208   // The utility function gradient is too big and we hit the dynamic boundary.
209   EXPECT_EQ(bitrate_controller.ComputeRateUpdateForOnlineLearningMode(
210                 monitor_block, kTargetSendingRate),
211             kTargetSendingRate * (1 - kInitialDynamicBoundary));
212   // For the second time we hit the dynamic boundary in the same direction, the
213   // boundary should increase.
214   EXPECT_EQ(bitrate_controller
215                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
216                                                         kTargetSendingRate)
217                 .bps(),
218             kTargetSendingRate.bps() *
219                 (1 - kInitialDynamicBoundary - kDynamicBoundaryIncrement));
220 }
221 
TEST(PccBitrateControllerTest,SlowStartMode)222 TEST(PccBitrateControllerTest, SlowStartMode) {
223   std::unique_ptr<MockUtilityFunction> mock_utility_function =
224       std::make_unique<MockUtilityFunction>();
225   constexpr double kFirstUtilityFunction = 1000;
226   EXPECT_CALL(*mock_utility_function, Compute(::testing::_))
227       .Times(4)
228       // For first 3 calls we expect to stay in the SLOW_START mode and double
229       // the sending rate since the utility function increases its value. For
230       // the last call utility function decreases its value, this means that
231       // we should not double the sending rate and exit SLOW_START mode.
232       .WillOnce(::testing::Return(kFirstUtilityFunction))
233       .WillOnce(::testing::Return(kFirstUtilityFunction + 1))
234       .WillOnce(::testing::Return(kFirstUtilityFunction + 2))
235       .WillOnce(::testing::Return(kFirstUtilityFunction + 1));
236 
237   PccBitrateController bitrate_controller(
238       kInitialConversionFactor, kInitialDynamicBoundary,
239       kDynamicBoundaryIncrement, std::move(mock_utility_function));
240   std::vector<PccMonitorInterval> monitor_block{PccMonitorInterval(
241       2 * kTargetSendingRate, kStartTime, kIntervalDuration)};
242   // To complete collecting feedback within monitor intervals.
243   monitor_block[0].OnPacketsFeedback(
244       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
245   EXPECT_EQ(
246       bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]),
247       kTargetSendingRate * 2);
248   EXPECT_EQ(
249       bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]),
250       kTargetSendingRate * 2);
251   EXPECT_EQ(
252       bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]),
253       kTargetSendingRate * 2);
254   EXPECT_EQ(
255       bitrate_controller.ComputeRateUpdateForSlowStartMode(monitor_block[0]),
256       absl::nullopt);
257 }
258 
TEST(PccBitrateControllerTest,StepSizeIncrease)259 TEST(PccBitrateControllerTest, StepSizeIncrease) {
260   std::unique_ptr<MockUtilityFunction> mock_utility_function =
261       std::make_unique<MockUtilityFunction>();
262   constexpr double kFirstMiUtilityFunction = 0;
263   const double kSecondMiUtilityFunction =
264       2 * kTargetSendingRate.bps() * kEpsilon;
265 
266   EXPECT_CALL(*mock_utility_function, Compute(::testing::_))
267       .Times(4)
268       .WillOnce(::testing::Return(kFirstMiUtilityFunction))
269       .WillOnce(::testing::Return(kSecondMiUtilityFunction))
270       .WillOnce(::testing::Return(kFirstMiUtilityFunction))
271       .WillOnce(::testing::Return(kSecondMiUtilityFunction));
272   std::vector<PccMonitorInterval> monitor_block{
273       PccMonitorInterval(kTargetSendingRate * (1 + kEpsilon), kStartTime,
274                          kIntervalDuration),
275       PccMonitorInterval(kTargetSendingRate * (1 - kEpsilon),
276                          kStartTime + kIntervalDuration, kIntervalDuration)};
277   // To complete collecting feedback within monitor intervals.
278   monitor_block[0].OnPacketsFeedback(
279       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
280   monitor_block[1].OnPacketsFeedback(
281       CreatePacketResults({kStartTime + 3 * kIntervalDuration}, {}, {}));
282 
283   double gradient = (kFirstMiUtilityFunction - kSecondMiUtilityFunction) /
284                     (kTargetSendingRate.bps() * 2 * kEpsilon);
285   PccBitrateController bitrate_controller(
286       kInitialConversionFactor, kInitialDynamicBoundary,
287       kDynamicBoundaryIncrement, std::move(mock_utility_function));
288   // If we are moving in the same direction - the step size should increase.
289   EXPECT_EQ(bitrate_controller
290                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
291                                                         kTargetSendingRate)
292                 .bps(),
293             kTargetSendingRate.bps() + kInitialConversionFactor * gradient);
294   EXPECT_EQ(bitrate_controller
295                 .ComputeRateUpdateForOnlineLearningMode(monitor_block,
296                                                         kTargetSendingRate)
297                 .bps(),
298             kTargetSendingRate.bps() + 2 * kInitialConversionFactor * gradient);
299 }
300 
301 }  // namespace test
302 }  // namespace pcc
303 }  // namespace webrtc
304