fw: access strategy
refs #1999
Change-Id: I5fc284d7ae82ed933bf5937d5c687885e73c3e0a
diff --git a/daemon/fw/access-strategy.cpp b/daemon/fw/access-strategy.cpp
new file mode 100644
index 0000000..ece5a83
--- /dev/null
+++ b/daemon/fw/access-strategy.cpp
@@ -0,0 +1,282 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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 "access-strategy.hpp"
+#include "core/logger.hpp"
+
+namespace nfd {
+namespace fw {
+
+NFD_LOG_INIT("AccessStrategy");
+
+const Name AccessStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/access/%FD%01");
+
+AccessStrategy::AccessStrategy(Forwarder& forwarder, const Name& name)
+ : Strategy(forwarder, name)
+ , m_removeFaceInfoConn(this->beforeRemoveFace.connect(
+ bind(&AccessStrategy::removeFaceInfo, this, _1)))
+{
+}
+
+AccessStrategy::~AccessStrategy()
+{
+}
+
+void
+AccessStrategy::afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ RetransmissionSuppression::Result suppressResult =
+ m_retransmissionSuppression.decide(inFace, interest, *pitEntry);
+ switch (suppressResult) {
+ case RetransmissionSuppression::NEW:
+ this->afterReceiveNewInterest(inFace, interest, fibEntry, pitEntry);
+ break;
+ case RetransmissionSuppression::FORWARD:
+ this->afterReceiveRetxInterest(inFace, interest, fibEntry, pitEntry);
+ break;
+ case RetransmissionSuppression::SUPPRESS:
+ NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-suppress");
+ break;
+ default:
+ BOOST_ASSERT(false);
+ break;
+ }
+}
+
+void
+AccessStrategy::afterReceiveNewInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ Name miName;
+ shared_ptr<MtInfo> mi;
+ std::tie(miName, mi) = this->findPrefixMeasurements(*pitEntry);
+
+ // has measurements for Interest Name?
+ if (mi != nullptr) {
+ NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
+ " new-interest mi=" << miName);
+
+ // send to last working nexthop
+ bool isSentToLastNexthop = this->sendToLastNexthop(inFace, pitEntry, *mi, fibEntry);
+
+ if (isSentToLastNexthop) {
+ return;
+ }
+ }
+ else {
+ NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
+ " new-interest no-mi");
+ }
+
+ // no measurements, or last working nexthop unavailable
+
+ // multicast to all nexthops
+ this->multicast(pitEntry, fibEntry);
+}
+
+void
+AccessStrategy::afterReceiveRetxInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-forward");
+ this->multicast(pitEntry, fibEntry, std::unordered_set<FaceId>{inFace.getId()});
+}
+
+bool
+AccessStrategy::sendToLastNexthop(const Face& inFace, shared_ptr<pit::Entry> pitEntry, MtInfo& mi,
+ shared_ptr<fib::Entry> fibEntry)
+{
+ if (mi.lastNexthop == INVALID_FACEID) {
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " no-last-nexthop");
+ return false;
+ }
+
+ if (mi.lastNexthop == inFace.getId()) {
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-is-downstream");
+ return false;
+ }
+
+ shared_ptr<Face> face = this->getFace(mi.lastNexthop);
+ if (face == nullptr || !fibEntry->hasNextHop(face)) {
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-gone");
+ return false;
+ }
+
+ if (pitEntry->violatesScope(*face)) {
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-violates-scope");
+ return false;
+ }
+
+ RttEstimator::Duration rto = mi.rtt.computeRto();
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << mi.lastNexthop <<
+ " last-nexthop rto=" << time::duration_cast<time::microseconds>(rto).count());
+
+ this->sendInterest(pitEntry, face);
+
+ // schedule RTO timeout
+ shared_ptr<PitInfo> pi = pitEntry->getOrCreateStrategyInfo<PitInfo>();
+ pi->rtoTimer = scheduler::schedule(rto,
+ bind(&AccessStrategy::afterRtoTimeout, this, weak_ptr<pit::Entry>(pitEntry),
+ weak_ptr<fib::Entry>(fibEntry), inFace.getId(), mi.lastNexthop));
+
+ return true;
+}
+
+void
+AccessStrategy::afterRtoTimeout(weak_ptr<pit::Entry> pitWeak, weak_ptr<fib::Entry> fibWeak,
+ FaceId inFace, FaceId firstOutFace)
+{
+ shared_ptr<pit::Entry> pitEntry = pitWeak.lock();
+ BOOST_ASSERT(pitEntry != nullptr);
+ // pitEntry can't become nullptr, because RTO timer should be cancelled upon pitEntry destruction
+
+ shared_ptr<fib::Entry> fibEntry = fibWeak.lock();
+ if (fibEntry == nullptr) {
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFace << " fib-gone");
+ return;
+ }
+
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFace <<
+ " multicast-except " << inFace << ',' << firstOutFace);
+ this->multicast(pitEntry, fibEntry, std::unordered_set<FaceId>{inFace, firstOutFace});
+}
+
+void
+AccessStrategy::multicast(shared_ptr<pit::Entry> pitEntry, shared_ptr<fib::Entry> fibEntry,
+ std::unordered_set<FaceId> exceptFaces)
+{
+ for (const fib::NextHop& nexthop : fibEntry->getNextHops()) {
+ shared_ptr<Face> face = nexthop.getFace();
+ if (exceptFaces.count(face->getId()) > 0) {
+ continue;
+ }
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << face->getId() <<
+ " multicast");
+ this->sendInterest(pitEntry, face);
+ }
+}
+
+void
+AccessStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
+ const Face& inFace, const Data& data)
+{
+ shared_ptr<PitInfo> pi = pitEntry->getStrategyInfo<PitInfo>();
+ if (pi != nullptr) {
+ pi->rtoTimer.cancel();
+ }
+
+ if (pitEntry->getInRecords().empty()) { // already satisfied by another upstream
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
+ " not-fastest");
+ return;
+ }
+
+ pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(inFace);
+ if (outRecord == pitEntry->getOutRecords().end()) { // no OutRecord
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
+ " no-out-record");
+ return;
+ }
+
+ time::steady_clock::Duration rtt = time::steady_clock::now() - outRecord->getLastRenewed();
+ NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
+ " rtt=" << time::duration_cast<time::microseconds>(rtt).count());
+ this->updateMeasurements(inFace, data, time::duration_cast<RttEstimator::Duration>(rtt));
+}
+
+void
+AccessStrategy::updateMeasurements(const Face& inFace, const Data& data,
+ const RttEstimator::Duration& rtt)
+{
+ FaceInfo& fi = m_fit[inFace.getId()];
+ fi.rtt.addMeasurement(rtt);
+
+ shared_ptr<MtInfo> mi = this->addPrefixMeasurements(data);
+ if (mi->lastNexthop != inFace.getId()) {
+ mi->lastNexthop = inFace.getId();
+ mi->rtt = fi.rtt;
+ }
+ else {
+ mi->rtt.addMeasurement(rtt);
+ }
+}
+
+AccessStrategy::MtInfo::MtInfo()
+ : lastNexthop(INVALID_FACEID)
+ , rtt(1, time::milliseconds(1), 0.1)
+{
+}
+
+std::tuple<Name, shared_ptr<AccessStrategy::MtInfo>>
+AccessStrategy::findPrefixMeasurements(const pit::Entry& pitEntry)
+{
+ shared_ptr<measurements::Entry> me = this->getMeasurements().findLongestPrefixMatch(pitEntry);
+ if (me == nullptr) {
+ return std::forward_as_tuple(Name(), nullptr);
+ }
+
+ shared_ptr<MtInfo> mi = me->getStrategyInfo<MtInfo>();
+ BOOST_ASSERT(mi != nullptr);
+ // XXX after runtime strategy change, it's possible that me exists but mi doesn't exist;
+ // this case needs another longest prefix match until mi is found
+ return std::forward_as_tuple(me->getName(), mi);
+}
+
+shared_ptr<AccessStrategy::MtInfo>
+AccessStrategy::addPrefixMeasurements(const Data& data)
+{
+ shared_ptr<measurements::Entry> me;
+ if (data.getName().size() >= 1) {
+ me = this->getMeasurements().get(data.getName().getPrefix(-1));
+ }
+ if (me == nullptr) { // parent of Data Name is not in this strategy, or Data Name is empty
+ me = this->getMeasurements().get(data.getName());
+ // Data Name must be in this strategy
+ BOOST_ASSERT(me != nullptr);
+ }
+
+ return me->getOrCreateStrategyInfo<MtInfo>();
+}
+
+AccessStrategy::FaceInfo::FaceInfo()
+ : rtt(1, time::milliseconds(1), 0.1)
+{
+}
+
+void
+AccessStrategy::removeFaceInfo(shared_ptr<Face> face)
+{
+ m_fit.erase(face->getId());
+}
+
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/access-strategy.hpp b/daemon/fw/access-strategy.hpp
new file mode 100644
index 0000000..7410b51
--- /dev/null
+++ b/daemon/fw/access-strategy.hpp
@@ -0,0 +1,177 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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_ACCESS_STRATEGY_HPP
+#define NFD_DAEMON_FW_ACCESS_STRATEGY_HPP
+
+#include "strategy.hpp"
+#include "rtt-estimator.hpp"
+#include "retransmission-suppression.hpp"
+#include <unordered_set>
+#include <unordered_map>
+
+namespace nfd {
+namespace fw {
+
+/** \brief Access Router Strategy version 1
+ *
+ * This strategy is designed for the last hop on the NDN testbed,
+ * where each nexthop connects to a laptop, links are lossy, and FIB is mostly correct.
+ *
+ * 1. Multicast the first Interest to all nexthops.
+ * 2. When Data comes back, remember last working nexthop of the prefix;
+ * the granularity of this knowledge is the parent of Data Name.
+ * 3. Forward subsequent Interests to the last working nexthop.
+ * If it doesn't respond, multicast again.
+ */
+class AccessStrategy : public Strategy
+{
+public:
+ AccessStrategy(Forwarder& forwarder, const Name& name = STRATEGY_NAME);
+
+ virtual
+ ~AccessStrategy();
+
+public: // triggers
+ virtual void
+ afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry) DECL_OVERRIDE;
+
+ virtual void
+ beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
+ const Face& inFace, const Data& data) DECL_OVERRIDE;
+
+private: // StrategyInfo
+ /** \brief StrategyInfo on PIT entry
+ */
+ class PitInfo : public StrategyInfo
+ {
+ public:
+ static constexpr int
+ getTypeId()
+ {
+ return 1010;
+ }
+
+ public:
+ scheduler::ScopedEventId rtoTimer;
+ };
+
+ /** \brief StrategyInfo in measurements table
+ */
+ class MtInfo : public StrategyInfo
+ {
+ public:
+ static constexpr int
+ getTypeId()
+ {
+ return 1011;
+ }
+
+ MtInfo();
+
+ public:
+ FaceId lastNexthop;
+ RttEstimator rtt;
+ };
+
+ /** \brief find per-prefix measurements for Interest
+ */
+ std::tuple<Name, shared_ptr<MtInfo>>
+ findPrefixMeasurements(const pit::Entry& pitEntry);
+
+ /** \brief get or create pre-prefix measurements for incoming Data
+ * \note This function creates MtInfo but doesn't update it.
+ */
+ shared_ptr<MtInfo>
+ addPrefixMeasurements(const Data& data);
+
+ /** \brief global per-face StrategyInfo
+ */
+ class FaceInfo
+ {
+ public:
+ FaceInfo();
+
+ public:
+ RttEstimator rtt;
+ };
+
+ typedef std::unordered_map<FaceId, FaceInfo> FaceInfoTable;
+
+ void
+ removeFaceInfo(shared_ptr<Face> face);
+
+private: // forwarding procedures
+ void
+ afterReceiveNewInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry);
+
+ void
+ afterReceiveRetxInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry);
+
+ /** \brief send to last working nexthop
+ * \return whether an Interest is sent
+ */
+ bool
+ sendToLastNexthop(const Face& inFace, shared_ptr<pit::Entry> pitEntry, MtInfo& mi,
+ shared_ptr<fib::Entry> fibEntry);
+
+ void
+ afterRtoTimeout(weak_ptr<pit::Entry> pitWeak, weak_ptr<fib::Entry> fibWeak,
+ FaceId inFace, FaceId firstOutFace);
+
+ /** \brief multicast to all nexthops
+ * \param exceptFaces don't forward to those faces
+ */
+ void
+ multicast(shared_ptr<pit::Entry> pitEntry,
+ shared_ptr<fib::Entry> fibEntry,
+ std::unordered_set<FaceId> exceptFaces = std::unordered_set<FaceId>());
+
+ void
+ updateMeasurements(const Face& inFace, const Data& data,
+ const RttEstimator::Duration& rtt);
+
+public:
+ static const Name STRATEGY_NAME;
+
+private:
+ FaceInfoTable m_fit;
+ RetransmissionSuppression m_retransmissionSuppression;
+ signal::ScopedConnection m_removeFaceInfoConn;
+};
+
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_ACCESS_STRATEGY_HPP
diff --git a/daemon/fw/available-strategies.cpp b/daemon/fw/available-strategies.cpp
index 45be270..28cab80 100644
--- a/daemon/fw/available-strategies.cpp
+++ b/daemon/fw/available-strategies.cpp
@@ -1,12 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014, 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
+ * Copyright (c) 2014-2015, 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.
@@ -28,6 +28,7 @@
#include "client-control-strategy.hpp"
#include "ncc-strategy.hpp"
#include "best-route-strategy2.hpp"
+#include "access-strategy.hpp"
namespace nfd {
namespace fw {
@@ -56,6 +57,7 @@
installStrategy<ClientControlStrategy>(forwarder);
installStrategy<NccStrategy>(forwarder);
installStrategy<BestRouteStrategy2>(forwarder);
+ installStrategy<AccessStrategy>(forwarder);
}
} // namespace fw
diff --git a/tests/daemon/fw/access-strategy.cpp b/tests/daemon/fw/access-strategy.cpp
new file mode 100644
index 0000000..934dfcd
--- /dev/null
+++ b/tests/daemon/fw/access-strategy.cpp
@@ -0,0 +1,353 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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/access-strategy.hpp"
+
+#include "tests/test-common.hpp"
+#include "topology-tester.hpp"
+
+namespace nfd {
+namespace tests {
+
+// This test suite tests AccessStrategy's behavior as a black box,
+// without accessing its internals.
+//
+// Many test assertions are qualitative rather than quantitative.
+// They capture the design highlights of the strategy without requiring a definite value,
+// so that the test suite is not fragile to minor changes in the strategy implementation.
+//
+// Topology graphes in this test suite are shown in ASCII art,
+// in a style similar to ns-3 and ndnSIM examples.
+// They are enclosed in multi-line comments, which is an intentional violation of
+// code style rule 3.25. This is necessary because some lines ends with '\' which
+// would cause "multi-line comment" compiler warning if '//' comments are used.
+
+BOOST_FIXTURE_TEST_SUITE(FwAccessStrategy, UnitTestTimeFixture)
+
+class TwoLaptopsFixture : public UnitTestTimeFixture
+{
+protected:
+ TwoLaptopsFixture()
+ {
+ /*
+ * +--------+
+ * +----->| router |<------+
+ * | +--------+ |
+ * 10ms | | 20ms
+ * v v
+ * +---------+ +---------+
+ * | laptopA | | laptopB |
+ * +---------+ +---------+
+ */
+
+ router = topo.addForwarder();
+ laptopA = topo.addForwarder();
+ laptopB = topo.addForwarder();
+
+ topo.setStrategy<fw::AccessStrategy>(router);
+
+ linkA = topo.addLink(time::milliseconds(10), {router, laptopA});
+ linkB = topo.addLink(time::milliseconds(20), {router, laptopB});
+ }
+
+protected:
+ TopologyTester topo;
+
+ TopologyNode router;
+ TopologyNode laptopA;
+ TopologyNode laptopB;
+ shared_ptr<TopologyLink> linkA;
+ shared_ptr<TopologyLink> linkB;
+};
+
+BOOST_FIXTURE_TEST_CASE(OneProducer, TwoLaptopsFixture)
+{
+ /*
+ * /------------------\
+ * | intervalConsumer |
+ * \------------------/
+ * ^ v
+ * | v /laptops/A
+ * |
+ * v
+ * /laptops << +--------+ >> /laptops
+ * +----->| router |<------+
+ * | +--------+ |
+ * 10ms | | 20ms
+ * v v
+ * +---------+ +---------+
+ * | laptopA | | laptopB |
+ * +---------+ +---------+
+ * ^ v
+ * | v /laptops/A
+ * v
+ * /--------------\
+ * | echoProducer |
+ * \--------------/
+ */
+
+ // two laptops have same prefix in router FIB
+ topo.registerPrefix(router, linkA->getFace(router), "ndn:/laptops");
+ topo.registerPrefix(router, linkB->getFace(router), "ndn:/laptops");
+
+ shared_ptr<TopologyAppLink> producer = topo.addAppFace(laptopA, "ndn:/laptops/A");
+ topo.addEchoProducer(*producer->getClientFace());
+
+ shared_ptr<TopologyAppLink> consumer = topo.addAppFace(router);
+ topo.addIntervalConsumer(*consumer->getClientFace(), "ndn:/laptops/A",
+ time::milliseconds(100), 100);
+
+ this->advanceClocks(time::milliseconds(5), time::seconds(12));
+
+ // most Interests should be satisfied, and few Interests can go to wrong laptop
+ BOOST_CHECK_GE(consumer->getForwarderFace()->m_sentDatas.size(), 97);
+ BOOST_CHECK_GE(linkA->getFace(router)->m_sentInterests.size(), 97);
+ BOOST_CHECK_LE(linkB->getFace(router)->m_sentInterests.size(), 5);
+}
+
+BOOST_FIXTURE_TEST_CASE(FastSlowProducer, TwoLaptopsFixture)
+{
+ /*
+ * /------------------\
+ * | intervalConsumer |
+ * \------------------/
+ * ^ v
+ * | v /laptops/BOTH
+ * |
+ * v
+ * /laptops << +--------+ >> /laptops
+ * +----->| router |<------+
+ * | +--------+ |
+ * 10ms | | 20ms
+ * v v
+ * +---------+ +---------+
+ * | laptopA | | laptopB |
+ * +---------+ +---------+
+ * ^ v ^ v
+ * | v /laptops/BOTH | v /laptops/BOTH
+ * v v
+ * /--------------\ /--------------\
+ * | echoProducer | | echoProducer |
+ * \--------------/ \--------------/
+ */
+
+ // two laptops have same prefix in router FIB
+ topo.registerPrefix(router, linkA->getFace(router), "ndn:/laptops");
+ topo.registerPrefix(router, linkB->getFace(router), "ndn:/laptops");
+
+ shared_ptr<TopologyAppLink> producerA = topo.addAppFace(laptopA, "ndn:/laptops/BOTH");
+ topo.addEchoProducer(*producerA->getClientFace());
+ shared_ptr<TopologyAppLink> producerB = topo.addAppFace(laptopB, "ndn:/laptops/BOTH");
+ topo.addEchoProducer(*producerB->getClientFace());
+
+ shared_ptr<TopologyAppLink> consumer = topo.addAppFace(router);
+ topo.addIntervalConsumer(*consumer->getClientFace(), "ndn:/laptops/BOTH",
+ time::milliseconds(100), 100);
+
+ this->advanceClocks(time::milliseconds(5), time::seconds(12));
+
+ // most Interests should be satisfied, and few Interests can go to slower laptopB
+ BOOST_CHECK_GE(consumer->getForwarderFace()->m_sentDatas.size(), 97);
+ BOOST_CHECK_GE(linkA->getFace(router)->m_sentInterests.size(), 90);
+ BOOST_CHECK_LE(linkB->getFace(router)->m_sentInterests.size(), 15);
+}
+
+BOOST_FIXTURE_TEST_CASE(ProducerMobility, TwoLaptopsFixture)
+{
+ /*
+ * /------------------\ /------------------\
+ * | intervalConsumer | | intervalConsumer |
+ * \------------------/ A \------------------/
+ * ^ v f ^ v
+ * | v /laptops/M t | v /laptops/M
+ * | e |
+ * v r v
+ * /laptops << +--------+ >> /laptops /laptops << +--------+ >> /laptops
+ * +----->| router |<------+ 6 +----->| router |<------+
+ * | +--------+ | | +--------+ |
+ * 10ms | | 20ms === s ==> 10ms | | 20ms
+ * v v e v v
+ * +---------+ +---------+ c +---------+ +---------+
+ * | laptopA | | laptopB | o | laptopA | | laptopB |
+ * +---------+ +---------+ n +---------+ +---------+
+ * ^ v d v ^
+ * | v /laptops/M s /laptops/M v |
+ * v v
+ * /--------------\ /--------------\
+ * | echoProducer | | echoProducer |
+ * \--------------/ \--------------/
+ */
+
+ // two laptops have same prefix in router FIB
+ topo.registerPrefix(router, linkA->getFace(router), "ndn:/laptops");
+ topo.registerPrefix(router, linkB->getFace(router), "ndn:/laptops");
+
+ shared_ptr<TopologyAppLink> producerA = topo.addAppFace(laptopA, "ndn:/laptops/M");
+ topo.addEchoProducer(*producerA->getClientFace());
+ shared_ptr<TopologyAppLink> producerB = topo.addAppFace(laptopB, "ndn:/laptops/M");
+ topo.addEchoProducer(*producerB->getClientFace());
+
+ shared_ptr<TopologyAppLink> consumer = topo.addAppFace(router);
+ topo.addIntervalConsumer(*consumer->getClientFace(), "ndn:/laptops/M",
+ time::milliseconds(100), 100);
+
+ // producer is initially on laptopA
+ producerB->fail();
+ this->advanceClocks(time::milliseconds(5), time::seconds(6));
+
+ // few Interests can go to laptopB
+ BOOST_CHECK_LE(linkB->getFace(router)->m_sentInterests.size(), 5);
+
+ // producer moves to laptopB
+ producerA->fail();
+ producerB->recover();
+ linkA->getFace(router)->m_sentInterests.clear();
+ this->advanceClocks(time::milliseconds(5), time::seconds(6));
+
+ // few additional Interests can go to laptopA
+ BOOST_CHECK_LE(linkA->getFace(router)->m_sentInterests.size(), 5);
+
+ // most Interests should be satisfied
+ BOOST_CHECK_GE(consumer->getForwarderFace()->m_sentDatas.size(), 97);
+}
+
+BOOST_FIXTURE_TEST_CASE(Bidirectional, TwoLaptopsFixture)
+{
+ /*
+ * /laptops << +--------+ >> /laptops
+ * +----->| router |<------+
+ * | +--------+ |
+ * ^ 10ms | | 20ms ^
+ * / ^ v v ^ /
+ * +---------+ +---------+
+ * +----->| laptopA | | laptopB |<------------+
+ * | +---------+ +---------+ |
+ * | ^ v /laptops/A ^ v /laptops/B |
+ * ^ | | v | v | ^
+ * /laptops/B ^ v v v v ^ /laptops/A
+ * /------------------\ /--------------\ /--------------\ /------------------\
+ * | intervalConsumer | | echoProducer | | echoProducer | | intervalConsumer |
+ * \------------------/ \--------------/ \--------------/ \------------------/
+ */
+
+ // laptops have default routes toward the router
+ topo.registerPrefix(laptopA, linkA->getFace(laptopA), "ndn:/");
+ topo.registerPrefix(laptopB, linkB->getFace(laptopB), "ndn:/");
+
+ // two laptops have same prefix in router FIB
+ topo.registerPrefix(router, linkA->getFace(router), "ndn:/laptops");
+ topo.registerPrefix(router, linkB->getFace(router), "ndn:/laptops");
+
+ shared_ptr<TopologyAppLink> producerA = topo.addAppFace(laptopA, "ndn:/laptops/A");
+ topo.addEchoProducer(*producerA->getClientFace());
+ shared_ptr<TopologyAppLink> producerB = topo.addAppFace(laptopB, "ndn:/laptops/B");
+ topo.addEchoProducer(*producerB->getClientFace());
+
+ shared_ptr<TopologyAppLink> consumerAB = topo.addAppFace(laptopA);
+ topo.addIntervalConsumer(*consumerAB->getClientFace(), "ndn:/laptops/B",
+ time::milliseconds(100), 100);
+ shared_ptr<TopologyAppLink> consumerBA = topo.addAppFace(laptopB);
+ topo.addIntervalConsumer(*consumerBA->getClientFace(), "ndn:/laptops/A",
+ time::milliseconds(100), 100);
+
+ this->advanceClocks(time::milliseconds(5), time::seconds(12));
+
+ // most Interests should be satisfied
+ BOOST_CHECK_GE(consumerAB->getForwarderFace()->m_sentDatas.size(), 97);
+ BOOST_CHECK_GE(consumerBA->getForwarderFace()->m_sentDatas.size(), 97);
+}
+
+BOOST_FIXTURE_TEST_CASE(PacketLoss, TwoLaptopsFixture)
+{
+ /*
+ * test case Interests
+ * |
+ * v
+ * +--------+
+ * | router |
+ * +--------+
+ * | v
+ * 10ms | v /laptops
+ * v
+ * +---------+
+ * | laptopA |
+ * +---------+
+ * ^ v
+ * | v /laptops/A
+ * v
+ * /--------------\
+ * | echoProducer |
+ * \--------------/
+ */
+
+ // laptopA has prefix in router FIB; laptopB is unused in this test case
+ topo.registerPrefix(router, linkA->getFace(router), "ndn:/laptops");
+
+ shared_ptr<TopologyAppLink> producerA = topo.addAppFace(laptopA, "ndn:/laptops/A");
+ topo.addEchoProducer(*producerA->getClientFace());
+
+ shared_ptr<TopologyAppLink> consumer = topo.addAppFace(router);
+
+ // Interest 1 completes normally
+ shared_ptr<Interest> interest1 = makeInterest("ndn:/laptops/A/1");
+ bool hasData1 = false;
+ consumer->getClientFace()->expressInterest(*interest1,
+ bind([&hasData1] { hasData1 = true; }));
+ this->advanceClocks(time::milliseconds(5), time::seconds(1));
+ BOOST_CHECK_EQUAL(hasData1, true);
+
+ // Interest 2 experiences a packet loss on initial transmission
+ shared_ptr<Interest> interest2a = makeInterest("ndn:/laptops/A/2");
+ bool hasData2a = false, hasTimeout2a = false;
+ consumer->getClientFace()->expressInterest(*interest2a,
+ bind([&hasData2a] { hasData2a = true; }),
+ bind([&hasTimeout2a] { hasTimeout2a = true; }));
+ producerA->fail();
+ this->advanceClocks(time::milliseconds(5), time::milliseconds(60));
+ BOOST_CHECK_EQUAL(hasData2a, false);
+ BOOST_CHECK_EQUAL(hasTimeout2a, false);
+
+ // Interest 2 retransmission is suppressed
+ shared_ptr<Interest> interest2b = makeInterest("ndn:/laptops/A/2");
+ bool hasData2b = false;
+ consumer->getClientFace()->expressInterest(*interest2b,
+ bind([&hasData2b] { hasData2b = true; }));
+ producerA->recover();
+ this->advanceClocks(time::milliseconds(5), time::seconds(1));
+ BOOST_CHECK_EQUAL(hasData2b, false);
+
+ // Interest 2 retransmission gets through, and is answered
+ shared_ptr<Interest> interest2c = makeInterest("ndn:/laptops/A/2");
+ bool hasData2c = false;
+ consumer->getClientFace()->expressInterest(*interest2c,
+ bind([&hasData2c] { hasData2c = true; }));
+ this->advanceClocks(time::milliseconds(5), time::seconds(1));
+ BOOST_CHECK_EQUAL(hasData2c, true);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/fw/topology-tester.hpp b/tests/daemon/fw/topology-tester.hpp
new file mode 100644
index 0000000..f343738
--- /dev/null
+++ b/tests/daemon/fw/topology-tester.hpp
@@ -0,0 +1,366 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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/>.
+ */
+
+/** \file
+ * \brief allows testing forwarding in a network topology
+ */
+
+#ifndef NFD_TESTS_NFD_FW_TOPOLOGY_TESTER_HPP
+#define NFD_TESTS_NFD_FW_TOPOLOGY_TESTER_HPP
+
+#include <unordered_map>
+#include <ndn-cxx/util/dummy-client-face.hpp>
+#include "fw/strategy.hpp"
+#include "tests/test-common.hpp"
+#include "../face/dummy-face.hpp"
+
+namespace nfd {
+namespace tests {
+
+using ndn::util::DummyClientFace;
+
+/** \brief identifies a node (forwarder) in the topology
+ */
+typedef size_t TopologyNode;
+
+/** \brief represents a network or local-app link
+ */
+class TopologyLinkBase : noncopyable
+{
+public:
+ TopologyLinkBase()
+ : m_isUp(true)
+ {
+ }
+
+ /** \brief fail the link, cause packets to be dropped silently
+ */
+ void
+ fail()
+ {
+ m_isUp = false;
+ }
+
+ /** \brief recover the link from a failure
+ */
+ void
+ recover()
+ {
+ m_isUp = true;
+ }
+
+protected:
+ bool m_isUp;
+};
+
+/** \brief represents a network link in the topology which connects two or more nodes
+ */
+class TopologyLink : public TopologyLinkBase
+{
+public:
+ /** \return a face of forwarder \p i which is attached to this link
+ */
+ shared_ptr<DummyFace>
+ getFace(TopologyNode i)
+ {
+ return m_faces.at(i)->face;
+ }
+
+private:
+ explicit
+ TopologyLink(const time::nanoseconds& delay)
+ : m_delay(delay)
+ {
+ BOOST_ASSERT(delay >= time::nanoseconds::zero());
+ }
+
+ struct LinkFace
+ {
+ shared_ptr<DummyFace> face;
+ };
+
+ void
+ addFace(TopologyNode i, shared_ptr<DummyFace> face)
+ {
+ BOOST_ASSERT(m_faces.count(i) == 0);
+
+ LinkFace* lf = new LinkFace();
+ lf->face = face;
+ face->onSendInterest.connect(bind(&TopologyLink::transmitInterest, this, i, _1));
+ face->onSendData.connect(bind(&TopologyLink::transmitData, this, i, _1));
+
+ m_faces[i].reset(lf);
+ }
+
+ friend class TopologyTester;
+
+private:
+ void
+ transmitInterest(TopologyNode i, const Interest& interest)
+ {
+ if (!m_isUp) {
+ return;
+ }
+
+ // Interest object cannot be shared between faces because
+ // Forwarder can set different IncomingFaceId.
+ Block wire = interest.wireEncode();
+ for (auto&& p : m_faces) {
+ if (p.first == i) {
+ continue;
+ }
+ shared_ptr<DummyFace> face = p.second->face;
+ scheduler::schedule(m_delay, [wire, face] {
+ auto interest = make_shared<Interest>(wire);
+ face->receiveInterest(*interest);
+ });
+ }
+ }
+
+ void
+ transmitData(TopologyNode i, const Data& data)
+ {
+ if (!m_isUp) {
+ return;
+ }
+
+ // Data object cannot be shared between faces because
+ // Forwarder can set different IncomingFaceId.
+ Block wire = data.wireEncode();
+ for (auto&& p : m_faces) {
+ if (p.first == i) {
+ continue;
+ }
+ shared_ptr<DummyFace> face = p.second->face;
+ scheduler::schedule(m_delay, [wire, face] {
+ auto data = make_shared<Data>(wire);
+ face->receiveData(*data);
+ });
+ }
+ }
+
+private:
+ time::nanoseconds m_delay;
+ std::unordered_map<TopologyNode, unique_ptr<LinkFace>> m_faces;
+};
+
+/** \brief represents a link to a local application
+ */
+class TopologyAppLink : public TopologyLinkBase
+{
+public:
+ /** \return face on forwarder side
+ */
+ shared_ptr<DummyLocalFace>
+ getForwarderFace()
+ {
+ return m_face;
+ }
+
+ /** \return face on application side
+ */
+ shared_ptr<DummyClientFace>
+ getClientFace()
+ {
+ return m_client;
+ }
+
+private:
+ explicit
+ TopologyAppLink(shared_ptr<DummyLocalFace> face)
+ : m_face(face)
+ , m_client(ndn::util::makeDummyClientFace(getGlobalIoService(), {false, false}))
+ {
+ m_client->onSendInterest.connect([this] (const Interest& interest) {
+ if (!m_isUp) {
+ return;
+ }
+ auto interest2 = interest.shared_from_this();
+ getGlobalIoService().post([=] { m_face->receiveInterest(*interest2); });
+ });
+
+ m_client->onSendData.connect([this] (const Data& data) {
+ if (!m_isUp) {
+ return;
+ }
+ auto data2 = data.shared_from_this();
+ getGlobalIoService().post([=] { m_face->receiveData(*data2); });
+ });
+
+ m_face->onSendInterest.connect([this] (const Interest& interest) {
+ if (!m_isUp) {
+ return;
+ }
+ auto interest2 = interest.shared_from_this();
+ getGlobalIoService().post([=] { m_client->receive(*interest2); });
+ });
+
+ m_face->onSendData.connect([this] (const Data& data) {
+ if (!m_isUp) {
+ return;
+ }
+ auto data2 = data.shared_from_this();
+ getGlobalIoService().post([=] { m_client->receive(*data2); });
+ });
+ }
+
+ friend class TopologyTester;
+
+private:
+ shared_ptr<DummyLocalFace> m_face;
+ shared_ptr<DummyClientFace> m_client;
+};
+
+/** \brief builds a topology for forwarding tests
+ */
+class TopologyTester : noncopyable
+{
+public:
+ /** \brief creates a forwarder
+ * \return index of new forwarder
+ */
+ TopologyNode
+ addForwarder()
+ {
+ size_t i = m_forwarders.size();
+ m_forwarders.push_back(std::move(unique_ptr<Forwarder>(new Forwarder())));
+ return i;
+ }
+
+ /** \return forwarder instance \p i
+ */
+ Forwarder&
+ getForwarder(TopologyNode i)
+ {
+ return *m_forwarders.at(i);
+ }
+
+ /** \brief sets strategy on forwarder \p i
+ * \tparam the strategy type
+ * \note Test scenario can also access StrategyChoice table directly.
+ */
+ template<typename S>
+ void
+ setStrategy(TopologyNode i, Name prefix = Name("ndn:/"))
+ {
+ Forwarder& forwarder = this->getForwarder(i);
+ StrategyChoice& strategyChoice = forwarder.getStrategyChoice();
+ shared_ptr<S> strategy = make_shared<S>(ref(forwarder));
+ strategyChoice.install(strategy);
+ strategyChoice.insert(prefix, strategy->getName());
+ }
+
+ /** \brief makes a link that interconnects two or more forwarders
+ *
+ * A face is created on each of \p forwarders .
+ * When a packet is sent onto one of the faces on this link,
+ * this packet will be received by all other faces on this link after \p delay .
+ */
+ shared_ptr<TopologyLink>
+ addLink(const time::nanoseconds& delay, std::initializer_list<TopologyNode> forwarders)
+ {
+ auto link = shared_ptr<TopologyLink>(new TopologyLink(delay));
+ for (TopologyNode i : forwarders) {
+ Forwarder& forwarder = this->getForwarder(i);
+ shared_ptr<DummyFace> face = make_shared<DummyFace>();
+ forwarder.addFace(face);
+ link->addFace(i, face);
+ }
+ return link;
+ }
+
+ /** \brief makes a link to local application
+ */
+ shared_ptr<TopologyAppLink>
+ addAppFace(TopologyNode i)
+ {
+ Forwarder& forwarder = this->getForwarder(i);
+ auto face = make_shared<DummyLocalFace>();
+ forwarder.addFace(face);
+
+ return shared_ptr<TopologyAppLink>(new TopologyAppLink(face));
+ }
+
+ /** \brief makes a link to local application, and register a prefix
+ */
+ shared_ptr<TopologyAppLink>
+ addAppFace(TopologyNode i, const Name& prefix, uint64_t cost = 0)
+ {
+ shared_ptr<TopologyAppLink> al = this->addAppFace(i);
+ this->registerPrefix(i, al->getForwarderFace(), prefix, cost);
+ return al;
+ }
+
+ /** \brief registers a prefix on a face
+ * \tparam F either DummyFace or DummyLocalFace
+ */
+ template<typename F>
+ void
+ registerPrefix(TopologyNode i, shared_ptr<F> face, const Name& prefix, uint64_t cost = 0)
+ {
+ Forwarder& forwarder = this->getForwarder(i);
+ Fib& fib = forwarder.getFib();
+ shared_ptr<fib::Entry> fibEntry = fib.insert(prefix).first;
+ fibEntry->addNextHop(face, cost);
+ }
+
+ /** \brief creates a producer application that answers every Interest with Data of same Name
+ */
+ void
+ addEchoProducer(DummyClientFace& face, const Name& prefix = "/")
+ {
+ face.setInterestFilter(prefix,
+ [&face] (const ndn::InterestFilter&, const Interest& interest) {
+ shared_ptr<Data> data = makeData(interest.getName());
+ face.put(*data);
+ });
+ }
+
+ /** \brief creates a consumer application that sends \p n Interests under \p prefix
+ * at \p interval fixed rate.
+ */
+ void
+ addIntervalConsumer(DummyClientFace& face, const Name& prefix,
+ const time::nanoseconds& interval, size_t n)
+ {
+ Name name(prefix);
+ name.appendTimestamp();
+ shared_ptr<Interest> interest = makeInterest(name);
+ face.expressInterest(*interest, bind([]{}));
+
+ if (n > 1) {
+ scheduler::schedule(interval, bind(&TopologyTester::addIntervalConsumer, this,
+ ref(face), prefix, interval, n - 1));
+ }
+ }
+
+private:
+ std::vector<unique_ptr<Forwarder>> m_forwarders;
+};
+
+} // namespace tests
+} // namespace nfd
+
+#endif // NFD_TESTS_NFD_FW_TOPOLOGY_TESTER_HPP