fw: use ndn-cxx's RttEstimator in AccessStrategy
Refs: #4887
Change-Id: I7e404df953f99374e676c7eb29897c45d0868eef
diff --git a/core/rtt-estimator.cpp b/core/rtt-estimator.cpp
deleted file mode 100644
index 8de3078..0000000
--- a/core/rtt-estimator.cpp
+++ /dev/null
@@ -1,80 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2017, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis
- *
- * This file is part of NFD (Named Data Networking Forwarding Daemon).
- * See AUTHORS.md for complete list of NFD authors and contributors.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- **/
-
-#include "rtt-estimator.hpp"
-
-namespace nfd {
-
-RttEstimator::RttEstimator(uint16_t maxMultiplier, Duration minRto, double gain)
- : m_maxMultiplier(maxMultiplier)
- , m_minRto(minRto.count())
- , m_rtt(RttEstimator::getInitialRtt().count())
- , m_gain(gain)
- , m_variance(0)
- , m_multiplier(1)
- , m_nSamples(0)
-{
-}
-
-void
-RttEstimator::addMeasurement(Duration measure)
-{
- double m = static_cast<double>(measure.count());
- if (m_nSamples > 0) {
- double err = m - m_rtt;
- double gErr = err * m_gain;
- m_rtt += gErr;
- double difference = std::abs(err) - m_variance;
- m_variance += difference * m_gain;
- }
- else {
- m_rtt = m;
- m_variance = m;
- }
- ++m_nSamples;
- m_multiplier = 1;
-}
-
-void
-RttEstimator::incrementMultiplier()
-{
- m_multiplier = std::min(static_cast<uint16_t>(m_multiplier + 1), m_maxMultiplier);
-}
-
-void
-RttEstimator::doubleMultiplier()
-{
- m_multiplier = std::min(static_cast<uint16_t>(m_multiplier * 2), m_maxMultiplier);
-}
-
-RttEstimator::Duration
-RttEstimator::computeRto() const
-{
- double rto = std::max(m_minRto, m_rtt + 4 * m_variance);
- rto *= m_multiplier;
- return Duration(static_cast<Duration::rep>(rto));
-}
-
-} // namespace nfd
diff --git a/core/rtt-estimator.hpp b/core/rtt-estimator.hpp
deleted file mode 100644
index e8a5eb9..0000000
--- a/core/rtt-estimator.hpp
+++ /dev/null
@@ -1,83 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2018, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis.
- *
- * This file is part of NFD (Named Data Networking Forwarding Daemon).
- * See AUTHORS.md for complete list of NFD authors and contributors.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef NFD_CORE_RTT_ESTIMATOR_HPP
-#define NFD_CORE_RTT_ESTIMATOR_HPP
-
-#include "core/common.hpp"
-
-namespace nfd {
-
-/**
- * \brief implements the Mean-Deviation RTT estimator
- *
- * \sa ns3::RttMeanDeviation
- *
- * This RttEstimator algorithm is designed for TCP, which is a continuous stream.
- * NDN Interest-Data traffic is not always a continuous stream,
- * so NDN may need a different RttEstimator.
- * The design of a more suitable RttEstimator is a research question.
- */
-class RttEstimator
-{
-public:
- using Duration = time::microseconds;
-
- RttEstimator(uint16_t maxMultiplier = 16,
- Duration minRto = 1_ms,
- double gain = 0.1);
-
- static Duration
- getInitialRtt()
- {
- return 1_s;
- }
-
- void
- addMeasurement(Duration measure);
-
- void
- incrementMultiplier();
-
- void
- doubleMultiplier();
-
- Duration
- computeRto() const;
-
-private:
- uint16_t m_maxMultiplier;
- double m_minRto;
-
- double m_rtt;
- double m_gain;
- double m_variance;
- uint16_t m_multiplier;
- uint32_t m_nSamples;
-};
-
-} // namespace nfd
-
-#endif // NFD_CORE_RTT_ESTIMATOR_HPP
diff --git a/daemon/face/lp-reliability.cpp b/daemon/face/lp-reliability.cpp
index 4489f6c..310f78e 100644
--- a/daemon/face/lp-reliability.cpp
+++ b/daemon/face/lp-reliability.cpp
@@ -114,7 +114,7 @@
if (frag.retxCount == 0) {
// This sequence had no retransmissions, so use it to estimate the RTO
- m_rttEst.addMeasurement(now - frag.sendTime, 1);
+ m_rttEst.addMeasurement(now - frag.sendTime);
}
// Look for frags with TxSequence numbers < ackSeq (allowing for wraparound) and consider them
diff --git a/daemon/fw/access-strategy.cpp b/daemon/fw/access-strategy.cpp
index b82ba40..6ae2767 100644
--- a/daemon/fw/access-strategy.cpp
+++ b/daemon/fw/access-strategy.cpp
@@ -36,7 +36,8 @@
AccessStrategy::AccessStrategy(Forwarder& forwarder, const Name& name)
: Strategy(forwarder)
- , m_removeFaceInfoConn(beforeRemoveFace.connect([this] (const Face& face) { removeFaceInfo(face); }))
+ , m_rttEstimatorOpts(make_shared<RttEstimator::Options>()) // use the default options
+ , m_removeFaceConn(beforeRemoveFace.connect([this] (const Face& face) { m_fit.erase(face.getId()); }))
{
ParsedInstanceName parsed = parseInstanceName(name);
if (!parsed.parameters.empty()) {
@@ -139,7 +140,7 @@
return false;
}
- auto rto = mi.rtt.computeRto();
+ auto rto = mi.rtt.getEstimatedRto();
NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << mi.lastNexthop
<< " last-nexthop rto=" << time::duration_cast<time::microseconds>(rto).count());
@@ -147,10 +148,11 @@
// schedule RTO timeout
PitInfo* pi = pitEntry->insertStrategyInfo<PitInfo>().first;
- pi->rtoTimer = getScheduler().schedule(rto, [=] {
- afterRtoTimeout(weak_ptr<pit::Entry>(pitEntry),
- ingress.face.getId(), ingress.endpoint, mi.lastNexthop);
- });
+ pi->rtoTimer = getScheduler().schedule(rto,
+ [this, pitWeak = weak_ptr<pit::Entry>(pitEntry), face = ingress.face.getId(),
+ endpoint = ingress.endpoint, lastNexthop = mi.lastNexthop] {
+ afterRtoTimeout(pitWeak, face, endpoint, lastNexthop);
+ });
return true;
}
@@ -226,15 +228,16 @@
auto rtt = time::steady_clock::now() - outRecord->getLastRenewed();
NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << ingress
<< " rtt=" << time::duration_cast<time::microseconds>(rtt).count());
- this->updateMeasurements(ingress.face, data, time::duration_cast<RttEstimator::Duration>(rtt));
+ this->updateMeasurements(ingress.face, data, rtt);
}
void
-AccessStrategy::updateMeasurements(const Face& inFace, const Data& data,
- const RttEstimator::Duration& rtt)
+AccessStrategy::updateMeasurements(const Face& inFace, const Data& data, time::nanoseconds rtt)
{
- ///\todo move FaceInfoTable out of AccessStrategy instance, to Measurements or somewhere else
- FaceInfo& fi = m_fit[inFace.getId()];
+ auto ret = m_fit.emplace(std::piecewise_construct,
+ std::forward_as_tuple(inFace.getId()),
+ std::forward_as_tuple(m_rttEstimatorOpts));
+ FaceInfo& fi = ret.first->second;
fi.rtt.addMeasurement(rtt);
MtInfo* mi = this->addPrefixMeasurements(data);
@@ -276,14 +279,7 @@
}
this->getMeasurements().extendLifetime(*me, 8_s);
-
- return me->insertStrategyInfo<MtInfo>().first;
-}
-
-void
-AccessStrategy::removeFaceInfo(const Face& face)
-{
- m_fit.erase(face.getId());
+ return me->insertStrategyInfo<MtInfo>(m_rttEstimatorOpts).first;
}
} // namespace fw
diff --git a/daemon/fw/access-strategy.hpp b/daemon/fw/access-strategy.hpp
index 857592b..0ce8917 100644
--- a/daemon/fw/access-strategy.hpp
+++ b/daemon/fw/access-strategy.hpp
@@ -28,7 +28,8 @@
#include "strategy.hpp"
#include "retx-suppression-fixed.hpp"
-#include "core/rtt-estimator.hpp"
+
+#include <ndn-cxx/util/rtt-estimator.hpp>
namespace nfd {
namespace fw {
@@ -65,6 +66,8 @@
const FaceEndpoint& ingress, const Data& data) override;
private: // StrategyInfo
+ using RttEstimator = ndn::util::RttEstimator;
+
/** \brief StrategyInfo on PIT entry
*/
class PitInfo : public StrategyInfo
@@ -91,9 +94,15 @@
return 1011;
}
+ explicit
+ MtInfo(shared_ptr<const RttEstimator::Options> opts)
+ : rtt(std::move(opts))
+ {
+ }
+
public:
FaceId lastNexthop = face::INVALID_FACEID;
- RttEstimator rtt{1, 1_ms, 0.1};
+ RttEstimator rtt;
};
/** \brief find per-prefix measurements for Interest
@@ -108,17 +117,22 @@
addPrefixMeasurements(const Data& data);
/** \brief global per-face StrategyInfo
+ * \todo Currently stored inside AccessStrategy instance; should be moved
+ * to measurements table or somewhere else.
*/
- struct FaceInfo
+ class FaceInfo
{
- RttEstimator rtt{1, 1_ms, 0.1};
+ public:
+ explicit
+ FaceInfo(shared_ptr<const RttEstimator::Options> opts)
+ : rtt(std::move(opts))
+ {
+ }
+
+ public:
+ RttEstimator rtt;
};
- typedef std::unordered_map<FaceId, FaceInfo> FaceInfoTable;
-
- void
- removeFaceInfo(const Face& face);
-
private: // forwarding procedures
void
afterReceiveNewInterest(const FaceEndpoint& ingress, const Interest& interest,
@@ -141,8 +155,8 @@
FaceId inFaceId, EndpointId inEndpointId, FaceId firstOutFaceId);
/** \brief multicast to all nexthops
- * \param exceptFace don't forward to this face; also, inFace is always excluded
- * \return how many Interests are sent
+ * \param exceptFace don't forward to this face; also, \p inFace is always excluded
+ * \return number of Interests that were sent
*/
size_t
multicast(const Face& inFace, const Interest& interest,
@@ -150,13 +164,13 @@
FaceId exceptFace = face::INVALID_FACEID);
void
- updateMeasurements(const Face& inFace, const Data& data,
- const RttEstimator::Duration& rtt);
+ updateMeasurements(const Face& inFace, const Data& data, time::nanoseconds rtt);
private:
- FaceInfoTable m_fit;
+ const shared_ptr<const RttEstimator::Options> m_rttEstimatorOpts;
+ std::unordered_map<FaceId, FaceInfo> m_fit;
RetxSuppressionFixed m_retxSuppression;
- signal::ScopedConnection m_removeFaceInfoConn;
+ signal::ScopedConnection m_removeFaceConn;
};
} // namespace fw
diff --git a/tests/core/rtt-estimator.t.cpp b/tests/core/rtt-estimator.t.cpp
deleted file mode 100644
index 6673ecd..0000000
--- a/tests/core/rtt-estimator.t.cpp
+++ /dev/null
@@ -1,80 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2019, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis.
- *
- * This file is part of NFD (Named Data Networking Forwarding Daemon).
- * See AUTHORS.md for complete list of NFD authors and contributors.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include "core/rtt-estimator.hpp"
-
-#include "tests/test-common.hpp"
-
-namespace nfd {
-namespace tests {
-
-BOOST_AUTO_TEST_SUITE(TestRttEstimator)
-
-static double
-computeRtoAsFloatSeconds(RttEstimator& rtt)
-{
- typedef time::duration<double, time::seconds::period> FloatSeconds;
-
- RttEstimator::Duration rto = rtt.computeRto();
- return time::duration_cast<FloatSeconds>(rto).count();
-}
-
-BOOST_AUTO_TEST_CASE(Basic)
-{
- RttEstimator rtt;
-
- for (int i = 0; i < 100; ++i) {
- rtt.addMeasurement(5_s);
- }
- double rto1 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_CLOSE(rto1, 5.0, 0.1);
-
- rtt.doubleMultiplier();
- double rto2 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_CLOSE(rto2, 10.0, 0.1);
-
- rtt.doubleMultiplier();
- double rto3 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_CLOSE(rto3, 20.0, 0.1);
-
- rtt.addMeasurement(5_s); // reset multiplier
- double rto4 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_CLOSE(rto4, 5.0, 0.1);
-
- rtt.incrementMultiplier();
- double rto5 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_CLOSE(rto5, 10.0, 0.1);
-
- for (int i = 0; i < 5; ++i) {
- rtt.addMeasurement(6_s);
- } // increased variance
- double rto6 = computeRtoAsFloatSeconds(rtt);
- BOOST_CHECK_GT(rto6, rto1);
-}
-
-BOOST_AUTO_TEST_SUITE_END() // TestRttEstimator
-
-} // namespace tests
-} // namespace nfd