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 "webrtc/modules/remote_bitrate_estimator/test/bwe.h"
12
13#include <vector>
14
15#include "testing/gtest/include/gtest/gtest.h"
16#include "webrtc/base/arraysize.h"
17
18namespace webrtc {
19namespace testing {
20namespace bwe {
21
22const int kSetCapacity = 1000;
23
24class LinkedSetTest : public ::testing::Test {
25 public:
26  LinkedSetTest() : linked_set_(kSetCapacity) {}
27
28  ~LinkedSetTest() {}
29
30 protected:
31  LinkedSet linked_set_;
32};
33
34TEST_F(LinkedSetTest, EmptySet) {
35  EXPECT_EQ(linked_set_.OldestSeqNumber(), 0);
36  EXPECT_EQ(linked_set_.NewestSeqNumber(), 0);
37}
38
39TEST_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
48TEST_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
67TEST_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
83class SequenceNumberOlderThanTest : public ::testing::Test {
84 public:
85  SequenceNumberOlderThanTest() {}
86  ~SequenceNumberOlderThanTest() {}
87
88 protected:
89  SequenceNumberOlderThan comparator_;
90};
91
92TEST_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
104class LossAccountTest : public ::testing::Test {
105 public:
106  LossAccountTest() {}
107  ~LossAccountTest() {}
108
109 protected:
110  LossAccount loss_account_;
111};
112
113TEST_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
131class BweReceiverTest : public ::testing::Test {
132 public:
133  BweReceiverTest() : bwe_receiver_(kFlowId) {}
134  ~BweReceiverTest() {}
135
136 protected:
137  const int kFlowId = 1;  // Arbitrary.
138  BweReceiver bwe_receiver_;
139};
140
141TEST_F(BweReceiverTest, ReceivingRateNoPackets) {
142  EXPECT_EQ(bwe_receiver_.RecentKbps(), static_cast<size_t>(0));
143}
144
145TEST_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
162TEST_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
181TEST_F(BweReceiverTest, PacketLossNoPackets) {
182  EXPECT_EQ(bwe_receiver_.RecentPacketLossRatio(), 0.0f);
183}
184
185TEST_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
191TEST_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.
233TEST_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
260TEST_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
276TEST_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.
295TEST_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.
314TEST_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
333TEST_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
362TEST_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