fw: RetxSuppressionExponential
refs #1913
Change-Id: I9bb2bae8d7600722920534f646cc8056b3d4843a
diff --git a/daemon/fw/retx-suppression-exponential.cpp b/daemon/fw/retx-suppression-exponential.cpp
new file mode 100644
index 0000000..a462f8a
--- /dev/null
+++ b/daemon/fw/retx-suppression-exponential.cpp
@@ -0,0 +1,97 @@
+/* -*- 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 "retx-suppression-exponential.hpp"
+
+namespace nfd {
+namespace fw {
+
+const RetxSuppressionExponential::Duration RetxSuppressionExponential::DEFAULT_INITIAL_INTERVAL =
+ time::milliseconds(1);
+const float RetxSuppressionExponential::DEFAULT_MULTIPLIER = 2.0;
+const RetxSuppressionExponential::Duration RetxSuppressionExponential::DEFAULT_MAX_INTERVAL =
+ time::milliseconds(250);
+
+class RetxSuppressionExponential::PitInfo : public StrategyInfo
+{
+public:
+ static constexpr int
+ getTypeId()
+ {
+ return 1020;
+ }
+
+ explicit
+ PitInfo(const Duration& initialInterval)
+ : suppressionInterval(initialInterval)
+ {
+ }
+
+public:
+ /** \brief if last transmission occurred within suppressionInterval,
+ * retransmission will be suppressed
+ */
+ Duration suppressionInterval;
+};
+
+RetxSuppressionExponential::RetxSuppressionExponential(const Duration& initialInterval,
+ float multiplier,
+ const Duration& maxInterval)
+ : m_initialInterval(initialInterval)
+ , m_multiplier(multiplier)
+ , m_maxInterval(maxInterval)
+{
+ BOOST_ASSERT(initialInterval > time::milliseconds::zero());
+ BOOST_ASSERT(multiplier >= 1.0);
+ BOOST_ASSERT(maxInterval >= initialInterval);
+}
+
+RetxSuppression::Result
+RetxSuppressionExponential::decide(const Face& inFace, const Interest& interest,
+ pit::Entry& pitEntry) const
+{
+ bool isNewPitEntry = !pitEntry.hasUnexpiredOutRecords();
+ if (isNewPitEntry) {
+ return NEW;
+ }
+
+ time::steady_clock::TimePoint lastOutgoing = this->getLastOutgoing(pitEntry);
+ time::steady_clock::TimePoint now = time::steady_clock::now();
+ time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing;
+
+ shared_ptr<PitInfo> pi = pitEntry.getOrCreateStrategyInfo<PitInfo>(m_initialInterval);
+ bool shouldSuppress = sinceLastOutgoing < pi->suppressionInterval;
+
+ if (shouldSuppress) {
+ return SUPPRESS;
+ }
+
+ pi->suppressionInterval = std::min(m_maxInterval,
+ time::duration_cast<Duration>(pi->suppressionInterval * m_multiplier));
+ return FORWARD;
+}
+
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/retx-suppression-exponential.hpp b/daemon/fw/retx-suppression-exponential.hpp
new file mode 100644
index 0000000..4909417
--- /dev/null
+++ b/daemon/fw/retx-suppression-exponential.hpp
@@ -0,0 +1,78 @@
+/* -*- 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_RETX_SUPPRESSION_EXPONENTIAL_HPP
+#define NFD_DAEMON_FW_RETX_SUPPRESSION_EXPONENTIAL_HPP
+
+#include "retx-suppression.hpp"
+
+namespace nfd {
+namespace fw {
+
+/** \brief a retransmission suppression decision algorithm that
+ * suppresses retransmissions using exponential backoff
+ *
+ * The i-th retransmission will be suppressed if the last transmission (out-record)
+ * occurred within MIN(initialInterval * multiplier^(i-1), maxInterval)
+ */
+class RetxSuppressionExponential : public RetxSuppression
+{
+public:
+ /** \brief time granularity
+ */
+ typedef time::microseconds Duration;
+
+ explicit
+ RetxSuppressionExponential(const Duration& initialInterval = DEFAULT_INITIAL_INTERVAL,
+ float multiplier = DEFAULT_MULTIPLIER,
+ const Duration& maxInterval = DEFAULT_MAX_INTERVAL);
+
+ /** \brief determines whether Interest is a retransmission,
+ * and if so, whether it shall be forwarded or suppressed
+ */
+ virtual Result
+ decide(const Face& inFace, const Interest& interest,
+ pit::Entry& pitEntry) const DECL_OVERRIDE;
+
+public:
+ /** \brief StrategyInfo on pit::Entry
+ */
+ class PitInfo;
+
+public:
+ static const Duration DEFAULT_INITIAL_INTERVAL;
+ static const float DEFAULT_MULTIPLIER;
+ static const Duration DEFAULT_MAX_INTERVAL;
+
+private:
+ const Duration m_initialInterval;
+ const float m_multiplier;
+ const Duration m_maxInterval;
+};
+
+} // namespace fw
+} // namespace nfd
+
+#endif // NFD_DAEMON_FW_RETX_SUPPRESSION_EXPONENTIAL_HPP
diff --git a/daemon/fw/retx-suppression-fixed.cpp b/daemon/fw/retx-suppression-fixed.cpp
index 74f2302..053c24f 100644
--- a/daemon/fw/retx-suppression-fixed.cpp
+++ b/daemon/fw/retx-suppression-fixed.cpp
@@ -38,24 +38,16 @@
RetxSuppression::Result
RetxSuppressionFixed::decide(const Face& inFace, const Interest& interest,
- const pit::Entry& pitEntry) const
+ pit::Entry& pitEntry) const
{
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 lastOutgoing = this->getLastOutgoing(pitEntry);
time::steady_clock::TimePoint now = time::steady_clock::now();
- time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing->getLastRenewed();
+ time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing;
bool shouldSuppress = sinceLastOutgoing < m_minRetxInterval;
return shouldSuppress ? SUPPRESS : FORWARD;
}
diff --git a/daemon/fw/retx-suppression-fixed.hpp b/daemon/fw/retx-suppression-fixed.hpp
index f88c83e..0f0ca19 100644
--- a/daemon/fw/retx-suppression-fixed.hpp
+++ b/daemon/fw/retx-suppression-fixed.hpp
@@ -45,7 +45,7 @@
*/
virtual Result
decide(const Face& inFace, const Interest& interest,
- const pit::Entry& pitEntry) const DECL_OVERRIDE;
+ pit::Entry& pitEntry) const DECL_OVERRIDE;
public:
static const time::milliseconds DEFAULT_MIN_RETX_INTERVAL;
diff --git a/daemon/fw/retx-suppression.cpp b/daemon/fw/retx-suppression.cpp
new file mode 100644
index 0000000..a420581
--- /dev/null
+++ b/daemon/fw/retx-suppression.cpp
@@ -0,0 +1,46 @@
+/* -*- 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 "retx-suppression.hpp"
+
+namespace nfd {
+namespace fw {
+
+time::steady_clock::TimePoint
+RetxSuppression::getLastOutgoing(const pit::Entry& pitEntry) const
+{
+ 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
+
+ return lastOutgoing->getLastRenewed();
+}
+
+} // namespace fw
+} // namespace nfd
diff --git a/daemon/fw/retx-suppression.hpp b/daemon/fw/retx-suppression.hpp
index 06aaf94..edc2a6d 100644
--- a/daemon/fw/retx-suppression.hpp
+++ b/daemon/fw/retx-suppression.hpp
@@ -54,7 +54,14 @@
* and if so, whether it shall be forwarded or suppressed
*/
virtual Result
- decide(const Face& inFace, const Interest& interest, const pit::Entry& pitEntry) const = 0;
+ decide(const Face& inFace, const Interest& interest, pit::Entry& pitEntry) const = 0;
+
+protected:
+ /** \return last out-record time
+ * \pre pitEntry has one or more unexpired out-records
+ */
+ time::steady_clock::TimePoint
+ getLastOutgoing(const pit::Entry& pitEntry) const;
};
} // namespace fw
diff --git a/tests/daemon/fw/retx-suppression.cpp b/tests/daemon/fw/retx-suppression.cpp
index e4417ce..bec696f 100644
--- a/tests/daemon/fw/retx-suppression.cpp
+++ b/tests/daemon/fw/retx-suppression.cpp
@@ -25,6 +25,7 @@
#include "fw/retx-suppression.hpp"
#include "fw/retx-suppression-fixed.hpp"
+#include "fw/retx-suppression-exponential.hpp"
#include "strategy-tester.hpp"
#include "tests/test-common.hpp"
@@ -35,6 +36,7 @@
using fw::RetxSuppression;
using fw::RetxSuppressionFixed;
+using fw::RetxSuppressionExponential;
BOOST_FIXTURE_TEST_SUITE(FwRetxSuppression, UnitTestTimeFixture)
@@ -87,6 +89,74 @@
BOOST_CHECK_EQUAL(rs.decide(*face2, *interest, *pitEntry), RetxSuppression::SUPPRESS);
}
+BOOST_AUTO_TEST_CASE(Exponential)
+{
+ Forwarder forwarder;
+ Pit& pit = forwarder.getPit();
+ RetxSuppressionExponential rs(time::milliseconds(10), 3.0, time::milliseconds(100));
+
+ shared_ptr<DummyFace> face1 = make_shared<DummyFace>();
+ shared_ptr<DummyFace> face2 = make_shared<DummyFace>();
+ forwarder.addFace(face1);
+ forwarder.addFace(face2);
+
+ shared_ptr<Interest> interest = makeInterest("ndn:/smuVeQSW6q");
+ shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
+
+ // @ 0ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::NEW);
+ pitEntry->insertOrUpdateOutRecord(face2, *interest);
+ // suppression interval is 10ms, until 10ms
+
+ this->advanceClocks(time::milliseconds(5)); // @ 5ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::SUPPRESS);
+ // suppression interval is 10ms, until 10ms
+
+ this->advanceClocks(time::milliseconds(6)); // @ 11ms
+ // note: what happens at *exactly* 10ms does not matter so it's untested,
+ // because in reality network timing won't be exact:
+ // incoming Interest is processed either before or after 10ms point
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::FORWARD);
+ pitEntry->insertOrUpdateOutRecord(face2, *interest);
+ // suppression interval is 30ms, until 41ms
+
+ this->advanceClocks(time::milliseconds(25)); // @ 36ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::SUPPRESS);
+ // suppression interval is 30ms, until 41ms
+
+ this->advanceClocks(time::milliseconds(6)); // @ 42ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::FORWARD);
+ // strategy decides not to forward, but suppression interval is increased nevertheless
+ // suppression interval is 90ms, until 101ms
+
+ this->advanceClocks(time::milliseconds(58)); // @ 100ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::SUPPRESS);
+ // suppression interval is 90ms, until 101ms
+
+ this->advanceClocks(time::milliseconds(3)); // @ 103ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::FORWARD);
+ pitEntry->insertOrUpdateOutRecord(face2, *interest);
+ // suppression interval is 100ms, until 203ms
+
+ this->advanceClocks(time::milliseconds(99)); // @ 202ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::SUPPRESS);
+ // suppression interval is 100ms, until 203ms
+
+ this->advanceClocks(time::milliseconds(2)); // @ 204ms
+ pitEntry->insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(rs.decide(*face1, *interest, *pitEntry), RetxSuppression::FORWARD);
+ pitEntry->insertOrUpdateOutRecord(face2, *interest);
+ // suppression interval is 100ms, until 304ms
+}
+
BOOST_AUTO_TEST_SUITE_END()
} // namespace tests