src/net/quic/congestion_control/inter_arrival_bitrate_ramp_up_test.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <algorithm>
   6
   7 #include "base/basictypes.h"
   8 #include "base/logging.h"
   9 #include "net/quic/congestion_control/inter_arrival_bitrate_ramp_up.h"
  10 #include "net/quic/test_tools/mock_clock.h"
  11 #include "testing/gtest/include/gtest/gtest.h"
  12
  13 using std::min;
  14
  15 namespace net {
  16 namespace test {
  17
  18 class InterArrivalBitrateRampUpTest : public ::testing::Test {
  19  protected:
  20   InterArrivalBitrateRampUpTest()
  21       : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
  22         hundred_ms_(QuicTime::Delta::FromMilliseconds(100)),
  23         bitrate_ramp_up_(&clock_) {
  24   }
  25   virtual void SetUp() {
  26     clock_.AdvanceTime(one_ms_);
  27   }
  28   const QuicTime::Delta one_ms_;
  29   const QuicTime::Delta hundred_ms_;
  30   MockClock clock_;
  31   InterArrivalBitrateRampUp bitrate_ramp_up_;
  32 };
  33
  34 TEST_F(InterArrivalBitrateRampUpTest, GoodEstimates) {
  35   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(100);
  36   QuicBandwidth available_channel_estimate =
  37       QuicBandwidth::FromKBytesPerSecond(200);
  38   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(400);
  39   QuicBandwidth halfway_point = available_channel_estimate.Add(
  40       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
  41   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
  42   bitrate_ramp_up_.Reset(start_rate,
  43                          available_channel_estimate,
  44                          channel_estimate);
  45
  46   // First concave growth, towards available_channel_estimate.
  47   for (int i = 0; i < 25; ++i) {
  48     clock_.AdvanceTime(hundred_ms_);
  49     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  50     EXPECT_GE(available_channel_estimate, sent_bitrate);
  51     EXPECT_LE(start_rate, sent_bitrate);
  52   }
  53   clock_.AdvanceTime(hundred_ms_);
  54   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  55   EXPECT_LE(available_channel_estimate, sent_bitrate);
  56
  57   // First convex growth, from available_channel_estimate.
  58   for (int j = 0; j < 25; ++j) {
  59     clock_.AdvanceTime(hundred_ms_);
  60     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  61     EXPECT_LE(available_channel_estimate, sent_bitrate);
  62     EXPECT_GE(halfway_point, sent_bitrate);
  63   }
  64   clock_.AdvanceTime(hundred_ms_);
  65   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  66   EXPECT_LE(halfway_point, sent_bitrate);
  67
  68   // Second concave growth, towards channel_estimate.
  69   for (int i = 0; i < 24; ++i) {
  70     clock_.AdvanceTime(hundred_ms_);
  71     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  72     EXPECT_GE(channel_estimate, sent_bitrate);
  73     EXPECT_LE(halfway_point, sent_bitrate);
  74   }
  75   clock_.AdvanceTime(hundred_ms_);
  76   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  77   EXPECT_LE(channel_estimate, sent_bitrate);
  78
  79   // Second convex growth, from channel_estimate.
  80   for (int j = 0; j < 25; ++j) {
  81     clock_.AdvanceTime(hundred_ms_);
  82     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  83     EXPECT_LE(channel_estimate, sent_bitrate);
  84   }
  85   clock_.AdvanceTime(hundred_ms_);
  86   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  87   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 100000,
  88               sent_bitrate.ToBytesPerSecond(), 10000);
  89
  90   // Verify that we increase cubic.
  91   for (int j = 0; j < 23; ++j) {
  92     clock_.AdvanceTime(hundred_ms_);
  93     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  94     EXPECT_LE(channel_estimate, sent_bitrate);
  95   }
  96   clock_.AdvanceTime(hundred_ms_);
  97   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
  98   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 750000,
  99               sent_bitrate.ToBytesPerSecond(), 10000);
 100 }
 101
 102 TEST_F(InterArrivalBitrateRampUpTest, GoodEstimatesLimitedSendRate) {
 103   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(100);
 104   QuicBandwidth available_channel_estimate =
 105       QuicBandwidth::FromKBytesPerSecond(200);
 106   QuicBandwidth max_sent_rate =
 107       QuicBandwidth::FromKBytesPerSecond(125);
 108   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(400);
 109   QuicBandwidth halfway_point = available_channel_estimate.Add(
 110       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
 111   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 112   bitrate_ramp_up_.Reset(start_rate,
 113                          available_channel_estimate,
 114                          channel_estimate);
 115
 116   // First concave growth, towards available_channel_estimate.
 117   // Should pass without being affected by the max_sent_rate.
 118   for (int i = 0; i < 25; ++i) {
 119     clock_.AdvanceTime(hundred_ms_);
 120     // Cap our previus sent rate.
 121     sent_bitrate = min(sent_bitrate, max_sent_rate);
 122     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 123     EXPECT_GE(available_channel_estimate, sent_bitrate);
 124     EXPECT_LE(start_rate, sent_bitrate);
 125   }
 126   clock_.AdvanceTime(hundred_ms_);
 127   // Cap our previus sent rate.
 128   sent_bitrate = min(sent_bitrate, max_sent_rate);
 129   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 130   EXPECT_LE(available_channel_estimate, sent_bitrate);
 131
 132   // First convex growth, from available_channel_estimate.
 133   for (int j = 0; j < 25; ++j) {
 134     clock_.AdvanceTime(hundred_ms_);
 135     // Cap our previus sent rate.
 136     sent_bitrate = min(sent_bitrate, max_sent_rate);
 137     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 138     EXPECT_LE(available_channel_estimate, sent_bitrate);
 139     EXPECT_GE(halfway_point, sent_bitrate);
 140   }
 141   clock_.AdvanceTime(hundred_ms_);
 142   sent_bitrate = min(sent_bitrate, max_sent_rate);
 143   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 144   // We expect 2 * sent_bitrate to cap the rate.
 145   EXPECT_LE(max_sent_rate.Add(max_sent_rate), sent_bitrate);
 146   // Remove our sent cap.
 147   // Expect bitrate to continue to ramp from its previous rate.
 148   for (int j = 0; j < 5; ++j) {
 149     clock_.AdvanceTime(hundred_ms_);
 150     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 151     EXPECT_LE(available_channel_estimate, sent_bitrate);
 152     EXPECT_LE(max_sent_rate.Add(max_sent_rate), sent_bitrate);
 153     EXPECT_GE(halfway_point, sent_bitrate);
 154   }
 155   clock_.AdvanceTime(hundred_ms_);
 156   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 157   EXPECT_LE(halfway_point, sent_bitrate);
 158 }
 159
 160 TEST_F(InterArrivalBitrateRampUpTest, GoodEstimatesCloseToChannelEstimate) {
 161   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(100);
 162   QuicBandwidth available_channel_estimate =
 163       QuicBandwidth::FromKBytesPerSecond(200);
 164   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(250);
 165   QuicBandwidth halfway_point = available_channel_estimate.Add(
 166       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
 167   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 168   bitrate_ramp_up_.Reset(start_rate,
 169                          available_channel_estimate,
 170                          channel_estimate);
 171
 172   // First concave growth, towards available_channel_estimate.
 173   for (int i = 0; i < 25; ++i) {
 174     clock_.AdvanceTime(hundred_ms_);
 175     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 176     EXPECT_GE(available_channel_estimate, sent_bitrate);
 177     EXPECT_LE(start_rate, sent_bitrate);
 178   }
 179   clock_.AdvanceTime(hundred_ms_);
 180   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 181   EXPECT_LE(available_channel_estimate, sent_bitrate);
 182
 183   // First convex growth, from available_channel_estimate.
 184   for (int j = 0; j < 15; ++j) {
 185     clock_.AdvanceTime(hundred_ms_);
 186     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 187     EXPECT_LE(available_channel_estimate, sent_bitrate);
 188     EXPECT_GE(halfway_point, sent_bitrate);
 189   }
 190   clock_.AdvanceTime(hundred_ms_);
 191   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 192   EXPECT_LE(halfway_point, sent_bitrate);
 193
 194   // Second concave growth, towards channel_estimate.
 195   for (int i = 0; i < 14; ++i) {
 196     clock_.AdvanceTime(hundred_ms_);
 197     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 198     EXPECT_GE(channel_estimate, sent_bitrate);
 199     EXPECT_LE(halfway_point, sent_bitrate);
 200   }
 201   clock_.AdvanceTime(hundred_ms_);
 202   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 203   EXPECT_LE(channel_estimate, sent_bitrate);
 204
 205   // Second convex growth, from channel_estimate.
 206   for (int j = 0; j < 25; ++j) {
 207     clock_.AdvanceTime(hundred_ms_);
 208     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 209     EXPECT_LE(channel_estimate, sent_bitrate);
 210   }
 211   clock_.AdvanceTime(hundred_ms_);
 212   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 213   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 100000,
 214               sent_bitrate.ToBytesPerSecond(), 10000);
 215
 216   // Verify that we increase cubic.
 217   for (int j = 0; j < 24; ++j) {
 218     clock_.AdvanceTime(hundred_ms_);
 219     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 220     EXPECT_LE(channel_estimate, sent_bitrate);
 221   }
 222   clock_.AdvanceTime(hundred_ms_);
 223   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 224   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 780000,
 225               sent_bitrate.ToBytesPerSecond(), 20000);
 226 }
 227
 228 TEST_F(InterArrivalBitrateRampUpTest, UncertainEstimates) {
 229   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(100);
 230   QuicBandwidth available_channel_estimate =
 231       QuicBandwidth::FromKBytesPerSecond(200);
 232   QuicBandwidth channel_estimate =
 233       QuicBandwidth::FromKBytesPerSecond(400 * 0.7f);
 234   QuicBandwidth halfway_point = available_channel_estimate.Add(
 235       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
 236   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 237   bitrate_ramp_up_.Reset(start_rate,
 238                          available_channel_estimate,
 239                          channel_estimate);
 240
 241   // First concave growth, towards available_channel_estimate.
 242   for (int i = 0; i < 20; ++i) {
 243     clock_.AdvanceTime(hundred_ms_);
 244     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 245     EXPECT_GE(available_channel_estimate, sent_bitrate);
 246     EXPECT_LE(start_rate, sent_bitrate);
 247   }
 248   clock_.AdvanceTime(hundred_ms_);
 249   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 250   EXPECT_LE(available_channel_estimate, sent_bitrate);
 251
 252   // First convex growth, from available_channel_estimate.
 253   for (int j = 0; j < 23; ++j) {
 254     clock_.AdvanceTime(hundred_ms_);
 255     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 256     EXPECT_LE(available_channel_estimate, sent_bitrate);
 257     EXPECT_GE(halfway_point, sent_bitrate);
 258   }
 259   clock_.AdvanceTime(hundred_ms_);
 260   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 261   EXPECT_LE(halfway_point, sent_bitrate);
 262
 263   // Second concave growth, towards channel_estimate.
 264   for (int i = 0; i < 12; ++i) {
 265     clock_.AdvanceTime(hundred_ms_);
 266     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 267     EXPECT_GE(channel_estimate, sent_bitrate);
 268     EXPECT_LE(halfway_point, sent_bitrate);
 269   }
 270   clock_.AdvanceTime(hundred_ms_);
 271   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 272   EXPECT_LE(channel_estimate, sent_bitrate);
 273
 274   // Second convex growth, from channel_estimate.
 275   for (int j = 0; j < 30; ++j) {
 276     clock_.AdvanceTime(hundred_ms_);
 277     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 278     EXPECT_LE(channel_estimate, sent_bitrate);
 279   }
 280   clock_.AdvanceTime(hundred_ms_);
 281   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 282   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 100000,
 283               sent_bitrate.ToBytesPerSecond(), 10000);
 284
 285   // Verify that we increase cubic.
 286   for (int j = 0; j < 23; ++j) {
 287     clock_.AdvanceTime(hundred_ms_);
 288     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 289     EXPECT_LE(channel_estimate, sent_bitrate);
 290   }
 291   clock_.AdvanceTime(hundred_ms_);
 292   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 293   EXPECT_NEAR(channel_estimate.ToBytesPerSecond() + 750000,
 294               sent_bitrate.ToBytesPerSecond(), 20000);
 295 }
 296
 297 TEST_F(InterArrivalBitrateRampUpTest, UnknownEstimates) {
 298   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(100);
 299   QuicBandwidth available_channel_estimate =
 300       QuicBandwidth::FromKBytesPerSecond(200);
 301   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(400);
 302   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 303   bitrate_ramp_up_.Reset(start_rate,
 304                          available_channel_estimate,
 305                          available_channel_estimate);
 306
 307   // First convex growth, from start_rate.
 308   for (int j = 0; j < 20; ++j) {
 309     clock_.AdvanceTime(hundred_ms_);
 310     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 311     EXPECT_LE(start_rate, sent_bitrate);
 312     EXPECT_GE(available_channel_estimate, sent_bitrate);
 313   }
 314   clock_.AdvanceTime(hundred_ms_);
 315   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 316   EXPECT_NEAR(available_channel_estimate.ToBytesPerSecond(),
 317               sent_bitrate.ToBytesPerSecond(), 10000);
 318
 319   // Verify that we increase cubic.
 320   for (int j = 0; j < 31; ++j) {
 321     clock_.AdvanceTime(hundred_ms_);
 322     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 323     EXPECT_GE(channel_estimate, sent_bitrate);
 324   }
 325   clock_.AdvanceTime(hundred_ms_);
 326   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 327   EXPECT_NEAR(channel_estimate.ToBytesPerSecond(),
 328               sent_bitrate.ToBytesPerSecond(), 10000);
 329 }
 330
 331 TEST_F(InterArrivalBitrateRampUpTest, UpdatingChannelEstimateHigher) {
 332   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(200);
 333   QuicBandwidth available_channel_estimate = start_rate;
 334   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(250);
 335   QuicBandwidth halfway_point = available_channel_estimate.Add(
 336       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
 337   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 338   bitrate_ramp_up_.Reset(start_rate,
 339                          available_channel_estimate,
 340                          channel_estimate);
 341
 342   // Convex growth, from available_channel_estimate.
 343   for (int j = 0; j < 16; ++j) {
 344     clock_.AdvanceTime(hundred_ms_);
 345     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 346     EXPECT_LE(available_channel_estimate, sent_bitrate);
 347     EXPECT_GE(halfway_point, sent_bitrate);
 348   }
 349   clock_.AdvanceTime(hundred_ms_);
 350   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 351   EXPECT_LE(halfway_point, sent_bitrate);
 352
 353   // Increse channel estimate.
 354   channel_estimate = QuicBandwidth::FromKBytesPerSecond(300);
 355   bitrate_ramp_up_.UpdateChannelEstimate(channel_estimate);
 356
 357   // Concave growth, towards channel_estimate.
 358   for (int i = 0; i < 22; ++i) {
 359     clock_.AdvanceTime(hundred_ms_);
 360     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 361     EXPECT_GE(channel_estimate, sent_bitrate);
 362     EXPECT_LE(halfway_point, sent_bitrate);
 363   }
 364   clock_.AdvanceTime(hundred_ms_);
 365   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 366   EXPECT_LE(channel_estimate, sent_bitrate);
 367 }
 368
 369 TEST_F(InterArrivalBitrateRampUpTest, UpdatingChannelEstimateLower) {
 370   QuicBandwidth start_rate = QuicBandwidth::FromKBytesPerSecond(200);
 371   QuicBandwidth available_channel_estimate = start_rate;
 372   QuicBandwidth channel_estimate = QuicBandwidth::FromKBytesPerSecond(250);
 373   QuicBandwidth halfway_point = available_channel_estimate.Add(
 374       channel_estimate.Subtract(available_channel_estimate).Scale(0.5f));
 375   QuicBandwidth sent_bitrate = QuicBandwidth::Zero();
 376   bitrate_ramp_up_.Reset(start_rate,
 377                          available_channel_estimate,
 378                          channel_estimate);
 379
 380   // Convex growth, from available_channel_estimate.
 381   for (int j = 0; j < 16; ++j) {
 382     clock_.AdvanceTime(hundred_ms_);
 383     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 384     EXPECT_LE(available_channel_estimate, sent_bitrate);
 385     EXPECT_GE(halfway_point, sent_bitrate);
 386   }
 387   clock_.AdvanceTime(hundred_ms_);
 388   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 389   EXPECT_LE(halfway_point, sent_bitrate);
 390
 391   // Decrese channel estimate.
 392   channel_estimate = QuicBandwidth::FromKBytesPerSecond(240);
 393   bitrate_ramp_up_.UpdateChannelEstimate(channel_estimate);
 394
 395   // Concave growth, towards channel_estimate.
 396   for (int i = 0; i < 11; ++i) {
 397     clock_.AdvanceTime(hundred_ms_);
 398     sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 399     EXPECT_GE(channel_estimate, sent_bitrate);
 400     EXPECT_LE(halfway_point, sent_bitrate);
 401   }
 402   clock_.AdvanceTime(hundred_ms_);
 403   sent_bitrate = bitrate_ramp_up_.GetNewBitrate(sent_bitrate);
 404   EXPECT_LE(channel_estimate, sent_bitrate);
 405 }
 406
 407 }  // namespace test
 408 }  // namespace net