src/third_party/webrtc/modules/remote_bitrate_estimator/test/bwe_test_framework_unittest.cc

   1 /*
   2  *  Copyright (c) 2013 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_test_framework.h"
  12
  13 #include <numeric>
  14
  15 #include "gtest/gtest.h"
  16 #include "webrtc/system_wrappers/interface/constructor_magic.h"
  17
  18 using std::vector;
  19
  20 namespace webrtc {
  21 namespace testing {
  22 namespace bwe {
  23
  24 TEST(BweTestFramework_RandomTest, Gaussian) {
  25   enum {
  26     kN = 100000,
  27     kBuckets = 100,
  28     kMean = 49,
  29     kStddev = 10
  30   };
  31
  32   Random random(0x12345678);
  33
  34   int buckets[kBuckets] = {0};
  35   for (int i = 0; i < kN; ++i) {
  36     int index = random.Gaussian(kMean, kStddev);
  37     if (index >= 0 && index < kBuckets) {
  38       buckets[index]++;
  39     }
  40   }
  41
  42   const double kPi = 3.14159265358979323846;
  43   const double kScale = kN / (kStddev * std::sqrt(2.0 * kPi));
  44   const double kDiv = -2.0 * kStddev * kStddev;
  45   double self_corr = 0.0;
  46   double bucket_corr = 0.0;
  47   for (int n = 0; n < kBuckets; ++n) {
  48     double normal_dist = kScale * std::exp((n - kMean) * (n - kMean) / kDiv);
  49     self_corr += normal_dist * normal_dist;
  50     bucket_corr += normal_dist * buckets[n];
  51   }
  52   printf("Correlation: %f (random sample), %f (self), %f (quotient)\n",
  53          bucket_corr, self_corr, bucket_corr / self_corr);
  54   EXPECT_NEAR(1.0, bucket_corr / self_corr, 0.0004);
  55 }
  56
  57 static bool IsSequenceNumberSorted(const Packets& packets) {
  58   PacketsConstIt last_it = packets.begin();
  59   for (PacketsConstIt it = last_it; it != packets.end(); ++it) {
  60     if (IsNewerSequenceNumber(last_it->header().sequenceNumber,
  61                               it->header().sequenceNumber)) {
  62       return false;
  63     }
  64     last_it = it;
  65   }
  66   return true;
  67 }
  68
  69 TEST(BweTestFramework_BwePacketTest, IsTimeSorted) {
  70   Packets packets;
  71   // Insert some packets in order...
  72   EXPECT_TRUE(IsTimeSorted(packets));
  73
  74   packets.push_back(BwePacket(100, 0));
  75   EXPECT_TRUE(IsTimeSorted(packets));
  76
  77   packets.push_back(BwePacket(110, 0));
  78   EXPECT_TRUE(IsTimeSorted(packets));
  79
  80   // ...and one out-of-order...
  81   packets.push_back(BwePacket(100, 0));
  82   EXPECT_FALSE(IsTimeSorted(packets));
  83
  84   // ...remove the out-of-order packet, insert another in-order packet.
  85   packets.pop_back();
  86   packets.push_back(BwePacket(120, 0));
  87   EXPECT_TRUE(IsTimeSorted(packets));
  88 }
  89
  90 TEST(BweTestFramework_BwePacketTest, IsSequenceNumberSorted) {
  91   Packets packets;
  92   // Insert some packets in order...
  93   EXPECT_TRUE(IsSequenceNumberSorted(packets));
  94
  95   packets.push_back(BwePacket(0, 100));
  96   EXPECT_TRUE(IsSequenceNumberSorted(packets));
  97
  98   packets.push_back(BwePacket(0, 110));
  99   EXPECT_TRUE(IsSequenceNumberSorted(packets));
 100
 101   // ...and one out-of-order...
 102   packets.push_back(BwePacket(0, 100));
 103   EXPECT_FALSE(IsSequenceNumberSorted(packets));
 104
 105   // ...remove the out-of-order packet, insert another in-order packet.
 106   packets.pop_back();
 107   packets.push_back(BwePacket(0, 120));
 108   EXPECT_TRUE(IsSequenceNumberSorted(packets));
 109 }
 110
 111 TEST(BweTestFramework_StatsTest, Mean) {
 112   Stats<int32_t> stats;
 113   EXPECT_EQ(0, stats.GetMean());
 114
 115   stats.Push(1);
 116   stats.Push(3);
 117   EXPECT_EQ(2, stats.GetMean());
 118
 119   // Integer division rounds (1+3-3)/3 to 0.
 120   stats.Push(-3);
 121   EXPECT_EQ(0, stats.GetMean());
 122 }
 123
 124 TEST(BweTestFramework_StatsTest, Variance) {
 125   Stats<int32_t> stats;
 126   EXPECT_EQ(0, stats.GetVariance());
 127
 128   // Mean is 2 ; ((1-2)*(1-2)+(3-2)*(3-2))/2 = (1+1)/2 = 1
 129   stats.Push(1);
 130   stats.Push(3);
 131   EXPECT_EQ(1, stats.GetVariance());
 132
 133   // Integer division rounds 26/3 to 8
 134   // Mean is 0 ; (1*1+3*3+(-4)*(-4))/3 = (1+9+16)/3 = 8
 135   stats.Push(-4);
 136   EXPECT_EQ(8, stats.GetVariance());
 137 }
 138
 139 TEST(BweTestFramework_StatsTest, StdDev) {
 140   Stats<int32_t> stats;
 141   EXPECT_EQ(0, stats.GetStdDev());
 142
 143   // Variance is 1 ; sqrt(1) = 1
 144   stats.Push(1);
 145   stats.Push(3);
 146   EXPECT_EQ(1, stats.GetStdDev());
 147
 148   // Variance is 8 ; sqrt(8) = 2 with integers.
 149   stats.Push(-4);
 150   EXPECT_EQ(2, stats.GetStdDev());
 151 }
 152
 153 TEST(BweTestFramework_StatsTest, MinMax) {
 154   Stats<int32_t> stats;
 155   EXPECT_EQ(0, stats.GetMin());
 156   EXPECT_EQ(0, stats.GetMax());
 157
 158   stats.Push(1);
 159   EXPECT_EQ(1, stats.GetMin());
 160   EXPECT_EQ(1, stats.GetMax());
 161
 162   stats.Push(3);
 163   EXPECT_EQ(1, stats.GetMin());
 164   EXPECT_EQ(3, stats.GetMax());
 165
 166   stats.Push(-4);
 167   EXPECT_EQ(-4, stats.GetMin());
 168   EXPECT_EQ(3, stats.GetMax());
 169 }
 170
 171 void TestVideoSender(VideoSender* sender, int64_t run_for_ms,
 172                      uint32_t expected_packets,
 173                      uint32_t expected_payload_size,
 174                      uint32_t expected_total_payload_size) {
 175   assert(sender);
 176   Packets packets;
 177   sender->RunFor(run_for_ms, &packets);
 178   ASSERT_TRUE(IsTimeSorted(packets));
 179   ASSERT_TRUE(IsSequenceNumberSorted(packets));
 180   EXPECT_EQ(expected_packets, packets.size());
 181   int64_t send_time_us = -1;
 182   uint32_t total_payload_size = 0;
 183   uint32_t absolute_send_time = 0;
 184   uint32_t absolute_send_time_wraps = 0;
 185   uint32_t rtp_timestamp = 0;
 186   uint32_t rtp_timestamp_wraps = 0;
 187   for (PacketsIt it = packets.begin(); it != packets.end(); ++it) {
 188     EXPECT_LE(send_time_us, it->send_time_us());
 189     send_time_us = it->send_time_us();
 190     if (sender->max_payload_size_bytes() != it->payload_size()) {
 191       EXPECT_EQ(expected_payload_size, it->payload_size());
 192     }
 193     total_payload_size += it->payload_size();
 194     if (absolute_send_time > it->header().extension.absoluteSendTime) {
 195       absolute_send_time_wraps++;
 196     }
 197     absolute_send_time = it->header().extension.absoluteSendTime;
 198     if (rtp_timestamp > it->header().timestamp) {
 199       rtp_timestamp_wraps++;
 200     }
 201     rtp_timestamp = it->header().timestamp;
 202   }
 203   EXPECT_EQ(expected_total_payload_size, total_payload_size);
 204   EXPECT_GE(1u, absolute_send_time_wraps);
 205   EXPECT_GE(1u, rtp_timestamp_wraps);
 206 }
 207
 208 TEST(BweTestFramework_VideoSenderTest, Fps1Kpbs80_1s) {
 209   // 1 fps, 80 kbps
 210   VideoSender sender(1.0f, 80, 0x1234, 0);
 211   EXPECT_EQ(10000u, sender.bytes_per_second());
 212   // We're at 1 fps, so all packets should be generated on first call, giving 10
 213   // packets of each 1000 bytes, total 10000 bytes.
 214   TestVideoSender(&sender, 1, 10, 1000, 10000);
 215   // 999ms, should see no output here.
 216   TestVideoSender(&sender, 998, 0, 0, 0);
 217   // 1999ms, should get data for one more frame.
 218   TestVideoSender(&sender, 1000, 10, 1000, 10000);
 219   // 2000ms, one more frame.
 220   TestVideoSender(&sender, 1, 10, 1000, 10000);
 221   // 2999ms, should see nothing.
 222   TestVideoSender(&sender, 999, 0, 0, 0);
 223 }
 224
 225 TEST(BweTestFramework_VideoSenderTest, Fps1Kpbs80_1s_Offset) {
 226   // 1 fps, 80 kbps, offset 0.5 of a frame period, ==0.5s in this case.
 227   VideoSender sender(1.0f, 80, 0x1234, 0.5f);
 228   EXPECT_EQ(10000u, sender.bytes_per_second());
 229   // 499ms, no output.
 230   TestVideoSender(&sender, 499, 0, 0, 0);
 231   // 500ms, first frame (this is the offset we set), 10 packets of 1000 bytes.
 232   TestVideoSender(&sender, 1, 10, 1000, 10000);
 233   // 1499ms, nothing.
 234   TestVideoSender(&sender, 999, 0, 0, 0);
 235   // 1999ms, second frame.
 236   TestVideoSender(&sender, 500, 10, 1000, 10000);
 237   // 2499ms, nothing.
 238   TestVideoSender(&sender, 500, 0, 0, 0);
 239   // 2500ms, third frame.
 240   TestVideoSender(&sender, 1, 10, 1000, 10000);
 241   // 3499ms, nothing.
 242   TestVideoSender(&sender, 999, 0, 0, 0);
 243 }
 244
 245 TEST(BweTestFramework_VideoSenderTest, Fps50Kpbs80_11s) {
 246   // 50 fps, 80 kbps.
 247   VideoSender sender(50.0f, 80, 0x1234, 0);
 248   EXPECT_EQ(10000u, sender.bytes_per_second());
 249   // 9998ms, should see 500 frames, 200 byte payloads, total 100000 bytes.
 250   TestVideoSender(&sender, 9998, 500, 200, 100000);
 251   // 9999ms, nothing.
 252   TestVideoSender(&sender, 1, 0, 0, 0);
 253   // 10000ms, 501st frame as a single packet.
 254   TestVideoSender(&sender, 1, 1, 200, 200);
 255   // 10998ms, 49 more frames.
 256   TestVideoSender(&sender, 998, 49, 200, 9800);
 257   // 10999ms, nothing.
 258   TestVideoSender(&sender, 1, 0, 0, 0);
 259 }
 260
 261 TEST(BweTestFramework_VideoSenderTest, Fps10Kpbs120_1s) {
 262   // 20 fps, 120 kbps.
 263   VideoSender sender(20.0f, 120, 0x1234, 0);
 264   EXPECT_EQ(15000u, sender.bytes_per_second());
 265   // 498ms, 10 frames with 750 byte payloads, total 7500 bytes.
 266   TestVideoSender(&sender, 498, 10, 750, 7500);
 267   // 499ms, nothing.
 268   TestVideoSender(&sender, 1, 0, 0, 0);
 269   // 500ms, one more frame.
 270   TestVideoSender(&sender, 1, 1, 750, 750);
 271   // 998ms, 9 more frames.
 272   TestVideoSender(&sender, 498, 9, 750, 6750);
 273   // 999ms, nothing.
 274   TestVideoSender(&sender, 1, 0, 0, 0);
 275 }
 276
 277 TEST(BweTestFramework_VideoSenderTest, Fps30Kpbs800_20s) {
 278   // 20 fps, 820 kbps.
 279   VideoSender sender(25.0f, 820, 0x1234, 0);
 280   EXPECT_EQ(102500u, sender.bytes_per_second());
 281   // 9998ms, 250 frames. 820 kbps = 102500 bytes/s, so total should be 1025000.
 282   // Each frame is 102500/25=4100 bytes, or 5 packets (4 @1000 bytes, 1 @100),
 283   // so packet count should be 5*250=1250 and last packet of each frame has
 284   // 100 bytes of payload.
 285   TestVideoSender(&sender, 9998, 1250, 100, 1025000);
 286   // 9999ms, nothing.
 287   TestVideoSender(&sender, 1, 0, 0, 0);
 288   // 19998ms, 250 more frames.
 289   TestVideoSender(&sender, 9999, 1250, 100, 1025000);
 290   // 19999ms, nothing.
 291   TestVideoSender(&sender, 1, 0, 0, 0);
 292   // 20038ms, one more frame, as described above (25fps == 40ms/frame).
 293   TestVideoSender(&sender, 39, 5, 100, 4100);
 294   // 20039ms, nothing.
 295   TestVideoSender(&sender, 1, 0, 0, 0);
 296 }
 297
 298 TEST(BweTestFramework_VideoSenderTest, TestAppendInOrder) {
 299   // 1 fps, 80 kbps, 250ms offset.
 300   VideoSender sender1(1.0f, 80, 0x1234, 0.25f);
 301   EXPECT_EQ(10000u, sender1.bytes_per_second());
 302   Packets packets;
 303   // Generate some packets, verify they are sorted.
 304   sender1.RunFor(999, &packets);
 305   ASSERT_TRUE(IsTimeSorted(packets));
 306   ASSERT_TRUE(IsSequenceNumberSorted(packets));
 307   EXPECT_EQ(10u, packets.size());
 308   // Generate some more packets and verify they are appended to end of list.
 309   sender1.RunFor(1000, &packets);
 310   ASSERT_TRUE(IsTimeSorted(packets));
 311   ASSERT_TRUE(IsSequenceNumberSorted(packets));
 312   EXPECT_EQ(20u, packets.size());
 313
 314   // Another sender, 2 fps, 160 kpbs, 150ms offset
 315   VideoSender sender2(2.0f, 160, 0x2234, 0.30f);
 316   EXPECT_EQ(20000u, sender2.bytes_per_second());
 317   // Generate some packets, verify that they are merged with the packets already
 318   // on the list.
 319   sender2.RunFor(999, &packets);
 320   ASSERT_TRUE(IsTimeSorted(packets));
 321   EXPECT_EQ(40u, packets.size());
 322   // Generate some more.
 323   sender2.RunFor(1000, &packets);
 324   ASSERT_TRUE(IsTimeSorted(packets));
 325   EXPECT_EQ(60u, packets.size());
 326 }
 327
 328 class BweTestFramework_RateCounterFilterTest : public ::testing::Test {
 329  public:
 330   BweTestFramework_RateCounterFilterTest()
 331     : filter_(),
 332       now_ms_(0) {
 333   }
 334   virtual ~BweTestFramework_RateCounterFilterTest() {}
 335
 336  protected:
 337   void TestRateCounter(int64_t run_for_ms, uint32_t payload_bits,
 338                        uint32_t expected_pps, uint32_t expected_bps) {
 339     Packets packets;
 340     RTPHeader header = {0};
 341     // "Send" a packet every 10 ms.
 342     for (int64_t i = 0; i < run_for_ms; i += 10, now_ms_ += 10) {
 343       packets.push_back(BwePacket(now_ms_ * 1000, payload_bits / 8, header));
 344     }
 345     filter_.RunFor(run_for_ms, &packets);
 346     ASSERT_TRUE(IsTimeSorted(packets));
 347     EXPECT_EQ(expected_pps, filter_.packets_per_second());
 348     EXPECT_EQ(expected_bps, filter_.bits_per_second());
 349   }
 350
 351  private:
 352   RateCounterFilter filter_;
 353   int64_t now_ms_;
 354
 355   DISALLOW_COPY_AND_ASSIGN(BweTestFramework_RateCounterFilterTest);
 356 };
 357
 358 TEST_F(BweTestFramework_RateCounterFilterTest, Short) {
 359   // 100ms, 100 bytes per packet, should result in 10 pps and 8 kbps. We're
 360   // generating one packet every 10 ms ; 10 * 800 = 8k
 361   TestRateCounter(100, 800, 10, 8000);
 362 }
 363
 364 TEST_F(BweTestFramework_RateCounterFilterTest, Medium) {
 365   // 100ms, like above.
 366   TestRateCounter(100, 800, 10, 8000);
 367   // 1000ms, 100 bpp, should result in 100 pps and 80 kbps. We're still
 368   // generating packets every 10 ms.
 369   TestRateCounter(900, 800, 100, 80000);
 370 }
 371
 372 TEST_F(BweTestFramework_RateCounterFilterTest, Long) {
 373   // 100ms, 1000ms, like above.
 374   TestRateCounter(100, 800, 10, 8000);
 375   TestRateCounter(900, 800, 100, 80000);
 376   // 2000ms, should only see rate of last second, so 100 pps, and 40 kbps now.
 377   TestRateCounter(1000, 400, 100, 40000);
 378   // 2500ms, half a second with zero payload size. We should get same pps as
 379   // before, but kbps should drop to half of previous rate.
 380   TestRateCounter(500, 0, 100, 20000);
 381   // Another half second with zero payload size. Now the kbps rate should drop
 382   // to zero.
 383   TestRateCounter(500, 0, 100, 0);
 384   // Increate payload size again. 200 * 100 * 0.5 = 10 kbps.
 385   TestRateCounter(500, 200, 100, 10000);
 386 }
 387
 388 static void TestLossFilter(float loss_percent, bool zero_tolerance) {
 389   LossFilter filter;
 390   filter.SetLoss(loss_percent);
 391   Packets::size_type sent_packets = 0;
 392   Packets::size_type remaining_packets = 0;
 393
 394   // No input should yield no output
 395   {
 396     Packets packets;
 397     sent_packets += packets.size();
 398     filter.RunFor(0, &packets);
 399     ASSERT_TRUE(IsTimeSorted(packets));
 400     ASSERT_TRUE(IsSequenceNumberSorted(packets));
 401     remaining_packets += packets.size();
 402     EXPECT_EQ(0u, sent_packets);
 403     EXPECT_EQ(0u, remaining_packets);
 404   }
 405
 406   // Generate and process 10000 packets in different batch sizes (some empty)
 407   for (int i = 0; i < 2225; ++i) {
 408     Packets packets;
 409     packets.insert(packets.end(), i % 10, BwePacket());
 410     sent_packets += packets.size();
 411     filter.RunFor(0, &packets);
 412     ASSERT_TRUE(IsTimeSorted(packets));
 413     ASSERT_TRUE(IsSequenceNumberSorted(packets));
 414     remaining_packets += packets.size();
 415   }
 416
 417   float loss_fraction = 0.01f * (100.0f - loss_percent);
 418   Packets::size_type expected_packets = loss_fraction * sent_packets;
 419   if (zero_tolerance) {
 420     EXPECT_EQ(expected_packets, remaining_packets);
 421   } else {
 422     // Require within 1% of expected
 423     EXPECT_NEAR(expected_packets, remaining_packets, 100);
 424   }
 425 }
 426
 427 TEST(BweTestFramework_LossFilterTest, Loss0) {
 428   // With 0% loss, the result should be exact (no loss).
 429   TestLossFilter(0.0f, true);
 430 }
 431
 432 TEST(BweTestFramework_LossFilterTest, Loss10) {
 433   TestLossFilter(10.0f, false);
 434 }
 435
 436 TEST(BweTestFramework_LossFilterTest, Loss50) {
 437   TestLossFilter(50.0f, false);
 438 }
 439
 440 TEST(BweTestFramework_LossFilterTest, Loss100) {
 441   // With 100% loss, the result should be exact (no packets out).
 442   TestLossFilter(100.0f, true);
 443 }
 444
 445 class BweTestFramework_DelayFilterTest : public ::testing::Test {
 446  public:
 447   BweTestFramework_DelayFilterTest()
 448     : filter_(),
 449       now_ms_(0),
 450       sequence_number_(0) {
 451   }
 452   virtual ~BweTestFramework_DelayFilterTest() {}
 453
 454  protected:
 455   void TestDelayFilter(int64_t run_for_ms, uint32_t in_packets,
 456                        uint32_t out_packets) {
 457     Packets packets;
 458     for (uint32_t i = 0; i < in_packets; ++i) {
 459       packets.push_back(BwePacket(now_ms_ * 1000 + (sequence_number_ >> 4),
 460                                   sequence_number_));
 461       sequence_number_++;
 462     }
 463     filter_.RunFor(run_for_ms, &packets);
 464     ASSERT_TRUE(IsTimeSorted(packets));
 465     ASSERT_TRUE(IsSequenceNumberSorted(packets));
 466     for (PacketsConstIt it = packets.begin(); it != packets.end(); ++it) {
 467       EXPECT_LE(now_ms_ * 1000, it->send_time_us());
 468     }
 469     EXPECT_EQ(out_packets, packets.size());
 470     accumulated_packets_.splice(accumulated_packets_.end(), packets);
 471     now_ms_ += run_for_ms;
 472   }
 473
 474   void TestDelayFilter(int64_t delay_ms) {
 475     filter_.SetDelay(delay_ms);
 476     TestDelayFilter(1, 0, 0);    // No input should yield no output
 477
 478     // Single packet
 479     TestDelayFilter(0, 1, 1);
 480     TestDelayFilter(delay_ms, 0, 0);
 481
 482     for (int i = 0; i < delay_ms; ++i) {
 483       filter_.SetDelay(i);
 484       TestDelayFilter(1, 10, 10);
 485     }
 486     TestDelayFilter(0, 0, 0);
 487     TestDelayFilter(delay_ms, 0, 0);
 488
 489     // Wait a little longer - should still see no output
 490     TestDelayFilter(delay_ms, 0, 0);
 491
 492     for (int i = 1; i < delay_ms + 1; ++i) {
 493       filter_.SetDelay(i);
 494       TestDelayFilter(1, 5, 5);
 495     }
 496     TestDelayFilter(0, 0, 0);
 497     filter_.SetDelay(2 * delay_ms);
 498     TestDelayFilter(1, 0, 0);
 499     TestDelayFilter(delay_ms, 13, 13);
 500     TestDelayFilter(delay_ms, 0, 0);
 501
 502     // Wait a little longer - should still see no output
 503     TestDelayFilter(delay_ms, 0, 0);
 504
 505     for (int i = 0; i < 2 * delay_ms; ++i) {
 506       filter_.SetDelay(2 * delay_ms - i - 1);
 507       TestDelayFilter(1, 5, 5);
 508     }
 509     TestDelayFilter(0, 0, 0);
 510     filter_.SetDelay(0);
 511     TestDelayFilter(0, 7, 7);
 512
 513     ASSERT_TRUE(IsTimeSorted(accumulated_packets_));
 514     ASSERT_TRUE(IsSequenceNumberSorted(accumulated_packets_));
 515   }
 516
 517   DelayFilter filter_;
 518   Packets accumulated_packets_;
 519
 520  private:
 521   int64_t now_ms_;
 522   uint32_t sequence_number_;
 523
 524   DISALLOW_COPY_AND_ASSIGN(BweTestFramework_DelayFilterTest);
 525 };
 526
 527 TEST_F(BweTestFramework_DelayFilterTest, Delay0) {
 528   TestDelayFilter(1, 0, 0);    // No input should yield no output
 529   TestDelayFilter(1, 10, 10);  // Expect no delay (delay time is zero)
 530   TestDelayFilter(1, 0, 0);    // Check no packets are still in buffer
 531   filter_.SetDelay(0);
 532   TestDelayFilter(1, 5, 5);    // Expect no delay (delay time is zero)
 533   TestDelayFilter(1, 0, 0);    // Check no packets are still in buffer
 534 }
 535
 536 TEST_F(BweTestFramework_DelayFilterTest, Delay1) {
 537   TestDelayFilter(1);
 538 }
 539
 540 TEST_F(BweTestFramework_DelayFilterTest, Delay2) {
 541   TestDelayFilter(2);
 542 }
 543
 544 TEST_F(BweTestFramework_DelayFilterTest, Delay20) {
 545   TestDelayFilter(20);
 546 }
 547
 548 TEST_F(BweTestFramework_DelayFilterTest, Delay100) {
 549   TestDelayFilter(100);
 550 }
 551
 552 TEST_F(BweTestFramework_DelayFilterTest, JumpToZeroDelay) {
 553   DelayFilter delay;
 554   Packets acc;
 555   Packets packets;
 556
 557   // Delay a bunch of packets, accumulate them to the 'acc' list.
 558   delay.SetDelay(100.0f);
 559   for (uint32_t i = 0; i < 10; ++i) {
 560     packets.push_back(BwePacket(i * 100, i));
 561   }
 562   delay.RunFor(1000, &packets);
 563   acc.splice(acc.end(), packets);
 564   ASSERT_TRUE(IsTimeSorted(acc));
 565   ASSERT_TRUE(IsSequenceNumberSorted(acc));
 566
 567   // Drop delay to zero, send a few more packets through the delay, append them
 568   // to the 'acc' list and verify that it is all sorted.
 569   delay.SetDelay(0.0f);
 570   for (uint32_t i = 10; i < 50; ++i) {
 571     packets.push_back(BwePacket(i * 100, i));
 572   }
 573   delay.RunFor(1000, &packets);
 574   acc.splice(acc.end(), packets);
 575   ASSERT_TRUE(IsTimeSorted(acc));
 576   ASSERT_TRUE(IsSequenceNumberSorted(acc));
 577 }
 578
 579 TEST_F(BweTestFramework_DelayFilterTest, IncreasingDelay) {
 580   // Gradually increase delay.
 581   for (int i = 1; i < 50; i += 4) {
 582     TestDelayFilter(i);
 583   }
 584   // Reach a steady state.
 585   filter_.SetDelay(100);
 586   TestDelayFilter(1, 20, 20);
 587   TestDelayFilter(2, 0, 0);
 588   TestDelayFilter(99, 20, 20);
 589   // Drop delay back down to zero.
 590   filter_.SetDelay(0);
 591   TestDelayFilter(1, 100, 100);
 592   TestDelayFilter(23010, 0, 0);
 593   ASSERT_TRUE(IsTimeSorted(accumulated_packets_));
 594   ASSERT_TRUE(IsSequenceNumberSorted(accumulated_packets_));
 595 }
 596
 597 static void TestJitterFilter(int64_t stddev_jitter_ms) {
 598   JitterFilter filter;
 599   filter.SetJitter(stddev_jitter_ms);
 600
 601   int64_t now_ms = 0;
 602   uint32_t sequence_number = 0;
 603
 604   // Generate packets, add jitter to them, accumulate the altered packets.
 605   Packets original;
 606   Packets jittered;
 607   for (uint32_t i = 0; i < 1000; ++i) {
 608     Packets packets;
 609     for (uint32_t j = 0; j < i % 100; ++j) {
 610       packets.push_back(BwePacket(now_ms * 1000, sequence_number++));
 611       now_ms += 5 * stddev_jitter_ms;
 612     }
 613     original.insert(original.end(), packets.begin(), packets.end());
 614     filter.RunFor(stddev_jitter_ms, &packets);
 615     jittered.splice(jittered.end(), packets);
 616   }
 617
 618   // Jittered packets should still be in order.
 619   ASSERT_TRUE(IsTimeSorted(original));
 620   ASSERT_TRUE(IsTimeSorted(jittered));
 621   ASSERT_TRUE(IsSequenceNumberSorted(original));
 622   ASSERT_TRUE(IsSequenceNumberSorted(jittered));
 623   EXPECT_EQ(original.size(), jittered.size());
 624
 625   // Make sure jittered and original packets are in same order. Collect time
 626   // difference (jitter) in stats, then check that mean jitter is close to zero
 627   // and standard deviation of jitter is what we set it to.
 628   Stats<double> jitter_us;
 629   for (PacketsIt it1 = original.begin(), it2 = jittered.begin();
 630        it1 != original.end() && it2 != jittered.end(); ++it1, ++it2) {
 631     EXPECT_EQ(it1->header().sequenceNumber, it2->header().sequenceNumber);
 632     jitter_us.Push(it2->send_time_us() - it1->send_time_us());
 633   }
 634   EXPECT_NEAR(0.0, jitter_us.GetMean(), stddev_jitter_ms * 1000.0 * 0.008);
 635   EXPECT_NEAR(stddev_jitter_ms * 1000.0, jitter_us.GetStdDev(),
 636               stddev_jitter_ms * 1000.0 * 0.02);
 637 }
 638
 639 TEST(BweTestFramework_JitterFilterTest, Jitter0) {
 640   TestJitterFilter(0);
 641 }
 642
 643 TEST(BweTestFramework_JitterFilterTest, Jitter1) {
 644   TestJitterFilter(1);
 645 }
 646
 647 TEST(BweTestFramework_JitterFilterTest, Jitter5) {
 648   TestJitterFilter(5);
 649 }
 650
 651 TEST(BweTestFramework_JitterFilterTest, Jitter10) {
 652   TestJitterFilter(10);
 653 }
 654
 655 TEST(BweTestFramework_JitterFilterTest, Jitter1031) {
 656   TestJitterFilter(1031);
 657 }
 658
 659 static void TestReorderFilter(uint32_t reorder_percent, uint32_t near) {
 660   const uint32_t kPacketCount = 10000;
 661
 662   // Generate packets with 10 ms interval.
 663   Packets packets;
 664   int64_t now_ms = 0;
 665   uint32_t sequence_number = 1;
 666   for (uint32_t i = 0; i < kPacketCount; ++i, now_ms += 10) {
 667     packets.push_back(BwePacket(now_ms * 1000, sequence_number++));
 668   }
 669   ASSERT_TRUE(IsTimeSorted(packets));
 670   ASSERT_TRUE(IsSequenceNumberSorted(packets));
 671
 672   // Reorder packets, verify that send times are still in order.
 673   ReorderFilter filter;
 674   filter.SetReorder(reorder_percent);
 675   filter.RunFor(now_ms, &packets);
 676   ASSERT_TRUE(IsTimeSorted(packets));
 677
 678   // We measure the amount of reordering by summing the distance by which out-
 679   // of-order packets have been moved in the stream.
 680   uint32_t distance = 0;
 681   uint32_t last_sequence_number = 0;
 682   for (PacketsIt it = packets.begin(); it != packets.end(); ++it) {
 683     uint32_t sequence_number = it->header().sequenceNumber;
 684     if (sequence_number < last_sequence_number) {
 685       distance += last_sequence_number - sequence_number;
 686     }
 687     last_sequence_number = sequence_number;
 688   }
 689
 690   // Because reordering is random, we allow a threshold when comparing. The
 691   // maximum distance a packet can be moved is PacketCount - 1.
 692   EXPECT_NEAR(((kPacketCount - 1) * reorder_percent) / 100, distance, near);
 693 }
 694
 695 TEST(BweTestFramework_ReorderFilterTest, Reorder0) {
 696   // For 0% reordering, no packets should have been moved, so result is exact.
 697   TestReorderFilter(0, 0);
 698 }
 699
 700 TEST(BweTestFramework_ReorderFilterTest, Reorder10) {
 701   TestReorderFilter(10, 30);
 702 }
 703
 704 TEST(BweTestFramework_ReorderFilterTest, Reorder20) {
 705   TestReorderFilter(20, 20);
 706 }
 707
 708 TEST(BweTestFramework_ReorderFilterTest, Reorder50) {
 709   TestReorderFilter(50, 20);
 710 }
 711
 712 TEST(BweTestFramework_ReorderFilterTest, Reorder70) {
 713   TestReorderFilter(70, 20);
 714 }
 715
 716 TEST(BweTestFramework_ReorderFilterTest, Reorder100) {
 717   // Note that because the implementation works by optionally swapping two
 718   // adjacent packets, when the likelihood of a swap is 1.0, a swap will always
 719   // occur, so the stream will be in order except for the first packet, which
 720   // has been moved to the end. Therefore we expect the result to be exact here.
 721   TestReorderFilter(100.0, 0);
 722 }
 723
 724 class BweTestFramework_ChokeFilterTest : public ::testing::Test {
 725  public:
 726   BweTestFramework_ChokeFilterTest()
 727     : filter_(),
 728       now_ms_(0),
 729       sequence_number_(0),
 730       output_packets_(),
 731       send_times_us_() {
 732   }
 733   virtual ~BweTestFramework_ChokeFilterTest() {}
 734
 735  protected:
 736   ChokeFilter filter_;
 737
 738   void TestChoke(int64_t run_for_ms, uint32_t packets_to_generate,
 739                  uint32_t expected_kbit_transmitted) {
 740     // Generate a bunch of packets, apply choke, verify output is ordered.
 741     Packets packets;
 742     RTPHeader header = {0};
 743     for (uint32_t i = 0; i < packets_to_generate; ++i) {
 744       int64_t send_time_ms = now_ms_ + (i * run_for_ms) / packets_to_generate;
 745       header.sequenceNumber = sequence_number_++;
 746       // Payload is 1000 bits.
 747       packets.push_back(BwePacket(send_time_ms * 1000, 125, header));
 748       send_times_us_.push_back(send_time_ms * 1000);
 749     }
 750     ASSERT_TRUE(IsTimeSorted(packets));
 751     filter_.RunFor(run_for_ms, &packets);
 752     now_ms_ += run_for_ms;
 753     output_packets_.splice(output_packets_.end(), packets);
 754     ASSERT_TRUE(IsTimeSorted(output_packets_));
 755     ASSERT_TRUE(IsSequenceNumberSorted(output_packets_));
 756
 757     // Sum up the transmitted bytes up until the current time.
 758     uint32_t bytes_transmitted = 0;
 759     while (!output_packets_.empty()) {
 760       const BwePacket& packet = output_packets_.front();
 761       if (packet.send_time_us() > now_ms_ * 1000) {
 762         break;
 763       }
 764       bytes_transmitted += packet.payload_size();
 765       output_packets_.pop_front();
 766     }
 767     EXPECT_EQ(expected_kbit_transmitted, (bytes_transmitted * 8) / 1000);
 768   }
 769
 770   void CheckMaxDelay(int64_t max_delay_ms) {
 771     for (PacketsIt it = output_packets_.begin(); it != output_packets_.end();
 772         ++it) {
 773       const BwePacket& packet = *it;
 774       int64_t delay_us = packet.send_time_us() -
 775           send_times_us_[packet.header().sequenceNumber];
 776       EXPECT_GE(max_delay_ms * 1000, delay_us);
 777     }
 778   }
 779
 780  private:
 781   int64_t now_ms_;
 782   uint32_t sequence_number_;
 783   Packets output_packets_;
 784   std::vector<int64_t> send_times_us_;
 785
 786   DISALLOW_COPY_AND_ASSIGN(BweTestFramework_ChokeFilterTest);
 787 };
 788
 789 TEST_F(BweTestFramework_ChokeFilterTest, Short) {
 790   // 100ms, 100 packets, 10 kbps choke -> 1 kbit of data should have propagated.
 791   // That is actually just a single packet, since each packet has 1000 bits of
 792   // payload.
 793   filter_.SetCapacity(10);
 794   TestChoke(100, 100, 1);
 795 }
 796
 797 TEST_F(BweTestFramework_ChokeFilterTest, Medium) {
 798   // 100ms, 10 packets, 10 kbps choke -> 1 packet through, or 1 kbit.
 799   filter_.SetCapacity(10);
 800   TestChoke(100, 10, 1);
 801   // 200ms, no new packets -> another packet through.
 802   TestChoke(100, 0, 1);
 803   // 1000ms, no new packets -> 8 more packets.
 804   TestChoke(800, 0, 8);
 805   // 2000ms, no new packets -> queue is empty so no output.
 806   TestChoke(1000, 0, 0);
 807 }
 808
 809 TEST_F(BweTestFramework_ChokeFilterTest, Long) {
 810   // 100ms, 100 packets in queue, 10 kbps choke -> 1 packet through, or 1 kbit.
 811   filter_.SetCapacity(10);
 812   TestChoke(100, 100, 1);
 813   // 200ms, no input, another packet through.
 814   TestChoke(100, 0, 1);
 815   // 1000ms, no input, 8 packets through.
 816   TestChoke(800, 0, 8);
 817   // 10000ms, no input, raise choke to 100 kbps. Remaining 90 packets in queue
 818   // should be propagated, for a total of 90 kbps.
 819   filter_.SetCapacity(100);
 820   TestChoke(9000, 0, 90);
 821   // 10100ms, 20 more packets -> 10 packets or 10 kbit through.
 822   TestChoke(100, 20, 10);
 823   // 10300ms, 10 more packets -> 20 packets out.
 824   TestChoke(200, 10, 20);
 825   // 11300ms, no input, queue should be empty.
 826   filter_.SetCapacity(10);
 827   TestChoke(1000, 0, 0);
 828 }
 829
 830 TEST_F(BweTestFramework_ChokeFilterTest, MaxDelay) {
 831   // 10 kbps choke, 500 ms delay cap
 832   filter_.SetCapacity(10);
 833   filter_.SetMaxDelay(500);
 834   // 100ms, 100 packets in queue, 10 kbps choke -> 1 packet through, or 1 kbit.
 835   TestChoke(100, 100, 1);
 836   CheckMaxDelay(500);
 837   // 500ms, no input, 4 more packets through.
 838   TestChoke(400, 0, 4);
 839   // 10000ms, no input, remaining packets should have been dropped.
 840   TestChoke(9500, 0, 0);
 841
 842   // 100 ms delay cap
 843   filter_.SetMaxDelay(100);
 844   // 10100ms, 50 more packets -> 2 packets or 2 kbit through.
 845   TestChoke(100, 50, 2);
 846   CheckMaxDelay(100);
 847   // 20000ms, no input, remaining packets in queue should have been dropped.
 848   TestChoke(9900, 0, 0);
 849
 850   // Reset delay cap (0 is no cap) and verify no packets are dropped.
 851   filter_.SetCapacity(10);
 852   filter_.SetMaxDelay(0);
 853   TestChoke(100, 100, 2);
 854   TestChoke(9900, 0, 98);
 855 }
 856 }  // namespace bwe
 857 }  // namespace testing
 858 }  // namespace webrtc