Adding RttStats class for BBR.
This is part of a series of CLs adding a network controller based on
the BBR congestion control method. The code is based on the QUIC BBR
implementation in Chromium.
Bug: webrtc:8415
Change-Id: Ib952b9c3f1cdd0741330a5ae95aebcf2488f7f1d
Reviewed-on: https://webrtc-review.googlesource.com/63644
Commit-Queue: Sebastian Jansson <srte@webrtc.org>
Reviewed-by: Philip Eliasson <philipel@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#22581}diff --git a/modules/congestion_controller/BUILD.gn b/modules/congestion_controller/BUILD.gn
index a88f5fb..3028e18 100644
--- a/modules/congestion_controller/BUILD.gn
+++ b/modules/congestion_controller/BUILD.gn
@@ -183,6 +183,7 @@
"../pacing:pacing",
"../remote_bitrate_estimator:remote_bitrate_estimator",
"../rtp_rtcp:rtp_rtcp_format",
+ "bbr:bbr_unittests",
"goog_cc:goog_cc_unittests",
"network_control:network_control_unittests",
"rtp:congestion_controller_unittests",
diff --git a/modules/congestion_controller/bbr/BUILD.gn b/modules/congestion_controller/bbr/BUILD.gn
new file mode 100644
index 0000000..ce39abd
--- /dev/null
+++ b/modules/congestion_controller/bbr/BUILD.gn
@@ -0,0 +1,34 @@
+# Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+#
+# Use of this source code is governed by a BSD-style license
+# that can be found in the LICENSE file in the root of the source
+# tree. An additional intellectual property rights grant can be found
+# in the file PATENTS. All contributing project authors may
+# be found in the AUTHORS file in the root of the source tree.
+
+import("../../../webrtc.gni")
+
+rtc_source_set("rtt_stats") {
+ sources = [
+ "rtt_stats.cc",
+ "rtt_stats.h",
+ ]
+ deps = [
+ "../../../rtc_base:rtc_base_approved",
+ "../network_control",
+ ]
+}
+
+if (rtc_include_tests) {
+ rtc_source_set("bbr_unittests") {
+ testonly = true
+ sources = [
+ "rtt_stats_unittest.cc",
+ ]
+ deps = [
+ ":rtt_stats",
+ "../../../test:test_support",
+ "../network_control",
+ ]
+ }
+}
diff --git a/modules/congestion_controller/bbr/rtt_stats.cc b/modules/congestion_controller/bbr/rtt_stats.cc
new file mode 100644
index 0000000..a7cfea8
--- /dev/null
+++ b/modules/congestion_controller/bbr/rtt_stats.cc
@@ -0,0 +1,96 @@
+/*
+ * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/congestion_controller/bbr/rtt_stats.h"
+
+#include <cstdlib>
+
+#include "modules/congestion_controller/network_control/include/network_units.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+namespace bbr {
+namespace {
+
+// Default initial rtt used before any samples are received.
+const int kInitialRttMs = 100;
+const double kAlpha = 0.125;
+const double kOneMinusAlpha = (1 - kAlpha);
+const double kBeta = 0.25;
+const double kOneMinusBeta = (1 - kBeta);
+const int64_t kNumMicrosPerMilli = 1000;
+} // namespace
+
+RttStats::RttStats()
+ : latest_rtt_(TimeDelta::Zero()),
+ min_rtt_(TimeDelta::Zero()),
+ smoothed_rtt_(TimeDelta::Zero()),
+ previous_srtt_(TimeDelta::Zero()),
+ mean_deviation_(TimeDelta::Zero()),
+ initial_rtt_us_(kInitialRttMs * kNumMicrosPerMilli) {}
+
+void RttStats::ExpireSmoothedMetrics() {
+ mean_deviation_ =
+ std::max(mean_deviation_, (smoothed_rtt_ - latest_rtt_).Abs());
+ smoothed_rtt_ = std::max(smoothed_rtt_, latest_rtt_);
+}
+
+// Updates the RTT based on a new sample.
+void RttStats::UpdateRtt(TimeDelta send_delta,
+ TimeDelta ack_delay,
+ Timestamp now) {
+ if (send_delta.IsInfinite() || send_delta <= TimeDelta::Zero()) {
+ RTC_LOG(LS_WARNING) << "Ignoring measured send_delta, because it's is "
+ << "either infinite, zero, or negative. send_delta = "
+ << send_delta;
+ return;
+ }
+
+ // Update min_rtt_ first. min_rtt_ does not use an rtt_sample corrected for
+ // ack_delay but the raw observed send_delta, since poor clock granularity at
+ // the client may cause a high ack_delay to result in underestimation of the
+ // min_rtt_.
+ if (min_rtt_.IsZero() || min_rtt_ > send_delta) {
+ min_rtt_ = send_delta;
+ }
+
+ // Correct for ack_delay if information received from the peer results in a
+ // positive RTT sample. Otherwise, we use the send_delta as a reasonable
+ // measure for smoothed_rtt.
+ TimeDelta rtt_sample = send_delta;
+ previous_srtt_ = smoothed_rtt_;
+
+ if (rtt_sample > ack_delay) {
+ rtt_sample = rtt_sample - ack_delay;
+ }
+ latest_rtt_ = rtt_sample;
+ // First time call.
+ if (smoothed_rtt_.IsZero()) {
+ smoothed_rtt_ = rtt_sample;
+ mean_deviation_ = rtt_sample / 2;
+ } else {
+ mean_deviation_ = kOneMinusBeta * mean_deviation_ +
+ kBeta * (smoothed_rtt_ - rtt_sample).Abs();
+ smoothed_rtt_ = kOneMinusAlpha * smoothed_rtt_ + kAlpha * rtt_sample;
+ RTC_LOG(LS_VERBOSE) << " smoothed_rtt(us):" << smoothed_rtt_.us()
+ << " mean_deviation(us):" << mean_deviation_.us();
+ }
+}
+
+void RttStats::OnConnectionMigration() {
+ latest_rtt_ = TimeDelta::Zero();
+ min_rtt_ = TimeDelta::Zero();
+ smoothed_rtt_ = TimeDelta::Zero();
+ mean_deviation_ = TimeDelta::Zero();
+ initial_rtt_us_ = kInitialRttMs * kNumMicrosPerMilli;
+}
+
+} // namespace bbr
+} // namespace webrtc
diff --git a/modules/congestion_controller/bbr/rtt_stats.h b/modules/congestion_controller/bbr/rtt_stats.h
new file mode 100644
index 0000000..26b843d
--- /dev/null
+++ b/modules/congestion_controller/bbr/rtt_stats.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+// A convenience class to store RTT samples and calculate smoothed RTT.
+// From the Quic BBR implementation in Chromium.
+
+#ifndef MODULES_CONGESTION_CONTROLLER_BBR_RTT_STATS_H_
+#define MODULES_CONGESTION_CONTROLLER_BBR_RTT_STATS_H_
+
+#include <algorithm>
+#include <cstdint>
+
+#include "modules/congestion_controller/network_control/include/network_units.h"
+#include "rtc_base/constructormagic.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+namespace bbr {
+
+class RttStats {
+ public:
+ RttStats();
+
+ // Updates the RTT from an incoming ack which is received |send_delta| after
+ // the packet is sent and the peer reports the ack being delayed |ack_delay|.
+ void UpdateRtt(TimeDelta send_delta, TimeDelta ack_delay, Timestamp now);
+
+ // Causes the smoothed_rtt to be increased to the latest_rtt if the latest_rtt
+ // is larger. The mean deviation is increased to the most recent deviation if
+ // it's larger.
+ void ExpireSmoothedMetrics();
+
+ // Called when connection migrates and RTT measurement needs to be reset.
+ void OnConnectionMigration();
+
+ // Returns the EWMA smoothed RTT for the connection.
+ // May return Zero if no valid updates have occurred.
+ TimeDelta smoothed_rtt() const { return smoothed_rtt_; }
+
+ // Returns the EWMA smoothed RTT prior to the most recent RTT sample.
+ TimeDelta previous_srtt() const { return previous_srtt_; }
+
+ int64_t initial_rtt_us() const { return initial_rtt_us_; }
+
+ // Sets an initial RTT to be used for SmoothedRtt before any RTT updates.
+ void set_initial_rtt_us(int64_t initial_rtt_us) {
+ RTC_DCHECK_GE(initial_rtt_us, 0);
+ if (initial_rtt_us <= 0) {
+ RTC_LOG(LS_ERROR) << "Attempt to set initial rtt to <= 0.";
+ return;
+ }
+ initial_rtt_us_ = initial_rtt_us;
+ }
+
+ // The most recent RTT measurement.
+ // May return Zero if no valid updates have occurred.
+ TimeDelta latest_rtt() const { return latest_rtt_; }
+
+ // Returns the min_rtt for the entire connection.
+ // May return Zero if no valid updates have occurred.
+ TimeDelta min_rtt() const { return min_rtt_; }
+
+ TimeDelta mean_deviation() const { return mean_deviation_; }
+
+ private:
+ TimeDelta latest_rtt_;
+ TimeDelta min_rtt_;
+ TimeDelta smoothed_rtt_;
+ TimeDelta previous_srtt_;
+ // Mean RTT deviation during this session.
+ // Approximation of standard deviation, the error is roughly 1.25 times
+ // larger than the standard deviation, for a normally distributed signal.
+ TimeDelta mean_deviation_;
+ int64_t initial_rtt_us_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(RttStats);
+};
+
+} // namespace bbr
+} // namespace webrtc
+
+#endif // MODULES_CONGESTION_CONTROLLER_BBR_RTT_STATS_H_
diff --git a/modules/congestion_controller/bbr/rtt_stats_unittest.cc b/modules/congestion_controller/bbr/rtt_stats_unittest.cc
new file mode 100644
index 0000000..1a07a527
--- /dev/null
+++ b/modules/congestion_controller/bbr/rtt_stats_unittest.cc
@@ -0,0 +1,160 @@
+/*
+ * Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/congestion_controller/bbr/rtt_stats.h"
+
+#include <vector>
+
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace bbr {
+namespace test {
+
+class RttStatsTest : public ::testing::Test {
+ protected:
+ RttStats rtt_stats_;
+};
+
+TEST_F(RttStatsTest, DefaultsBeforeUpdate) {
+ EXPECT_LT(0u, rtt_stats_.initial_rtt_us());
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.min_rtt());
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.smoothed_rtt());
+}
+
+TEST_F(RttStatsTest, SmoothedRtt) {
+ // Verify that ack_delay is corrected for in Smoothed RTT.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(300), TimeDelta::ms(100),
+ Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.smoothed_rtt());
+ // Verify that effective RTT of zero does not change Smoothed RTT.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(200), TimeDelta::ms(200),
+ Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.smoothed_rtt());
+ // Verify that large erroneous ack_delay does not change Smoothed RTT.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(200), TimeDelta::ms(300),
+ Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.smoothed_rtt());
+}
+
+// Ensure that the potential rounding artifacts in EWMA calculation do not cause
+// the SRTT to drift too far from the exact value.
+TEST_F(RttStatsTest, SmoothedRttStability) {
+ for (int64_t time = 3; time < 20000; time++) {
+ RttStats stats;
+ for (int64_t i = 0; i < 100; i++) {
+ stats.UpdateRtt(TimeDelta::us(time), TimeDelta::ms(0), Timestamp::ms(0));
+ int64_t time_delta_us = stats.smoothed_rtt().us() - time;
+ ASSERT_LE(std::abs(time_delta_us), 1);
+ }
+ }
+}
+
+TEST_F(RttStatsTest, PreviousSmoothedRtt) {
+ // Verify that ack_delay is corrected for in Smoothed RTT.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(300), TimeDelta::ms(100),
+ Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.smoothed_rtt());
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.previous_srtt());
+ // Ensure the previous SRTT is 200ms after a 100ms sample.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(100), TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(100), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::us(187500).us(), rtt_stats_.smoothed_rtt().us());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.previous_srtt());
+}
+
+TEST_F(RttStatsTest, MinRtt) {
+ rtt_stats_.UpdateRtt(TimeDelta::ms(200), TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.min_rtt());
+ rtt_stats_.UpdateRtt(TimeDelta::ms(10), TimeDelta::Zero(),
+ Timestamp::ms(0) + TimeDelta::ms(10));
+ EXPECT_EQ(TimeDelta::ms(10), rtt_stats_.min_rtt());
+ rtt_stats_.UpdateRtt(TimeDelta::ms(50), TimeDelta::Zero(),
+ Timestamp::ms(0) + TimeDelta::ms(20));
+ EXPECT_EQ(TimeDelta::ms(10), rtt_stats_.min_rtt());
+ rtt_stats_.UpdateRtt(TimeDelta::ms(50), TimeDelta::Zero(),
+ Timestamp::ms(0) + TimeDelta::ms(30));
+ EXPECT_EQ(TimeDelta::ms(10), rtt_stats_.min_rtt());
+ rtt_stats_.UpdateRtt(TimeDelta::ms(50), TimeDelta::Zero(),
+ Timestamp::ms(0) + TimeDelta::ms(40));
+ EXPECT_EQ(TimeDelta::ms(10), rtt_stats_.min_rtt());
+ // Verify that ack_delay does not go into recording of min_rtt_.
+ rtt_stats_.UpdateRtt(TimeDelta::ms(7), TimeDelta::ms(2),
+ Timestamp::ms(0) + TimeDelta::ms(50));
+ EXPECT_EQ(TimeDelta::ms(7), rtt_stats_.min_rtt());
+}
+
+TEST_F(RttStatsTest, ExpireSmoothedMetrics) {
+ TimeDelta initial_rtt = TimeDelta::ms(10);
+ rtt_stats_.UpdateRtt(initial_rtt, TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(initial_rtt, rtt_stats_.min_rtt());
+ EXPECT_EQ(initial_rtt, rtt_stats_.smoothed_rtt());
+
+ EXPECT_EQ(0.5 * initial_rtt, rtt_stats_.mean_deviation());
+
+ // Update once with a 20ms RTT.
+ TimeDelta doubled_rtt = 2 * initial_rtt;
+ rtt_stats_.UpdateRtt(doubled_rtt, TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(1.125 * initial_rtt, rtt_stats_.smoothed_rtt());
+
+ // Expire the smoothed metrics, increasing smoothed rtt and mean deviation.
+ rtt_stats_.ExpireSmoothedMetrics();
+ EXPECT_EQ(doubled_rtt, rtt_stats_.smoothed_rtt());
+ EXPECT_EQ(0.875 * initial_rtt, rtt_stats_.mean_deviation());
+
+ // Now go back down to 5ms and expire the smoothed metrics, and ensure the
+ // mean deviation increases to 15ms.
+ TimeDelta half_rtt = 0.5 * initial_rtt;
+ rtt_stats_.UpdateRtt(half_rtt, TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_GT(doubled_rtt, rtt_stats_.smoothed_rtt());
+ EXPECT_LT(initial_rtt, rtt_stats_.mean_deviation());
+}
+
+TEST_F(RttStatsTest, UpdateRttWithBadSendDeltas) {
+ // Make sure we ignore bad RTTs.
+
+ TimeDelta initial_rtt = TimeDelta::ms(10);
+ rtt_stats_.UpdateRtt(initial_rtt, TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(initial_rtt, rtt_stats_.min_rtt());
+ EXPECT_EQ(initial_rtt, rtt_stats_.smoothed_rtt());
+
+ std::vector<TimeDelta> bad_send_deltas;
+ bad_send_deltas.push_back(TimeDelta::Zero());
+ bad_send_deltas.push_back(TimeDelta::Infinity());
+ bad_send_deltas.push_back(TimeDelta::us(-1000));
+
+ for (TimeDelta bad_send_delta : bad_send_deltas) {
+ rtt_stats_.UpdateRtt(bad_send_delta, TimeDelta::Zero(), Timestamp::ms(0));
+ EXPECT_EQ(initial_rtt, rtt_stats_.min_rtt());
+ EXPECT_EQ(initial_rtt, rtt_stats_.smoothed_rtt());
+ }
+}
+
+TEST_F(RttStatsTest, ResetAfterConnectionMigrations) {
+ rtt_stats_.UpdateRtt(TimeDelta::ms(300), TimeDelta::ms(100),
+ Timestamp::ms(0));
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::ms(200), rtt_stats_.smoothed_rtt());
+ EXPECT_EQ(TimeDelta::ms(300), rtt_stats_.min_rtt());
+
+ // Reset rtt stats on connection migrations.
+ rtt_stats_.OnConnectionMigration();
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.latest_rtt());
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.smoothed_rtt());
+ EXPECT_EQ(TimeDelta::Zero(), rtt_stats_.min_rtt());
+}
+
+} // namespace test
+} // namespace bbr
+} // namespace webrtc
diff --git a/modules/congestion_controller/network_control/include/network_units.h b/modules/congestion_controller/network_control/include/network_units.h
index 8145c75..1812b0d 100644
--- a/modules/congestion_controller/network_control/include/network_units.h
+++ b/modules/congestion_controller/network_control/include/network_units.h
@@ -91,6 +91,9 @@
TimeDelta operator*(int32_t scalar) const {
return TimeDelta::us(us() * scalar);
}
+ TimeDelta operator/(int64_t scalar) const {
+ return TimeDelta::us(us() / scalar);
+ }
bool operator==(const TimeDelta& other) const {
return microseconds_ == other.microseconds_;
}
