Implements Kathleen Nichols' time-windowed min-max algorithm for QUIC.

net/quic/congestion_control/windowed_filter_test.cc

Index: net/quic/congestion_control/windowed_filter_test.cc
diff --git a/net/quic/congestion_control/windowed_filter_test.cc b/net/quic/congestion_control/windowed_filter_test.cc
new file mode 100644
index 0000000000000000000000000000000000000000..f6f30e01cbda8643322af138252be59b43b8f691
--- /dev/null
+++ b/net/quic/congestion_control/windowed_filter_test.cc
@@ -0,0 +1,313 @@
+// Copyright (c) 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+#include "net/quic/congestion_control/windowed_filter.h"
+
+#include "base/logging.h"
+#include "net/quic/congestion_control/rtt_stats.h"
+#include "net/quic/quic_bandwidth.h"
+#include "net/quic/quic_protocol.h"
+#include "net/quic/quic_time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+namespace test {
+
+class WindowedFilterTest : public ::testing::Test {
+ public:
+  // Set the window to 99ms, so 25ms is more than a quarter rtt.
+  WindowedFilterTest()
+      : windowed_min_rtt_(QuicTime::Delta::FromMilliseconds(99),
+                          QuicTime::Delta::Zero()),
+        windowed_max_bw_(QuicTime::Delta::FromMilliseconds(99),
+                         QuicBandwidth::Zero()) {}
+
+  // Sets up windowed_min_rtt_ to have the following values:
+  // Best = 20ms, recorded at 25ms
+  // Second best = 40ms, recorded at 75ms
+  // Third best = 50ms, recorded at 100ms
+  void InitializeMinFilter() {
+    QuicTime now = QuicTime::Zero();
+    QuicTime::Delta rtt_sample = QuicTime::Delta::FromMilliseconds(10);
+    for (int i = 0; i < 5; ++i) {
+      windowed_min_rtt_.Update(rtt_sample, now);
+      VLOG(1) << "i: " << i << " sample: " << rtt_sample.ToMilliseconds()
+              << " mins: "
+              << " " << windowed_min_rtt_.GetBest().ToMilliseconds() << " "
+              << windowed_min_rtt_.GetSecondBest().ToMilliseconds() << " "
+              << windowed_min_rtt_.GetThirdBest().ToMilliseconds();
+      now = now.Add(QuicTime::Delta::FromMilliseconds(25));
+      rtt_sample = rtt_sample.Add(QuicTime::Delta::FromMilliseconds(10));
+    }
+    EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20),
+              windowed_min_rtt_.GetBest());
+    EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
+              windowed_min_rtt_.GetSecondBest());
+    EXPECT_EQ(QuicTime::Delta::FromMilliseconds(50),
+              windowed_min_rtt_.GetThirdBest());
+  }
+
+  // Sets up windowed_max_bw_ to have the following values:
+  // Best = 900 bps, recorded at 25ms
+  // Second best = 700 bps, recorded at 75ms
+  // Third best = 600 bps, recorded at 100ms
+  void InitializeMaxFilter() {
+    QuicTime now = QuicTime::Zero();
+    QuicBandwidth bw_sample = QuicBandwidth::FromBitsPerSecond(1000);
+    for (int i = 0; i < 5; ++i) {
+      windowed_max_bw_.Update(bw_sample, now);
+      VLOG(1) << "i: " << i << " sample: " << bw_sample.ToBitsPerSecond()
+              << " maxs: "
+              << " " << windowed_max_bw_.GetBest().ToBitsPerSecond() << " "
+              << windowed_max_bw_.GetSecondBest().ToBitsPerSecond() << " "
+              << windowed_max_bw_.GetThirdBest().ToBitsPerSecond();
+      now = now.Add(QuicTime::Delta::FromMilliseconds(25));
+      bw_sample = bw_sample.Subtract(QuicBandwidth::FromBitsPerSecond(100));
+    }
+    EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900),
+              windowed_max_bw_.GetBest());
+    EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
+              windowed_max_bw_.GetSecondBest());
+    EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(600),
+              windowed_max_bw_.GetThirdBest());
+  }
+
+ protected:
+  WindowedFilter<QuicTime::Delta, MinFilter<QuicTime::Delta>> windowed_min_rtt_;
+  WindowedFilter<QuicBandwidth, MaxFilter<QuicBandwidth>> windowed_max_bw_;
+};
+
+TEST_F(WindowedFilterTest, UninitializedEstimates) {
+  EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetBest());
+  EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(QuicTime::Delta::Zero(), windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetBest());
+  EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(QuicBandwidth::Zero(), windowed_max_bw_.GetThirdBest());
+}
+
+TEST_F(WindowedFilterTest, MonotonicallyIncreasingMin) {
+  QuicTime now = QuicTime::Zero();
+  QuicTime::Delta rtt_sample = QuicTime::Delta::FromMilliseconds(10);
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(QuicTime::Delta::FromMilliseconds(10), windowed_min_rtt_.GetBest());
+
+  // Gradually increase the rtt samples and ensure the windowed min rtt starts
+  // rising.
+  for (int i = 0; i < 6; ++i) {
+    now = now.Add(QuicTime::Delta::FromMilliseconds(25));
+    rtt_sample = rtt_sample.Add(QuicTime::Delta::FromMilliseconds(10));
+    windowed_min_rtt_.Update(rtt_sample, now);
+    VLOG(1) << "i: " << i << " sample: " << rtt_sample.ToMilliseconds()
+            << " mins: "
+            << " " << windowed_min_rtt_.GetBest().ToMilliseconds() << " "
+            << windowed_min_rtt_.GetSecondBest().ToMilliseconds() << " "
+            << windowed_min_rtt_.GetThirdBest().ToMilliseconds();
+    if (i < 3) {
+      EXPECT_EQ(QuicTime::Delta::FromMilliseconds(10),
+                windowed_min_rtt_.GetBest());
+    } else if (i == 3) {
+      EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20),
+                windowed_min_rtt_.GetBest());
+    } else if (i < 6) {
+      EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
+                windowed_min_rtt_.GetBest());
+    }
+  }
+}
+
+TEST_F(WindowedFilterTest, MonotonicallyDecreasingMax) {
+  QuicTime now = QuicTime::Zero();
+  QuicBandwidth bw_sample = QuicBandwidth::FromBitsPerSecond(1000);
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(1000), windowed_max_bw_.GetBest());
+
+  // Gradually decrease the bw samples and ensure the windowed max bw starts
+  // decreasing.
+  for (int i = 0; i < 6; ++i) {
+    now = now.Add(QuicTime::Delta::FromMilliseconds(25));
+    bw_sample = bw_sample.Subtract(QuicBandwidth::FromBitsPerSecond(100));
+    windowed_max_bw_.Update(bw_sample, now);
+    VLOG(1) << "i: " << i << " sample: " << bw_sample.ToBitsPerSecond()
+            << " maxs: "
+            << " " << windowed_max_bw_.GetBest().ToBitsPerSecond() << " "
+            << windowed_max_bw_.GetSecondBest().ToBitsPerSecond() << " "
+            << windowed_max_bw_.GetThirdBest().ToBitsPerSecond();
+    if (i < 3) {
+      EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(1000),
+                windowed_max_bw_.GetBest());
+    } else if (i == 3) {
+      EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900),
+                windowed_max_bw_.GetBest());
+    } else if (i < 6) {
+      EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
+                windowed_max_bw_.GetBest());
+    }
+  }
+}
+
+TEST_F(WindowedFilterTest, SampleChangesThirdBestMin) {
+  InitializeMinFilter();
+  // RTT sample lower than the third-choice min-rtt sets that, but nothing else.
+  QuicTime::Delta rtt_sample = windowed_min_rtt_.GetThirdBest().Subtract(
+      QuicTime::Delta::FromMilliseconds(5));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(QuicTime::Delta::FromMilliseconds(40),
+            windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20), windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, SampleChangesThirdBestMax) {
+  InitializeMaxFilter();
+  // BW sample higher than the third-choice max sets that, but nothing else.
+  QuicBandwidth bw_sample =
+      windowed_max_bw_.GetThirdBest().Add(QuicBandwidth::FromBitsPerSecond(50));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(700),
+            windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900), windowed_max_bw_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, SampleChangesSecondBestMin) {
+  InitializeMinFilter();
+  // RTT sample lower than the second-choice min sets that and also
+  // the third-choice min.
+  QuicTime::Delta rtt_sample = windowed_min_rtt_.GetSecondBest().Subtract(
+      QuicTime::Delta::FromMilliseconds(5));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(QuicTime::Delta::FromMilliseconds(20), windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, SampleChangesSecondBestMax) {
+  InitializeMaxFilter();
+  // BW sample higher than the second-choice max sets that and also
+  // the third-choice max.
+  QuicBandwidth bw_sample = windowed_max_bw_.GetSecondBest().Add(
+      QuicBandwidth::FromBitsPerSecond(50));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(QuicBandwidth::FromBitsPerSecond(900), windowed_max_bw_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, SampleChangesAllMins) {
+  InitializeMinFilter();
+  // RTT sample lower than the first-choice min-rtt sets that and also
+  // the second and third-choice mins.
+  QuicTime::Delta rtt_sample = windowed_min_rtt_.GetBest().Subtract(
+      QuicTime::Delta::FromMilliseconds(5));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, SampleChangesAllMaxs) {
+  InitializeMaxFilter();
+  // BW sample higher than the first-choice max sets that and also
+  // the second and third-choice maxs.
+  QuicBandwidth bw_sample =
+      windowed_max_bw_.GetBest().Add(QuicBandwidth::FromBitsPerSecond(50));
+  // Latest sample was recorded at 100ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(101));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireBestMin) {
+  InitializeMinFilter();
+  QuicTime::Delta old_third_best = windowed_min_rtt_.GetThirdBest();
+  QuicTime::Delta old_second_best = windowed_min_rtt_.GetSecondBest();
+  QuicTime::Delta rtt_sample =
+      old_third_best.Add(QuicTime::Delta::FromMilliseconds(5));
+  // Best min sample was recorded at 25ms, so expiry time is 124ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(125));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(old_third_best, windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(old_second_best, windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireBestMax) {
+  InitializeMaxFilter();
+  QuicBandwidth old_third_best = windowed_max_bw_.GetThirdBest();
+  QuicBandwidth old_second_best = windowed_max_bw_.GetSecondBest();
+  QuicBandwidth bw_sample =
+      old_third_best.Subtract(QuicBandwidth::FromBitsPerSecond(50));
+  // Best max sample was recorded at 25ms, so expiry time is 124ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(125));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(old_third_best, windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(old_second_best, windowed_max_bw_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireSecondBestMin) {
+  InitializeMinFilter();
+  QuicTime::Delta old_third_best = windowed_min_rtt_.GetThirdBest();
+  QuicTime::Delta rtt_sample =
+      old_third_best.Add(QuicTime::Delta::FromMilliseconds(5));
+  // Second best min sample was recorded at 75ms, so expiry time is 174ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(175));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(old_third_best, windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireSecondBestMax) {
+  InitializeMaxFilter();
+  QuicBandwidth old_third_best = windowed_max_bw_.GetThirdBest();
+  QuicBandwidth bw_sample =
+      old_third_best.Subtract(QuicBandwidth::FromBitsPerSecond(50));
+  // Second best max sample was recorded at 75ms, so expiry time is 174ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(175));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(old_third_best, windowed_max_bw_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireAllMins) {
+  InitializeMinFilter();
+  QuicTime::Delta rtt_sample = windowed_min_rtt_.GetThirdBest().Add(
+      QuicTime::Delta::FromMilliseconds(5));
+  // Third best min sample was recorded at 100ms, so expiry time is 199ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(200));
+  windowed_min_rtt_.Update(rtt_sample, now);
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetThirdBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetSecondBest());
+  EXPECT_EQ(rtt_sample, windowed_min_rtt_.GetBest());
+}
+
+TEST_F(WindowedFilterTest, ExpireAllMaxs) {
+  InitializeMaxFilter();
+  QuicBandwidth bw_sample = windowed_max_bw_.GetThirdBest().Subtract(
+      QuicBandwidth::FromBitsPerSecond(50));
+  // Third best max sample was recorded at 100ms, so expiry time is 199ms.
+  QuicTime now = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(200));
+  windowed_max_bw_.Update(bw_sample, now);
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetThirdBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetSecondBest());
+  EXPECT_EQ(bw_sample, windowed_max_bw_.GetBest());
+}
+
+}  // namespace test
+}  // namespace net