table+fw: move forwarding semantics out of PIT entry
refs #3546
Change-Id: I1e6f87fd81176c116b6d758156da1cf96ea03608
diff --git a/daemon/fw/access-strategy.cpp b/daemon/fw/access-strategy.cpp
index b1ed449..8d53168 100644
--- a/daemon/fw/access-strategy.cpp
+++ b/daemon/fw/access-strategy.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "access-strategy.hpp"
+#include "pit-algorithm.hpp"
#include "core/logger.hpp"
namespace nfd {
@@ -131,7 +132,7 @@
return false;
}
- if (pitEntry->violatesScope(*face)) {
+ if (violatesScope(*pitEntry, *face)) {
NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-violates-scope");
return false;
}
diff --git a/daemon/fw/best-route-strategy.cpp b/daemon/fw/best-route-strategy.cpp
index 45dd4a5..d6d9bb0 100644
--- a/daemon/fw/best-route-strategy.cpp
+++ b/daemon/fw/best-route-strategy.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "best-route-strategy.hpp"
+#include "pit-algorithm.hpp"
namespace nfd {
namespace fw {
@@ -40,27 +41,20 @@
{
}
-static inline bool
-predicate_PitEntry_canForwardTo_NextHop(shared_ptr<pit::Entry> pitEntry,
- const fib::NextHop& nexthop)
-{
- return pitEntry->canForwardTo(*nexthop.getFace());
-}
-
void
BestRouteStrategy::afterReceiveInterest(const Face& inFace,
- const Interest& interest,
- shared_ptr<fib::Entry> fibEntry,
- shared_ptr<pit::Entry> pitEntry)
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
{
- if (pitEntry->hasUnexpiredOutRecords()) {
+ if (hasPendingOutRecords(*pitEntry)) {
// not a new Interest, don't forward
return;
}
const fib::NextHopList& nexthops = fibEntry->getNextHops();
fib::NextHopList::const_iterator it = std::find_if(nexthops.begin(), nexthops.end(),
- bind(&predicate_PitEntry_canForwardTo_NextHop, pitEntry, _1));
+ [&pitEntry] (const fib::NextHop& nexthop) { return canForwardToLegacy(*pitEntry, *nexthop.getFace()); });
if (it == nexthops.end()) {
this->rejectPendingInterest(pitEntry);
diff --git a/daemon/fw/best-route-strategy2.cpp b/daemon/fw/best-route-strategy2.cpp
index 477b0a3..96791be 100644
--- a/daemon/fw/best-route-strategy2.cpp
+++ b/daemon/fw/best-route-strategy2.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "best-route-strategy2.hpp"
+#include "pit-algorithm.hpp"
#include "core/logger.hpp"
namespace nfd {
@@ -65,7 +66,7 @@
return false;
// forwarding would violate scope
- if (pitEntry->violatesScope(*upstream))
+ if (violatesScope(*pitEntry, *upstream))
return false;
if (wantUnused) {
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index e8a0ade..ef792ae 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -24,6 +24,7 @@
*/
#include "forwarder.hpp"
+#include "pit-algorithm.hpp"
#include "core/logger.hpp"
#include "core/random.hpp"
#include "strategy.hpp"
@@ -129,8 +130,8 @@
shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
// detect duplicate Nonce in PIT entry
- bool hasDuplicateNonceInPit = pitEntry->findNonce(interest.getNonce(), inFace) !=
- pit::DUPLICATE_NONCE_NONE;
+ bool hasDuplicateNonceInPit = fw::findDuplicateNonce(*pitEntry, interest.getNonce(), inFace) !=
+ fw::DUPLICATE_NONCE_NONE;
if (hasDuplicateNonceInPit) {
// goto Interest loop pipeline
this->onInterestLoop(inFace, interest);
@@ -298,7 +299,7 @@
" interest=" << pitEntry->getName());
// scope control
- if (pitEntry->violatesScope(outFace)) {
+ if (fw::violatesScope(*pitEntry, outFace)) {
NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
" interest=" << pitEntry->getName() << " violates scope");
return;
@@ -329,7 +330,7 @@
void
Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
{
- if (pitEntry->hasUnexpiredOutRecords()) {
+ if (fw::hasPendingOutRecords(*pitEntry)) {
NFD_LOG_ERROR("onInterestReject interest=" << pitEntry->getName() <<
" cannot reject forwarded Interest");
return;
diff --git a/daemon/fw/multicast-strategy.cpp b/daemon/fw/multicast-strategy.cpp
index a2559e4..3c92130 100644
--- a/daemon/fw/multicast-strategy.cpp
+++ b/daemon/fw/multicast-strategy.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "multicast-strategy.hpp"
+#include "pit-algorithm.hpp"
namespace nfd {
namespace fw {
@@ -38,20 +39,20 @@
void
MulticastStrategy::afterReceiveInterest(const Face& inFace,
- const Interest& interest,
- shared_ptr<fib::Entry> fibEntry,
- shared_ptr<pit::Entry> pitEntry)
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
{
const fib::NextHopList& nexthops = fibEntry->getNextHops();
for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
shared_ptr<Face> outFace = it->getFace();
- if (pitEntry->canForwardTo(*outFace)) {
+ if (canForwardToLegacy(*pitEntry, *outFace)) {
this->sendInterest(pitEntry, outFace);
}
}
- if (!pitEntry->hasUnexpiredOutRecords()) {
+ if (!hasPendingOutRecords(*pitEntry)) {
this->rejectPendingInterest(pitEntry);
}
}
diff --git a/daemon/fw/ncc-strategy.cpp b/daemon/fw/ncc-strategy.cpp
index 9ecb2cd..5f4c7fa 100644
--- a/daemon/fw/ncc-strategy.cpp
+++ b/daemon/fw/ncc-strategy.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "ncc-strategy.hpp"
+#include "pit-algorithm.hpp"
#include "core/random.hpp"
#include <boost/random/uniform_int_distribution.hpp>
@@ -60,7 +61,7 @@
shared_ptr<PitEntryInfo> pitEntryInfo =
pitEntry->getOrCreateStrategyInfo<PitEntryInfo>();
- bool isNewPitEntry = !pitEntry->hasUnexpiredOutRecords();
+ bool isNewPitEntry = !hasPendingOutRecords(*pitEntry);
if (!isNewPitEntry) {
return;
}
@@ -74,7 +75,7 @@
shared_ptr<Face> bestFace = measurementsEntryInfo->getBestFace();
if (static_cast<bool>(bestFace) && fibEntry->hasNextHop(bestFace) &&
- pitEntry->canForwardTo(*bestFace)) {
+ canForwardToLegacy(*pitEntry, *bestFace)) {
// TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
deferFirst = measurementsEntryInfo->prediction;
deferRange = time::microseconds((deferFirst.count() + 1) / 2);
@@ -88,7 +89,7 @@
// use first eligible nexthop
auto firstEligibleNexthop = std::find_if(nexthops.begin(), nexthops.end(),
[&pitEntry] (const fib::NextHop& nexthop) {
- return pitEntry->canForwardTo(*nexthop.getFace());
+ return canForwardToLegacy(*pitEntry, *nexthop.getFace());
});
if (firstEligibleNexthop != nexthops.end()) {
this->sendInterest(pitEntry, firstEligibleNexthop->getFace());
@@ -97,7 +98,7 @@
shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
- pitEntry->canForwardTo(*previousFace)) {
+ canForwardToLegacy(*pitEntry, *previousFace)) {
--nUpstreams;
}
@@ -138,7 +139,7 @@
shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
- pitEntry->canForwardTo(*previousFace)) {
+ canForwardToLegacy(*pitEntry, *previousFace)) {
this->sendInterest(pitEntry, previousFace);
}
@@ -146,7 +147,7 @@
bool isForwarded = false;
for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
shared_ptr<Face> face = it->getFace();
- if (pitEntry->canForwardTo(*face)) {
+ if (canForwardToLegacy(*pitEntry, *face)) {
isForwarded = true;
this->sendInterest(pitEntry, face);
break;
diff --git a/daemon/fw/pit-algorithm.cpp b/daemon/fw/pit-algorithm.cpp
new file mode 100644
index 0000000..ac04e2a
--- /dev/null
+++ b/daemon/fw/pit-algorithm.cpp
@@ -0,0 +1,122 @@
+/* -*- 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 "pit-algorithm.hpp"
+
+namespace nfd {
+namespace fw {
+
+namespace scope_prefix {
+const Name LOCALHOST("ndn:/localhost");
+const Name LOCALHOP("ndn:/localhop");
+} // namespace scope_prefix
+
+bool
+violatesScope(const pit::Entry& pitEntry, const Face& outFace)
+{
+ if (outFace.getScope() == ndn::nfd::FACE_SCOPE_LOCAL) {
+ return false;
+ }
+ BOOST_ASSERT(outFace.getScope() == ndn::nfd::FACE_SCOPE_NON_LOCAL);
+
+ if (scope_prefix::LOCALHOST.isPrefixOf(pitEntry.getName())) {
+ // face is non-local, violates localhost scope
+ return true;
+ }
+
+ if (scope_prefix::LOCALHOP.isPrefixOf(pitEntry.getName())) {
+ // face is non-local, violates localhop scope unless PIT entry has local in-record
+ return std::none_of(pitEntry.getInRecords().begin(), pitEntry.getInRecords().end(),
+ [] (const pit::InRecord& inRecord) { return inRecord.getFace()->getScope() == ndn::nfd::FACE_SCOPE_LOCAL; });
+ }
+
+ // Name is not subject to scope control
+ return false;
+}
+
+bool
+canForwardToLegacy(const pit::Entry& pitEntry, const Face& face)
+{
+ time::steady_clock::TimePoint now = time::steady_clock::now();
+
+ bool hasUnexpiredOutRecord = std::any_of(pitEntry.getOutRecords().begin(), pitEntry.getOutRecords().end(),
+ [&face, &now] (const pit::OutRecord& outRecord) {
+ return outRecord.getFace().get() == &face && outRecord.getExpiry() >= now;
+ });
+ if (hasUnexpiredOutRecord) {
+ return false;
+ }
+
+ bool hasUnexpiredOtherInRecord = std::any_of(pitEntry.getInRecords().begin(), pitEntry.getInRecords().end(),
+ [&face, &now] (const pit::InRecord& inRecord) {
+ return inRecord.getFace().get() != &face && inRecord.getExpiry() >= now;
+ });
+ if (!hasUnexpiredOtherInRecord) {
+ return false;
+ }
+
+ return !violatesScope(pitEntry, face);
+}
+
+int
+findDuplicateNonce(const pit::Entry& pitEntry, uint32_t nonce, const Face& face)
+{
+ int dnw = DUPLICATE_NONCE_NONE;
+
+ for (const pit::InRecord& inRecord : pitEntry.getInRecords()) {
+ if (inRecord.getLastNonce() == nonce) {
+ if (inRecord.getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_IN_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_IN_OTHER;
+ }
+ }
+ }
+
+ for (const pit::OutRecord& outRecord : pitEntry.getOutRecords()) {
+ if (outRecord.getLastNonce() == nonce) {
+ if (outRecord.getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_OUT_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_OUT_OTHER;
+ }
+ }
+ }
+
+ return dnw;
+}
+
+bool
+hasPendingOutRecords(const pit::Entry& pitEntry)
+{
+ time::steady_clock::TimePoint now = time::steady_clock::now();
+ return std::any_of(pitEntry.getOutRecords().begin(), pitEntry.getOutRecords().end(),
+ [&now] (const pit::OutRecord& outRecord) { return outRecord.getExpiry() >= now; });
+}
+
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/pit-algorithm.hpp b/daemon/fw/pit-algorithm.hpp
new file mode 100644
index 0000000..c5732b8
--- /dev/null
+++ b/daemon/fw/pit-algorithm.hpp
@@ -0,0 +1,117 @@
+/* -*- 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_PIT_ALGORITHM_HPP
+#define NFD_DAEMON_FW_PIT_ALGORITHM_HPP
+
+#include "table/pit-entry.hpp"
+
+/** \file
+ * This file contains algorithms that operate on a PIT entry.
+ */
+
+namespace nfd {
+namespace fw {
+
+/** \brief contain Name prefix that affects namespace-based scope control
+ * \sa http://redmine.named-data.net/projects/nfd/wiki/ScopeControl
+ */
+namespace scope_prefix {
+
+/** \brief ndn:/localhost
+ *
+ * The localhost scope limits propagation to the applications on the originating host.
+ *
+ * Interest and Data packets under prefix ndn:/localhost are restricted by these rules:
+ * \li Interest can come from and go to local faces only.
+ * \li Data can come from and go to local faces only.
+ */
+extern const Name LOCALHOST;
+
+/** \brief ndn:/localhop
+ *
+ * The localhop scope limits propagation to no further than the next node.
+ *
+ * Interest packets under prefix ndn:/localhop are restricted by these rules:
+ * \li Interest can come from a local face or a non-local face.
+ * \li If PIT entry has at least one in-record from a local face,
+ * it can be forwarded to local faces and non-local faces.
+ * \li If PIT entry has all in-records from non-local faces,
+ * it can only be forwarded to local faces.
+ * \li PIT entry can be satisfied by Data from any source.
+ *
+ * Data packets under prefix ndn:/localhop are unrestricted.
+ */
+extern const Name LOCALHOP;
+
+} // namespace scope_prefix
+
+/** \brief determine whether forwarding the Interest in \p pitEntry to \p outFace would violate scope
+ * \sa http://redmine.named-data.net/projects/nfd/wiki/ScopeControl
+ */
+bool
+violatesScope(const pit::Entry& pitEntry, const Face& outFace);
+
+/** \brief decide whether Interest can be forwarded to face
+ *
+ * \return true if out-record of this face does not exist or has expired,
+ * and there is an in-record not of this face,
+ * and scope is not violated
+ *
+ * \note This algorithm has a weakness that it does not permit consumer retransmissions
+ * before out-record expires. Therefore, it's not recommended to use this function
+ * in new strategies.
+ * \todo find a better name for this function
+ */
+bool
+canForwardToLegacy(const pit::Entry& pitEntry, const Face& face);
+
+/** \brief indicates where duplicate Nonces are found
+ */
+enum DuplicateNonceWhere {
+ DUPLICATE_NONCE_NONE = 0, ///< no duplicate Nonce is found
+ DUPLICATE_NONCE_IN_SAME = (1 << 0), ///< in-record of same face
+ DUPLICATE_NONCE_IN_OTHER = (1 << 1), ///< in-record of other face
+ DUPLICATE_NONCE_OUT_SAME = (1 << 2), ///< out-record of same face
+ DUPLICATE_NONCE_OUT_OTHER = (1 << 3) ///< out-record of other face
+};
+
+/** \brief determine whether \p pitEntry has duplicate Nonce \p nonce
+ * \return OR'ed DuplicateNonceWhere
+ */
+int
+findDuplicateNonce(const pit::Entry& pitEntry, uint32_t nonce, const Face& face);
+
+/** \brief determine whether \p pitEntry has any pending out-records
+ * \return true if there is one or more unexpired OutRecords
+ * \todo #3545 take Nack into consideration
+ */
+bool
+hasPendingOutRecords(const pit::Entry& pitEntry);
+
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_PIT_ALGORITHM_HPP
diff --git a/daemon/fw/retx-suppression-exponential.cpp b/daemon/fw/retx-suppression-exponential.cpp
index a462f8a..3cca0ab 100644
--- a/daemon/fw/retx-suppression-exponential.cpp
+++ b/daemon/fw/retx-suppression-exponential.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "retx-suppression-exponential.hpp"
+#include "pit-algorithm.hpp"
namespace nfd {
namespace fw {
@@ -72,7 +73,7 @@
RetxSuppressionExponential::decide(const Face& inFace, const Interest& interest,
pit::Entry& pitEntry) const
{
- bool isNewPitEntry = !pitEntry.hasUnexpiredOutRecords();
+ bool isNewPitEntry = !hasPendingOutRecords(pitEntry);
if (isNewPitEntry) {
return NEW;
}
diff --git a/daemon/fw/retx-suppression-fixed.cpp b/daemon/fw/retx-suppression-fixed.cpp
index 053c24f..b8b2eb8 100644
--- a/daemon/fw/retx-suppression-fixed.cpp
+++ b/daemon/fw/retx-suppression-fixed.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,6 +24,7 @@
*/
#include "retx-suppression-fixed.hpp"
+#include "pit-algorithm.hpp"
namespace nfd {
namespace fw {
@@ -40,7 +41,7 @@
RetxSuppressionFixed::decide(const Face& inFace, const Interest& interest,
pit::Entry& pitEntry) const
{
- bool isNewPitEntry = !pitEntry.hasUnexpiredOutRecords();
+ bool isNewPitEntry = !hasPendingOutRecords(pitEntry);
if (isNewPitEntry) {
return NEW;
}