fw: Adaptive SRTT-based Forwarding strategy
refs: #3566
Change-Id: Idae198bb0c2ae25e25aeceec0552b1c11be89c14
diff --git a/daemon/fw/asf-measurements.cpp b/daemon/fw/asf-measurements.cpp
new file mode 100644
index 0000000..1a2eca2
--- /dev/null
+++ b/daemon/fw/asf-measurements.cpp
@@ -0,0 +1,271 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "asf-measurements.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+NFD_LOG_INIT("AsfMeasurements");
+
+const RttStats::Rtt RttStats::RTT_TIMEOUT(-1.0);
+const RttStats::Rtt RttStats::RTT_NO_MEASUREMENT(0.0);
+const double RttStats::ALPHA = 0.125;
+
+RttStats::RttStats()
+ : m_srtt(RTT_NO_MEASUREMENT)
+ , m_rtt(RTT_NO_MEASUREMENT)
+{
+}
+
+void
+RttStats::addRttMeasurement(RttEstimator::Duration& durationRtt)
+{
+ m_rtt = static_cast<RttStats::Rtt>(durationRtt.count());
+
+ m_rttEstimator.addMeasurement(durationRtt);
+
+ m_srtt = computeSrtt(m_srtt, m_rtt);
+}
+
+RttStats::Rtt
+RttStats::computeSrtt(Rtt previousSrtt, Rtt currentRtt)
+{
+ if (previousSrtt == RTT_NO_MEASUREMENT) {
+ return currentRtt;
+ }
+
+ return Rtt(ALPHA * currentRtt + (1 - ALPHA) * previousSrtt);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+FaceInfo::FaceInfo()
+ : m_isTimeoutScheduled(false)
+{
+}
+
+FaceInfo::~FaceInfo()
+{
+ cancelTimeoutEvent();
+ scheduler::cancel(m_measurementExpirationId);
+}
+
+void
+FaceInfo::setTimeoutEvent(const scheduler::EventId& id, const ndn::Name& interestName)
+{
+ if (!m_isTimeoutScheduled) {
+ m_timeoutEventId = id;
+ m_isTimeoutScheduled = true;
+ m_lastInterestName = interestName;
+ }
+ else {
+ BOOST_THROW_EXCEPTION(FaceInfo::Error("Tried to schedule a timeout for a face that already has a timeout scheduled."));
+ }
+}
+
+void
+FaceInfo::cancelTimeoutEvent()
+{
+ scheduler::cancel(m_timeoutEventId);
+ m_isTimeoutScheduled = false;
+}
+
+void
+FaceInfo::cancelTimeoutEvent(const ndn::Name& prefix)
+{
+ if (isTimeoutScheduled() && doesNameMatchLastInterest(prefix)) {
+ cancelTimeoutEvent();
+ }
+}
+
+bool
+FaceInfo::doesNameMatchLastInterest(const ndn::Name& name)
+{
+ return m_lastInterestName.isPrefixOf(name);
+}
+
+void
+FaceInfo::recordRtt(const shared_ptr<pit::Entry> pitEntry, const Face& inFace)
+{
+ // Calculate RTT
+ pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(inFace);
+ time::steady_clock::Duration steadyRtt = time::steady_clock::now() - outRecord->getLastRenewed();
+ RttEstimator::Duration durationRtt = time::duration_cast<RttEstimator::Duration>(steadyRtt);
+
+ m_rttStats.addRttMeasurement(durationRtt);
+
+ NFD_LOG_TRACE("Recording RTT for FaceId: " << inFace.getId()
+ << " RTT: " << m_rttStats.getRtt()
+ << " SRTT: " << m_rttStats.getSrtt());
+}
+
+void
+FaceInfo::recordTimeout(const ndn::Name& interestName)
+{
+ m_rttStats.recordTimeout();
+ cancelTimeoutEvent(interestName);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+NamespaceInfo::NamespaceInfo()
+ : m_isProbingDue(false)
+ , m_hasFirstProbeBeenScheduled(false)
+{
+}
+
+FaceInfo*
+NamespaceInfo::getFaceInfo(const fib::Entry& fibEntry, const Face& face)
+{
+ FaceInfoTable::iterator it = m_fit.find(face.getId());
+
+ if (it != m_fit.end()) {
+ return &it->second;
+ }
+ else {
+ return nullptr;
+ }
+}
+
+FaceInfo&
+NamespaceInfo::getOrCreateFaceInfo(const fib::Entry& fibEntry, const Face& face)
+{
+ FaceInfoTable::iterator it = m_fit.find(face.getId());
+
+ FaceInfo* info = nullptr;
+
+ if (it == m_fit.end()) {
+ const auto& pair = m_fit.insert(std::make_pair(face.getId(), FaceInfo()));
+ info = &pair.first->second;
+
+ extendFaceInfoLifetime(*info, face);
+ }
+ else {
+ info = &it->second;
+ }
+
+ return *info;
+}
+
+void
+NamespaceInfo::expireFaceInfo(nfd::face::FaceId faceId)
+{
+ m_fit.erase(faceId);
+}
+
+void
+NamespaceInfo::extendFaceInfoLifetime(FaceInfo& info, const Face& face)
+{
+ // Cancel previous expiration
+ scheduler::cancel(info.getMeasurementExpirationEventId());
+
+ // Refresh measurement
+ scheduler::EventId id = scheduler::schedule(AsfMeasurements::MEASUREMENTS_LIFETIME,
+ bind(&NamespaceInfo::expireFaceInfo, this, face.getId()));
+
+ info.setMeasurementExpirationEventId(id);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+constexpr time::microseconds AsfMeasurements::MEASUREMENTS_LIFETIME;
+
+AsfMeasurements::AsfMeasurements(MeasurementsAccessor& measurements)
+ : m_measurements(measurements)
+{
+}
+
+FaceInfo*
+AsfMeasurements::getFaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& face)
+{
+ NamespaceInfo& info = getOrCreateNamespaceInfo(fibEntry, interest);
+ return info.getFaceInfo(fibEntry, face);
+}
+
+FaceInfo&
+AsfMeasurements::getOrCreateFaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& face)
+{
+ NamespaceInfo& info = getOrCreateNamespaceInfo(fibEntry, interest);
+ return info.getOrCreateFaceInfo(fibEntry, face);
+}
+
+shared_ptr<NamespaceInfo>
+AsfMeasurements::getNamespaceInfo(const ndn::Name& prefix)
+{
+ shared_ptr<measurements::Entry> me = m_measurements.findLongestPrefixMatch(prefix);
+
+ if (me == nullptr) {
+ return nullptr;
+ }
+
+ // Set or update entry lifetime
+ extendLifetime(me);
+
+ shared_ptr<NamespaceInfo> info = me->getOrCreateStrategyInfo<NamespaceInfo>();
+ BOOST_ASSERT(info != nullptr);
+
+ return info;
+}
+
+NamespaceInfo&
+AsfMeasurements::getOrCreateNamespaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest)
+{
+ shared_ptr<measurements::Entry> me = m_measurements.get(fibEntry);
+
+ // If the FIB entry is not under the strategy's namespace, find a part of the prefix
+ // that falls under the strategy's namespace
+ for (size_t prefixLen = fibEntry.getPrefix().size() + 1;
+ me == nullptr && prefixLen <= interest.getName().size(); ++prefixLen) {
+ me = m_measurements.get(interest.getName().getPrefix(prefixLen));
+ }
+
+ // Either the FIB entry or the Interest's name must be under this strategy's namespace
+ BOOST_ASSERT(me != nullptr);
+
+ // Set or update entry lifetime
+ extendLifetime(me);
+
+ shared_ptr<NamespaceInfo> info = me->getOrCreateStrategyInfo<NamespaceInfo>();
+ BOOST_ASSERT(info != nullptr);
+
+ return *info;
+}
+
+void
+AsfMeasurements::extendLifetime(shared_ptr<measurements::Entry> me)
+{
+ if (me != nullptr) {
+ m_measurements.extendLifetime(*me, MEASUREMENTS_LIFETIME);
+ }
+}
+
+} // namespace asf
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/asf-measurements.hpp b/daemon/fw/asf-measurements.hpp
new file mode 100644
index 0000000..8339d97
--- /dev/null
+++ b/daemon/fw/asf-measurements.hpp
@@ -0,0 +1,311 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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_DAEMON_FW_ASF_MEASUREMENTS_HPP
+#define NFD_DAEMON_FW_ASF_MEASUREMENTS_HPP
+
+#include "fw/rtt-estimator.hpp"
+#include "fw/strategy-info.hpp"
+#include "table/measurements-accessor.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+class RttStats
+{
+public:
+ typedef time::duration<double, boost::micro> Rtt;
+
+ RttStats();
+
+ void
+ addRttMeasurement(RttEstimator::Duration& durationRtt);
+
+ void
+ recordTimeout()
+ {
+ m_rtt = RTT_TIMEOUT;
+ }
+
+ Rtt
+ getRtt() const
+ {
+ return m_rtt;
+ }
+
+ Rtt
+ getSrtt() const
+ {
+ return m_srtt;
+ }
+
+ RttEstimator::Duration
+ computeRto() const
+ {
+ return m_rttEstimator.computeRto();
+ }
+
+private:
+ static Rtt
+ computeSrtt(Rtt previousSrtt, Rtt currentRtt);
+
+public:
+ static const Rtt RTT_TIMEOUT;
+ static const Rtt RTT_NO_MEASUREMENT;
+
+private:
+ Rtt m_srtt;
+ Rtt m_rtt;
+ RttEstimator m_rttEstimator;
+
+ static const double ALPHA;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+/** \brief Strategy information for each face in a namespace
+*/
+class FaceInfo
+{
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+ FaceInfo();
+
+ ~FaceInfo();
+
+ void
+ setTimeoutEvent(const scheduler::EventId& id, const ndn::Name& interestName);
+
+ void
+ setMeasurementExpirationEventId(const scheduler::EventId& id)
+ {
+ m_measurementExpirationId = id;
+ }
+
+ const scheduler::EventId&
+ getMeasurementExpirationEventId()
+ {
+ return m_measurementExpirationId;
+ }
+
+ void
+ cancelTimeoutEvent(const ndn::Name& prefix);
+
+ bool
+ isTimeoutScheduled() const
+ {
+ return m_isTimeoutScheduled;
+ }
+
+ void
+ recordRtt(const shared_ptr<pit::Entry> pitEntry, const Face& inFace);
+
+ void
+ recordTimeout(const ndn::Name& interestName);
+
+ bool
+ isTimeout() const
+ {
+ return getRtt() == RttStats::RTT_TIMEOUT;
+ }
+
+ RttEstimator::Duration
+ computeRto() const
+ {
+ return m_rttStats.computeRto();
+ }
+
+ RttStats::Rtt
+ getRtt() const
+ {
+ return m_rttStats.getRtt();
+ }
+
+ RttStats::Rtt
+ getSrtt() const
+ {
+ return m_rttStats.getSrtt();
+ }
+
+ bool
+ hasSrttMeasurement() const
+ {
+ return getSrtt() != RttStats::RTT_NO_MEASUREMENT;
+ }
+
+private:
+ void
+ cancelTimeoutEvent();
+
+ bool
+ doesNameMatchLastInterest(const ndn::Name& name);
+
+private:
+ RttStats m_rttStats;
+ ndn::Name m_lastInterestName;
+
+ // Timeout associated with measurement
+ scheduler::EventId m_measurementExpirationId;
+
+ // RTO associated with Interest
+ scheduler::EventId m_timeoutEventId;
+ bool m_isTimeoutScheduled;
+};
+
+typedef std::unordered_map<face::FaceId, FaceInfo> FaceInfoTable;
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+/** \brief stores stategy information about each face in this namespace
+ */
+class NamespaceInfo : public StrategyInfo
+{
+public:
+ NamespaceInfo();
+
+ static constexpr int
+ getTypeId()
+ {
+ return 1030;
+ }
+
+ FaceInfo&
+ getOrCreateFaceInfo(const fib::Entry& fibEntry, const Face& face);
+
+ FaceInfo*
+ getFaceInfo(const fib::Entry& fibEntry, const Face& face);
+
+ void
+ expireFaceInfo(nfd::face::FaceId faceId);
+
+ void
+ extendFaceInfoLifetime(FaceInfo& info, const Face& face);
+
+ FaceInfo&
+ get(nfd::face::FaceId faceId)
+ {
+ return m_fit.at(faceId);
+ }
+
+ FaceInfoTable::iterator
+ find(nfd::face::FaceId faceId)
+ {
+ return m_fit.find(faceId);
+ }
+
+ FaceInfoTable::iterator
+ end()
+ {
+ return m_fit.end();
+ }
+
+ const FaceInfoTable::iterator
+ insert(nfd::face::FaceId faceId)
+ {
+ const auto& pair = m_fit.insert(std::make_pair(faceId, FaceInfo()));
+ return pair.first;
+ }
+
+ bool
+ isProbingDue() const
+ {
+ return m_isProbingDue;
+ }
+
+ void
+ setIsProbingDue(bool isProbingDue)
+ {
+ m_isProbingDue = isProbingDue;
+ }
+
+ bool
+ isFirstProbeScheduled() const
+ {
+ return m_hasFirstProbeBeenScheduled;
+ }
+
+ void
+ setHasFirstProbeBeenScheduled(bool hasBeenScheduled)
+ {
+ m_hasFirstProbeBeenScheduled = hasBeenScheduled;
+ }
+
+private:
+ FaceInfoTable m_fit;
+
+ bool m_isProbingDue;
+ bool m_hasFirstProbeBeenScheduled;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+/** \brief Helper class to retrieve and create strategy measurements
+ */
+class AsfMeasurements : noncopyable
+{
+public:
+ explicit
+ AsfMeasurements(MeasurementsAccessor& measurements);
+
+ FaceInfo*
+ getFaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& face);
+
+ FaceInfo&
+ getOrCreateFaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& face);
+
+ shared_ptr<NamespaceInfo>
+ getNamespaceInfo(const ndn::Name& prefix);
+
+ NamespaceInfo&
+ getOrCreateNamespaceInfo(const fib::Entry& fibEntry, const ndn::Interest& interest);
+
+ void
+ extendLifetime(shared_ptr<measurements::Entry> me);
+
+public:
+ static constexpr time::microseconds MEASUREMENTS_LIFETIME = time::seconds(300);
+
+private:
+ MeasurementsAccessor& m_measurements;
+};
+
+} // namespace asf
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_ASF_MEASUREMENTS_HPP
diff --git a/daemon/fw/asf-probing-module.cpp b/daemon/fw/asf-probing-module.cpp
new file mode 100644
index 0000000..4be41f0
--- /dev/null
+++ b/daemon/fw/asf-probing-module.cpp
@@ -0,0 +1,195 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "asf-probing-module.hpp"
+
+#include "random.hpp"
+
+#include <boost/random/uniform_real_distribution.hpp>
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+constexpr time::seconds ProbingModule::DEFAULT_PROBING_INTERVAL;
+
+static_assert(ProbingModule::DEFAULT_PROBING_INTERVAL < AsfMeasurements::MEASUREMENTS_LIFETIME,
+ "ProbingModule::DEFAULT_PROBING_INTERVAL must be less than AsfMeasurements::MEASUREMENTS_LIFETIME");
+
+ProbingModule::ProbingModule(AsfMeasurements& measurements)
+ : m_probingInterval(DEFAULT_PROBING_INTERVAL)
+ , m_measurements(measurements)
+{
+}
+
+void
+ProbingModule::scheduleProbe(shared_ptr<fib::Entry> fibEntry, const time::milliseconds& interval)
+{
+ ndn::Name prefix = fibEntry->getPrefix();
+
+ // Set the probing flag for the namespace to true after passed interval of time
+ scheduler::schedule(interval, [this, prefix] {
+ shared_ptr<NamespaceInfo> info = m_measurements.getNamespaceInfo(prefix);
+
+ if (info == nullptr) {
+ // fib::Entry with the passed prefix has been removed or the fib::Entry has
+ // a name that is not controlled by the AsfStrategy
+ return;
+ }
+ else {
+ info->setIsProbingDue(true);
+ }
+ });
+}
+
+shared_ptr<Face>
+ProbingModule::getFaceToProbe(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ const Face& faceUsed)
+{
+ FaceInfoFacePairSet rankedFaces(
+ [] (FaceInfoFacePair pairLhs, FaceInfoFacePair pairRhs) -> bool {
+ // Sort by RTT
+ // If a face has timed-out, rank it behind non-timed-out faces
+ FaceInfo& lhs = *pairLhs.first;
+ FaceInfo& rhs = *pairRhs.first;
+
+ return (!lhs.isTimeout() && rhs.isTimeout()) ||
+ (lhs.isTimeout() == rhs.isTimeout() && lhs.getSrtt() < rhs.getSrtt());
+ });
+
+ // Put eligible faces into rankedFaces. If a face does not have an RTT measurement,
+ // immediately pick the face for probing
+ for (const fib::NextHop& hop : fibEntry->getNextHops()) {
+ const shared_ptr<Face>& hopFace = hop.getFace();
+
+ // Don't send probe Interest back to the incoming face or use the same face
+ // as the forwarded Interest
+ if (hopFace->getId() == inFace.getId() || hopFace->getId() == faceUsed.getId()) {
+ continue;
+ }
+
+ FaceInfo* info = m_measurements.getFaceInfo(*fibEntry, interest, *hopFace);
+
+ // If no RTT has been recorded, probe this face
+ if (info == nullptr || !info->hasSrttMeasurement()) {
+ return hopFace;
+ }
+
+ // Add FaceInfo to container sorted by RTT
+ rankedFaces.insert(std::make_pair(info, hopFace));
+ }
+
+ if (rankedFaces.empty()) {
+ // No Face to probe
+ return nullptr;
+ }
+
+ return getFaceBasedOnProbability(rankedFaces);
+}
+
+bool
+ProbingModule::isProbingNeeded(shared_ptr<fib::Entry> fibEntry, const ndn::Interest& interest)
+{
+ // Return the probing status flag for a namespace
+ NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(*fibEntry, interest);
+
+ // If a first probe has not been scheduled for a namespace
+ if (!info.isFirstProbeScheduled()) {
+ // Schedule first probe between 0 and 5 seconds
+ uint64_t interval = getRandomNumber(0, 5000);
+ scheduleProbe(fibEntry, time::milliseconds(interval));
+
+ info.setHasFirstProbeBeenScheduled(true);
+ }
+
+ return info.isProbingDue();
+}
+
+void
+ProbingModule::afterForwardingProbe(shared_ptr<fib::Entry> fibEntry, const ndn::Interest& interest)
+{
+ // After probing is done, need to set probing flag to false and
+ // schedule another future probe
+ NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(*fibEntry, interest);
+ info.setIsProbingDue(false);
+
+ scheduleProbe(fibEntry, m_probingInterval);
+}
+
+shared_ptr<Face>
+ProbingModule::getFaceBasedOnProbability(const FaceInfoFacePairSet& rankedFaces)
+{
+ double randomNumber = getRandomNumber(0, 1);
+ uint64_t rankSum = ((rankedFaces.size() + 1) * rankedFaces.size()) / 2;
+
+ uint64_t rank = 1;
+ double offset = 0.0;
+
+ for (const FaceInfoFacePair pair : rankedFaces) {
+ double probability = getProbingProbability(rank++, rankSum, rankedFaces.size());
+
+ // Is the random number within the bounds of this face's probability + the previous faces'
+ // probability?
+ //
+ // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
+ // randomNumber = 0.92
+ //
+ // The face with FaceId: 3 should be picked
+ // (0.68 < 0.5 + 0.33 + 0.17) == true
+ //
+ if (randomNumber <= offset + probability) {
+ // Found face to probe
+ return pair.second;
+ }
+
+ offset += probability;
+ }
+
+ // Given a set of Faces, this method should always select a Face to probe
+ BOOST_ASSERT(false);
+ return nullptr;
+}
+
+double
+ProbingModule::getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces)
+{
+ // p = n + 1 - j ; n: # faces
+ // ---------
+ // sum(ranks)
+ return static_cast<double>(nFaces + 1 - rank) / rankSum;
+}
+
+double
+ProbingModule::getRandomNumber(double start, double end)
+{
+ boost::random::uniform_real_distribution<double> distribution(start, end);
+ return distribution(getGlobalRng());
+}
+
+} // namespace asf
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/asf-probing-module.hpp b/daemon/fw/asf-probing-module.hpp
new file mode 100644
index 0000000..a10b1f8
--- /dev/null
+++ b/daemon/fw/asf-probing-module.hpp
@@ -0,0 +1,85 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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_DAEMON_FW_ASF_PROBING_MODULE_HPP
+#define NFD_DAEMON_FW_ASF_PROBING_MODULE_HPP
+
+#include "asf-measurements.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+/** \brief ASF Probing Module
+ */
+class ProbingModule
+{
+public:
+ explicit
+ ProbingModule(AsfMeasurements& measurements);
+
+ void
+ scheduleProbe(shared_ptr<fib::Entry> fibEntry, const time::milliseconds& interval);
+
+ shared_ptr<Face>
+ getFaceToProbe(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ const Face& faceUsed);
+
+ bool
+ isProbingNeeded(shared_ptr<fib::Entry> fibEntry, const ndn::Interest& interest);
+
+ void
+ afterForwardingProbe(shared_ptr<fib::Entry> fibEntry, const ndn::Interest& interest);
+
+private:
+ // Used to associate FaceInfo with the face in a NextHop
+ typedef std::pair<FaceInfo*, shared_ptr<Face>> FaceInfoFacePair;
+ typedef std::function<bool(FaceInfoFacePair, FaceInfoFacePair)> FaceInfoPredicate;
+ typedef std::set<FaceInfoFacePair, FaceInfoPredicate> FaceInfoFacePairSet;
+
+ shared_ptr<Face>
+ getFaceBasedOnProbability(const FaceInfoFacePairSet& rankedFaces);
+
+ double
+ getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces);
+
+ double
+ getRandomNumber(double start, double end);
+
+public:
+ static constexpr time::seconds DEFAULT_PROBING_INTERVAL = time::seconds(60);
+
+private:
+ time::seconds m_probingInterval;
+ AsfMeasurements& m_measurements;
+};
+
+} // namespace asf
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_ASF_PROBING_MODULE_HPP
diff --git a/daemon/fw/asf-strategy.cpp b/daemon/fw/asf-strategy.cpp
new file mode 100644
index 0000000..6a45c7e
--- /dev/null
+++ b/daemon/fw/asf-strategy.cpp
@@ -0,0 +1,293 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "asf-strategy.hpp"
+
+#include "core/logger.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+NFD_LOG_INIT("AsfStrategy");
+
+const Name AsfStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/asf/%FD%01");
+const time::milliseconds AsfStrategy::RETX_SUPPRESSION_INITIAL(10);
+const time::milliseconds AsfStrategy::RETX_SUPPRESSION_MAX(250);
+
+NFD_REGISTER_STRATEGY(AsfStrategy);
+
+AsfStrategy::AsfStrategy(Forwarder& forwarder, const Name& name)
+ : Strategy(forwarder, name)
+ , m_measurements(getMeasurements())
+ , m_probing(m_measurements)
+ , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
+ RetxSuppressionExponential::DEFAULT_MULTIPLIER,
+ RETX_SUPPRESSION_MAX)
+{
+}
+
+AsfStrategy::~AsfStrategy()
+{
+}
+
+void
+AsfStrategy::afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ // Should the Interest be suppressed?
+ RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
+
+ switch (suppressResult) {
+ case RetxSuppression::NEW:
+ case RetxSuppression::FORWARD:
+ break;
+ case RetxSuppression::SUPPRESS:
+ NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
+ return;
+ }
+
+ const fib::NextHopList& nexthops = fibEntry->getNextHops();
+
+ if (nexthops.size() == 0) {
+ sendNoRouteNack(inFace, interest, pitEntry);
+ this->rejectPendingInterest(pitEntry);
+ return;
+ }
+
+ const shared_ptr<Face> faceToUse = getBestFaceForForwarding(*fibEntry, interest, inFace);
+
+ if (faceToUse == nullptr) {
+ sendNoRouteNack(inFace, interest, pitEntry);
+ this->rejectPendingInterest(pitEntry);
+ return;
+ }
+
+ forwardInterest(interest, *fibEntry, pitEntry, faceToUse);
+
+ // If necessary, send probe
+ if (m_probing.isProbingNeeded(fibEntry, interest)) {
+ shared_ptr<Face> faceToProbe = m_probing.getFaceToProbe(inFace, interest, fibEntry, *faceToUse);
+
+ if (faceToProbe != nullptr) {
+ NFD_LOG_TRACE("Sending probe for " << fibEntry->getPrefix()
+ << " to FaceId: " << faceToProbe->getId());
+
+ bool wantNewNonce = true;
+ forwardInterest(interest, *fibEntry, pitEntry, faceToProbe, wantNewNonce);
+ m_probing.afterForwardingProbe(fibEntry, interest);
+ }
+ }
+}
+
+void
+AsfStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
+ const Face& inFace,
+ const Data& data)
+{
+ shared_ptr<NamespaceInfo> namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
+
+ if (namespaceInfo == nullptr) {
+ NFD_LOG_TRACE("Could not find measurements entry for " << pitEntry->getName());
+ return;
+ }
+
+ // Record the RTT between the Interest out to Data in
+ FaceInfo& faceInfo = namespaceInfo->get(inFace.getId());
+ faceInfo.recordRtt(pitEntry, inFace);
+
+ // Extend lifetime for measurements associated with Face
+ namespaceInfo->extendFaceInfoLifetime(faceInfo, inFace);
+
+ if (faceInfo.isTimeoutScheduled()) {
+ faceInfo.cancelTimeoutEvent(data.getName());
+ }
+}
+
+void
+AsfStrategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ NFD_LOG_DEBUG("Nack for " << nack.getInterest() << " from=" << inFace.getId() << ": " << nack.getReason());
+ onTimeout(pitEntry->getName(), inFace.getId());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+void
+AsfStrategy::forwardInterest(const Interest& interest,
+ const fib::Entry& fibEntry,
+ shared_ptr<pit::Entry> pitEntry,
+ shared_ptr<Face> outFace,
+ bool wantNewNonce)
+{
+ this->sendInterest(pitEntry, outFace, wantNewNonce);
+
+ FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interest, *outFace);
+
+ // Refresh measurements since Face is being used for forwarding
+ NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
+ namespaceInfo.extendFaceInfoLifetime(faceInfo, *outFace);
+
+ if (!faceInfo.isTimeoutScheduled()) {
+ // Estimate and schedule timeout
+ RttEstimator::Duration timeout = faceInfo.computeRto();
+
+ NFD_LOG_TRACE("Scheduling timeout for " << fibEntry.getPrefix()
+ << " FaceId: " << outFace->getId()
+ << " in " << time::duration_cast<time::milliseconds>(timeout) << " ms");
+
+ scheduler::EventId id = scheduler::schedule(timeout,
+ bind(&AsfStrategy::onTimeout, this, interest.getName(), outFace->getId()));
+
+ faceInfo.setTimeoutEvent(id, interest.getName());
+ }
+}
+
+struct FaceStats
+{
+ shared_ptr<Face> face;
+ RttStats::Rtt rtt;
+ RttStats::Rtt srtt;
+ uint64_t cost;
+};
+
+double
+getValueForSorting(const FaceStats& stats)
+{
+ // These values allow faces with no measurements to be ranked better than timeouts
+ // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
+ static const RttStats::Rtt SORTING_RTT_TIMEOUT = time::microseconds::max();
+ static const RttStats::Rtt SORTING_RTT_NO_MEASUREMENT = SORTING_RTT_TIMEOUT / 2;
+
+ if (stats.rtt == RttStats::RTT_TIMEOUT) {
+ return SORTING_RTT_TIMEOUT.count();
+ }
+ else if (stats.rtt == RttStats::RTT_NO_MEASUREMENT) {
+ return SORTING_RTT_NO_MEASUREMENT.count();
+ }
+ else {
+ return stats.srtt.count();
+ }
+}
+
+const shared_ptr<Face>
+AsfStrategy::getBestFaceForForwarding(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& inFace)
+{
+ NFD_LOG_TRACE("Looking for best face for " << fibEntry.getPrefix());
+
+ typedef std::function<bool(const FaceStats&, const FaceStats&)> FaceStatsPredicate;
+ typedef std::set<FaceStats, FaceStatsPredicate> FaceStatsSet;
+
+ FaceStatsSet rankedFaces(
+ [] (const FaceStats& lhs, const FaceStats& rhs) -> bool {
+ // Sort by RTT and then by cost
+ double lhsValue = getValueForSorting(lhs);
+ double rhsValue = getValueForSorting(rhs);
+
+ if (lhsValue < rhsValue) {
+ return true;
+ }
+ else if (lhsValue == rhsValue) {
+ return lhs.cost < rhs.cost;
+ }
+ else {
+ return false;
+ }
+ });
+
+ for (const fib::NextHop& hop : fibEntry.getNextHops()) {
+
+ const shared_ptr<Face>& hopFace = hop.getFace();
+
+ if (hopFace->getId() == inFace.getId()) {
+ continue;
+ }
+
+ FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, *hopFace);
+
+ if (info == nullptr) {
+ FaceStats stats = {hopFace,
+ RttStats::RTT_NO_MEASUREMENT,
+ RttStats::RTT_NO_MEASUREMENT,
+ hop.getCost()};
+
+ rankedFaces.insert(stats);
+ }
+ else {
+ FaceStats stats = {hopFace, info->getRtt(), info->getSrtt(), hop.getCost()};
+ rankedFaces.insert(stats);
+ }
+ }
+
+ FaceStatsSet::iterator it = rankedFaces.begin();
+
+ if (it != rankedFaces.end()) {
+ return it->face;
+ }
+ else {
+ return nullptr;
+ }
+}
+
+void
+AsfStrategy::onTimeout(const ndn::Name& interestName, nfd::face::FaceId faceId)
+{
+ NFD_LOG_TRACE("FaceId: " << faceId << " for " << interestName << " has timed-out");
+
+ shared_ptr<NamespaceInfo> namespaceInfo = m_measurements.getNamespaceInfo(interestName);
+
+ if (namespaceInfo == nullptr) {
+ NFD_LOG_TRACE("FibEntry for " << interestName << " has been removed since timeout scheduling");
+ return;
+ }
+
+ FaceInfoTable::iterator it = namespaceInfo->find(faceId);
+
+ if (it == namespaceInfo->end()) {
+ it = namespaceInfo->insert(faceId);
+ }
+
+ FaceInfo& faceInfo = it->second;
+ faceInfo.recordTimeout(interestName);
+}
+
+void
+AsfStrategy::sendNoRouteNack(const Face& inFace, const Interest& interest, shared_ptr<pit::Entry> pitEntry)
+{
+ NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
+
+ lp::NackHeader nackHeader;
+ nackHeader.setReason(lp::NackReason::NO_ROUTE);
+ this->sendNack(pitEntry, inFace, nackHeader);
+}
+
+} // namespace asf
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/asf-strategy.hpp b/daemon/fw/asf-strategy.hpp
new file mode 100644
index 0000000..1e028cc
--- /dev/null
+++ b/daemon/fw/asf-strategy.hpp
@@ -0,0 +1,107 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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_DAEMON_FW_ASF_STRATEGY_HPP
+#define NFD_DAEMON_FW_ASF_STRATEGY_HPP
+
+#include "asf-measurements.hpp"
+#include "asf-probing-module.hpp"
+#include "fw/retx-suppression-exponential.hpp"
+#include "fw/strategy.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+
+/** \brief Adaptive SRTT-based Forwarding Strategy
+ *
+ * \see Vince Lehman, Ashlesh Gawande, Rodrigo Aldecoa, Dmitri Krioukov, Beichuan Zhang, Lixia Zhang, and Lan Wang,
+ * "An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN,"
+ * NDN Technical Report NDN-0042, 2016. http://named-data.net/techreports.html
+ */
+class AsfStrategy : public Strategy
+{
+public:
+ explicit
+ AsfStrategy(Forwarder& forwarder, const Name& name = STRATEGY_NAME);
+
+ virtual
+ ~AsfStrategy();
+
+public: // triggers
+ virtual void
+ afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry) override;
+
+ virtual void
+ beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
+ const Face& inFace, const Data& data) override;
+
+ virtual void
+ afterReceiveNack(const Face& inFace, const lp::Nack& nack,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry) override;
+
+private:
+ void
+ forwardInterest(const Interest& interest,
+ const fib::Entry& fibEntry,
+ shared_ptr<pit::Entry> pitEntry,
+ shared_ptr<Face> outFace,
+ bool wantNewNonce = false);
+
+ const shared_ptr<Face>
+ getBestFaceForForwarding(const fib::Entry& fibEntry, const ndn::Interest& interest, const Face& inFace);
+
+ void
+ onTimeout(const ndn::Name& interestName, nfd::face::FaceId faceId);
+
+ void
+ sendNoRouteNack(const Face& inFace, const Interest& interest, shared_ptr<pit::Entry> pitEntry);
+
+public:
+ static const Name STRATEGY_NAME;
+
+private:
+ AsfMeasurements m_measurements;
+ ProbingModule m_probing;
+
+private:
+ RetxSuppressionExponential m_retxSuppression;
+
+ static const time::milliseconds RETX_SUPPRESSION_INITIAL;
+ static const time::milliseconds RETX_SUPPRESSION_MAX;
+};
+
+} // namespace asf
+
+using asf::AsfStrategy;
+
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_ASF_STRATEGY_HPP
diff --git a/tests/daemon/fw/asf-measurements.t.cpp b/tests/daemon/fw/asf-measurements.t.cpp
new file mode 100644
index 0000000..2b83004
--- /dev/null
+++ b/tests/daemon/fw/asf-measurements.t.cpp
@@ -0,0 +1,130 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "fw/asf-measurements.hpp"
+
+#include "tests/daemon/face/dummy-face.hpp"
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+namespace tests {
+
+using namespace nfd::tests;
+
+BOOST_AUTO_TEST_SUITE(Fw)
+BOOST_AUTO_TEST_SUITE(TestAsfMeasurements)
+
+BOOST_AUTO_TEST_SUITE(TestRttStats)
+
+BOOST_FIXTURE_TEST_CASE(Basic, BaseFixture)
+{
+ RttStats stats;
+
+ BOOST_CHECK_EQUAL(stats.getRtt(), RttStats::RTT_NO_MEASUREMENT);
+ BOOST_CHECK_EQUAL(stats.getSrtt(), RttStats::RTT_NO_MEASUREMENT);
+
+ // Receive Data back in 50ms
+ RttEstimator::Duration rtt(time::milliseconds(50));
+ stats.addRttMeasurement(rtt);
+
+ BOOST_CHECK_EQUAL(stats.getRtt(), rtt);
+ BOOST_CHECK_EQUAL(stats.getSrtt(), rtt);
+
+ // Receive Data back in 50ms
+ stats.addRttMeasurement(rtt);
+
+ BOOST_CHECK_EQUAL(stats.getRtt(), rtt);
+ BOOST_CHECK_EQUAL(stats.getSrtt(), rtt);
+
+ // Receive Data back with a higher RTT
+ RttEstimator::Duration higherRtt(time::milliseconds(100));
+ stats.addRttMeasurement(higherRtt);
+
+ BOOST_CHECK_EQUAL(stats.getRtt(), higherRtt);
+ BOOST_CHECK_GT(stats.getSrtt(), rtt);
+ BOOST_CHECK_LT(stats.getSrtt(), higherRtt);
+
+ // Simulate timeout
+ RttStats::Rtt previousSrtt = stats.getSrtt();
+
+ stats.recordTimeout();
+
+ BOOST_CHECK_EQUAL(stats.getRtt(), RttStats::RTT_TIMEOUT);
+ BOOST_CHECK_EQUAL(stats.getSrtt(), previousSrtt);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // TestRttStats
+
+BOOST_AUTO_TEST_SUITE(TestFaceInfo)
+
+BOOST_FIXTURE_TEST_CASE(Basic, UnitTestTimeFixture)
+{
+ FaceInfo info;
+
+ scheduler::EventId id = scheduler::schedule(time::seconds(1), []{});
+ ndn::Name interestName("/ndn/interest");
+
+ // Receive Interest and forward to next hop; should update RTO information
+ info.setTimeoutEvent(id, interestName);
+ BOOST_CHECK_EQUAL(info.isTimeoutScheduled(), true);
+
+ // If the strategy tries to schedule an RTO when one is already scheduled, throw an exception
+ BOOST_CHECK_THROW(info.setTimeoutEvent(id, interestName), FaceInfo::Error);
+
+ // Receive Data
+ shared_ptr<Interest> interest = makeInterest(interestName);
+ shared_ptr<pit::Entry> pitEntry = make_shared<pit::Entry>(*interest);
+ std::shared_ptr<DummyFace> face = make_shared<DummyFace>();
+
+ pitEntry->insertOrUpdateOutRecord(face, *interest);
+
+ RttEstimator::Duration rtt(50);
+ this->advanceClocks(time::milliseconds(5), rtt);
+
+ info.recordRtt(pitEntry, *face);
+ info.cancelTimeoutEvent(interestName);
+
+ BOOST_CHECK_EQUAL(info.getRtt(), rtt);
+ BOOST_CHECK_EQUAL(info.getSrtt(), rtt);
+
+ // Send out another Interest which times out
+ info.setTimeoutEvent(id, interestName);
+
+ info.recordTimeout(interestName);
+ BOOST_CHECK_EQUAL(info.getRtt(), RttStats::RTT_TIMEOUT);
+ BOOST_CHECK_EQUAL(info.isTimeoutScheduled(), false);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // TestFaceInfo
+
+BOOST_AUTO_TEST_SUITE_END() // TestAsfStrategy
+BOOST_AUTO_TEST_SUITE_END() // Fw
+
+} // namespace tests
+} // namespace asf
+} // namespace fw
+} // namespace nfd
diff --git a/tests/daemon/fw/asf-strategy.t.cpp b/tests/daemon/fw/asf-strategy.t.cpp
new file mode 100644
index 0000000..687b0e2
--- /dev/null
+++ b/tests/daemon/fw/asf-strategy.t.cpp
@@ -0,0 +1,190 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "fw/asf-strategy.hpp"
+
+#include "tests/test-common.hpp"
+#include "topology-tester.hpp"
+
+namespace nfd {
+namespace fw {
+namespace asf {
+namespace tests {
+
+using namespace nfd::fw::tests;
+
+BOOST_AUTO_TEST_SUITE(Fw)
+BOOST_FIXTURE_TEST_SUITE(TestAsfStrategy, UnitTestTimeFixture)
+
+class AsfGridFixture : public UnitTestTimeFixture
+{
+protected:
+ AsfGridFixture()
+ {
+ /*
+ * +---------+
+ * +----->| nodeB |<------+
+ * | +---------+ |
+ * 10ms | | 10ms
+ * v v
+ * +---------+ +---------+
+ * | nodeA | | nodeC |
+ * +---------+ +---------+
+ * ^ ^
+ * 100ms | | 100ms
+ * | +---------+ |
+ * +----->| nodeD |<------+
+ * +---------+
+ */
+
+ nodeA = topo.addForwarder("A");
+ nodeB = topo.addForwarder("B");
+ nodeC = topo.addForwarder("C");
+ nodeD = topo.addForwarder("D");
+
+ topo.setStrategy<fw::AsfStrategy>(nodeA);
+ topo.setStrategy<fw::AsfStrategy>(nodeB);
+ topo.setStrategy<fw::AsfStrategy>(nodeC);
+ topo.setStrategy<fw::AsfStrategy>(nodeD);
+
+ linkAB = topo.addLink("AB", time::milliseconds(10), {nodeA, nodeB});
+ linkAD = topo.addLink("AD", time::milliseconds(100), {nodeA, nodeD});
+ linkBC = topo.addLink("BC", time::milliseconds(10), {nodeB, nodeC});
+ linkCD = topo.addLink("CD", time::milliseconds(100), {nodeC, nodeD});
+
+ consumer = topo.addAppFace("c", nodeA);
+ producer = topo.addAppFace("p", nodeC, PRODUCER_PREFIX);
+ topo.addEchoProducer(producer->getClientFace());
+
+ // Register producer prefix on consumer node
+ topo.registerPrefix(nodeA, linkAB->getFace(nodeA), PRODUCER_PREFIX, 10);
+ topo.registerPrefix(nodeA, linkAD->getFace(nodeA), PRODUCER_PREFIX, 5);
+ }
+
+ void
+ runConsumer()
+ {
+ topo.addIntervalConsumer(consumer->getClientFace(), PRODUCER_PREFIX, time::seconds(1), 30);
+ this->advanceClocks(time::milliseconds(1), time::seconds(30));
+ }
+
+protected:
+ TopologyTester topo;
+
+ TopologyNode nodeA;
+ TopologyNode nodeB;
+ TopologyNode nodeC;
+ TopologyNode nodeD;
+
+ shared_ptr<TopologyLink> linkAB;
+ shared_ptr<TopologyLink> linkAD;
+ shared_ptr<TopologyLink> linkBC;
+ shared_ptr<TopologyLink> linkCD;
+
+ shared_ptr<TopologyAppLink> consumer;
+ shared_ptr<TopologyAppLink> producer;
+
+ static const Name PRODUCER_PREFIX;
+};
+
+const Name AsfGridFixture::PRODUCER_PREFIX = Name("ndn:/hr/C");
+
+BOOST_FIXTURE_TEST_CASE(Basic, AsfGridFixture)
+{
+ // Both nodeB and nodeD have FIB entries to reach the producer
+ topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
+ topo.registerPrefix(nodeD, linkCD->getFace(nodeD), PRODUCER_PREFIX);
+
+ runConsumer();
+
+ // ASF should use the Face to nodeD because it has lower routing cost.
+ // After 5 seconds, a probe Interest should be sent to the Face to nodeB,
+ // and the probe should return Data quicker. ASF should then use the Face
+ // to nodeB to forward the remaining Interests.
+ BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 30);
+ BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 24);
+ BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 6);
+
+ // If the link from nodeA to nodeB fails, ASF should start using the Face
+ // to nodeD again.
+ linkAB->fail();
+
+ runConsumer();
+
+ // Only 59 Data because the first Interest to nodeB after the failure should timeout
+ BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 59);
+ BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 30);
+ BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 30);
+
+ // If the link from nodeA to nodeB recovers, ASF should probe the Face
+ // to nodeB and start using it again.
+ linkAB->recover();
+
+ // Advance time to ensure probing is due
+ this->advanceClocks(time::milliseconds(1), time::seconds(10));
+
+ runConsumer();
+
+ BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 89);
+ BOOST_CHECK_GE(linkAB->getFace(nodeA).getCounters().nOutInterests, 50);
+ BOOST_CHECK_LE(linkAD->getFace(nodeA).getCounters().nOutInterests, 40);
+
+ // If both links fail, nodeA should forward to the next hop with the lowest cost
+ linkAB->fail();
+ linkAD->fail();
+
+ runConsumer();
+
+ BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 89);
+ BOOST_CHECK_LE(linkAB->getFace(nodeA).getCounters().nOutInterests, 60);
+ BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 60);
+}
+
+BOOST_FIXTURE_TEST_CASE(Nack, AsfGridFixture)
+{
+ // nodeB has a FIB entry to reach the producer, but nodeD does not
+ topo.registerPrefix(nodeB, linkBC->getFace(nodeB), PRODUCER_PREFIX);
+
+ // The strategy should first try to send to nodeD. But since nodeD does not have a route for
+ // the producer's prefix, it should return a NO_ROUTE Nack. The strategy should then start using the Face to
+ // nodeB.
+ runConsumer();
+
+ BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nInNacks, 1);
+ BOOST_CHECK_EQUAL(consumer->getForwarderFace().getCounters().nOutData, 29);
+ BOOST_CHECK_EQUAL(linkAB->getFace(nodeA).getCounters().nOutInterests, 29);
+
+ // nodeD should receive 2 Interests: one for the very first Interest and
+ // another from a probe
+ BOOST_CHECK_GE(linkAD->getFace(nodeA).getCounters().nOutInterests, 2);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // TestAsfStrategy
+BOOST_AUTO_TEST_SUITE_END() // Fw
+
+} // namespace tests
+} // namespace asf
+} // namespace fw
+} // namespace nfd