1 /*
2  *  Copyright (c) 2012 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 "rtc_base/rate_statistics.h"
12 
13 #include <cstdlib>
14 
15 #include "test/gtest.h"
16 
17 namespace {
18 
19 using webrtc::RateStatistics;
20 
21 const int64_t kWindowMs = 500;
22 
23 class RateStatisticsTest : public ::testing::Test {
24  protected:
RateStatisticsTest()25   RateStatisticsTest() : stats_(kWindowMs, 8000) {}
26   RateStatistics stats_;
27 };
28 
TEST_F(RateStatisticsTest,TestStrictMode)29 TEST_F(RateStatisticsTest, TestStrictMode) {
30   int64_t now_ms = 0;
31   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
32 
33   const uint32_t kPacketSize = 1500u;
34   const uint32_t kExpectedRateBps = kPacketSize * 1000 * 8;
35 
36   // Single data point is not enough for valid estimate.
37   stats_.Update(kPacketSize, now_ms++);
38   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
39 
40   // Expecting 1200 kbps since the window is initially kept small and grows as
41   // we have more data.
42   stats_.Update(kPacketSize, now_ms);
43   EXPECT_EQ(kExpectedRateBps, *stats_.Rate(now_ms));
44 
45   stats_.Reset();
46   // Expecting 0 after init.
47   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
48 
49   const int kInterval = 10;
50   for (int i = 0; i < 100000; ++i) {
51     if (i % kInterval == 0)
52       stats_.Update(kPacketSize, now_ms);
53 
54     // Approximately 1200 kbps expected. Not exact since when packets
55     // are removed we will jump 10 ms to the next packet.
56     if (i > kInterval) {
57       absl::optional<uint32_t> rate = stats_.Rate(now_ms);
58       EXPECT_TRUE(static_cast<bool>(rate));
59       uint32_t samples = i / kInterval + 1;
60       uint64_t total_bits = samples * kPacketSize * 8;
61       uint32_t rate_bps = static_cast<uint32_t>((1000 * total_bits) / (i + 1));
62       EXPECT_NEAR(rate_bps, *rate, 22000u);
63     }
64     now_ms += 1;
65   }
66   now_ms += kWindowMs;
67   // The window is 2 seconds. If nothing has been received for that time
68   // the estimate should be 0.
69   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
70 }
71 
TEST_F(RateStatisticsTest,IncreasingThenDecreasingBitrate)72 TEST_F(RateStatisticsTest, IncreasingThenDecreasingBitrate) {
73   int64_t now_ms = 0;
74   stats_.Reset();
75   // Expecting 0 after init.
76   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
77 
78   stats_.Update(1000, ++now_ms);
79   const uint32_t kExpectedBitrate = 8000000;
80   // 1000 bytes per millisecond until plateau is reached.
81   int prev_error = kExpectedBitrate;
82   absl::optional<uint32_t> bitrate;
83   while (++now_ms < 10000) {
84     stats_.Update(1000, now_ms);
85     bitrate = stats_.Rate(now_ms);
86     EXPECT_TRUE(static_cast<bool>(bitrate));
87     int error = kExpectedBitrate - *bitrate;
88     error = std::abs(error);
89     // Expect the estimation error to decrease as the window is extended.
90     EXPECT_LE(error, prev_error + 1);
91     prev_error = error;
92   }
93   // Window filled, expect to be close to 8000000.
94   EXPECT_EQ(kExpectedBitrate, *bitrate);
95 
96   // 1000 bytes per millisecond until 10-second mark, 8000 kbps expected.
97   while (++now_ms < 10000) {
98     stats_.Update(1000, now_ms);
99     bitrate = stats_.Rate(now_ms);
100     EXPECT_EQ(kExpectedBitrate, *bitrate);
101   }
102 
103   // Zero bytes per millisecond until 0 is reached.
104   while (++now_ms < 20000) {
105     stats_.Update(0, now_ms);
106     absl::optional<uint32_t> new_bitrate = stats_.Rate(now_ms);
107     if (static_cast<bool>(new_bitrate) && *new_bitrate != *bitrate) {
108       // New bitrate must be lower than previous one.
109       EXPECT_LT(*new_bitrate, *bitrate);
110     } else {
111       // 0 kbps expected.
112       EXPECT_EQ(0u, *new_bitrate);
113       break;
114     }
115     bitrate = new_bitrate;
116   }
117 
118   // Zero bytes per millisecond until 20-second mark, 0 kbps expected.
119   while (++now_ms < 20000) {
120     stats_.Update(0, now_ms);
121     EXPECT_EQ(0u, *stats_.Rate(now_ms));
122   }
123 }
124 
TEST_F(RateStatisticsTest,ResetAfterSilence)125 TEST_F(RateStatisticsTest, ResetAfterSilence) {
126   int64_t now_ms = 0;
127   stats_.Reset();
128   // Expecting 0 after init.
129   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
130 
131   const uint32_t kExpectedBitrate = 8000000;
132   // 1000 bytes per millisecond until the window has been filled.
133   int prev_error = kExpectedBitrate;
134   absl::optional<uint32_t> bitrate;
135   while (++now_ms < 10000) {
136     stats_.Update(1000, now_ms);
137     bitrate = stats_.Rate(now_ms);
138     if (bitrate) {
139       int error = kExpectedBitrate - *bitrate;
140       error = std::abs(error);
141       // Expect the estimation error to decrease as the window is extended.
142       EXPECT_LE(error, prev_error + 1);
143       prev_error = error;
144     }
145   }
146   // Window filled, expect to be close to 8000000.
147   EXPECT_EQ(kExpectedBitrate, *bitrate);
148 
149   now_ms += kWindowMs + 1;
150   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
151   stats_.Update(1000, now_ms);
152   ++now_ms;
153   stats_.Update(1000, now_ms);
154   // We expect two samples of 1000 bytes, and that the bitrate is measured over
155   // 500 ms, i.e. 2 * 8 * 1000 / 0.500 = 32000.
156   EXPECT_EQ(32000u, *stats_.Rate(now_ms));
157 
158   // Reset, add the same samples again.
159   stats_.Reset();
160   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
161   stats_.Update(1000, now_ms);
162   ++now_ms;
163   stats_.Update(1000, now_ms);
164   // We expect two samples of 1000 bytes, and that the bitrate is measured over
165   // 2 ms (window size has been reset) i.e. 2 * 8 * 1000 / 0.002 = 8000000.
166   EXPECT_EQ(kExpectedBitrate, *stats_.Rate(now_ms));
167 }
168 
TEST_F(RateStatisticsTest,HandlesChangingWindowSize)169 TEST_F(RateStatisticsTest, HandlesChangingWindowSize) {
170   int64_t now_ms = 0;
171   stats_.Reset();
172 
173   // Sanity test window size.
174   EXPECT_TRUE(stats_.SetWindowSize(kWindowMs, now_ms));
175   EXPECT_FALSE(stats_.SetWindowSize(kWindowMs + 1, now_ms));
176   EXPECT_FALSE(stats_.SetWindowSize(0, now_ms));
177   EXPECT_TRUE(stats_.SetWindowSize(1, now_ms));
178   EXPECT_TRUE(stats_.SetWindowSize(kWindowMs, now_ms));
179 
180   // Fill the buffer at a rate of 1 byte / millisecond (8 kbps).
181   const int kBatchSize = 10;
182   for (int i = 0; i <= kWindowMs; i += kBatchSize)
183     stats_.Update(kBatchSize, now_ms += kBatchSize);
184   EXPECT_EQ(static_cast<uint32_t>(8000), *stats_.Rate(now_ms));
185 
186   // Halve the window size, rate should stay the same.
187   EXPECT_TRUE(stats_.SetWindowSize(kWindowMs / 2, now_ms));
188   EXPECT_EQ(static_cast<uint32_t>(8000), *stats_.Rate(now_ms));
189 
190   // Double the window size again, rate should stay the same. (As the window
191   // won't actually expand until new bit and bobs fall into it.
192   EXPECT_TRUE(stats_.SetWindowSize(kWindowMs, now_ms));
193   EXPECT_EQ(static_cast<uint32_t>(8000), *stats_.Rate(now_ms));
194 
195   // Fill the now empty half with bits it twice the rate.
196   for (int i = 0; i < kWindowMs / 2; i += kBatchSize)
197     stats_.Update(kBatchSize * 2, now_ms += kBatchSize);
198 
199   // Rate should have increase be 50%.
200   EXPECT_EQ(static_cast<uint32_t>((8000 * 3) / 2), *stats_.Rate(now_ms));
201 }
202 
TEST_F(RateStatisticsTest,RespectsWindowSizeEdges)203 TEST_F(RateStatisticsTest, RespectsWindowSizeEdges) {
204   int64_t now_ms = 0;
205   stats_.Reset();
206   // Expecting 0 after init.
207   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
208 
209   // One byte per ms, using one big sample.
210   stats_.Update(kWindowMs, now_ms);
211   now_ms += kWindowMs - 2;
212   // Shouldn't work! (Only one sample, not full window size.)
213   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
214 
215   // Window size should be full, and the single data point should be accepted.
216   ++now_ms;
217   absl::optional<uint32_t> bitrate = stats_.Rate(now_ms);
218   EXPECT_TRUE(static_cast<bool>(bitrate));
219   EXPECT_EQ(1000 * 8u, *bitrate);
220 
221   // Add another, now we have twice the bitrate.
222   stats_.Update(kWindowMs, now_ms);
223   bitrate = stats_.Rate(now_ms);
224   EXPECT_TRUE(static_cast<bool>(bitrate));
225   EXPECT_EQ(2 * 1000 * 8u, *bitrate);
226 
227   // Now that first sample should drop out...
228   now_ms += 1;
229   bitrate = stats_.Rate(now_ms);
230   EXPECT_TRUE(static_cast<bool>(bitrate));
231   EXPECT_EQ(1000 * 8u, *bitrate);
232 }
233 
TEST_F(RateStatisticsTest,HandlesZeroCounts)234 TEST_F(RateStatisticsTest, HandlesZeroCounts) {
235   int64_t now_ms = 0;
236   stats_.Reset();
237   // Expecting 0 after init.
238   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
239 
240   stats_.Update(kWindowMs, now_ms);
241   now_ms += kWindowMs - 1;
242   stats_.Update(0, now_ms);
243   absl::optional<uint32_t> bitrate = stats_.Rate(now_ms);
244   EXPECT_TRUE(static_cast<bool>(bitrate));
245   EXPECT_EQ(1000 * 8u, *bitrate);
246 
247   // Move window along so first data point falls out.
248   ++now_ms;
249   bitrate = stats_.Rate(now_ms);
250   EXPECT_TRUE(static_cast<bool>(bitrate));
251   EXPECT_EQ(0u, *bitrate);
252 
253   // Move window so last data point falls out.
254   now_ms += kWindowMs;
255   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
256 }
257 
TEST_F(RateStatisticsTest,HandlesQuietPeriods)258 TEST_F(RateStatisticsTest, HandlesQuietPeriods) {
259   int64_t now_ms = 0;
260   stats_.Reset();
261   // Expecting 0 after init.
262   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
263 
264   stats_.Update(0, now_ms);
265   now_ms += kWindowMs - 1;
266   absl::optional<uint32_t> bitrate = stats_.Rate(now_ms);
267   EXPECT_TRUE(static_cast<bool>(bitrate));
268   EXPECT_EQ(0u, *bitrate);
269 
270   // Move window along so first data point falls out.
271   ++now_ms;
272   EXPECT_FALSE(static_cast<bool>(stats_.Rate(now_ms)));
273 
274   // Move window a long way out.
275   now_ms += 2 * kWindowMs;
276   stats_.Update(0, now_ms);
277   bitrate = stats_.Rate(now_ms);
278   EXPECT_TRUE(static_cast<bool>(bitrate));
279   EXPECT_EQ(0u, *bitrate);
280 }
281 
TEST_F(RateStatisticsTest,HandlesBigNumbers)282 TEST_F(RateStatisticsTest, HandlesBigNumbers) {
283   int64_t large_number = 0x100000000u;
284   int64_t now_ms = 0;
285   stats_.Update(large_number, now_ms++);
286   stats_.Update(large_number, now_ms);
287   EXPECT_TRUE(stats_.Rate(now_ms));
288   EXPECT_EQ(large_number * RateStatistics::kBpsScale, *stats_.Rate(now_ms));
289 }
290 
TEST_F(RateStatisticsTest,HandlesTooLargeNumbers)291 TEST_F(RateStatisticsTest, HandlesTooLargeNumbers) {
292   int64_t very_large_number = std::numeric_limits<int64_t>::max();
293   int64_t now_ms = 0;
294   stats_.Update(very_large_number, now_ms++);
295   stats_.Update(very_large_number, now_ms);
296   // This should overflow the internal accumulator.
297   EXPECT_FALSE(stats_.Rate(now_ms));
298 }
299 
TEST_F(RateStatisticsTest,HandlesSomewhatLargeNumbers)300 TEST_F(RateStatisticsTest, HandlesSomewhatLargeNumbers) {
301   int64_t very_large_number = std::numeric_limits<int64_t>::max();
302   int64_t now_ms = 0;
303   stats_.Update(very_large_number / 4, now_ms++);
304   stats_.Update(very_large_number / 4, now_ms);
305   // This should generate a rate of more than int64_t max, but still
306   // accumulate less than int64_t overflow.
307   EXPECT_FALSE(stats_.Rate(now_ms));
308 }
309 
310 }  // namespace
311