fw: abstract retransmission suppression logic
Consumer retransmission suppression logic of best-route v2 strategy
is abstracted into RetransmissionSuppression class, so that it can
be reused in other strategies.
refs #2377
Change-Id: I7de2c2d0e60c5ad3467e24283e9b03bd03f65bdc
diff --git a/daemon/fw/best-route-strategy2.cpp b/daemon/fw/best-route-strategy2.cpp
index 044f5e9..bd58590 100644
--- a/daemon/fw/best-route-strategy2.cpp
+++ b/daemon/fw/best-route-strategy2.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.
@@ -32,8 +32,6 @@
NFD_LOG_INIT("BestRouteStrategy2");
const Name BestRouteStrategy2::STRATEGY_NAME("ndn:/localhost/nfd/strategy/best-route/%FD%02");
-/// \todo don't use fixed interval; make it adaptive or use exponential back-off #1913
-const time::milliseconds BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL(100);
BestRouteStrategy2::BestRouteStrategy2(Forwarder& forwarder, const Name& name)
: Strategy(forwarder, name)
@@ -73,12 +71,6 @@
return true;
}
-static inline bool
-compare_OutRecord_lastRenewed(const pit::OutRecord& a, const pit::OutRecord& b)
-{
- return a.getLastRenewed() < b.getLastRenewed();
-}
-
/** \brief pick an eligible NextHop with earliest OutRecord
* \note It is assumed that every nexthop has an OutRecord
*/
@@ -111,8 +103,9 @@
const fib::NextHopList& nexthops = fibEntry->getNextHops();
fib::NextHopList::const_iterator it = nexthops.end();
- bool isNewPitEntry = !pitEntry->hasUnexpiredOutRecords();
- if (isNewPitEntry) {
+ RetransmissionSuppression::Result suppression =
+ m_retransmissionSuppression.decide(inFace, interest, *pitEntry);
+ if (suppression == RetransmissionSuppression::NEW) {
// forward to nexthop with lowest cost except downstream
it = std::find_if(nexthops.begin(), nexthops.end(),
bind(&predicate_NextHop_eligible, pitEntry, _1, inFace.getId(),
@@ -131,24 +124,16 @@
return;
}
- // when was the last outgoing Interest?
- const pit::OutRecordCollection& outRecords = pitEntry->getOutRecords();
- pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
- outRecords.begin(), outRecords.end(), &compare_OutRecord_lastRenewed);
- BOOST_ASSERT(lastOutgoing != outRecords.end()); // otherwise it's new PIT entry
-
- time::steady_clock::TimePoint now = time::steady_clock::now();
- time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing->getLastRenewed();
- bool shouldRetransmit = sinceLastOutgoing >= MIN_RETRANSMISSION_INTERVAL;
- if (!shouldRetransmit) {
+ if (suppression == RetransmissionSuppression::SUPPRESS) {
NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
- << " dontRetransmit sinceLastOutgoing=" << sinceLastOutgoing.count());
+ << " suppressed");
return;
}
// find an unused upstream with lowest cost except downstream
it = std::find_if(nexthops.begin(), nexthops.end(),
- bind(&predicate_NextHop_eligible, pitEntry, _1, inFace.getId(), true, now));
+ bind(&predicate_NextHop_eligible, pitEntry, _1, inFace.getId(),
+ true, time::steady_clock::now()));
if (it != nexthops.end()) {
shared_ptr<Face> outFace = it->getFace();
this->sendInterest(pitEntry, outFace);
diff --git a/daemon/fw/best-route-strategy2.hpp b/daemon/fw/best-route-strategy2.hpp
index bb259d0..5a0f3be 100644
--- a/daemon/fw/best-route-strategy2.hpp
+++ b/daemon/fw/best-route-strategy2.hpp
@@ -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.
@@ -27,6 +27,7 @@
#define NFD_DAEMON_FW_BEST_ROUTE_STRATEGY2_HPP
#include "strategy.hpp"
+#include "retransmission-suppression.hpp"
namespace nfd {
namespace fw {
@@ -52,7 +53,9 @@
public:
static const Name STRATEGY_NAME;
- static const time::milliseconds MIN_RETRANSMISSION_INTERVAL;
+
+private:
+ RetransmissionSuppression m_retransmissionSuppression;
};
} // namespace fw
diff --git a/daemon/fw/retransmission-suppression.cpp b/daemon/fw/retransmission-suppression.cpp
new file mode 100644
index 0000000..be1ff0b
--- /dev/null
+++ b/daemon/fw/retransmission-suppression.cpp
@@ -0,0 +1,59 @@
+/* -*- 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 "retransmission-suppression.hpp"
+
+namespace nfd {
+namespace fw {
+
+/// \todo don't use fixed interval; make it adaptive or use exponential back-off #1913
+const time::milliseconds RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL(100);
+
+RetransmissionSuppression::Result
+RetransmissionSuppression::decide(const Face& inFace, const Interest& interest,
+ const pit::Entry& pitEntry)
+{
+ bool isNewPitEntry = !pitEntry.hasUnexpiredOutRecords();
+ if (isNewPitEntry) {
+ return NEW;
+ }
+
+ // when was the last outgoing Interest?
+ const pit::OutRecordCollection& outRecords = pitEntry.getOutRecords();
+ pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
+ outRecords.begin(), outRecords.end(),
+ [] (const pit::OutRecord& a, const pit::OutRecord& b) {
+ return a.getLastRenewed() < b.getLastRenewed();
+ });
+ BOOST_ASSERT(lastOutgoing != outRecords.end()); // otherwise it's new PIT entry
+
+ time::steady_clock::TimePoint now = time::steady_clock::now();
+ time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing->getLastRenewed();
+ bool shouldSuppress = sinceLastOutgoing < MIN_RETRANSMISSION_INTERVAL;
+ return shouldSuppress ? SUPPRESS : FORWARD;
+}
+
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/retransmission-suppression.hpp b/daemon/fw/retransmission-suppression.hpp
new file mode 100644
index 0000000..4553433
--- /dev/null
+++ b/daemon/fw/retransmission-suppression.hpp
@@ -0,0 +1,66 @@
+/* -*- 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_RETRANSMISSION_SUPPRESSION_HPP
+#define NFD_DAEMON_FW_RETRANSMISSION_SUPPRESSION_HPP
+
+#include "strategy.hpp"
+
+namespace nfd {
+namespace fw {
+
+/** \brief helper for consumer retransmission suppression
+ */
+class RetransmissionSuppression : noncopyable
+{
+public:
+ enum Result {
+ /** \brief Interest is new (not a retransmission)
+ */
+ NEW,
+
+ /** \brief Interest is retransmission and should be forwarded
+ */
+ FORWARD,
+
+ /** \brief Interest is retransmission and should be suppressed
+ */
+ SUPPRESS
+ };
+
+ /** \brief determines whether Interest is a retransmission,
+ * and if so, whether it shall be forwarded or suppressed
+ */
+ Result
+ decide(const Face& inFace, const Interest& interest, const pit::Entry& pitEntry);
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ static const time::milliseconds MIN_RETRANSMISSION_INTERVAL;
+};
+
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_RETRANSMISSION_SUPPRESSION_HPP
diff --git a/tests/daemon/fw/best-route-strategy2.cpp b/tests/daemon/fw/best-route-strategy2.cpp
index d956e9f..687bfcb 100644
--- a/tests/daemon/fw/best-route-strategy2.cpp
+++ b/tests/daemon/fw/best-route-strategy2.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.
@@ -62,13 +62,13 @@
shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
const time::nanoseconds TICK = time::duration_cast<time::nanoseconds>(
- fw::BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL * 0.01);
+ fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 0.01);
const time::nanoseconds RETRANSMISSION_10P = time::duration_cast<time::nanoseconds>(
- fw::BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL * 0.1); // 10%
+ fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 0.1); // 10%
const time::nanoseconds RETRANSMISSION_70P = time::duration_cast<time::nanoseconds>(
- fw::BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL * 0.7); // 70%
+ fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 0.7); // 70%
const time::nanoseconds RETRANSMISSION_2 = time::duration_cast<time::nanoseconds>(
- fw::BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL * 2.0); // x2
+ fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 2.0); // x2
// first Interest goes to nexthop with lowest FIB cost,
// however face1 is downstream so it cannot be used
@@ -99,7 +99,7 @@
retxFrom4Evt = scheduler::schedule(RETRANSMISSION_10P, periodicalRetxFrom4);
};
periodicalRetxFrom4();
- this->advanceClocks(TICK, fw::BestRouteStrategy2::MIN_RETRANSMISSION_INTERVAL * 16);
+ this->advanceClocks(TICK, fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 16);
scheduler::cancel(retxFrom4Evt);
// nexthops for accepted retransmissions: follow FIB cost,
diff --git a/tests/daemon/fw/retransmission-suppression.cpp b/tests/daemon/fw/retransmission-suppression.cpp
new file mode 100644
index 0000000..c1ba968
--- /dev/null
+++ b/tests/daemon/fw/retransmission-suppression.cpp
@@ -0,0 +1,90 @@
+/* -*- 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/retransmission-suppression.hpp"
+#include "strategy-tester.hpp"
+
+#include "tests/test-common.hpp"
+#include "tests/daemon/face/dummy-face.hpp"
+
+namespace nfd {
+namespace tests {
+
+using fw::RetransmissionSuppression;
+
+BOOST_FIXTURE_TEST_SUITE(FwRetransmissionSuppression, UnitTestTimeFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+ Forwarder forwarder;
+ Pit& pit = forwarder.getPit();
+ RetransmissionSuppression rs;
+
+ shared_ptr<DummyFace> face1 = make_shared<DummyFace>();
+ shared_ptr<DummyFace> face2 = make_shared<DummyFace>();
+ shared_ptr<DummyFace> face3 = make_shared<DummyFace>();
+ forwarder.addFace(face1);
+ forwarder.addFace(face2);
+ forwarder.addFace(face3);
+
+ shared_ptr<Interest> interest = makeInterest("ndn:/0JiimvmxK8");
+ shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
+
+ const time::nanoseconds RETRANSMISSION_10P = time::duration_cast<time::nanoseconds>(
+ fw::RetransmissionSuppression::MIN_RETRANSMISSION_INTERVAL * 0.1);
+
+ // @ time 0
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetransmissionSuppression::NEW);
+ pitEntry->insertOrUpdateOutRecord(face3, *interest);
+
+ this->advanceClocks(RETRANSMISSION_10P, 5); // @ time 0.5 interval
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetransmissionSuppression::SUPPRESS);
+ pitEntry->insertOrUpdateInRecord(face2, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face2, *interest, *pitEntry), RetransmissionSuppression::SUPPRESS);
+
+ this->advanceClocks(RETRANSMISSION_10P, 6); // @ time 1.1 interval
+ pitEntry->insertOrUpdateInRecord(face2, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face2, *interest, *pitEntry), RetransmissionSuppression::FORWARD);
+ // but strategy decides not to forward
+
+ this->advanceClocks(RETRANSMISSION_10P, 1); // @ time 1.2 interval
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetransmissionSuppression::FORWARD);
+ // retransmission suppress shall still give clearance for forwarding
+ pitEntry->insertOrUpdateOutRecord(face3, *interest); // and strategy forwards
+
+ this->advanceClocks(RETRANSMISSION_10P, 2); // @ time 1.4 interval
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetransmissionSuppression::SUPPRESS);
+ pitEntry->insertOrUpdateInRecord(face2, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face2, *interest, *pitEntry), RetransmissionSuppression::SUPPRESS);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd