util: split RttEstimator into two classes
Also remove afterMeasurement signal, effectively reverting
commit 4ad933a757836b7f7418359cff5ae87610f39d55
Refs: #4887
Change-Id: I6c9b1620250992e07bed0773ee8f043e8e1e1f04
diff --git a/ndn-cxx/util/rtt-estimator.cpp b/ndn-cxx/util/rtt-estimator.cpp
index e214ebb..a0a4779 100644
--- a/ndn-cxx/util/rtt-estimator.cpp
+++ b/ndn-cxx/util/rtt-estimator.cpp
@@ -21,6 +21,7 @@
* @author Shuo Yang
* @author Weiwei Liu
* @author Chavoosh Ghasemi
+ * @author Davide Pesavento
*/
#include "ndn-cxx/util/rtt-estimator.hpp"
@@ -28,58 +29,56 @@
namespace ndn {
namespace util {
-RttEstimator::RttEstimator(const Options& options)
- : m_options(options)
- , m_sRtt(0)
- , m_rttVar(0)
- , m_rto(m_options.initialRto)
- , m_rttMin(time::nanoseconds::max())
- , m_rttMax(time::nanoseconds::min())
- , m_rttAvg(0)
- , m_nRttSamples(0)
+RttEstimator::RttEstimator(shared_ptr<const Options> options)
+ : m_options(options ? std::move(options) : make_shared<const Options>())
+ , m_rto(m_options->initialRto)
{
- BOOST_ASSERT(m_options.alpha >= 0 && m_options.alpha <= 1);
- BOOST_ASSERT(m_options.beta >= 0 && m_options.beta <= 1);
- BOOST_ASSERT(m_options.initialRto >= 0_ns);
- BOOST_ASSERT(m_options.minRto >= 0_ns);
- BOOST_ASSERT(m_options.maxRto >= m_options.minRto);
- BOOST_ASSERT(m_options.k >= 0);
- BOOST_ASSERT(m_options.rtoBackoffMultiplier >= 1);
+ BOOST_ASSERT(m_options->alpha >= 0 && m_options->alpha <= 1);
+ BOOST_ASSERT(m_options->beta >= 0 && m_options->beta <= 1);
+ BOOST_ASSERT(m_options->initialRto >= 0_ns);
+ BOOST_ASSERT(m_options->minRto >= 0_ns);
+ BOOST_ASSERT(m_options->maxRto >= m_options->minRto);
+ BOOST_ASSERT(m_options->k >= 0);
+ BOOST_ASSERT(m_options->rtoBackoffMultiplier >= 1);
}
void
-RttEstimator::addMeasurement(time::nanoseconds rtt, size_t nExpectedSamples,
- optional<uint64_t> segNum)
+RttEstimator::addMeasurement(time::nanoseconds rtt, size_t nExpectedSamples)
{
+ BOOST_ASSERT(rtt >= 0_ns);
BOOST_ASSERT(nExpectedSamples > 0);
- if (m_nRttSamples == 0) { // first measurement
+ if (!hasSamples()) { // first measurement
m_sRtt = rtt;
m_rttVar = m_sRtt / 2;
}
else {
- double alpha = m_options.alpha / nExpectedSamples;
- double beta = m_options.beta / nExpectedSamples;
+ double alpha = m_options->alpha / nExpectedSamples;
+ double beta = m_options->beta / nExpectedSamples;
m_rttVar = time::duration_cast<time::nanoseconds>((1 - beta) * m_rttVar +
beta * time::abs(m_sRtt - rtt));
m_sRtt = time::duration_cast<time::nanoseconds>((1 - alpha) * m_sRtt + alpha * rtt);
}
- m_rto = clamp(m_sRtt + m_options.k * m_rttVar,
- m_options.minRto, m_options.maxRto);
-
- afterMeasurement({rtt, m_sRtt, m_rttVar, m_rto, segNum});
-
- 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++;
+ m_rto = clamp(m_sRtt + m_options->k * m_rttVar,
+ m_options->minRto, m_options->maxRto);
}
void
RttEstimator::backoffRto()
{
- m_rto = clamp(m_rto * m_options.rtoBackoffMultiplier,
- m_options.minRto, m_options.maxRto);
+ m_rto = clamp(m_rto * m_options->rtoBackoffMultiplier,
+ m_options->minRto, m_options->maxRto);
+}
+
+void
+RttEstimatorWithStats::addMeasurement(time::nanoseconds rtt, size_t nExpectedSamples)
+{
+ RttEstimator::addMeasurement(rtt, nExpectedSamples);
+
+ 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++;
}
} // namespace util
diff --git a/ndn-cxx/util/rtt-estimator.hpp b/ndn-cxx/util/rtt-estimator.hpp
index da43ea4..ba3255c 100644
--- a/ndn-cxx/util/rtt-estimator.hpp
+++ b/ndn-cxx/util/rtt-estimator.hpp
@@ -21,19 +21,19 @@
* @author Shuo Yang
* @author Weiwei Liu
* @author Chavoosh Ghasemi
+ * @author Davide Pesavento
*/
#ifndef NDN_CXX_UTIL_RTT_ESTIMATOR_HPP
#define NDN_CXX_UTIL_RTT_ESTIMATOR_HPP
-#include "ndn-cxx/util/signal.hpp"
#include "ndn-cxx/util/time.hpp"
namespace ndn {
namespace util {
/**
- * @brief RTT Estimator.
+ * @brief RTT/RTO estimator.
*
* This class implements the "Mean-Deviation" RTT estimator, as discussed in RFC 6298,
* with the modifications to RTO calculation described in RFC 7323 Appendix G.
@@ -41,15 +41,8 @@
class RttEstimator
{
public:
- class Options
+ struct Options
{
- public:
- constexpr
- Options() noexcept
- {
- }
-
- public:
double alpha = 0.125; ///< weight of exponential moving average for smoothed RTT
double beta = 0.25; ///< weight of exponential moving average for RTT variation
time::nanoseconds initialRto = 1_s; ///< initial RTO value
@@ -60,29 +53,28 @@
};
/**
- * @brief Creates an RTT estimator.
- *
- * Configures the RTT estimator with the default parameters if an instance of Options
- * is not passed to the constructor.
+ * @brief Constructor.
+ * @param options options for the estimator; if nullptr, a default set of options is used
*/
explicit
- RttEstimator(const Options& options = Options());
+ RttEstimator(shared_ptr<const Options> options = nullptr);
/**
* @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 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(time::nanoseconds rtt, size_t nExpectedSamples,
- optional<uint64_t> segNum = nullopt);
+ addMeasurement(time::nanoseconds rtt, size_t nExpectedSamples = 1);
+
+ bool
+ hasSamples() const
+ {
+ return m_sRtt != -1_ns;
+ }
/**
* @brief Returns the estimated RTO value.
@@ -94,6 +86,67 @@
}
/**
+ * @brief Returns the smoothed RTT value (SRTT).
+ * @pre `hasSamples() == true`
+ */
+ time::nanoseconds
+ getSmoothedRtt() const
+ {
+ return m_sRtt;
+ }
+
+ /**
+ * @brief Returns the RTT variation (RTTVAR).
+ * @pre `hasSamples() == true`
+ */
+ time::nanoseconds
+ getRttVariation() const
+ {
+ return m_rttVar;
+ }
+
+ /**
+ * @brief Backoff RTO by a factor of Options::rtoBackoffMultiplier.
+ */
+ void
+ backoffRto();
+
+protected:
+ shared_ptr<const Options> m_options;
+
+private:
+ time::nanoseconds m_sRtt{-1}; ///< smoothed round-trip time
+ time::nanoseconds m_rttVar{-1}; ///< round-trip time variation
+ time::nanoseconds m_rto; ///< retransmission timeout
+};
+
+/**
+ * @brief RTT/RTO estimator that also maintains min/max/average RTT statistics.
+ */
+class RttEstimatorWithStats : private RttEstimator
+{
+public:
+ using RttEstimator::Options;
+ using RttEstimator::RttEstimator;
+
+ using RttEstimator::hasSamples;
+ using RttEstimator::getEstimatedRto;
+ using RttEstimator::getSmoothedRtt;
+ using RttEstimator::getRttVariation;
+ using RttEstimator::backoffRto;
+
+ /**
+ * @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 the current number of in-flight Interests. Please refer to
+ * Appendix G of RFC 7323 for details.
+ * @note Do not call this function with RTT samples from retransmitted Interests (per Karn's algorithm).
+ */
+ void
+ addMeasurement(time::nanoseconds rtt, size_t nExpectedSamples = 1);
+
+ /**
* @brief Returns the minimum RTT observed.
*/
time::nanoseconds
@@ -120,51 +173,11 @@
return m_rttAvg;
}
- /**
- * @brief Returns the smoothed RTT value (SRTT).
- */
- time::nanoseconds
- getSmoothedRtt() const
- {
- return m_sRtt;
- }
-
- /**
- * @brief Returns the RTT variation (RTTVAR).
- */
- time::nanoseconds
- getRttVariation() const
- {
- return m_rttVar;
- }
-
- /**
- * @brief Backoff RTO by a factor of Options::rtoBackoffMultiplier.
- */
- void
- backoffRto();
-
-public:
- struct Sample
- {
- time::nanoseconds rtt; ///< measured RTT
- time::nanoseconds sRtt; ///< smoothed RTT
- time::nanoseconds rttVar; ///< RTT variation
- time::nanoseconds rto; ///< retransmission timeout
- optional<uint64_t> segNum; ///< segment number, see description in addMeasurement()
- };
-
- Signal<RttEstimator, Sample> afterMeasurement;
-
private:
- const Options m_options;
- time::nanoseconds m_sRtt; ///< smoothed round-trip time
- time::nanoseconds m_rttVar; ///< round-trip time variation
- time::nanoseconds m_rto; ///< retransmission timeout
- time::nanoseconds m_rttMin;
- time::nanoseconds m_rttMax;
- time::nanoseconds m_rttAvg;
- int64_t m_nRttSamples;
+ time::nanoseconds m_rttMin = time::nanoseconds::max();
+ time::nanoseconds m_rttMax = time::nanoseconds::min();
+ time::nanoseconds m_rttAvg = 0_ns;
+ int64_t m_nRttSamples = 0;
};
} // namespace util
diff --git a/ndn-cxx/util/segment-fetcher.cpp b/ndn-cxx/util/segment-fetcher.cpp
index 80a5c38..6e5d492 100644
--- a/ndn-cxx/util/segment-fetcher.cpp
+++ b/ndn-cxx/util/segment-fetcher.cpp
@@ -69,7 +69,7 @@
, m_face(face)
, m_scheduler(m_face.getIoService())
, m_validator(validator)
- , m_rttEstimator(options.rttOptions)
+ , m_rttEstimator(make_shared<RttEstimator::Options>(options.rttOptions))
, m_timeLastSegmentReceived(time::steady_clock::now())
, m_nextSegmentNum(0)
, m_cwnd(options.initCwnd)
@@ -266,9 +266,9 @@
uint64_t currentSegment = data.getName().get(-1).toSegment();
// Add measurement to RTO estimator (if not retransmission)
if (pendingSegmentIt->second.state == SegmentState::FirstInterest) {
+ BOOST_ASSERT(m_nSegmentsInFlight >= 0);
m_rttEstimator.addMeasurement(m_timeLastSegmentReceived - pendingSegmentIt->second.sendTime,
- std::max<int64_t>(m_nSegmentsInFlight + 1, 1),
- currentSegment);
+ static_cast<size_t>(m_nSegmentsInFlight) + 1);
}
// Remove from pending segments map
diff --git a/tests/unit/util/rtt-estimator.t.cpp b/tests/unit/util/rtt-estimator.t.cpp
index 10c2c74..b819c9b 100644
--- a/tests/unit/util/rtt-estimator.t.cpp
+++ b/tests/unit/util/rtt-estimator.t.cpp
@@ -34,9 +34,109 @@
BOOST_AUTO_TEST_SUITE(Util)
BOOST_AUTO_TEST_SUITE(TestRttEstimator)
-BOOST_AUTO_TEST_CASE(MinAvgMaxRtt)
+BOOST_AUTO_TEST_CASE(CopyAssign)
{
- RttEstimator rttEstimator;
+ RttEstimator est1;
+ RttEstimator est2;
+
+ est1.addMeasurement(100_ms);
+ est1.addMeasurement(150_ms);
+ est2.addMeasurement(75_ms);
+ est2.addMeasurement(70_ms);
+
+ BOOST_CHECK_NE(est1.getEstimatedRto(), est2.getEstimatedRto());
+ BOOST_CHECK_NE(est1.getRttVariation(), est2.getRttVariation());
+ BOOST_CHECK_NE(est1.getSmoothedRtt(), est2.getSmoothedRtt());
+
+ est1 = est2;
+
+ BOOST_CHECK_EQUAL(est1.getEstimatedRto(), est2.getEstimatedRto());
+ BOOST_CHECK_EQUAL(est1.getRttVariation(), est2.getRttVariation());
+ BOOST_CHECK_EQUAL(est1.getSmoothedRtt(), est2.getSmoothedRtt());
+}
+
+BOOST_AUTO_TEST_CASE(EstimatedRto)
+{
+ auto opts = make_shared<RttEstimator::Options>();
+ opts->initialRto = 400_ms;
+ opts->maxRto = 2_s;
+ RttEstimator rttEstimator(opts);
+
+ // check initial values
+ BOOST_CHECK_EQUAL(rttEstimator.hasSamples(), false);
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), -1_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), -1_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts->initialRto);
+
+ // first measurement
+ rttEstimator.addMeasurement(200_ms);
+
+ BOOST_CHECK_EQUAL(rttEstimator.hasSamples(), true);
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 200_ms);
+ BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 100_ms);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 600_ms);
+
+ rttEstimator.addMeasurement(100_ms, 1);
+
+ BOOST_CHECK_EQUAL(rttEstimator.hasSamples(), true);
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 187500_us);
+ BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 100000_us);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 587500_us);
+
+ // expected samples larger than 1
+ rttEstimator.addMeasurement(50_ms, 5);
+
+ BOOST_CHECK_EQUAL(rttEstimator.hasSamples(), true);
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 184062500_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 101875000_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 591562500_ns);
+
+ // check if minRto works
+ for (int i = 0; i < 20; i++) {
+ rttEstimator.addMeasurement(10_ms);
+ }
+
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 22046646_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts->minRto);
+
+ // check if maxRto works
+ for (int i = 0; i < 10; i++) {
+ rttEstimator.addMeasurement(1_s);
+ rttEstimator.addMeasurement(10_ms);
+ }
+
+ BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 440859284_ns);
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts->maxRto);
+}
+
+BOOST_AUTO_TEST_CASE(BackoffRto)
+{
+ auto opts = make_shared<RttEstimator::Options>();
+ opts->initialRto = 500_ms;
+ opts->maxRto = 4_s;
+ RttEstimator rttEstimator(opts);
+
+ rttEstimator.backoffRto();
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 1_s);
+
+ // check if minRto works
+ for (int i = 0; i < 10; i++) {
+ rttEstimator.addMeasurement(5_ms);
+ }
+ rttEstimator.backoffRto();
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 400_ms);
+
+ // check if maxRto works
+ for (int i = 0; i < 10; i++) {
+ rttEstimator.addMeasurement(5_s);
+ }
+ rttEstimator.backoffRto();
+ BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 4_s);
+}
+
+BOOST_AUTO_TEST_CASE(Stats)
+{
+ RttEstimatorWithStats rttEstimator;
// check initial values
BOOST_CHECK_EQUAL(rttEstimator.getMinRtt().count(), std::numeric_limits<time::nanoseconds::rep>::max());
@@ -44,9 +144,9 @@
BOOST_CHECK_EQUAL(rttEstimator.getMaxRtt().count(), std::numeric_limits<time::nanoseconds::rep>::min());
// start with three samples
- rttEstimator.addMeasurement(100_ms, 1);
- rttEstimator.addMeasurement(400_ms, 1);
- rttEstimator.addMeasurement(250_ms, 1);
+ rttEstimator.addMeasurement(100_ms);
+ rttEstimator.addMeasurement(400_ms);
+ rttEstimator.addMeasurement(250_ms);
BOOST_CHECK_EQUAL(rttEstimator.getMinRtt(), 100_ms);
BOOST_CHECK_EQUAL(rttEstimator.getAvgRtt(), 250_ms);
@@ -65,109 +165,6 @@
BOOST_CHECK_EQUAL(rttEstimator.getMaxRtt(), 700_ms);
}
-BOOST_AUTO_TEST_CASE(EstimatedRto)
-{
- RttEstimator::Options opts;
- opts.initialRto = 400_ms;
- opts.maxRto = 2_s;
- RttEstimator rttEstimator(opts);
-
- // check initial values
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 0_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 0_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts.initialRto);
-
- // first measurement
- rttEstimator.addMeasurement(200_ms, 1);
-
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 200_ms);
- BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 100_ms);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 600_ms);
-
- rttEstimator.addMeasurement(100_ms, 1);
-
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 187500_us);
- BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 100000_us);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 587500_us);
-
- // expected samples larger than 1
- rttEstimator.addMeasurement(50_ms, 5);
-
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 184062500_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getRttVariation(), 101875000_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 591562500_ns);
-
- // check if minRto works
- for (int i = 0; i < 20; i++) {
- rttEstimator.addMeasurement(10_ms, 1);
- }
-
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 22046646_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts.minRto);
-
- // check if maxRto works
- for (int i = 0; i < 10; i++) {
- rttEstimator.addMeasurement(1_s, 1);
- rttEstimator.addMeasurement(10_ms, 1);
- }
-
- BOOST_CHECK_EQUAL(rttEstimator.getSmoothedRtt(), 440859284_ns);
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), opts.maxRto);
-}
-
-BOOST_AUTO_TEST_CASE(BackoffRto)
-{
- RttEstimator::Options opts;
- opts.initialRto = 500_ms;
- opts.maxRto = 4_s;
- RttEstimator rttEstimator(opts);
-
- rttEstimator.backoffRto();
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 1_s);
-
- // check if minRto works
- for (int i = 0; i < 10; i++) {
- rttEstimator.addMeasurement(5_ms, 1);
- }
- rttEstimator.backoffRto();
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 400_ms);
-
- // check if maxRto works
- for (int i = 0; i < 10; i++) {
- rttEstimator.addMeasurement(5_s, 1);
- }
- rttEstimator.backoffRto();
- BOOST_CHECK_EQUAL(rttEstimator.getEstimatedRto(), 4_s);
-}
-
-BOOST_AUTO_TEST_CASE(AfterMeasurement)
-{
- RttEstimator rttEstimator;
-
- int nHandlerInvocations = 0;
- rttEstimator.afterMeasurement.connectSingleShot([&nHandlerInvocations] (const auto& sample) {
- ++nHandlerInvocations;
- BOOST_CHECK_EQUAL(sample.rtt, 80_ms);
- BOOST_CHECK_EQUAL(sample.sRtt, 80_ms);
- BOOST_CHECK_EQUAL(sample.rttVar, 40_ms);
- BOOST_CHECK_EQUAL(sample.rto, 240_ms);
- BOOST_CHECK(!sample.segNum.has_value());
- });
- rttEstimator.addMeasurement(80_ms, 1);
- BOOST_CHECK_EQUAL(nHandlerInvocations, 1);
-
- rttEstimator.afterMeasurement.connectSingleShot([&nHandlerInvocations] (const auto& sample) {
- ++nHandlerInvocations;
- BOOST_CHECK_EQUAL(sample.rtt, 40_ms);
- BOOST_CHECK_EQUAL(sample.sRtt, 75_ms);
- BOOST_CHECK_EQUAL(sample.rttVar, 40_ms);
- BOOST_CHECK_EQUAL(sample.rto, 235_ms);
- BOOST_CHECK(sample.segNum == 42U);
- });
- rttEstimator.addMeasurement(40_ms, 1, 42);
- BOOST_CHECK_EQUAL(nHandlerInvocations, 2);
-}
-
BOOST_AUTO_TEST_SUITE_END() // TestRttEstimator
BOOST_AUTO_TEST_SUITE_END() // Util