fw: basic forwarding procedure & strategy skeleton
refs #1131 #1136
Change-Id: I3e97cb17bf85082b6499a310120409379f8eaa65
diff --git a/daemon/fw/best-route-strategy.cpp b/daemon/fw/best-route-strategy.cpp
new file mode 100644
index 0000000..12db744
--- /dev/null
+++ b/daemon/fw/best-route-strategy.cpp
@@ -0,0 +1,37 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "best-route-strategy.hpp"
+
+namespace nfd {
+
+BestRouteStrategy::BestRouteStrategy(Forwarder& fw)
+ : Strategy(fw)
+{
+}
+
+BestRouteStrategy::~BestRouteStrategy()
+{
+}
+
+void
+BestRouteStrategy::afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry,
+ pit::InRecordCollection::iterator pitInRecord)
+{
+ const fib::NextHopList& nexthops = fibEntry->getNextHops();
+ if (nexthops.size() == 0) {
+ this->rebuffPendingInterest(pitEntry);
+ return;
+ }
+
+ shared_ptr<Face> outFace = nexthops.begin()->getFace();
+ this->sendInterest(pitEntry, outFace);
+}
+
+} // namespace nfd
diff --git a/daemon/fw/best-route-strategy.hpp b/daemon/fw/best-route-strategy.hpp
new file mode 100644
index 0000000..8e9f127
--- /dev/null
+++ b/daemon/fw/best-route-strategy.hpp
@@ -0,0 +1,38 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NFD_FW_BEST_ROUTE_STRATEGY_HPP
+#define NFD_FW_BEST_ROUTE_STRATEGY_HPP
+
+#include "strategy.hpp"
+
+namespace nfd {
+
+/** \class BestRouteStrategy
+ * \brief a forwarding strategy that forwards Interest
+ * to the first nexthop
+ */
+class BestRouteStrategy : public Strategy
+{
+public:
+ explicit
+ BestRouteStrategy(Forwarder& fw);
+
+ virtual
+ ~BestRouteStrategy();
+
+ virtual void
+ afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry,
+ pit::InRecordCollection::iterator pitInRecord
+ );
+};
+
+} // namespace nfd
+
+#endif // NFD_FW_BEST_ROUTE_STRATEGY_HPP
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 15881e3..1ba6808 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -9,6 +9,7 @@
namespace nfd {
Forwarder::Forwarder(boost::asio::io_service& ioService)
+ : m_scheduler(ioService)
{
}
@@ -26,11 +27,227 @@
void
Forwarder::onInterest(const Face& face, const Interest& interest)
{
+ this->onIncomingInterest(const_cast<Face&>(face), interest);
}
void
Forwarder::onData(const Face& face, const Data& data)
{
+ this->onIncomingData(const_cast<Face&>(face), data);
}
+void
+Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
+{
+ // receive Interest
+
+ // PIT insert
+ std::pair<shared_ptr<pit::Entry>, bool>
+ pitInsertResult = m_pit.insert(interest);
+ shared_ptr<pit::Entry> pitEntry = pitInsertResult.first;
+
+ // detect loop and record Nonce
+ bool isLoop = ! pitEntry->addNonce(interest.getNonce());
+ if (isLoop) {
+ // goto Interest loop pipeline
+ this->onInterestLoop(inFace, interest, pitEntry);
+ return;
+ }
+
+ // cancel unsatisfy & straggler timer
+ this->cancelUnsatisfyAndStragglerTimer(pitEntry);
+
+ const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+ bool isPending = inRecords.begin() == inRecords.end();
+
+ if (!isPending) {
+ // CS lookup
+ const Data* csMatch = m_cs.find(interest);
+ if (csMatch != 0) {
+ // XXX should we lookup PIT for other Interests that also match csMatch?
+
+ // goto outgoing Data pipeline
+ this->onOutgoingData(*csMatch, inFace);
+ return;
+ }
+ }
+
+ // insert InRecord
+ pit::InRecordCollection::iterator inRecordIt =
+ pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
+
+ // app chosen nexthops
+ bool isAppChosenNexthops = false; // TODO get from local control header
+ if (isAppChosenNexthops) {
+ // TODO foreach chosen nexthop: goto outgoing Interest pipeline
+ return;
+ }
+
+ // FIB lookup
+ shared_ptr<fib::Entry> fibEntry
+ = m_fib.findLongestPrefixMatch(interest.getName());
+ // TODO use Fib::findParent(pitEntry)
+
+ // dispatch to strategy
+ // TODO
+}
+
+void
+Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
+ shared_ptr<pit::Entry> pitEntry)
+{
+ // do nothing, which means Interest is dropped
+}
+
+void
+Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
+{
+ // pick Interest
+ const Interest& interest = pitEntry->getInterest();
+ // TODO pick the last incoming Interest
+
+ // insert OutRecord
+ pit::OutRecordCollection::iterator outRecordIt =
+ pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
+
+ // set PIT unsatisfy timer
+ this->setUnsatisfyTimer(pitEntry);
+
+ // send Interest
+ outFace.sendInterest(interest);
+}
+
+void
+Forwarder::onInterestRebuff(shared_ptr<pit::Entry> pitEntry)
+{
+ // set PIT straggler timer
+ this->setStragglerTimer(pitEntry);
+}
+
+void
+Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
+{
+ // invoke PIT unsatisfied callback
+ // TODO
+
+ // PIT delete
+ m_pit.remove(pitEntry);
+}
+
+void
+Forwarder::onIncomingData(Face& inFace, const Data& data)
+{
+ // receive Data
+
+ // PIT match
+ shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
+ if (pitMatches->begin() == pitMatches->end()) {
+ // goto Data unsolicited pipeline
+ this->onDataUnsolicited(inFace, data);
+ return;
+ }
+
+ // CS insert
+ m_cs.insert(data);
+
+ std::set<shared_ptr<Face> > pendingDownstreams;
+ // foreach PitEntry
+ for (pit::DataMatchResult::iterator it = pitMatches->begin();
+ it != pitMatches->end(); ++it) {
+ shared_ptr<pit::Entry> pitEntry = *it;
+
+ // cancel unsatisfy & straggler timer
+ this->cancelUnsatisfyAndStragglerTimer(pitEntry);
+
+ // remember pending downstreams
+ const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+ for (pit::InRecordCollection::const_iterator it = inRecords.begin();
+ it != inRecords.end(); ++it) {
+ if (it->getExpiry() > time::now()) {
+ pendingDownstreams.insert(it->getFace());
+ }
+ }
+
+ // mark PIT satisfied
+ pitEntry->deleteInRecords();
+ pitEntry->deleteOutRecord(inFace.shared_from_this());
+
+ // set PIT straggler timer
+ this->setStragglerTimer(pitEntry);
+
+ // invoke PIT satisfy callback
+ // TODO
+ }
+
+ // foreach pending downstream
+ for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
+ it != pendingDownstreams.end(); ++it) {
+ // goto outgoing Data pipeline
+ this->onOutgoingData(data, **it);
+ }
+}
+
+void
+Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
+{
+ // accept to cache?
+ bool acceptToCache = false;// TODO decision
+ if (acceptToCache) {
+ // CS insert
+ m_cs.insert(data);
+ }
+}
+
+void
+Forwarder::onOutgoingData(const Data& data, Face& outFace)
+{
+ // traffic manager
+ // pass through
+
+ // send Data
+ outFace.sendData(data);
+}
+
+static inline bool
+compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
+{
+ return a.getExpiry() < b.getExpiry();
+}
+
+void
+Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
+{
+ const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+ pit::InRecordCollection::const_iterator lastExpiring =
+ std::max_element(inRecords.begin(), inRecords.end(),
+ &compare_InRecord_expiry);
+
+ time::Point lastExpiry = lastExpiring->getExpiry();
+ time::Duration lastExpiryFromNow = lastExpiry - time::now();
+ if (lastExpiryFromNow <= time::seconds(0)) {
+ // TODO all InRecords are already expired; will this happen?
+ }
+
+ pitEntry->m_unsatisfyTimer = m_scheduler.scheduleEvent(lastExpiryFromNow,
+ bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
+}
+
+void
+Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+{
+ time::Duration stragglerTime = time::milliseconds(100);
+
+ pitEntry->m_stragglerTimer = m_scheduler.scheduleEvent(stragglerTime,
+ bind(&Pit::remove, &m_pit, pitEntry));
+}
+
+void
+Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+{
+ m_scheduler.cancelEvent(pitEntry->m_unsatisfyTimer);
+ m_scheduler.cancelEvent(pitEntry->m_stragglerTimer);
+}
+
+
+
} // namespace nfd
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 6395f29..591254e 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -8,7 +8,11 @@
#define NFD_FW_FORWARDER_HPP
#include "common.hpp"
+#include "core/scheduler.hpp"
#include "face/face.hpp"
+#include "table/fib.hpp"
+#include "table/pit.hpp"
+#include "table/cs.hpp"
namespace nfd {
@@ -34,10 +38,69 @@
void
onData(const Face& face, const Data& data);
+private: // pipelines
+ /** \brief incoming Interest pipeline
+ */
+ void
+ onIncomingInterest(Face& inFace, const Interest& interest);
+
+ /** \brief Interest loop pipeline
+ */
+ void
+ onInterestLoop(Face& inFace, const Interest& interest,
+ shared_ptr<pit::Entry> pitEntry);
+
+ /** \brief outgoing Interest pipeline
+ */
+ void
+ onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace);
+
+ /** \brief Interest rebuff pipeline
+ */
+ void
+ onInterestRebuff(shared_ptr<pit::Entry> pitEntry);
+
+ /** \brief Interest unsatisfied pipeline
+ */
+ void
+ onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry);
+
+ /** \brief incoming Data pipeline
+ */
+ void
+ onIncomingData(Face& inFace, const Data& data);
+
+ /** \brief Data unsolicited pipeline
+ */
+ void
+ onDataUnsolicited(Face& inFace, const Data& data);
+
+ /** \brief outgoing Data pipeline
+ */
+ void
+ onOutgoingData(const Data& data, Face& outFace);
+
private:
+ void
+ setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry);
+
+ void
+ setStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+
+ void
+ cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+
+private:
+ Scheduler m_scheduler;
+ Fib m_fib;
+ Pit m_pit;
+ Cs m_cs;
// container< shared_ptr<Face> > m_faces;
+
+ // allow Strategy (base class) to enter pipelines
+ friend class Strategy;
};
-}
+} // namespace nfd
#endif // NFD_FW_FORWARDER_HPP
diff --git a/daemon/fw/strategy.cpp b/daemon/fw/strategy.cpp
new file mode 100644
index 0000000..ed1233f
--- /dev/null
+++ b/daemon/fw/strategy.cpp
@@ -0,0 +1,34 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "strategy.hpp"
+
+namespace nfd {
+
+Strategy::Strategy(Forwarder& fw)
+ : m_fw(fw)
+{
+}
+
+Strategy::~Strategy()
+{
+}
+
+
+void
+Strategy::sendInterest(shared_ptr<pit::Entry> pitEntry,
+ shared_ptr<Face> outFace)
+{
+ m_fw.onOutgoingInterest(pitEntry, *outFace);
+}
+
+void
+Strategy::rebuffPendingInterest(shared_ptr<pit::Entry> pitEntry)
+{
+ m_fw.onInterestRebuff(pitEntry);
+}
+
+} // namespace nfd
diff --git a/daemon/fw/strategy.hpp b/daemon/fw/strategy.hpp
new file mode 100644
index 0000000..1a6e47f
--- /dev/null
+++ b/daemon/fw/strategy.hpp
@@ -0,0 +1,65 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NFD_FW_STRATEGY_HPP
+#define NFD_FW_STRATEGY_HPP
+
+#include "forwarder.hpp"
+
+namespace nfd {
+
+/** \class Strategy
+ * \brief represents a forwarding strategy
+ */
+class Strategy
+{
+public:
+ explicit
+ Strategy(Forwarder& fw);
+
+ virtual
+ ~Strategy();
+
+ virtual void
+ afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry,
+ pit::InRecordCollection::iterator pitInRecord
+ ) =0;
+
+ //virtual void
+ //beforeExpirePendingInterest() =0;
+
+ //virtual void
+ //afterAddFibEntry() =0;
+
+ //virtual void
+ //afterUpdateFibEntry() =0;
+
+ //virtual void
+ //beforeRemoveFibEntry() =0;
+
+protected: // actions
+ /// send Interest to outFace
+ void
+ sendInterest(shared_ptr<pit::Entry> pitEntry,
+ shared_ptr<Face> outFace);
+
+ /** \brief decide that a pending Interest cannot be forwarded
+ * This shall not be called if the pending Interest has been
+ * forwarded earlier, and does not need to be resent now.
+ */
+ void
+ rebuffPendingInterest(shared_ptr<pit::Entry> pitEntry);
+
+private:
+ Forwarder& m_fw;
+};
+
+} // namespace nfd
+
+#endif // NFD_FW_STRATEGY_HPP
diff --git a/daemon/table/pit-entry.cpp b/daemon/table/pit-entry.cpp
index 094ea6e..7a719df 100644
--- a/daemon/table/pit-entry.cpp
+++ b/daemon/table/pit-entry.cpp
@@ -34,9 +34,12 @@
}
bool
-Entry::isNonceSeen(uint32_t nonce) const
+Entry::addNonce(uint32_t nonce)
{
- return m_nonces.count(nonce) > 0;
+ std::pair<std::set<uint32_t>::iterator, bool> insertResult =
+ m_nonces.insert(nonce);
+
+ return insertResult.second;
}
static inline bool
@@ -56,7 +59,6 @@
}
it->update(interest);
- m_nonces.insert(interest.getNonce());
return it;
}
diff --git a/daemon/table/pit-entry.hpp b/daemon/table/pit-entry.hpp
index 00e8a79..98665fc 100644
--- a/daemon/table/pit-entry.hpp
+++ b/daemon/table/pit-entry.hpp
@@ -9,6 +9,7 @@
#include "pit-in-record.hpp"
#include "pit-out-record.hpp"
+#include "core/scheduler.hpp"
namespace nfd {
namespace pit {
@@ -46,14 +47,17 @@
const OutRecordCollection&
getOutRecords() const;
- /** \brief determines whether nonce is seen before
- * in an incoming or outgoing Interest
+ /** \brief records a nonce
+ *
+ * \return{ true if nonce is new; false if nonce is seen before }
*/
bool
- isNonceSeen(uint32_t nonce) const;
+ addNonce(uint32_t nonce);
/** \brief inserts a InRecord for face, and updates it with interest
+ *
* If InRecord for face exists, the existing one is updated.
+ * This method does not add the Nonce as a seen Nonce.
* \return{ an iterator to the InRecord }
*/
InRecordCollection::iterator
@@ -64,6 +68,7 @@
deleteInRecords();
/** \brief inserts a OutRecord for face, and updates it with interest
+ *
* If OutRecord for face exists, the existing one is updated.
* \return{ an iterator to the OutRecord }
*/
@@ -73,6 +78,10 @@
/// deletes one OutRecord for face if exists
void
deleteOutRecord(shared_ptr<Face> face);
+
+public:
+ EventId m_unsatisfyTimer;
+ EventId m_stragglerTimer;
private:
std::set<uint32_t> m_nonces;
diff --git a/tests/table/pit.cpp b/tests/table/pit.cpp
index 2564799..3d81c72 100644
--- a/tests/table/pit.cpp
+++ b/tests/table/pit.cpp
@@ -13,7 +13,7 @@
BOOST_AUTO_TEST_SUITE(TablePit)
-BOOST_AUTO_TEST_CASE(Entry)
+BOOST_AUTO_TEST_CASE(EntryInOutRecords)
{
shared_ptr<Face> face1 = make_shared<DummyFace>(1);
shared_ptr<Face> face2 = make_shared<DummyFace>(2);
@@ -33,10 +33,6 @@
BOOST_CHECK(entry.getInterest().getName().equals(name));
BOOST_CHECK(entry.getName().equals(name));
- // isNonceSeen should not record the Nonce
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), false);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), false);
-
const pit::InRecordCollection& inRecords1 = entry.getInRecords();
BOOST_CHECK_EQUAL(inRecords1.size(), 0);
const pit::OutRecordCollection& outRecords1 = entry.getOutRecords();
@@ -74,9 +70,6 @@
- time::milliseconds(interest1.getInterestLifetime())),
(after2 - before2));
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), false);
-
// update InRecord
time::Point before3 = time::now();
pit::InRecordCollection::iterator in2 =
@@ -91,10 +84,6 @@
- time::milliseconds(interest2.getInterestLifetime())),
(after3 - before3));
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest3.getNonce()), false);
-
// insert another InRecord
pit::InRecordCollection::iterator in3 =
entry.insertOrUpdateInRecord(face2, interest3);
@@ -102,20 +91,11 @@
BOOST_CHECK_EQUAL(inRecords4.size(), 2);
BOOST_CHECK_EQUAL(in3->getFace(), face2);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest3.getNonce()), true);
-
// delete all InRecords
entry.deleteInRecords();
const pit::InRecordCollection& inRecords5 = entry.getInRecords();
BOOST_CHECK_EQUAL(inRecords5.size(), 0);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest3.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest4.getNonce()), false);
-
// insert another OutRecord
pit::OutRecordCollection::iterator out2 =
entry.insertOrUpdateOutRecord(face2, interest4);
@@ -123,21 +103,25 @@
BOOST_CHECK_EQUAL(outRecords3.size(), 2);
BOOST_CHECK_EQUAL(out2->getFace(), face2);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest3.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest4.getNonce()), true);
-
// delete OutRecord
entry.deleteOutRecord(face2);
const pit::OutRecordCollection& outRecords4 = entry.getOutRecords();
BOOST_REQUIRE_EQUAL(outRecords4.size(), 1);
BOOST_CHECK_EQUAL(outRecords4.begin()->getFace(), face1);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest1.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest2.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest3.getNonce()), true);
- BOOST_CHECK_EQUAL(entry.isNonceSeen(interest4.getNonce()), true);
+}
+
+BOOST_AUTO_TEST_CASE(EntryNonce)
+{
+ Name name("ndn:/qtCQ7I1c");
+ Interest interest(name);
+
+ pit::Entry entry(interest);
+
+ BOOST_CHECK_EQUAL(entry.addNonce(25559), true);
+ BOOST_CHECK_EQUAL(entry.addNonce(25559), false);
+ BOOST_CHECK_EQUAL(entry.addNonce(19004), true);
+ BOOST_CHECK_EQUAL(entry.addNonce(19004), false);
}
BOOST_AUTO_TEST_CASE(Insert)