1 /*
2  *  Copyright (c) 2015 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/remote_bitrate_estimator/test/bwe.h"
12 
13 #include <vector>
14 
15 #include "rtc_base/arraysize.h"
16 #include "test/gtest.h"
17 
18 namespace webrtc {
19 namespace testing {
20 namespace bwe {
21 
22 const int kSetCapacity = 1000;
23 
24 class LinkedSetTest : public ::testing::Test {
25  public:
LinkedSetTest()26   LinkedSetTest() : linked_set_(kSetCapacity) {}
27 
~LinkedSetTest()28   ~LinkedSetTest() {}
29 
30  protected:
31   LinkedSet linked_set_;
32 };
33 
TEST_F(LinkedSetTest,EmptySet)34 TEST_F(LinkedSetTest, EmptySet) {
35   EXPECT_EQ(linked_set_.OldestSeqNumber(), 0);
36   EXPECT_EQ(linked_set_.NewestSeqNumber(), 0);
37 }
38 
TEST_F(LinkedSetTest,SinglePacket)39 TEST_F(LinkedSetTest, SinglePacket) {
40   const uint16_t kSeqNumber = 1;  // Arbitrary.
41   // Other parameters don't matter here.
42   linked_set_.Insert(kSeqNumber, 0, 0, 0);
43 
44   EXPECT_EQ(linked_set_.OldestSeqNumber(), kSeqNumber);
45   EXPECT_EQ(linked_set_.NewestSeqNumber(), kSeqNumber);
46 }
47 
TEST_F(LinkedSetTest,MultiplePackets)48 TEST_F(LinkedSetTest, MultiplePackets) {
49   const uint16_t kNumberPackets = 100;
50 
51   std::vector<uint16_t> sequence_numbers;
52   for (size_t i = 0; i < kNumberPackets; ++i) {
53     sequence_numbers.push_back(static_cast<uint16_t>(i + 1));
54   }
55   random_shuffle(sequence_numbers.begin(), sequence_numbers.end());
56 
57   for (size_t i = 0; i < kNumberPackets; ++i) {
58     // Other parameters don't matter here.
59     linked_set_.Insert(static_cast<uint16_t>(i), 0, 0, 0);
60   }
61 
62   // Packets arriving out of order should not affect the following values:
63   EXPECT_EQ(linked_set_.OldestSeqNumber(), 0);
64   EXPECT_EQ(linked_set_.NewestSeqNumber(), kNumberPackets - 1);
65 }
66 
TEST_F(LinkedSetTest,Overflow)67 TEST_F(LinkedSetTest, Overflow) {
68   const int kFirstSeqNumber = -100;
69   const int kLastSeqNumber = 100;
70 
71   for (int i = kFirstSeqNumber; i <= kLastSeqNumber; ++i) {
72     // Other parameters don't matter here.
73     linked_set_.Insert(static_cast<uint16_t>(i), 0, 0, 0);
74   }
75 
76   // Packets arriving out of order should not affect the following values:
77   EXPECT_EQ(linked_set_.OldestSeqNumber(),
78             static_cast<uint16_t>(kFirstSeqNumber));
79   EXPECT_EQ(linked_set_.NewestSeqNumber(),
80             static_cast<uint16_t>(kLastSeqNumber));
81 }
82 
83 class SequenceNumberOlderThanTest : public ::testing::Test {
84  public:
SequenceNumberOlderThanTest()85   SequenceNumberOlderThanTest() {}
~SequenceNumberOlderThanTest()86   ~SequenceNumberOlderThanTest() {}
87 
88  protected:
89   SequenceNumberOlderThan comparator_;
90 };
91 
TEST_F(SequenceNumberOlderThanTest,Operator)92 TEST_F(SequenceNumberOlderThanTest, Operator) {
93   // Operator()(x, y) returns true <==> y is newer than x.
94   EXPECT_TRUE(comparator_.operator()(0x0000, 0x0001));
95   EXPECT_TRUE(comparator_.operator()(0x0001, 0x1000));
96   EXPECT_FALSE(comparator_.operator()(0x0001, 0x0000));
97   EXPECT_FALSE(comparator_.operator()(0x0002, 0x0002));
98   EXPECT_TRUE(comparator_.operator()(0xFFF6, 0x000A));
99   EXPECT_FALSE(comparator_.operator()(0x000A, 0xFFF6));
100   EXPECT_TRUE(comparator_.operator()(0x0000, 0x8000));
101   EXPECT_FALSE(comparator_.operator()(0x8000, 0x0000));
102 }
103 
104 class LossAccountTest : public ::testing::Test {
105  public:
LossAccountTest()106   LossAccountTest() {}
~LossAccountTest()107   ~LossAccountTest() {}
108 
109  protected:
110   LossAccount loss_account_;
111 };
112 
TEST_F(LossAccountTest,Operations)113 TEST_F(LossAccountTest, Operations) {
114   const size_t kTotal = 100;  // Arbitrary values.
115   const size_t kLost = 10;
116 
117   LossAccount rhs(kTotal, kLost);
118 
119   loss_account_.Add(rhs);
120   EXPECT_EQ(loss_account_.num_total, kTotal);
121   EXPECT_EQ(loss_account_.num_lost, kLost);
122   EXPECT_NEAR(loss_account_.LossRatio(), static_cast<float>(kLost) / kTotal,
123               0.001f);
124 
125   loss_account_.Subtract(rhs);
126   EXPECT_EQ(loss_account_.num_total, 0UL);
127   EXPECT_EQ(loss_account_.num_lost, 0UL);
128   EXPECT_NEAR(loss_account_.LossRatio(), 0.0f, 0.001f);
129 }
130 
131 class BweReceiverTest : public ::testing::Test {
132  public:
BweReceiverTest()133   BweReceiverTest() : bwe_receiver_(kFlowId) {}
~BweReceiverTest()134   ~BweReceiverTest() {}
135 
136  protected:
137   const int kFlowId = 1;  // Arbitrary.
138   BweReceiver bwe_receiver_;
139 };
140 
TEST_F(BweReceiverTest,ReceivingRateNoPackets)141 TEST_F(BweReceiverTest, ReceivingRateNoPackets) {
142   EXPECT_EQ(bwe_receiver_.RecentKbps(), static_cast<size_t>(0));
143 }
144 
TEST_F(BweReceiverTest,ReceivingRateSinglePacket)145 TEST_F(BweReceiverTest, ReceivingRateSinglePacket) {
146   const size_t kPayloadSizeBytes = 500 * 1000;
147   const int64_t kSendTimeUs = 300 * 1000;
148   const int64_t kArrivalTimeMs = kSendTimeUs / 1000 + 100;
149   const uint16_t kSequenceNumber = 1;
150   const int64_t kTimeWindowMs = BweReceiver::kReceivingRateTimeWindowMs;
151 
152   const MediaPacket media_packet(kFlowId, kSendTimeUs, kPayloadSizeBytes,
153                                  kSequenceNumber);
154   bwe_receiver_.ReceivePacket(kArrivalTimeMs, media_packet);
155 
156   const size_t kReceivingRateKbps = 8 * kPayloadSizeBytes / kTimeWindowMs;
157 
158   EXPECT_NEAR(bwe_receiver_.RecentKbps(), kReceivingRateKbps,
159               static_cast<float>(kReceivingRateKbps) / 100.0f);
160 }
161 
TEST_F(BweReceiverTest,ReceivingRateSmallPackets)162 TEST_F(BweReceiverTest, ReceivingRateSmallPackets) {
163   const size_t kPayloadSizeBytes = 100 * 1000;
164   const int64_t kTimeGapMs = 50;  // Between each packet.
165   const int64_t kOneWayDelayMs = 50;
166 
167   for (int i = 1; i < 50; ++i) {
168     int64_t send_time_us = i * kTimeGapMs * 1000;
169     int64_t arrival_time_ms = send_time_us / 1000 + kOneWayDelayMs;
170     uint16_t sequence_number = i;
171     const MediaPacket media_packet(kFlowId, send_time_us, kPayloadSizeBytes,
172                                    sequence_number);
173     bwe_receiver_.ReceivePacket(arrival_time_ms, media_packet);
174   }
175 
176   const size_t kReceivingRateKbps = 8 * kPayloadSizeBytes / kTimeGapMs;
177   EXPECT_NEAR(bwe_receiver_.RecentKbps(), kReceivingRateKbps,
178               static_cast<float>(kReceivingRateKbps) / 100.0f);
179 }
180 
TEST_F(BweReceiverTest,PacketLossNoPackets)181 TEST_F(BweReceiverTest, PacketLossNoPackets) {
182   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
183 }
184 
TEST_F(BweReceiverTest,PacketLossSinglePacket)185 TEST_F(BweReceiverTest, PacketLossSinglePacket) {
186   const MediaPacket media_packet(kFlowId, 0, 0, 0);
187   bwe_receiver_.ReceivePacket(0, media_packet);
188   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
189 }
190 
TEST_F(BweReceiverTest,PacketLossContiguousPackets)191 TEST_F(BweReceiverTest, PacketLossContiguousPackets) {
192   const int64_t kTimeWindowMs = BweReceiver::kPacketLossTimeWindowMs;
193   size_t set_capacity = bwe_receiver_.GetSetCapacity();
194 
195   for (int i = 0; i < 10; ++i) {
196     uint16_t sequence_number = static_cast<uint16_t>(i);
197     // Sequence_number and flow_id are the only members that matter here.
198     const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
199     // Arrival time = 0, all packets will be considered.
200     bwe_receiver_.ReceivePacket(0, media_packet);
201   }
202   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
203 
204   for (int i = 30; i > 20; i--) {
205     uint16_t sequence_number = static_cast<uint16_t>(i);
206     // Sequence_number and flow_id are the only members that matter here.
207     const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
208     // Only the packets sent in this for loop will be considered.
209     bwe_receiver_.ReceivePacket(2 * kTimeWindowMs, media_packet);
210   }
211   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
212 
213   // Should handle uint16_t overflow.
214   for (int i = 0xFFFF - 10; i < 0xFFFF + 10; ++i) {
215     uint16_t sequence_number = static_cast<uint16_t>(i);
216     const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
217     // Only the packets sent in this for loop will be considered.
218     bwe_receiver_.ReceivePacket(4 * kTimeWindowMs, media_packet);
219   }
220   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
221 
222   // Should handle set overflow.
223   for (int i = 0; i < set_capacity * 1.5; ++i) {
224     uint16_t sequence_number = static_cast<uint16_t>(i);
225     const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
226     // Only the packets sent in this for loop will be considered.
227     bwe_receiver_.ReceivePacket(6 * kTimeWindowMs, media_packet);
228   }
229   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
230 }
231 
232 // Should handle duplicates.
TEST_F(BweReceiverTest,PacketLossDuplicatedPackets)233 TEST_F(BweReceiverTest, PacketLossDuplicatedPackets) {
234   const int64_t kTimeWindowMs = BweReceiver::kPacketLossTimeWindowMs;
235 
236   for (int i = 0; i < 10; ++i) {
237     const MediaPacket media_packet(kFlowId, 0, 0, 0);
238     // Arrival time = 0, all packets will be considered.
239     bwe_receiver_.ReceivePacket(0, media_packet);
240   }
241   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
242 
243   // Missing the element 5.
244   const uint16_t kSequenceNumbers[] = {1, 2, 3, 4, 6, 7, 8};
245   const int kNumPackets = arraysize(kSequenceNumbers);
246 
247   // Insert each sequence number twice.
248   for (int i = 0; i < 2; ++i) {
249     for (int j = 0; j < kNumPackets; j++) {
250       const MediaPacket media_packet(kFlowId, 0, 0, kSequenceNumbers[j]);
251       // Only the packets sent in this for loop will be considered.
252       bwe_receiver_.ReceivePacket(2 * kTimeWindowMs, media_packet);
253     }
254   }
255 
256   EXPECT_NEAR(bwe_receiver_.RecentPacketLossRatio(), 1.0f / (kNumPackets + 1),
257               0.1f / (kNumPackets + 1));
258 }
259 
TEST_F(BweReceiverTest,PacketLossLakingPackets)260 TEST_F(BweReceiverTest, PacketLossLakingPackets) {
261   size_t set_capacity = bwe_receiver_.GetSetCapacity();
262   EXPECT_LT(set_capacity, static_cast<size_t>(0xFFFF));
263 
264   // Missing every other packet.
265   for (size_t i = 0; i < set_capacity; ++i) {
266     if ((i & 1) == 0) {  // Only even sequence numbers.
267       uint16_t sequence_number = static_cast<uint16_t>(i);
268       const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
269       // Arrival time = 0, all packets will be considered.
270       bwe_receiver_.ReceivePacket(0, media_packet);
271     }
272   }
273   EXPECT_NEAR(bwe_receiver_.RecentPacketLossRatio(), 0.5f, 0.01f);
274 }
275 
TEST_F(BweReceiverTest,PacketLossLakingFewPackets)276 TEST_F(BweReceiverTest, PacketLossLakingFewPackets) {
277   size_t set_capacity = bwe_receiver_.GetSetCapacity();
278   EXPECT_LT(set_capacity, static_cast<size_t>(0xFFFF));
279 
280   const int kPeriod = 100;
281   // Missing one for each kPeriod packets.
282   for (size_t i = 0; i < set_capacity; ++i) {
283     if ((i % kPeriod) != 0) {
284       uint16_t sequence_number = static_cast<uint16_t>(i);
285       const MediaPacket media_packet(kFlowId, 0, 0, sequence_number);
286       // Arrival time = 0, all packets will be considered.
287       bwe_receiver_.ReceivePacket(0, media_packet);
288     }
289   }
290   EXPECT_NEAR(bwe_receiver_.RecentPacketLossRatio(), 1.0f / kPeriod,
291               0.1f / kPeriod);
292 }
293 
294 // Packet's sequence numbers greatly apart, expect high loss.
TEST_F(BweReceiverTest,PacketLossWideGap)295 TEST_F(BweReceiverTest, PacketLossWideGap) {
296   const int64_t kTimeWindowMs = BweReceiver::kPacketLossTimeWindowMs;
297 
298   const MediaPacket media_packet1(0, 0, 0, 1);
299   const MediaPacket media_packet2(0, 0, 0, 1000);
300   // Only these two packets will be considered.
301   bwe_receiver_.ReceivePacket(0, media_packet1);
302   bwe_receiver_.ReceivePacket(0, media_packet2);
303   EXPECT_NEAR(bwe_receiver_.RecentPacketLossRatio(), 0.998f, 0.0001f);
304 
305   const MediaPacket media_packet3(0, 0, 0, 0);
306   const MediaPacket media_packet4(0, 0, 0, 0x8000);
307   // Only these two packets will be considered.
308   bwe_receiver_.ReceivePacket(2 * kTimeWindowMs, media_packet3);
309   bwe_receiver_.ReceivePacket(2 * kTimeWindowMs, media_packet4);
310   EXPECT_NEAR(bwe_receiver_.RecentPacketLossRatio(), 0.99994f, 0.00001f);
311 }
312 
313 // Packets arriving unordered should not be counted as losted.
TEST_F(BweReceiverTest,PacketLossUnorderedPackets)314 TEST_F(BweReceiverTest, PacketLossUnorderedPackets) {
315   size_t num_packets = bwe_receiver_.GetSetCapacity() / 2;
316   std::vector<uint16_t> sequence_numbers;
317 
318   for (size_t i = 0; i < num_packets; ++i) {
319     sequence_numbers.push_back(static_cast<uint16_t>(i + 1));
320   }
321 
322   random_shuffle(sequence_numbers.begin(), sequence_numbers.end());
323 
324   for (size_t i = 0; i < num_packets; ++i) {
325     const MediaPacket media_packet(kFlowId, 0, 0, sequence_numbers[i]);
326     // Arrival time = 0, all packets will be considered.
327     bwe_receiver_.ReceivePacket(0, media_packet);
328   }
329 
330   EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
331 }
332 
TEST_F(BweReceiverTest,RecentKbps)333 TEST_F(BweReceiverTest, RecentKbps) {
334   EXPECT_EQ(bwe_receiver_.RecentKbps(), 0U);
335 
336   const size_t kPacketSizeBytes = 1200;
337   const int kNumPackets = 100;
338 
339   double window_size_s = bwe_receiver_.BitrateWindowS();
340 
341   // Receive packets at the same time.
342   for (int i = 0; i < kNumPackets; ++i) {
343     MediaPacket packet(kFlowId, 0L, kPacketSizeBytes, static_cast<uint16_t>(i));
344     bwe_receiver_.ReceivePacket(0, packet);
345   }
346 
347   EXPECT_NEAR(bwe_receiver_.RecentKbps(),
348               (8 * kNumPackets * kPacketSizeBytes) / (1000 * window_size_s),
349               10);
350 
351   int64_t time_gap_ms =
352       2 * 1000 * window_size_s;  // Larger than rate_counter time window.
353 
354   MediaPacket packet(kFlowId, time_gap_ms * 1000, kPacketSizeBytes,
355                      static_cast<uint16_t>(kNumPackets));
356   bwe_receiver_.ReceivePacket(time_gap_ms, packet);
357 
358   EXPECT_NEAR(bwe_receiver_.RecentKbps(),
359               (8 * kPacketSizeBytes) / (1000 * window_size_s), 10);
360 }
361 
TEST_F(BweReceiverTest,Loss)362 TEST_F(BweReceiverTest, Loss) {
363   EXPECT_NEAR(bwe_receiver_.GlobalReceiverPacketLossRatio(), 0.0f, 0.001f);
364 
365   LossAccount loss_account = bwe_receiver_.LinkedSetPacketLossRatio();
366   EXPECT_NEAR(loss_account.LossRatio(), 0.0f, 0.001f);
367 
368   // Insert packets 1-50 and 151-200;
369   for (int i = 1; i <= 200; ++i) {
370     // Packet size and timestamp do not matter here.
371     MediaPacket packet(kFlowId, 0L, 0UL, static_cast<uint16_t>(i));
372     bwe_receiver_.ReceivePacket(0, packet);
373     if (i == 50) {
374       i += 100;
375     }
376   }
377 
378   loss_account = bwe_receiver_.LinkedSetPacketLossRatio();
379   EXPECT_NEAR(loss_account.LossRatio(), 0.5f, 0.001f);
380 
381   bwe_receiver_.RelieveSetAndUpdateLoss();
382   EXPECT_EQ(bwe_receiver_.received_packets_.size(), 100U / 10);
383 
384   // No packet loss within the preserved packets.
385   loss_account = bwe_receiver_.LinkedSetPacketLossRatio();
386   EXPECT_NEAR(loss_account.LossRatio(), 0.0f, 0.001f);
387 
388   // RelieveSetAndUpdateLoss automatically updates loss account.
389   EXPECT_NEAR(bwe_receiver_.GlobalReceiverPacketLossRatio(), 0.5f, 0.001f);
390 }
391 
392 }  // namespace bwe
393 }  // namespace testing
394 }  // namespace webrtc
395