fw: use dead Nonce list in pipelines
refs #1953
Change-Id: I0faef2a985b03fe96387c2e0181588713550b9ce
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 1b677be..d8bc19f 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -74,9 +74,11 @@
// PIT insert
shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
- // detect loop and record Nonce
- bool isLoop = ! pitEntry->addNonce(interest.getNonce());
- if (isLoop) {
+ // detect duplicate Nonce
+ int dnw = pitEntry->findNonce(interest.getNonce(), inFace);
+ bool hasDuplicateNonce = (dnw != pit::DUPLICATE_NONCE_NONE) ||
+ m_deadNonceList.has(interest.getName(), interest.getNonce());
+ if (hasDuplicateNonce) {
// goto Interest loop pipeline
this->onInterestLoop(inFace, interest, pitEntry);
return;
@@ -96,7 +98,7 @@
// XXX should we lookup PIT for other Interests that also match csMatch?
// set PIT straggler timer
- this->setStragglerTimer(pitEntry);
+ this->setStragglerTimer(pitEntry, true, csMatch->getFreshnessPeriod());
// goto outgoing Data pipeline
this->onOutgoingData(*csMatch, inFace);
@@ -208,7 +210,7 @@
this->cancelUnsatisfyAndStragglerTimer(pitEntry);
// set PIT straggler timer
- this->setStragglerTimer(pitEntry);
+ this->setStragglerTimer(pitEntry, false);
}
void
@@ -220,6 +222,20 @@
this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
pitEntry));
+ // goto Interest Finalize pipeline
+ this->onInterestFinalize(pitEntry, false);
+}
+
+void
+Forwarder::onInterestFinalize(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod)
+{
+ NFD_LOG_DEBUG("onInterestFinalize interest=" << pitEntry->getName() <<
+ (isSatisfied ? " satisfied" : " unsatisfied"));
+
+ // Dead Nonce List insert if necessary
+ this->insertDeadNonceList(*pitEntry, isSatisfied, dataFreshnessPeriod, 0);
+
// PIT delete
this->cancelUnsatisfyAndStragglerTimer(pitEntry);
m_pit.erase(pitEntry);
@@ -277,12 +293,15 @@
this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyInterest, _1,
pitEntry, cref(inFace), cref(data)));
+ // Dead Nonce List insert if necessary (for OutRecord of inFace)
+ this->insertDeadNonceList(*pitEntry, true, data.getFreshnessPeriod(), &inFace);
+
// mark PIT satisfied
pitEntry->deleteInRecords();
pitEntry->deleteOutRecord(inFace.shared_from_this());
// set PIT straggler timer
- this->setStragglerTimer(pitEntry);
+ this->setStragglerTimer(pitEntry, true, data.getFreshnessPeriod());
}
// foreach pending downstream
@@ -364,13 +383,14 @@
}
void
-Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod)
{
time::nanoseconds stragglerTime = time::milliseconds(100);
scheduler::cancel(pitEntry->m_stragglerTimer);
pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
- bind(&Pit::erase, &m_pit, pitEntry));
+ bind(&Forwarder::onInterestFinalize, this, pitEntry, isSatisfied, dataFreshnessPeriod));
}
void
@@ -380,4 +400,49 @@
scheduler::cancel(pitEntry->m_stragglerTimer);
}
+static inline void
+insertNonceToDnl(DeadNonceList& dnl, const pit::Entry& pitEntry,
+ const pit::OutRecord& outRecord)
+{
+ dnl.add(pitEntry.getName(), outRecord.getLastNonce());
+}
+
+void
+Forwarder::insertDeadNonceList(pit::Entry& pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod,
+ Face* upstream)
+{
+ // need Dead Nonce List insert?
+ bool needDnl = false;
+ if (isSatisfied) {
+ bool hasFreshnessPeriod = dataFreshnessPeriod >= time::milliseconds::zero();
+ // Data never becomes stale if it doesn't have FreshnessPeriod field
+ needDnl = static_cast<bool>(pitEntry.getInterest().getMustBeFresh()) &&
+ (hasFreshnessPeriod && dataFreshnessPeriod < m_deadNonceList.getLifetime());
+ }
+ else {
+ needDnl = true;
+ }
+
+ if (!needDnl) {
+ return;
+ }
+
+ // Dead Nonce List insert
+ if (upstream == 0) {
+ // insert all outgoing Nonces
+ const pit::OutRecordCollection& outRecords = pitEntry.getOutRecords();
+ std::for_each(outRecords.begin(), outRecords.end(),
+ bind(&insertNonceToDnl, ref(m_deadNonceList), cref(pitEntry), _1));
+ }
+ else {
+ // insert outgoing Nonce of a specific face
+ pit::OutRecordCollection::const_iterator outRecord =
+ pitEntry.getOutRecord(upstream->shared_from_this());
+ if (outRecord != pitEntry.getOutRecords().end()) {
+ m_deadNonceList.add(pitEntry.getName(), outRecord->getLastNonce());
+ }
+ }
+}
+
} // namespace nfd
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 8c5ed79..a753f15 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -1,11 +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
+ * 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
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,7 +21,7 @@
*
* 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_FORWARDER_HPP
#define NFD_DAEMON_FW_FORWARDER_HPP
@@ -34,6 +35,7 @@
#include "table/cs.hpp"
#include "table/measurements.hpp"
#include "table/strategy-choice.hpp"
+#include "table/dead-nonce-list.hpp"
namespace nfd {
@@ -99,6 +101,9 @@
StrategyChoice&
getStrategyChoice();
+ DeadNonceList&
+ getDeadNonceList();
+
PUBLIC_WITH_TESTS_ELSE_PRIVATE: // pipelines
/** \brief incoming Interest pipeline
*/
@@ -127,6 +132,14 @@
VIRTUAL_WITH_TESTS void
onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry);
+ /** \brief Interest finalize pipeline
+ * \param isSatisfied whether the Interest has been satisfied
+ * \param dataFreshnessPeriod FreshnessPeriod of satisfying Data
+ */
+ VIRTUAL_WITH_TESTS void
+ onInterestFinalize(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod = time::milliseconds(-1));
+
/** \brief incoming Data pipeline
*/
VIRTUAL_WITH_TESTS void
@@ -147,11 +160,21 @@
setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry);
VIRTUAL_WITH_TESTS void
- setStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+ setStragglerTimer(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod = time::milliseconds(-1));
VIRTUAL_WITH_TESTS void
cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+ /** \brief insert Nonce to Dead Nonce List if necessary
+ * \param upstream if null, insert Nonces from all OutRecords;
+ * if not null, insert Nonce only on the OutRecord of this face
+ */
+ VIRTUAL_WITH_TESTS void
+ insertDeadNonceList(pit::Entry& pitEntry, bool isSatisfied,
+ const time::milliseconds& dataFreshnessPeriod,
+ Face* upstream);
+
/// call trigger (method) on the effective strategy of pitEntry
#ifdef WITH_TESTS
virtual void
@@ -174,6 +197,7 @@
Cs m_cs;
Measurements m_measurements;
StrategyChoice m_strategyChoice;
+ DeadNonceList m_deadNonceList;
static const Name LOCALHOST_NAME;
@@ -253,6 +277,12 @@
return m_strategyChoice;
}
+inline DeadNonceList&
+Forwarder::getDeadNonceList()
+{
+ return m_deadNonceList;
+}
+
#ifdef WITH_TESTS
inline void
Forwarder::dispatchToStrategy(shared_ptr<pit::Entry> pitEntry, function<void(fw::Strategy*)> trigger)
diff --git a/daemon/table/dead-nonce-list.hpp b/daemon/table/dead-nonce-list.hpp
index ad2e0ad..1c7f7cc 100644
--- a/daemon/table/dead-nonce-list.hpp
+++ b/daemon/table/dead-nonce-list.hpp
@@ -83,6 +83,11 @@
size_t
size() const;
+ /** \return expected lifetime
+ */
+ const time::nanoseconds&
+ getLifetime() const;
+
private: // Entry and Index
typedef uint64_t Entry;
@@ -206,6 +211,12 @@
static const size_t EVICT_LIMIT;
};
+inline const time::nanoseconds&
+DeadNonceList::getLifetime() const
+{
+ return m_lifetime;
+}
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
diff --git a/daemon/table/pit-entry.cpp b/daemon/table/pit-entry.cpp
index e089a09..35cc2e0 100644
--- a/daemon/table/pit-entry.cpp
+++ b/daemon/table/pit-entry.cpp
@@ -126,10 +126,38 @@
return false;
}
-bool
-Entry::addNonce(uint32_t nonce)
+int
+Entry::findNonce(uint32_t nonce, const Face& face) const
{
- return m_nonceList.add(nonce);
+ // TODO should we ignore expired in/out records?
+
+ int dnw = DUPLICATE_NONCE_NONE;
+
+ for (InRecordCollection::const_iterator it = m_inRecords.begin();
+ it != m_inRecords.end(); ++it) {
+ if (it->getLastNonce() == nonce) {
+ if (it->getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_IN_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_IN_OTHER;
+ }
+ }
+ }
+
+ for (OutRecordCollection::const_iterator it = m_outRecords.begin();
+ it != m_outRecords.end(); ++it) {
+ if (it->getLastNonce() == nonce) {
+ if (it->getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_OUT_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_OUT_OTHER;
+ }
+ }
+ }
+
+ return dnw;
}
InRecordCollection::iterator
@@ -170,7 +198,6 @@
}
it->update(interest);
- m_nonceList.add(interest.getNonce());
return it;
}
diff --git a/daemon/table/pit-entry.hpp b/daemon/table/pit-entry.hpp
index 420bb29..5a691de 100644
--- a/daemon/table/pit-entry.hpp
+++ b/daemon/table/pit-entry.hpp
@@ -26,7 +26,6 @@
#ifndef NFD_DAEMON_TABLE_PIT_ENTRY_HPP
#define NFD_DAEMON_TABLE_PIT_ENTRY_HPP
-#include "pit-nonce-list.hpp"
#include "pit-in-record.hpp"
#include "pit-out-record.hpp"
#include "core/scheduler.hpp"
@@ -49,6 +48,20 @@
*/
typedef std::list<OutRecord> OutRecordCollection;
+/** \brief indicates where duplicate Nonces are found
+ */
+enum DuplicateNonceWhere {
+ DUPLICATE_NONCE_NONE = 0,
+ /// in-record of same face
+ DUPLICATE_NONCE_IN_SAME = (1 << 0),
+ /// in-record of other face
+ DUPLICATE_NONCE_IN_OTHER = (1 << 1),
+ /// out-record of same face
+ DUPLICATE_NONCE_OUT_SAME = (1 << 2),
+ /// out-record of other face
+ DUPLICATE_NONCE_OUT_OTHER = (1 << 3)
+};
+
/** \brief represents a PIT entry
*/
class Entry : public StrategyInfoHost, noncopyable
@@ -86,12 +99,11 @@
bool
violatesScope(const Face& face) const;
- /** \brief records a nonce
- *
- * \return true if nonce is new; false if nonce is seen before
+ /** \brief finds where a duplicate Nonce appears
+ * \return OR'ed DuplicateNonceWhere
*/
- bool
- addNonce(uint32_t nonce);
+ int
+ findNonce(uint32_t nonce, const Face& face) const;
public: // InRecord
const InRecordCollection&
@@ -156,7 +168,6 @@
EventId m_stragglerTimer;
private:
- pit::NonceList m_nonceList;
shared_ptr<const Interest> m_interest;
InRecordCollection m_inRecords;
OutRecordCollection m_outRecords;
diff --git a/daemon/table/pit-nonce-list.cpp b/daemon/table/pit-nonce-list.cpp
deleted file mode 100644
index 02502ab..0000000
--- a/daemon/table/pit-nonce-list.cpp
+++ /dev/null
@@ -1,66 +0,0 @@
-/* -*- 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
- *
- * 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-nonce-list.hpp"
-
-namespace nfd {
-namespace pit {
-
-// The NonceList has limited capacity to avoid memory explosion
-// if PIT entry is constantly refreshed (NFD Bug #1770).
-// Current implementation keeps nonces in a set to detect duplicates,
-// and a queue to evict the oldest nonce when capacity limit is reached.
-// A limitation is that a nonce first appeared at time 0 and duplicated at time 10
-// could be evicted before a nonce appeared only once at time 5;
-// this limitation should not affect normal operation.
-
-const size_t NonceList::CAPACITY = 256;
-
-NonceList::NonceList()
-{
-}
-
-bool
-NonceList::add(uint32_t nonce)
-{
- bool isNew = m_nonceSet.insert(nonce).second;
- if (!isNew)
- return false;
-
- m_nonceQueue.push(nonce);
- BOOST_ASSERT(m_nonceSet.size() == m_nonceQueue.size());
-
- if (m_nonceSet.size() > CAPACITY) {
- size_t nErased = m_nonceSet.erase(m_nonceQueue.front());
- BOOST_ASSERT(nErased == 1);
- m_nonceQueue.pop();
- BOOST_ASSERT(m_nonceSet.size() == m_nonceQueue.size());
- BOOST_ASSERT(m_nonceSet.size() <= CAPACITY);
- }
- return true;
-}
-
-} // namespace pit
-} // namespace nfd
diff --git a/daemon/table/pit-nonce-list.hpp b/daemon/table/pit-nonce-list.hpp
deleted file mode 100644
index 393ae34..0000000
--- a/daemon/table/pit-nonce-list.hpp
+++ /dev/null
@@ -1,64 +0,0 @@
-/* -*- 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
- *
- * 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_TABLE_PIT_NONCE_LIST_HPP
-#define NFD_DAEMON_TABLE_PIT_NONCE_LIST_HPP
-
-#include "common.hpp"
-
-namespace nfd {
-namespace pit {
-
-/** \brief represents a Nonce list
- */
-class NonceList : noncopyable
-{
-public:
- NonceList();
-
- /** \brief records a nonce
- * \return true if nonce is new; false if nonce is seen before
- */
- bool
- add(uint32_t nonce);
-
- size_t
- size() const
- {
- return m_nonceSet.size();
- }
-
-public:
- static const size_t CAPACITY;
-
-private:
- std::set<uint32_t> m_nonceSet;
- std::queue<uint32_t> m_nonceQueue;
-};
-
-} // namespace pit
-} // namespace nfd
-
-#endif // NFD_DAEMON_TABLE_PIT_NONCE_LIST_HPP