1 /*
2  *  Copyright (c) 2019 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/goog_cc/robust_throughput_estimator.h"
12 
13 #include <stddef.h>
14 #include <stdint.h>
15 
16 #include <algorithm>
17 #include <memory>
18 
19 #include "absl/strings/string_view.h"
20 #include "api/units/data_size.h"
21 #include "api/units/time_delta.h"
22 #include "api/units/timestamp.h"
23 #include "test/explicit_key_value_config.h"
24 #include "test/gtest.h"
25 
26 namespace webrtc {
27 
CreateRobustThroughputEstimatorSettings(absl::string_view field_trial_string)28 RobustThroughputEstimatorSettings CreateRobustThroughputEstimatorSettings(
29     absl::string_view field_trial_string) {
30   test::ExplicitKeyValueConfig trials(field_trial_string);
31   RobustThroughputEstimatorSettings settings(&trials);
32   return settings;
33 }
34 
35 class FeedbackGenerator {
36  public:
CreateFeedbackVector(size_t number_of_packets,DataSize packet_size,DataRate send_rate,DataRate recv_rate)37   std::vector<PacketResult> CreateFeedbackVector(size_t number_of_packets,
38                                                  DataSize packet_size,
39                                                  DataRate send_rate,
40                                                  DataRate recv_rate) {
41     std::vector<PacketResult> packet_feedback_vector(number_of_packets);
42     for (size_t i = 0; i < number_of_packets; i++) {
43       packet_feedback_vector[i].sent_packet.send_time = send_clock_;
44       packet_feedback_vector[i].sent_packet.sequence_number = sequence_number_;
45       packet_feedback_vector[i].sent_packet.size = packet_size;
46       send_clock_ += packet_size / send_rate;
47       recv_clock_ += packet_size / recv_rate;
48       sequence_number_ += 1;
49       packet_feedback_vector[i].receive_time = recv_clock_;
50     }
51     return packet_feedback_vector;
52   }
53 
CurrentReceiveClock()54   Timestamp CurrentReceiveClock() { return recv_clock_; }
55 
AdvanceReceiveClock(TimeDelta delta)56   void AdvanceReceiveClock(TimeDelta delta) { recv_clock_ += delta; }
57 
AdvanceSendClock(TimeDelta delta)58   void AdvanceSendClock(TimeDelta delta) { send_clock_ += delta; }
59 
60  private:
61   Timestamp send_clock_ = Timestamp::Millis(100000);
62   Timestamp recv_clock_ = Timestamp::Millis(10000);
63   uint16_t sequence_number_ = 100;
64 };
65 
TEST(RobustThroughputEstimatorTest,InitialEstimate)66 TEST(RobustThroughputEstimatorTest, InitialEstimate) {
67   FeedbackGenerator feedback_generator;
68   RobustThroughputEstimator throughput_estimator(
69       CreateRobustThroughputEstimatorSettings(
70           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
71           "enabled:true/"));
72   DataRate send_rate(DataRate::BytesPerSec(100000));
73   DataRate recv_rate(DataRate::BytesPerSec(100000));
74 
75   // No estimate until the estimator has enough data.
76   std::vector<PacketResult> packet_feedback =
77       feedback_generator.CreateFeedbackVector(9, DataSize::Bytes(1000),
78                                               send_rate, recv_rate);
79   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
80   EXPECT_FALSE(throughput_estimator.bitrate().has_value());
81 
82   // Estimate once `required_packets` packets have been received.
83   packet_feedback = feedback_generator.CreateFeedbackVector(
84       1, DataSize::Bytes(1000), send_rate, recv_rate);
85   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
86   auto throughput = throughput_estimator.bitrate();
87   EXPECT_EQ(throughput, send_rate);
88 
89   // Estimate remains stable when send and receive rates are stable.
90   packet_feedback = feedback_generator.CreateFeedbackVector(
91       15, DataSize::Bytes(1000), send_rate, recv_rate);
92   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
93   throughput = throughput_estimator.bitrate();
94   EXPECT_EQ(throughput, send_rate);
95 }
96 
TEST(RobustThroughputEstimatorTest,EstimateAdapts)97 TEST(RobustThroughputEstimatorTest, EstimateAdapts) {
98   FeedbackGenerator feedback_generator;
99   RobustThroughputEstimator throughput_estimator(
100       CreateRobustThroughputEstimatorSettings(
101           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
102           "enabled:true/"));
103 
104   // 1 second, 800kbps, estimate is stable.
105   DataRate send_rate(DataRate::BytesPerSec(100000));
106   DataRate recv_rate(DataRate::BytesPerSec(100000));
107   for (int i = 0; i < 10; ++i) {
108     std::vector<PacketResult> packet_feedback =
109         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
110                                                 send_rate, recv_rate);
111     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
112     auto throughput = throughput_estimator.bitrate();
113     EXPECT_EQ(throughput, send_rate);
114   }
115 
116   // 1 second, 1600kbps, estimate increases
117   send_rate = DataRate::BytesPerSec(200000);
118   recv_rate = DataRate::BytesPerSec(200000);
119   for (int i = 0; i < 20; ++i) {
120     std::vector<PacketResult> packet_feedback =
121         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
122                                                 send_rate, recv_rate);
123     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
124     auto throughput = throughput_estimator.bitrate();
125     ASSERT_TRUE(throughput.has_value());
126     EXPECT_GE(throughput.value(), DataRate::BytesPerSec(100000));
127     EXPECT_LE(throughput.value(), send_rate);
128   }
129 
130   // 1 second, 1600kbps, estimate is stable
131   for (int i = 0; i < 20; ++i) {
132     std::vector<PacketResult> packet_feedback =
133         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
134                                                 send_rate, recv_rate);
135     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
136     auto throughput = throughput_estimator.bitrate();
137     EXPECT_EQ(throughput, send_rate);
138   }
139 
140   // 1 second, 400kbps, estimate decreases
141   send_rate = DataRate::BytesPerSec(50000);
142   recv_rate = DataRate::BytesPerSec(50000);
143   for (int i = 0; i < 5; ++i) {
144     std::vector<PacketResult> packet_feedback =
145         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
146                                                 send_rate, recv_rate);
147     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
148     auto throughput = throughput_estimator.bitrate();
149     ASSERT_TRUE(throughput.has_value());
150     EXPECT_LE(throughput.value(), DataRate::BytesPerSec(200000));
151     EXPECT_GE(throughput.value(), send_rate);
152   }
153 
154   // 1 second, 400kbps, estimate is stable
155   send_rate = DataRate::BytesPerSec(50000);
156   recv_rate = DataRate::BytesPerSec(50000);
157   for (int i = 0; i < 5; ++i) {
158     std::vector<PacketResult> packet_feedback =
159         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
160                                                 send_rate, recv_rate);
161     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
162     auto throughput = throughput_estimator.bitrate();
163     EXPECT_EQ(throughput, send_rate);
164   }
165 }
166 
TEST(RobustThroughputEstimatorTest,CappedByReceiveRate)167 TEST(RobustThroughputEstimatorTest, CappedByReceiveRate) {
168   FeedbackGenerator feedback_generator;
169   RobustThroughputEstimator throughput_estimator(
170       CreateRobustThroughputEstimatorSettings(
171           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
172           "enabled:true/"));
173   DataRate send_rate(DataRate::BytesPerSec(100000));
174   DataRate recv_rate(DataRate::BytesPerSec(25000));
175 
176   std::vector<PacketResult> packet_feedback =
177       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
178                                               send_rate, recv_rate);
179   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
180   auto throughput = throughput_estimator.bitrate();
181   ASSERT_TRUE(throughput.has_value());
182   EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
183               recv_rate.bytes_per_sec<double>(),
184               0.05 * recv_rate.bytes_per_sec<double>());  // Allow 5% error
185 }
186 
TEST(RobustThroughputEstimatorTest,CappedBySendRate)187 TEST(RobustThroughputEstimatorTest, CappedBySendRate) {
188   FeedbackGenerator feedback_generator;
189   RobustThroughputEstimator throughput_estimator(
190       CreateRobustThroughputEstimatorSettings(
191           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
192           "enabled:true/"));
193   DataRate send_rate(DataRate::BytesPerSec(50000));
194   DataRate recv_rate(DataRate::BytesPerSec(100000));
195 
196   std::vector<PacketResult> packet_feedback =
197       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
198                                               send_rate, recv_rate);
199   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
200   auto throughput = throughput_estimator.bitrate();
201   ASSERT_TRUE(throughput.has_value());
202   EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
203               send_rate.bytes_per_sec<double>(),
204               0.05 * send_rate.bytes_per_sec<double>());  // Allow 5% error
205 }
206 
TEST(RobustThroughputEstimatorTest,DelaySpike)207 TEST(RobustThroughputEstimatorTest, DelaySpike) {
208   FeedbackGenerator feedback_generator;
209   // This test uses a 500ms window to amplify the effect
210   // of a delay spike.
211   RobustThroughputEstimator throughput_estimator(
212       CreateRobustThroughputEstimatorSettings(
213           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
214           "enabled:true,window_duration:500ms/"));
215   DataRate send_rate(DataRate::BytesPerSec(100000));
216   DataRate recv_rate(DataRate::BytesPerSec(100000));
217 
218   std::vector<PacketResult> packet_feedback =
219       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
220                                               send_rate, recv_rate);
221   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
222   auto throughput = throughput_estimator.bitrate();
223   EXPECT_EQ(throughput, send_rate);
224 
225   // Delay spike. 25 packets sent, but none received.
226   feedback_generator.AdvanceReceiveClock(TimeDelta::Millis(250));
227 
228   // Deliver all of the packets during the next 50 ms. (During this time,
229   // we'll have sent an additional 5 packets, so we need to receive 30
230   // packets at 1000 bytes each in 50 ms, i.e. 600000 bytes per second).
231   recv_rate = DataRate::BytesPerSec(600000);
232   // Estimate should not drop.
233   for (int i = 0; i < 30; ++i) {
234     packet_feedback = feedback_generator.CreateFeedbackVector(
235         1, DataSize::Bytes(1000), send_rate, recv_rate);
236     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
237     throughput = throughput_estimator.bitrate();
238     ASSERT_TRUE(throughput.has_value());
239     EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
240                 send_rate.bytes_per_sec<double>(),
241                 0.05 * send_rate.bytes_per_sec<double>());  // Allow 5% error
242   }
243 
244   // Delivery at normal rate. When the packets received before the gap
245   // has left the estimator's window, the receive rate will be high, but the
246   // estimate should be capped by the send rate.
247   recv_rate = DataRate::BytesPerSec(100000);
248   for (int i = 0; i < 20; ++i) {
249     packet_feedback = feedback_generator.CreateFeedbackVector(
250         5, DataSize::Bytes(1000), send_rate, recv_rate);
251     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
252     throughput = throughput_estimator.bitrate();
253     ASSERT_TRUE(throughput.has_value());
254     EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
255                 send_rate.bytes_per_sec<double>(),
256                 0.05 * send_rate.bytes_per_sec<double>());  // Allow 5% error
257   }
258 }
259 
TEST(RobustThroughputEstimatorTest,HighLoss)260 TEST(RobustThroughputEstimatorTest, HighLoss) {
261   FeedbackGenerator feedback_generator;
262   RobustThroughputEstimator throughput_estimator(
263       CreateRobustThroughputEstimatorSettings(
264           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
265           "enabled:true/"));
266   DataRate send_rate(DataRate::BytesPerSec(100000));
267   DataRate recv_rate(DataRate::BytesPerSec(100000));
268 
269   std::vector<PacketResult> packet_feedback =
270       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
271                                               send_rate, recv_rate);
272 
273   // 50% loss
274   for (size_t i = 0; i < packet_feedback.size(); i++) {
275     if (i % 2 == 1) {
276       packet_feedback[i].receive_time = Timestamp::PlusInfinity();
277     }
278   }
279 
280   std::sort(packet_feedback.begin(), packet_feedback.end(),
281             PacketResult::ReceiveTimeOrder());
282   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
283   auto throughput = throughput_estimator.bitrate();
284   ASSERT_TRUE(throughput.has_value());
285   EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
286               send_rate.bytes_per_sec<double>() / 2,
287               0.05 * send_rate.bytes_per_sec<double>() / 2);  // Allow 5% error
288 }
289 
TEST(RobustThroughputEstimatorTest,ReorderedFeedback)290 TEST(RobustThroughputEstimatorTest, ReorderedFeedback) {
291   FeedbackGenerator feedback_generator;
292   RobustThroughputEstimator throughput_estimator(
293       CreateRobustThroughputEstimatorSettings(
294           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
295           "enabled:true/"));
296   DataRate send_rate(DataRate::BytesPerSec(100000));
297   DataRate recv_rate(DataRate::BytesPerSec(100000));
298 
299   std::vector<PacketResult> packet_feedback =
300       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
301                                               send_rate, recv_rate);
302   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
303   auto throughput = throughput_estimator.bitrate();
304   EXPECT_EQ(throughput, send_rate);
305 
306   std::vector<PacketResult> delayed_feedback =
307       feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
308                                               send_rate, recv_rate);
309   packet_feedback = feedback_generator.CreateFeedbackVector(
310       10, DataSize::Bytes(1000), send_rate, recv_rate);
311 
312   // Since we're missing some feedback, it's expected that the
313   // estimate will drop.
314   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
315   throughput = throughput_estimator.bitrate();
316   ASSERT_TRUE(throughput.has_value());
317   EXPECT_LT(throughput.value(), send_rate);
318 
319   // But it should completely recover as soon as we get the feedback.
320   throughput_estimator.IncomingPacketFeedbackVector(delayed_feedback);
321   throughput = throughput_estimator.bitrate();
322   EXPECT_EQ(throughput, send_rate);
323 
324   // It should then remain stable (as if the feedbacks weren't reordered.)
325   for (int i = 0; i < 10; ++i) {
326     packet_feedback = feedback_generator.CreateFeedbackVector(
327         15, DataSize::Bytes(1000), send_rate, recv_rate);
328     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
329     throughput = throughput_estimator.bitrate();
330     EXPECT_EQ(throughput, send_rate);
331   }
332 }
333 
TEST(RobustThroughputEstimatorTest,DeepReordering)334 TEST(RobustThroughputEstimatorTest, DeepReordering) {
335   FeedbackGenerator feedback_generator;
336   // This test uses a 500ms window to amplify the
337   // effect of reordering.
338   RobustThroughputEstimator throughput_estimator(
339       CreateRobustThroughputEstimatorSettings(
340           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
341           "enabled:true,window_duration:500ms/"));
342   DataRate send_rate(DataRate::BytesPerSec(100000));
343   DataRate recv_rate(DataRate::BytesPerSec(100000));
344 
345   std::vector<PacketResult> delayed_packets =
346       feedback_generator.CreateFeedbackVector(1, DataSize::Bytes(1000),
347                                               send_rate, recv_rate);
348 
349   for (int i = 0; i < 10; i++) {
350     std::vector<PacketResult> packet_feedback =
351         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
352                                                 send_rate, recv_rate);
353     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
354     auto throughput = throughput_estimator.bitrate();
355     EXPECT_EQ(throughput, send_rate);
356   }
357 
358   // Delayed packet arrives ~1 second after it should have.
359   // Since the window is 500 ms, the delayed packet was sent ~500
360   // ms before the second oldest packet. However, the send rate
361   // should not drop.
362   delayed_packets.front().receive_time =
363       feedback_generator.CurrentReceiveClock();
364   throughput_estimator.IncomingPacketFeedbackVector(delayed_packets);
365   auto throughput = throughput_estimator.bitrate();
366   ASSERT_TRUE(throughput.has_value());
367   EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
368               send_rate.bytes_per_sec<double>(),
369               0.05 * send_rate.bytes_per_sec<double>());  // Allow 5% error
370 
371   // Thoughput should stay stable.
372   for (int i = 0; i < 10; i++) {
373     std::vector<PacketResult> packet_feedback =
374         feedback_generator.CreateFeedbackVector(10, DataSize::Bytes(1000),
375                                                 send_rate, recv_rate);
376     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
377     auto throughput = throughput_estimator.bitrate();
378     ASSERT_TRUE(throughput.has_value());
379     EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
380                 send_rate.bytes_per_sec<double>(),
381                 0.05 * send_rate.bytes_per_sec<double>());  // Allow 5% error
382   }
383 }
384 
TEST(RobustThroughputEstimatorTest,StreamPausedAndResumed)385 TEST(RobustThroughputEstimatorTest, StreamPausedAndResumed) {
386   FeedbackGenerator feedback_generator;
387   RobustThroughputEstimator throughput_estimator(
388       CreateRobustThroughputEstimatorSettings(
389           "WebRTC-Bwe-RobustThroughputEstimatorSettings/"
390           "enabled:true/"));
391   DataRate send_rate(DataRate::BytesPerSec(100000));
392   DataRate recv_rate(DataRate::BytesPerSec(100000));
393 
394   std::vector<PacketResult> packet_feedback =
395       feedback_generator.CreateFeedbackVector(20, DataSize::Bytes(1000),
396                                               send_rate, recv_rate);
397   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
398   auto throughput = throughput_estimator.bitrate();
399   EXPECT_TRUE(throughput.has_value());
400   double expected_bytes_per_sec = 100 * 1000.0;
401   EXPECT_NEAR(throughput.value().bytes_per_sec<double>(),
402               expected_bytes_per_sec,
403               0.05 * expected_bytes_per_sec);  // Allow 5% error
404 
405   // No packets sent or feedback received for 60s.
406   feedback_generator.AdvanceSendClock(TimeDelta::Seconds(60));
407   feedback_generator.AdvanceReceiveClock(TimeDelta::Seconds(60));
408 
409   // Resume sending packets at the same rate as before. The estimate
410   // will initially be invalid, due to lack of recent data.
411   packet_feedback = feedback_generator.CreateFeedbackVector(
412       5, DataSize::Bytes(1000), send_rate, recv_rate);
413   throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
414   throughput = throughput_estimator.bitrate();
415   EXPECT_FALSE(throughput.has_value());
416 
417   // But be back to the normal level once we have enough data.
418   for (int i = 0; i < 4; ++i) {
419     packet_feedback = feedback_generator.CreateFeedbackVector(
420         5, DataSize::Bytes(1000), send_rate, recv_rate);
421     throughput_estimator.IncomingPacketFeedbackVector(packet_feedback);
422     throughput = throughput_estimator.bitrate();
423     EXPECT_EQ(throughput, send_rate);
424   }
425 }
426 
427 }  // namespace webrtc
428