util: add afterMeasurement signal to RttEstimator
Refs: #4887
Change-Id: Ie48871a346f2960a7894c45a9386c52f3e1d9af2
diff --git a/ndn-cxx/util/rtt-estimator.cpp b/ndn-cxx/util/rtt-estimator.cpp
index 75fed28..c0d62d6 100644
--- a/ndn-cxx/util/rtt-estimator.cpp
+++ b/ndn-cxx/util/rtt-estimator.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (C) 2016-2018, Arizona Board of Regents.
+ * Copyright (C) 2016-2019, Arizona Board of Regents.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -25,9 +25,6 @@
#include "ndn-cxx/util/rtt-estimator.hpp"
-#include <cmath>
-#include <limits>
-
namespace ndn {
namespace util {
@@ -35,7 +32,7 @@
: m_options(options)
, m_sRtt(std::numeric_limits<double>::quiet_NaN())
, m_rttVar(std::numeric_limits<double>::quiet_NaN())
- , m_rto(m_options.initialRto.count())
+ , m_rto(m_options.initialRto)
, m_rttMin(std::numeric_limits<double>::max())
, m_rttMax(std::numeric_limits<double>::min())
, m_rttAvg(0.0)
@@ -44,7 +41,8 @@
}
void
-RttEstimator::addMeasurement(MillisecondsDouble rtt, size_t nExpectedSamples)
+RttEstimator::addMeasurement(MillisecondsDouble rtt, size_t nExpectedSamples,
+ optional<uint64_t> segNum)
{
BOOST_ASSERT(nExpectedSamples > 0);
@@ -62,10 +60,11 @@
}
m_rto = clamp(m_rto, m_options.minRto, m_options.maxRto);
+ afterMeasurement({rtt, m_sRtt, m_rttVar, m_rto, segNum});
- m_rttAvg = MillisecondsDouble((m_nRttSamples * m_rttAvg.count() + rtt.count()) / (m_nRttSamples + 1));
- m_rttMax = std::max<MillisecondsDouble>(rtt, m_rttMax);
- m_rttMin = std::min<MillisecondsDouble>(rtt, m_rttMin);
+ m_rttAvg = (m_nRttSamples * m_rttAvg + rtt) / (m_nRttSamples + 1);
+ m_rttMax = std::max(rtt, m_rttMax);
+ m_rttMin = std::min(rtt, m_rttMin);
m_nRttSamples++;
}
diff --git a/ndn-cxx/util/rtt-estimator.hpp b/ndn-cxx/util/rtt-estimator.hpp
index 71f49f4..358fb65 100644
--- a/ndn-cxx/util/rtt-estimator.hpp
+++ b/ndn-cxx/util/rtt-estimator.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (C) 2016-2018, Arizona Board of Regents.
+ * Copyright (C) 2016-2019, Arizona Board of Regents.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -43,7 +43,6 @@
public:
using MillisecondsDouble = time::duration<double, time::milliseconds::period>;
-public:
class Options
{
public:
@@ -53,38 +52,42 @@
}
public:
- double alpha = 0.125; ///< weight of exponential moving average for meanRtt
- double beta = 0.25; ///< weight of exponential moving average for varRtt
- int k = 4; ///< factor of RTT variation when calculating RTO
- MillisecondsDouble initialRto = MillisecondsDouble(1000.0); ///< initial RTO value
- MillisecondsDouble minRto = MillisecondsDouble(200.0); ///< lower bound of RTO
- MillisecondsDouble maxRto = MillisecondsDouble(20000.0); ///< upper bound of RTO
- int rtoBackoffMultiplier = 2;
+ double alpha = 0.125; ///< weight of exponential moving average for smoothed RTT
+ double beta = 0.25; ///< weight of exponential moving average for RTT variation
+ MillisecondsDouble initialRto{1000.0}; ///< initial RTO value
+ MillisecondsDouble minRto{200.0}; ///< lower bound of RTO
+ MillisecondsDouble maxRto{60000.0}; ///< upper bound of RTO
+ int k = 4; ///< RTT variation multiplier used when calculating RTO
+ int rtoBackoffMultiplier = 2; ///< RTO multiplier used in backoff operation
};
/**
- * @brief Create a RTT Estimator
+ * @brief Creates an RTT estimator.
*
- * Configures the RTT Estimator with the default parameters if an instance of Options
+ * Configures the RTT estimator with the default parameters if an instance of Options
* is not passed to the constructor.
*/
explicit
RttEstimator(const Options& options = Options());
/**
- * @brief Add a new RTT measurement to the estimator.
+ * @brief Records a new RTT measurement.
*
- * @param rtt the sampled rtt
- * @param nExpectedSamples number of expected samples, must be greater than 0.
- * It should be set to current number of in-flight Interests. Please
- * refer to Appendix G of RFC 7323 for details.
- * @note Don't add RTT measurements for retransmissions
+ * @param rtt the sampled RTT
+ * @param nExpectedSamples number of expected samples, must be greater than 0. It should be
+ * set to the current number of in-flight Interests. Please refer to
+ * Appendix G of RFC 7323 for details.
+ * @param segNum segment number or other opaque sample identifier. This value is not used by
+ * the estimator, but is passed verbatim to afterMeasurement() signal subscribers.
+ *
+ * @note Do not call this function with RTT samples from retransmitted Interests (per Karn's algorithm).
*/
void
- addMeasurement(MillisecondsDouble rtt, size_t nExpectedSamples);
+ addMeasurement(MillisecondsDouble rtt, size_t nExpectedSamples,
+ optional<uint64_t> segNum = nullopt);
/**
- * @brief Returns the estimated RTO value
+ * @brief Returns the estimated RTO value.
*/
MillisecondsDouble
getEstimatedRto() const
@@ -93,7 +96,7 @@
}
/**
- * @brief Returns the minimum RTT observed
+ * @brief Returns the minimum RTT observed.
*/
MillisecondsDouble
getMinRtt() const
@@ -102,7 +105,7 @@
}
/**
- * @brief Returns the maximum RTT observed
+ * @brief Returns the maximum RTT observed.
*/
MillisecondsDouble
getMaxRtt() const
@@ -111,7 +114,7 @@
}
/**
- * @brief Returns the average RTT
+ * @brief Returns the average RTT.
*/
MillisecondsDouble
getAvgRtt() const
@@ -120,20 +123,36 @@
}
/**
- * @brief Backoff RTO by a factor of Options::rtoBackoffMultiplier
+ * @brief Backoff RTO by a factor of Options::rtoBackoffMultiplier.
*/
void
backoffRto();
+public:
+ struct Sample
+ {
+ MillisecondsDouble rtt; ///< measured RTT
+ MillisecondsDouble sRtt; ///< smoothed RTT
+ MillisecondsDouble rttVar; ///< RTT variation
+ MillisecondsDouble rto; ///< retransmission timeout
+ optional<uint64_t> segNum; ///< segment number, see description in addMeasurement()
+ };
+
+ Signal<RttEstimator, Sample> afterMeasurement;
+
private:
const Options m_options;
- MillisecondsDouble m_sRtt; ///< smoothed round-trip time
- MillisecondsDouble m_rttVar; ///< round-trip time variation
- MillisecondsDouble m_rto; ///< retransmission timeout
+
+NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ MillisecondsDouble m_sRtt; ///< smoothed round-trip time
+ MillisecondsDouble m_rttVar; ///< round-trip time variation
+ MillisecondsDouble m_rto; ///< retransmission timeout
+
+private:
MillisecondsDouble m_rttMin;
MillisecondsDouble m_rttMax;
MillisecondsDouble m_rttAvg;
- int64_t m_nRttSamples; ///< number of RTT samples
+ int64_t m_nRttSamples;
};
} // namespace util
diff --git a/ndn-cxx/util/segment-fetcher.cpp b/ndn-cxx/util/segment-fetcher.cpp
index 680ff59..80a5c38 100644
--- a/ndn-cxx/util/segment-fetcher.cpp
+++ b/ndn-cxx/util/segment-fetcher.cpp
@@ -267,7 +267,8 @@
// Add measurement to RTO estimator (if not retransmission)
if (pendingSegmentIt->second.state == SegmentState::FirstInterest) {
m_rttEstimator.addMeasurement(m_timeLastSegmentReceived - pendingSegmentIt->second.sendTime,
- std::max<int64_t>(m_nSegmentsInFlight + 1, 1));
+ std::max<int64_t>(m_nSegmentsInFlight + 1, 1),
+ currentSegment);
}
// Remove from pending segments map
diff --git a/tests/unit/util/rtt-estimator.t.cpp b/tests/unit/util/rtt-estimator.t.cpp
new file mode 100644
index 0000000..01fe4f8
--- /dev/null
+++ b/tests/unit/util/rtt-estimator.t.cpp
@@ -0,0 +1,183 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2016-2019, Regents of the University of California,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+ * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#include "ndn-cxx/util/rtt-estimator.hpp"
+
+#include "tests/boost-test.hpp"
+
+#include <cmath>
+
+namespace ndn {
+namespace util {
+namespace tests {
+
+BOOST_AUTO_TEST_SUITE(Util)
+BOOST_AUTO_TEST_SUITE(TestRttEstimator)
+
+using Millis = RttEstimator::MillisecondsDouble;
+
+BOOST_AUTO_TEST_CASE(MinAvgMaxRtt)
+{
+ RttEstimator rttEstimator;
+
+ // check initial values
+ BOOST_CHECK_CLOSE(rttEstimator.getMinRtt().count(), std::numeric_limits<double>::max(), 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getAvgRtt().count(), 0.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getMaxRtt().count(), std::numeric_limits<double>::min(), 0.001);
+
+ // start with three samples
+ rttEstimator.addMeasurement(Millis(100), 1);
+ rttEstimator.addMeasurement(Millis(400), 1);
+ rttEstimator.addMeasurement(Millis(250), 1);
+
+ BOOST_CHECK_CLOSE(rttEstimator.getMinRtt().count(), 100.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getAvgRtt().count(), 250.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getMaxRtt().count(), 400.0, 0.001);
+
+ // add another sample (new minimum)
+ rttEstimator.addMeasurement(Millis(50), 2);
+ BOOST_CHECK_CLOSE(rttEstimator.getMinRtt().count(), 50.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getAvgRtt().count(), 200.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getMaxRtt().count(), 400.0, 0.001);
+
+ // add another sample (new maximum)
+ rttEstimator.addMeasurement(Millis(700), 1);
+ BOOST_CHECK_CLOSE(rttEstimator.getMinRtt().count(), 50.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getAvgRtt().count(), 300.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getMaxRtt().count(), 700.0, 0.001);
+}
+
+BOOST_AUTO_TEST_CASE(EstimatedRto)
+{
+ RttEstimator::Options opts;
+ opts.initialRto = Millis(1000);
+ opts.maxRto = Millis(4000);
+ RttEstimator rttEstimator(opts);
+
+ // check initial values
+ BOOST_CHECK(std::isnan(rttEstimator.m_sRtt.count()));
+ BOOST_CHECK(std::isnan(rttEstimator.m_rttVar.count()));
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 1000.0, 0.001);
+
+ // first measurement
+ rttEstimator.addMeasurement(Millis(100), 1);
+
+ BOOST_CHECK_CLOSE(rttEstimator.m_sRtt.count(), 100.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.m_rttVar.count(), 50.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 300.0, 0.001);
+
+ rttEstimator.m_sRtt = Millis(500);
+ rttEstimator.m_rttVar = Millis(100);
+ rttEstimator.m_rto = Millis(900);
+
+ rttEstimator.addMeasurement(Millis(100), 1);
+
+ BOOST_CHECK_CLOSE(rttEstimator.m_sRtt.count(), 450.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.m_rttVar.count(), 175.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 1150.0, 0.001);
+
+ // expected samples larger than 1
+ rttEstimator.addMeasurement(Millis(100), 5);
+
+ BOOST_CHECK_CLOSE(rttEstimator.m_sRtt.count(), 441.25, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.m_rttVar.count(), 183.75, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 1176.25, 0.001);
+
+ rttEstimator.m_sRtt = Millis(100.0);
+ rttEstimator.m_rttVar = Millis(30.0);
+ rttEstimator.m_rto = Millis(220.0);
+
+ // check if minRto works
+ rttEstimator.addMeasurement(Millis(100), 1);
+
+ BOOST_CHECK_CLOSE(rttEstimator.m_sRtt.count(), 100.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.m_rttVar.count(), 22.5, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 200.0, 0.001);
+
+ rttEstimator.m_sRtt = Millis(2000);
+ rttEstimator.m_rttVar = Millis(400);
+ rttEstimator.m_rto = Millis(3600);
+
+ // check if maxRto works
+ rttEstimator.addMeasurement(Millis(100), 1);
+
+ BOOST_CHECK_CLOSE(rttEstimator.m_sRtt.count(), 1762.5, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.m_rttVar.count(), 775.0, 0.001);
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 4000.0, 0.001);
+}
+
+BOOST_AUTO_TEST_CASE(BackoffRto)
+{
+ RttEstimator::Options opts;
+ opts.initialRto = Millis(500);
+ opts.maxRto = Millis(4000);
+ RttEstimator rttEstimator(opts);
+
+ rttEstimator.backoffRto();
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 1000.0, 0.001);
+
+ // check if minRto works
+ rttEstimator.m_rto = Millis(10);
+ rttEstimator.backoffRto();
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 200.0, 0.001);
+
+ // check if maxRto works
+ rttEstimator.m_rto = Millis(3000);
+ rttEstimator.backoffRto();
+ BOOST_CHECK_CLOSE(rttEstimator.getEstimatedRto().count(), 4000.0, 0.001);
+}
+
+BOOST_AUTO_TEST_CASE(AfterMeasurement)
+{
+ RttEstimator rttEstimator;
+
+ int nHandlerInvocations = 0;
+ rttEstimator.afterMeasurement.connectSingleShot([&nHandlerInvocations] (const auto& sample) {
+ ++nHandlerInvocations;
+ BOOST_CHECK_CLOSE(sample.rtt.count(), 80.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.sRtt.count(), 80.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.rttVar.count(), 40.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.rto.count(), 240.0, 0.001);
+ BOOST_CHECK(!sample.segNum.has_value());
+ });
+ rttEstimator.addMeasurement(Millis(80), 1);
+ BOOST_CHECK_EQUAL(nHandlerInvocations, 1);
+
+ rttEstimator.afterMeasurement.connectSingleShot([&nHandlerInvocations] (const auto& sample) {
+ ++nHandlerInvocations;
+ BOOST_CHECK_CLOSE(sample.rtt.count(), 40.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.sRtt.count(), 75.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.rttVar.count(), 40.0, 0.001);
+ BOOST_CHECK_CLOSE(sample.rto.count(), 235.0, 0.001);
+ BOOST_CHECK(sample.segNum == 42U);
+ });
+ rttEstimator.addMeasurement(Millis(40), 1, 42);
+ BOOST_CHECK_EQUAL(nHandlerInvocations, 2);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // TestRttEstimator
+BOOST_AUTO_TEST_SUITE_END() // Util
+
+} // namespace tests
+} // namespace util
+} // namespace ndn