fw: per upstream retx exponential suppression for multicast strategy
refs: #4066
Change-Id: Ic1047b871dc9dc040e95ac5edceaae9994cd2849
diff --git a/daemon/fw/access-strategy.cpp b/daemon/fw/access-strategy.cpp
index b391ba9..2176f2f 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-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -60,15 +60,15 @@
AccessStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
const shared_ptr<pit::Entry>& pitEntry)
{
- RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
+ RetxSuppressionResult suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
switch (suppressResult) {
- case RetxSuppression::NEW:
+ case RetxSuppressionResult::NEW:
this->afterReceiveNewInterest(inFace, interest, pitEntry);
break;
- case RetxSuppression::FORWARD:
+ case RetxSuppressionResult::FORWARD:
this->afterReceiveRetxInterest(inFace, interest, pitEntry);
break;
- case RetxSuppression::SUPPRESS:
+ case RetxSuppressionResult::SUPPRESS:
NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-suppress");
break;
default:
diff --git a/daemon/fw/algorithm.cpp b/daemon/fw/algorithm.cpp
index 320a92a..db2c4cf 100644
--- a/daemon/fw/algorithm.cpp
+++ b/daemon/fw/algorithm.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -120,5 +120,18 @@
});
}
+time::steady_clock::TimePoint
+getLastOutgoing(const pit::Entry& pitEntry)
+{
+ pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
+ pitEntry.out_begin(), pitEntry.out_end(),
+ [] (const pit::OutRecord& a, const pit::OutRecord& b) {
+ return a.getLastRenewed() < b.getLastRenewed();
+ });
+ BOOST_ASSERT(lastOutgoing != pitEntry.out_end());
+
+ return lastOutgoing->getLastRenewed();
+}
+
} // namespace fw
} // namespace nfd
diff --git a/daemon/fw/algorithm.hpp b/daemon/fw/algorithm.hpp
index 480fcab..c696d16 100644
--- a/daemon/fw/algorithm.hpp
+++ b/daemon/fw/algorithm.hpp
@@ -108,6 +108,12 @@
bool
hasPendingOutRecords(const pit::Entry& pitEntry);
+/** \return last out-record time
+ * \pre pitEntry has one or more unexpired out-records
+ */
+time::steady_clock::TimePoint
+getLastOutgoing(const pit::Entry& pitEntry);
+
} // namespace fw
} // namespace nfd
diff --git a/daemon/fw/asf-strategy.cpp b/daemon/fw/asf-strategy.cpp
index baf8230..ffeaead 100644
--- a/daemon/fw/asf-strategy.cpp
+++ b/daemon/fw/asf-strategy.cpp
@@ -1,5 +1,5 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
+/*
* Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
@@ -69,13 +69,13 @@
const shared_ptr<pit::Entry>& pitEntry)
{
// Should the Interest be suppressed?
- RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
+ RetxSuppressionResult suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
switch (suppressResult) {
- case RetxSuppression::NEW:
- case RetxSuppression::FORWARD:
+ case RetxSuppressionResult::NEW:
+ case RetxSuppressionResult::FORWARD:
break;
- case RetxSuppression::SUPPRESS:
+ case RetxSuppressionResult::SUPPRESS:
NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
return;
}
diff --git a/daemon/fw/best-route-strategy2.cpp b/daemon/fw/best-route-strategy2.cpp
index 11add67..5f12ed2 100644
--- a/daemon/fw/best-route-strategy2.cpp
+++ b/daemon/fw/best-route-strategy2.cpp
@@ -1,5 +1,5 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
+/*
* Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
@@ -124,8 +124,8 @@
BestRouteStrategy2::afterReceiveInterest(const Face& inFace, const Interest& interest,
const shared_ptr<pit::Entry>& pitEntry)
{
- RetxSuppression::Result suppression = m_retxSuppression.decide(inFace, interest, *pitEntry);
- if (suppression == RetxSuppression::SUPPRESS) {
+ RetxSuppressionResult suppression = m_retxSuppression.decidePerPitEntry(*pitEntry);
+ if (suppression == RetxSuppressionResult::SUPPRESS) {
NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
<< " suppressed");
return;
@@ -135,7 +135,7 @@
const fib::NextHopList& nexthops = fibEntry.getNextHops();
fib::NextHopList::const_iterator it = nexthops.end();
- if (suppression == RetxSuppression::NEW) {
+ if (suppression == RetxSuppressionResult::NEW) {
// forward to nexthop with lowest cost except downstream
it = std::find_if(nexthops.begin(), nexthops.end(),
bind(&isNextHopEligible, cref(inFace), interest, _1, pitEntry,
diff --git a/daemon/fw/multicast-strategy.cpp b/daemon/fw/multicast-strategy.cpp
index 7b38bc1..f51693b 100644
--- a/daemon/fw/multicast-strategy.cpp
+++ b/daemon/fw/multicast-strategy.cpp
@@ -1,5 +1,5 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
+/*
* Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
@@ -66,25 +66,25 @@
MulticastStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
const shared_ptr<pit::Entry>& pitEntry)
{
- // Should the Interest be suppressed?
- RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
- switch (suppressResult) {
- case RetxSuppression::NEW:
- case RetxSuppression::FORWARD:
- break;
- case RetxSuppression::SUPPRESS:
- NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
- return;
- }
-
const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
const fib::NextHopList& nexthops = fibEntry.getNextHops();
int nEligibleNextHops = 0;
+ bool isSuppressed = false;
+
for (const auto& nexthop : nexthops) {
Face& outFace = nexthop.getFace();
+ RetxSuppressionResult suppressResult = m_retxSuppression.decidePerUpstream(*pitEntry, outFace);
+
+ if (suppressResult == RetxSuppressionResult::SUPPRESS) {
+ NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
+ << "to=" << outFace.getId() << " suppressed");
+ isSuppressed = true;
+ continue;
+ }
+
if ((outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
wouldViolateScope(inFace, interest, outFace)) {
continue;
@@ -93,17 +93,21 @@
this->sendInterest(pitEntry, outFace, interest);
NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
<< " pitEntry-to=" << outFace.getId());
+
+ if (suppressResult == RetxSuppressionResult::FORWARD) {
+ m_retxSuppression.incrementIntervalForOutRecord(*pitEntry->getOutRecord(outFace));
+ }
++nEligibleNextHops;
}
- if (nEligibleNextHops == 0) {
- NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
+ if (nEligibleNextHops == 0 && !isSuppressed) {
+ NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
- lp::NackHeader nackHeader;
- nackHeader.setReason(lp::NackReason::NO_ROUTE);
- this->sendNack(pitEntry, inFace, nackHeader);
+ lp::NackHeader nackHeader;
+ nackHeader.setReason(lp::NackReason::NO_ROUTE);
+ this->sendNack(pitEntry, inFace, nackHeader);
- this->rejectPendingInterest(pitEntry);
+ this->rejectPendingInterest(pitEntry);
}
}
diff --git a/daemon/fw/retx-suppression-exponential.cpp b/daemon/fw/retx-suppression-exponential.cpp
index 28f6df5..f2ff1b2 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-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,7 +24,6 @@
*/
#include "retx-suppression-exponential.hpp"
-#include "algorithm.hpp"
namespace nfd {
namespace fw {
@@ -69,16 +68,15 @@
BOOST_ASSERT(maxInterval >= initialInterval);
}
-RetxSuppression::Result
-RetxSuppressionExponential::decide(const Face& inFace, const Interest& interest,
- pit::Entry& pitEntry) const
+RetxSuppressionResult
+RetxSuppressionExponential::decidePerPitEntry(pit::Entry& pitEntry)
{
bool isNewPitEntry = !hasPendingOutRecords(pitEntry);
if (isNewPitEntry) {
- return NEW;
+ return RetxSuppressionResult::NEW;
}
- time::steady_clock::TimePoint lastOutgoing = this->getLastOutgoing(pitEntry);
+ time::steady_clock::TimePoint lastOutgoing = getLastOutgoing(pitEntry);
time::steady_clock::TimePoint now = time::steady_clock::now();
time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing;
@@ -86,12 +84,45 @@
bool shouldSuppress = sinceLastOutgoing < pi->suppressionInterval;
if (shouldSuppress) {
- return SUPPRESS;
+ return RetxSuppressionResult::SUPPRESS;
}
pi->suppressionInterval = std::min(m_maxInterval,
- time::duration_cast<Duration>(pi->suppressionInterval * m_multiplier));
- return FORWARD;
+ time::duration_cast<Duration>(pi->suppressionInterval * m_multiplier));
+
+ return RetxSuppressionResult::FORWARD;
+}
+
+RetxSuppressionResult
+RetxSuppressionExponential::decidePerUpstream(pit::Entry& pitEntry, Face& outFace)
+{
+ // NEW if outRecord for the face does not exist
+ auto outRecord = pitEntry.getOutRecord(outFace);
+ if (outRecord == pitEntry.out_end()) {
+ return RetxSuppressionResult::NEW;
+ }
+
+ time::steady_clock::TimePoint lastOutgoing = outRecord->getLastRenewed();
+ time::steady_clock::TimePoint now = time::steady_clock::now();
+ time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing;
+
+ // insertStrategyInfo does not insert m_initialInterval again if it already exists
+ PitInfo* pi = outRecord->insertStrategyInfo<PitInfo>(m_initialInterval).first;
+ bool shouldSuppress = sinceLastOutgoing < pi->suppressionInterval;
+
+ if (shouldSuppress) {
+ return RetxSuppressionResult::SUPPRESS;
+ }
+
+ return RetxSuppressionResult::FORWARD;
+}
+
+void
+RetxSuppressionExponential::incrementIntervalForOutRecord(pit::OutRecord& outRecord)
+{
+ PitInfo* pi = outRecord.insertStrategyInfo<PitInfo>(m_initialInterval).first;
+ pi->suppressionInterval = std::min(m_maxInterval,
+ time::duration_cast<Duration>(pi->suppressionInterval * m_multiplier));
}
} // namespace fw
diff --git a/daemon/fw/retx-suppression-exponential.hpp b/daemon/fw/retx-suppression-exponential.hpp
index a2fbe7b..8455b5e 100644
--- a/daemon/fw/retx-suppression-exponential.hpp
+++ b/daemon/fw/retx-suppression-exponential.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -26,6 +26,7 @@
#ifndef NFD_DAEMON_FW_RETX_SUPPRESSION_EXPONENTIAL_HPP
#define NFD_DAEMON_FW_RETX_SUPPRESSION_EXPONENTIAL_HPP
+#include "algorithm.hpp"
#include "retx-suppression.hpp"
namespace nfd {
@@ -37,7 +38,7 @@
* 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
+class RetxSuppressionExponential
{
public:
/** \brief time granularity
@@ -49,12 +50,22 @@
float multiplier = DEFAULT_MULTIPLIER,
const Duration& maxInterval = DEFAULT_MAX_INTERVAL);
- /** \brief determines whether Interest is a retransmission,
+ /** \brief determines whether Interest is a retransmission per pit entry
* and if so, whether it shall be forwarded or suppressed
*/
- virtual Result
- decide(const Face& inFace, const Interest& interest,
- pit::Entry& pitEntry) const override;
+ RetxSuppressionResult
+ decidePerPitEntry(pit::Entry& pitEntry);
+
+ /** \brief determines whether Interest is a retransmission per upstream
+ * and if so, whether it shall be forwarded or suppressed
+ */
+ RetxSuppressionResult
+ decidePerUpstream(pit::Entry& pitEntry, Face& outFace);
+
+ /** \brief Increment the suppression interval for out record
+ */
+ void
+ incrementIntervalForOutRecord(pit::OutRecord& outRecord);
public:
/** \brief StrategyInfo on pit::Entry
diff --git a/daemon/fw/retx-suppression-fixed.cpp b/daemon/fw/retx-suppression-fixed.cpp
index d2c74dc..6245ae3 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-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -24,7 +24,6 @@
*/
#include "retx-suppression-fixed.hpp"
-#include "algorithm.hpp"
namespace nfd {
namespace fw {
@@ -37,20 +36,19 @@
BOOST_ASSERT(minRetxInterval > time::milliseconds::zero());
}
-RetxSuppression::Result
-RetxSuppressionFixed::decide(const Face& inFace, const Interest& interest,
- pit::Entry& pitEntry) const
+RetxSuppressionResult
+RetxSuppressionFixed::decidePerPitEntry(pit::Entry& pitEntry) const
{
bool isNewPitEntry = !hasPendingOutRecords(pitEntry);
if (isNewPitEntry) {
- return NEW;
+ return RetxSuppressionResult::NEW;
}
- time::steady_clock::TimePoint lastOutgoing = this->getLastOutgoing(pitEntry);
+ time::steady_clock::TimePoint lastOutgoing = getLastOutgoing(pitEntry);
time::steady_clock::TimePoint now = time::steady_clock::now();
time::steady_clock::Duration sinceLastOutgoing = now - lastOutgoing;
bool shouldSuppress = sinceLastOutgoing < m_minRetxInterval;
- return shouldSuppress ? SUPPRESS : FORWARD;
+ return shouldSuppress ? RetxSuppressionResult::SUPPRESS : RetxSuppressionResult::FORWARD;
}
} // namespace fw
diff --git a/daemon/fw/retx-suppression-fixed.hpp b/daemon/fw/retx-suppression-fixed.hpp
index 95baae1..33ee765 100644
--- a/daemon/fw/retx-suppression-fixed.hpp
+++ b/daemon/fw/retx-suppression-fixed.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -26,6 +26,7 @@
#ifndef NFD_DAEMON_FW_RETX_SUPPRESSION_FIXED_HPP
#define NFD_DAEMON_FW_RETX_SUPPRESSION_FIXED_HPP
+#include "algorithm.hpp"
#include "retx-suppression.hpp"
namespace nfd {
@@ -34,7 +35,7 @@
/** \brief a retransmission suppression decision algorithm that
* suppresses retransmissions within a fixed duration
*/
-class RetxSuppressionFixed : public RetxSuppression
+class RetxSuppressionFixed
{
public:
explicit
@@ -43,9 +44,8 @@
/** \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 override;
+ RetxSuppressionResult
+ decidePerPitEntry(pit::Entry& pitEntry) const;
public:
static const time::milliseconds DEFAULT_MIN_RETX_INTERVAL;
diff --git a/daemon/fw/retx-suppression.cpp b/daemon/fw/retx-suppression.cpp
deleted file mode 100644
index 9ae122a..0000000
--- a/daemon/fw/retx-suppression.cpp
+++ /dev/null
@@ -1,45 +0,0 @@
-/* -*- 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 "retx-suppression.hpp"
-
-namespace nfd {
-namespace fw {
-
-time::steady_clock::TimePoint
-RetxSuppression::getLastOutgoing(const pit::Entry& pitEntry) const
-{
- pit::OutRecordCollection::const_iterator lastOutgoing = std::max_element(
- pitEntry.out_begin(), pitEntry.out_end(),
- [] (const pit::OutRecord& a, const pit::OutRecord& b) {
- return a.getLastRenewed() < b.getLastRenewed();
- });
- BOOST_ASSERT(lastOutgoing != pitEntry.out_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 edc2a6d..ad983e7 100644
--- a/daemon/fw/retx-suppression.hpp
+++ b/daemon/fw/retx-suppression.hpp
@@ -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-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -26,42 +26,23 @@
#ifndef NFD_DAEMON_FW_RETX_SUPPRESSION_HPP
#define NFD_DAEMON_FW_RETX_SUPPRESSION_HPP
-#include "strategy.hpp"
+#include "core/common.hpp"
namespace nfd {
namespace fw {
-/** \brief helper for consumer retransmission suppression
- */
-class RetxSuppression : 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
+enum class RetxSuppressionResult {
+ /** \brief Interest is new (not a retransmission)
*/
- virtual Result
- decide(const Face& inFace, const Interest& interest, pit::Entry& pitEntry) const = 0;
+ NEW,
-protected:
- /** \return last out-record time
- * \pre pitEntry has one or more unexpired out-records
+ /** \brief Interest is retransmission and should be forwarded
*/
- time::steady_clock::TimePoint
- getLastOutgoing(const pit::Entry& pitEntry) const;
+ FORWARD,
+
+ /** \brief Interest is retransmission and should be suppressed
+ */
+ SUPPRESS
};
} // namespace fw