face: add best-effort link-layer reliability
refs #3931
Change-Id: I009fabe000f4dd4ceb62acab6b0c735c13112430
diff --git a/daemon/face/generic-link-service.cpp b/daemon/face/generic-link-service.cpp
index 2a7f527..9d1d0fc 100644
--- a/daemon/face/generic-link-service.cpp
+++ b/daemon/face/generic-link-service.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,
@@ -48,12 +48,47 @@
, m_options(options)
, m_fragmenter(m_options.fragmenterOptions, this)
, m_reassembler(m_options.reassemblerOptions, this)
+ , m_reliability(m_options.reliabilityOptions, this)
, m_lastSeqNo(-2)
{
m_reassembler.beforeTimeout.connect(bind([this] { ++this->nReassemblyTimeouts; }));
}
void
+GenericLinkService::setOptions(const GenericLinkService::Options& options)
+{
+ m_options = options;
+ m_fragmenter.setOptions(m_options.fragmenterOptions);
+ m_reassembler.setOptions(m_options.reassemblerOptions);
+ m_reliability.setOptions(m_options.reliabilityOptions);
+}
+
+void
+GenericLinkService::requestIdlePacket()
+{
+ // No need to request Acks to attach to this packet from LpReliability, as they are already
+ // attached in sendLpPacket
+ this->sendLpPacket({});
+}
+
+void
+GenericLinkService::sendLpPacket(lp::Packet&& pkt)
+{
+ const ssize_t mtu = this->getTransport()->getMtu();
+ if (m_options.reliabilityOptions.isEnabled) {
+ m_reliability.piggyback(pkt, mtu);
+ }
+
+ Transport::Packet tp(pkt.wireEncode());
+ if (mtu != MTU_UNLIMITED && tp.packet.size() > static_cast<size_t>(mtu)) {
+ ++this->nOutOverMtu;
+ NFD_LOG_FACE_WARN("attempted to send packet over MTU limit");
+ return;
+ }
+ this->sendPacket(std::move(tp));
+}
+
+void
GenericLinkService::doSendInterest(const Interest& interest)
{
lp::Packet lpPacket(interest.wireEncode());
@@ -115,29 +150,30 @@
}
}
else {
- frags.push_back(pkt);
+ frags.push_back(std::move(pkt));
}
- if (frags.size() > 1) {
- // sequence is needed only if packet is fragmented
- this->assignSequences(frags);
- }
- else {
+ if (frags.size() == 1) {
// even if indexed fragmentation is enabled, the fragmenter should not
// fragment the packet if it can fit in MTU
- BOOST_ASSERT(frags.size() > 0);
BOOST_ASSERT(!frags.front().has<lp::FragIndexField>());
BOOST_ASSERT(!frags.front().has<lp::FragCountField>());
}
- for (const lp::Packet& frag : frags) {
- Transport::Packet tp(frag.wireEncode());
- if (mtu != MTU_UNLIMITED && tp.packet.size() > static_cast<size_t>(mtu)) {
- ++this->nOutOverMtu;
- NFD_LOG_FACE_WARN("attempt to send packet over MTU limit");
- continue;
- }
- this->sendPacket(std::move(tp));
+ // Only assign sequences to fragments if reliability enabled and packet contains a fragment,
+ // or there is more than 1 fragment
+ if ((m_options.reliabilityOptions.isEnabled && frags.front().has<lp::FragmentField>()) ||
+ frags.size() > 1) {
+ // Assign sequences to all fragments
+ this->assignSequences(frags);
+ }
+
+ if (m_options.reliabilityOptions.isEnabled && frags.front().has<lp::FragmentField>()) {
+ m_reliability.observeOutgoing(frags);
+ }
+
+ for (lp::Packet& frag : frags) {
+ this->sendLpPacket(std::move(frag));
}
}
@@ -159,6 +195,10 @@
try {
lp::Packet pkt(packet.packet);
+ if (m_options.reliabilityOptions.isEnabled) {
+ m_reliability.processIncomingPacket(pkt);
+ }
+
if (!pkt.has<lp::FragmentField>()) {
NFD_LOG_FACE_TRACE("received IDLE packet: DROP");
return;
diff --git a/daemon/face/generic-link-service.hpp b/daemon/face/generic-link-service.hpp
index b675ae2..89d4a69 100644
--- a/daemon/face/generic-link-service.hpp
+++ b/daemon/face/generic-link-service.hpp
@@ -32,6 +32,7 @@
#include "link-service.hpp"
#include "lp-fragmenter.hpp"
#include "lp-reassembler.hpp"
+#include "lp-reliability.hpp"
namespace nfd {
namespace face {
@@ -71,10 +72,24 @@
/** \brief count of invalid reassembled network-layer packets dropped
*/
PacketCounter nInNetInvalid;
+
+ /** \brief count of network-layer packets that did not require retransmission of a fragment
+ */
+ PacketCounter nAcknowledged;
+
+ /** \brief count of network-layer packets that had at least one fragment retransmitted, but were
+ * eventually received in full
+ */
+ PacketCounter nRetransmitted;
+
+ /** \brief count of network-layer packets dropped because a fragment reached the maximum number
+ * of retransmissions
+ */
+ PacketCounter nRetxExhausted;
};
/** \brief GenericLinkService is a LinkService that implements the NDNLPv2 protocol
- * \sa http://redmine.named-data.net/projects/nfd/wiki/NDNLPv2
+ * \sa https://redmine.named-data.net/projects/nfd/wiki/NDNLPv2
* \todo #3941 declare GenericLinkServiceCounters as virtual inheritance
*/
class GenericLinkService : public LinkService
@@ -108,6 +123,10 @@
/** \brief options for reassembly
*/
LpReassembler::Options reassemblerOptions;
+
+ /** \brief options for reliability
+ */
+ LpReliability::Options reliabilityOptions;
};
/** \brief counters provided by GenericLinkService
@@ -131,6 +150,17 @@
getCounters() const override;
PROTECTED_WITH_TESTS_ELSE_PRIVATE: // send path
+ /** \brief request an IDLE packet to transmit pending service fields
+ */
+ void
+ requestIdlePacket();
+
+ /** \brief send an LpPacket fragment
+ * \param pkt LpPacket to send
+ */
+ void
+ sendLpPacket(lp::Packet&& pkt);
+
/** \brief send Interest
*/
void
@@ -146,7 +176,7 @@
void
doSendNack(const ndn::lp::Nack& nack) override;
-private:
+private: // send path
/** \brief encode link protocol fields from tags onto an outgoing LpPacket
* \param netPkt network-layer packet to extract tags from
* \param lpPacket LpPacket to add link protocol fields to
@@ -222,11 +252,14 @@
void
decodeNack(const Block& netPkt, const lp::Packet& firstPkt);
-private:
+PROTECTED_WITH_TESTS_ELSE_PRIVATE:
Options m_options;
LpFragmenter m_fragmenter;
LpReassembler m_reassembler;
+ LpReliability m_reliability;
lp::Sequence m_lastSeqNo;
+
+ friend class LpReliability;
};
inline const GenericLinkService::Options&
@@ -235,12 +268,6 @@
return m_options;
}
-inline void
-GenericLinkService::setOptions(const GenericLinkService::Options& options)
-{
- m_options = options;
-}
-
inline const GenericLinkService::Counters&
GenericLinkService::getCounters() const
{
diff --git a/daemon/face/lp-reliability.cpp b/daemon/face/lp-reliability.cpp
new file mode 100644
index 0000000..fb95099
--- /dev/null
+++ b/daemon/face/lp-reliability.cpp
@@ -0,0 +1,309 @@
+/* -*- 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,
+ * 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 "lp-reliability.hpp"
+#include "generic-link-service.hpp"
+#include "transport.hpp"
+
+namespace nfd {
+namespace face {
+
+LpReliability::LpReliability(const LpReliability::Options& options, GenericLinkService* linkService)
+ : m_options(options)
+ , m_linkService(linkService)
+ , m_firstUnackedFrag(m_unackedFrags.begin())
+ , m_isIdleAckTimerRunning(false)
+{
+ BOOST_ASSERT(m_linkService != nullptr);
+
+ BOOST_ASSERT(m_options.idleAckTimerPeriod > time::nanoseconds::zero());
+}
+
+void
+LpReliability::setOptions(const Options& options)
+{
+ BOOST_ASSERT(options.idleAckTimerPeriod > time::nanoseconds::zero());
+
+ if (m_options.isEnabled && !options.isEnabled) {
+ this->stopIdleAckTimer();
+ }
+
+ m_options = options;
+}
+
+const GenericLinkService*
+LpReliability::getLinkService() const
+{
+ return m_linkService;
+}
+
+void
+LpReliability::observeOutgoing(const std::vector<lp::Packet>& frags)
+{
+ BOOST_ASSERT(m_options.isEnabled);
+
+ // The sequence number of the first fragment is used to identify the NetPkt.
+ lp::Sequence netPktIdentifier = frags.at(0).get<lp::SequenceField>();
+ auto& netPkt = m_netPkts.emplace(netPktIdentifier, NetPkt{}).first->second;
+ auto unackedFragsIt = m_unackedFrags.begin();
+ auto netPktUnackedFragsIt = netPkt.unackedFrags.begin();
+
+ for (const lp::Packet& frag : frags) {
+ // Store LpPacket for future retransmissions
+ lp::Sequence seq = frag.get<lp::SequenceField>();
+ unackedFragsIt = m_unackedFrags.emplace_hint(unackedFragsIt, seq, frag);
+ unackedFragsIt->second.rtoTimer =
+ scheduler::schedule(m_rto.computeRto(), bind(&LpReliability::onLpPacketLost, this, seq));
+ unackedFragsIt->second.sendTime = time::steady_clock::now();
+ netPktUnackedFragsIt = netPkt.unackedFrags.insert(netPktUnackedFragsIt, seq);
+ if (m_unackedFrags.size() == 1) {
+ m_firstUnackedFrag = unackedFragsIt;
+ }
+ }
+}
+
+void
+LpReliability::processIncomingPacket(const lp::Packet& pkt)
+{
+ BOOST_ASSERT(m_options.isEnabled);
+
+ auto now = time::steady_clock::now();
+
+ // Extract and parse Acks
+ for (lp::Sequence ackSeq : pkt.list<lp::AckField>()) {
+ auto txFrag = m_unackedFrags.find(ackSeq);
+ if (txFrag == m_unackedFrags.end()) {
+ // Ignore an Ack for an unknown sequence number
+ continue;
+ }
+
+ // Cancel the RTO timer for the acknowledged fragment
+ txFrag->second.rtoTimer.cancel();
+
+ if (txFrag->second.retxCount == 0) {
+ // This sequence had no retransmissions, so use it to calculate the RTO
+ m_rto.addMeasurement(time::duration_cast<RttEstimator::Duration>(now - txFrag->second.sendTime));
+ }
+
+ // Look for Acks with sequence numbers < ackSeq (allowing for wraparound) and consider them lost
+ // if a configurable number of Acks containing greater sequence numbers have been received.
+ auto lostLpPackets = findLostLpPackets(ackSeq);
+
+ // Remove the fragment from the map of unacknowledged sequences and from its associated network
+ // packet (removing the network packet if it has been received in whole by remote host).
+ // Potentially increment the start of the window.
+ onLpPacketAcknowledged(txFrag, getNetPktByFrag(ackSeq));
+
+ // Resend or fail fragments considered lost. This must be done separately from the above
+ // enhanced for loop because onLpPacketLost may delete the fragment from m_unackedFrags.
+ for (const lp::Sequence& seq : lostLpPackets) {
+ this->onLpPacketLost(seq);
+ }
+ }
+
+ // If has Fragment field, extract Sequence and add to AckQueue
+ if (pkt.has<lp::FragmentField>() && pkt.has<lp::SequenceField>()) {
+ m_ackQueue.push(pkt.get<lp::SequenceField>());
+ if (!m_isIdleAckTimerRunning) {
+ this->startIdleAckTimer();
+ }
+ }
+}
+
+void
+LpReliability::piggyback(lp::Packet& pkt, ssize_t mtu)
+{
+ BOOST_ASSERT(m_options.isEnabled);
+
+ int maxAcks = std::numeric_limits<int>::max();
+ if (mtu > 0) {
+ // Ack Type (3 octets) + Ack Length (1 octet) + sizeof(lp::Sequence)
+ size_t ackSize = 3 + 1 + sizeof(lp::Sequence);
+ ndn::EncodingEstimator estimator;
+ maxAcks = (mtu - pkt.wireEncode(estimator)) / ackSize;
+ }
+
+ ssize_t nAcksInPkt = 0;
+ while (!m_ackQueue.empty() && nAcksInPkt < maxAcks) {
+ pkt.add<lp::AckField>(m_ackQueue.front());
+ m_ackQueue.pop();
+ nAcksInPkt++;
+ }
+}
+
+void
+LpReliability::startIdleAckTimer()
+{
+ BOOST_ASSERT(!m_isIdleAckTimerRunning);
+ m_isIdleAckTimerRunning = true;
+
+ m_idleAckTimer = scheduler::schedule(m_options.idleAckTimerPeriod, [this] {
+ while (!m_ackQueue.empty()) {
+ m_linkService->requestIdlePacket();
+ }
+
+ m_isIdleAckTimerRunning = false;
+ });
+}
+
+void
+LpReliability::stopIdleAckTimer()
+{
+ m_idleAckTimer.cancel();
+ m_isIdleAckTimerRunning = false;
+}
+
+std::vector<lp::Sequence>
+LpReliability::findLostLpPackets(lp::Sequence ackSeq)
+{
+ std::vector<lp::Sequence> lostLpPackets;
+
+ for (auto it = m_firstUnackedFrag; ; ++it) {
+ if (it == m_unackedFrags.end()) {
+ it = m_unackedFrags.begin();
+ }
+
+ if (it->first == ackSeq) {
+ break;
+ }
+
+ auto& unackedFrag = it->second;
+
+ unackedFrag.nGreaterSeqAcks++;
+
+ if (unackedFrag.nGreaterSeqAcks >= m_options.seqNumLossThreshold && !unackedFrag.wasTimedOutBySeq) {
+ unackedFrag.wasTimedOutBySeq = true;
+ lostLpPackets.push_back(it->first);
+ }
+ }
+
+ return lostLpPackets;
+}
+
+void
+LpReliability::onLpPacketLost(lp::Sequence seq)
+{
+ auto& txFrag = m_unackedFrags.at(seq);
+ auto netPktIt = getNetPktByFrag(seq);
+
+ // Check if maximum number of retransmissions exceeded
+ if (txFrag.retxCount >= m_options.maxRetx) {
+ // Delete all LpPackets of NetPkt from TransmitCache
+ lp::Sequence firstSeq = *(netPktIt->second.unackedFrags.begin());
+ lp::Sequence lastSeq = *(std::prev(netPktIt->second.unackedFrags.end()));
+ if (lastSeq >= firstSeq) { // Normal case: no wraparound
+ m_unackedFrags.erase(m_unackedFrags.find(firstSeq), std::next(m_unackedFrags.find(lastSeq)));
+ }
+ else { // sequence number wraparound
+ m_unackedFrags.erase(m_unackedFrags.find(firstSeq), m_unackedFrags.end());
+ m_unackedFrags.erase(m_unackedFrags.begin(), std::next(m_unackedFrags.find(lastSeq)));
+ }
+
+ m_netPkts.erase(netPktIt);
+
+ ++m_linkService->nRetxExhausted;
+ }
+ else {
+ txFrag.retxCount++;
+
+ // Start RTO timer for this sequence
+ txFrag.rtoTimer = scheduler::schedule(m_rto.computeRto(),
+ bind(&LpReliability::onLpPacketLost, this, seq));
+
+ // Retransmit fragment
+ m_linkService->sendLpPacket(lp::Packet(txFrag.pkt));
+ }
+}
+
+void
+LpReliability::onLpPacketAcknowledged(std::map<lp::Sequence, LpReliability::UnackedFrag>::iterator fragIt,
+ std::map<lp::Sequence, LpReliability::NetPkt>::iterator netPktIt)
+{
+ lp::Sequence seq = fragIt->first;
+ // We need to store the sequence of the window begin in case we are erasing it from m_unackedFrags
+ lp::Sequence firstUnackedSeq = m_firstUnackedFrag->first;
+ auto nextSeqIt = m_unackedFrags.erase(fragIt);
+ netPktIt->second.unackedFrags.erase(seq);
+
+ if (!m_unackedFrags.empty() && firstUnackedSeq == seq) {
+ // If "first" fragment in send window (allowing for wraparound), increment window begin
+ if (nextSeqIt == m_unackedFrags.end()) {
+ m_firstUnackedFrag = m_unackedFrags.begin();
+ }
+ else {
+ m_firstUnackedFrag = nextSeqIt;
+ }
+ }
+
+ // Check if network-layer packet completely received. If so, delete network packet mapping
+ // and increment counter
+ if (netPktIt->second.unackedFrags.empty()) {
+ if (netPktIt->second.didRetx) {
+ ++m_linkService->nRetransmitted;
+ }
+ else {
+ ++m_linkService->nAcknowledged;
+ }
+ m_netPkts.erase(netPktIt);
+ }
+}
+
+std::map<lp::Sequence, LpReliability::NetPkt>::iterator
+LpReliability::getNetPktByFrag(lp::Sequence seq)
+{
+ BOOST_ASSERT(!m_netPkts.empty());
+ auto it = m_netPkts.lower_bound(seq);
+ if (it == m_netPkts.end()) {
+ // This can happen because of sequence number wraparound in the middle of a network packet.
+ // In this case, the network packet will be at the end of m_netPkts and we will need to
+ // decrement the iterator to m_netPkts.end() to the one before it.
+ --it;
+ }
+ return it;
+}
+
+LpReliability::UnackedFrag::UnackedFrag(lp::Packet pkt)
+ : pkt(std::move(pkt))
+ , sendTime(time::steady_clock::now())
+ , retxCount(0)
+ , nGreaterSeqAcks(0)
+ , wasTimedOutBySeq(false)
+{
+}
+
+LpReliability::NetPkt::NetPkt()
+ : didRetx(false)
+{
+}
+
+std::ostream&
+operator<<(std::ostream& os, const FaceLogHelper<LpReliability>& flh)
+{
+ os << FaceLogHelper<LinkService>(*flh.obj.getLinkService());
+ return os;
+}
+
+} // namespace face
+} // namespace nfd
diff --git a/daemon/face/lp-reliability.hpp b/daemon/face/lp-reliability.hpp
new file mode 100644
index 0000000..47d5973
--- /dev/null
+++ b/daemon/face/lp-reliability.hpp
@@ -0,0 +1,195 @@
+/* -*- 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,
+ * 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_FACE_LP_RELIABILITY_HPP
+#define NFD_DAEMON_FACE_LP_RELIABILITY_HPP
+
+#include "core/common.hpp"
+#include "core/rtt-estimator.hpp"
+#include "core/scheduler.hpp"
+
+#include "face-log.hpp"
+
+#include <ndn-cxx/lp/packet.hpp>
+#include <ndn-cxx/lp/sequence.hpp>
+
+#include <queue>
+
+namespace nfd {
+namespace face {
+
+class GenericLinkService;
+
+/** \brief provides for reliable sending and receiving of link-layer packets
+ * \sa https://redmine.named-data.net/projects/nfd/wiki/NDNLPv2
+ */
+class LpReliability : noncopyable
+{
+public:
+ struct Options
+ {
+ /** \brief enables link-layer reliability
+ */
+ bool isEnabled = false;
+
+ /** \brief maximum number of retransmissions for an LpPacket
+ */
+ size_t maxRetx = 3;
+
+ /** \brief period between sending pending Acks in an IDLE packet
+ */
+ time::nanoseconds idleAckTimerPeriod = time::milliseconds(5);
+
+ /** \brief a fragment is considered lost if this number of fragments with greater sequence
+ * numbers are acknowledged
+ */
+ size_t seqNumLossThreshold = 3;
+ };
+
+ LpReliability(const Options& options, GenericLinkService* linkService);
+
+ /** \brief set options for reliability
+ */
+ void
+ setOptions(const Options& options);
+
+ /** \return GenericLinkService that owns this instance
+ *
+ * This is only used for logging, and may be nullptr.
+ */
+ const GenericLinkService*
+ getLinkService() const;
+
+ /** \brief observe outgoing fragment(s) of a network packet
+ * \param frags fragments of network packet
+ */
+ void
+ observeOutgoing(const std::vector<lp::Packet>& frags);
+
+ /** \brief extract and parse all Acks and add Ack for contained Fragment (if any) to AckQueue
+ * \param pkt incoming LpPacket
+ */
+ void
+ processIncomingPacket(const lp::Packet& pkt);
+
+ /** \brief called by GenericLinkService to attach Acks onto an outgoing LpPacket
+ * \param pkt outgoing LpPacket to attach Acks to
+ * \param mtu MTU of the Transport
+ */
+ void
+ piggyback(lp::Packet& pkt, ssize_t mtu);
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /** \brief start the idle Ack timer
+ *
+ * This timer requests an IDLE packet to acknowledge pending fragments not already piggybacked.
+ * It is called regularly on a period configured in Options::idleAckTimerPeriod. This allows Acks
+ * to be returned to the sender, even if the link goes idle.
+ */
+ void
+ startIdleAckTimer();
+
+ /** \brief cancel the idle Ack timer
+ */
+ void
+ stopIdleAckTimer();
+
+private:
+ /** \brief find and mark as lost fragments where a configurable number of Acks have been received
+ * for greater sequence numbers
+ * \param ackSeq sequence number of received Ack
+ * \return vector containing sequence numbers marked lost by this mechanism
+ */
+ std::vector<lp::Sequence>
+ findLostLpPackets(lp::Sequence ackSeq);
+
+ /** \brief resend (or declare as lost) a lost fragment
+ */
+ void
+ onLpPacketLost(lp::Sequence seq);
+
+ class UnackedFrag;
+ class NetPkt;
+
+ /** \brief remove the fragment with the given sequence number from the map of unacknowledged
+ * fragments as well as its associated network packet
+ * \param fragIt iterator to fragment to be removed
+ *
+ * If the given sequence marks the beginning of the send window, the window will be incremented.
+ * If the associated network packet has been fully transmitted, it will be removed.
+ */
+ void
+ onLpPacketAcknowledged(std::map<lp::Sequence, UnackedFrag>::iterator fragIt,
+ std::map<lp::Sequence, NetPkt>::iterator netPktIt);
+
+ std::map<lp::Sequence, NetPkt>::iterator
+ getNetPktByFrag(lp::Sequence seq);
+
+private:
+ /** \brief contains a sent fragment that has not been acknowledged and associated data
+ */
+ class UnackedFrag
+ {
+ public:
+ // Allows implicit conversion from an lp::Packet
+ UnackedFrag(lp::Packet pkt);
+
+ public:
+ lp::Packet pkt;
+ scheduler::ScopedEventId rtoTimer;
+ time::steady_clock::TimePoint sendTime;
+ size_t retxCount;
+ size_t nGreaterSeqAcks; //!< number of Acks received for sequences greater than this fragment
+ bool wasTimedOutBySeq; //!< whether this fragment has been timed out by the sequence number mechanic
+ };
+
+ /** \brief contains a network-layer packet with unacknowledged fragments
+ */
+ class NetPkt
+ {
+ public:
+ NetPkt();
+
+ public:
+ std::set<lp::Sequence> unackedFrags;
+ bool didRetx;
+ };
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ Options m_options;
+ GenericLinkService* m_linkService;
+ std::map<lp::Sequence, UnackedFrag> m_unackedFrags;
+ std::map<lp::Sequence, UnackedFrag>::iterator m_firstUnackedFrag;
+ std::map<lp::Sequence, NetPkt> m_netPkts;
+ std::queue<lp::Sequence> m_ackQueue;
+ scheduler::ScopedEventId m_idleAckTimer;
+ bool m_isIdleAckTimerRunning;
+ RttEstimator m_rto;
+};
+
+} // namespace face
+} // namespace nfd
+
+#endif // NFD_DAEMON_FACE_LP_RELIABILITY_HPP
diff --git a/daemon/fw/access-strategy.hpp b/daemon/fw/access-strategy.hpp
index 31f2180..4374fa2 100644
--- a/daemon/fw/access-strategy.hpp
+++ b/daemon/fw/access-strategy.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,
@@ -27,7 +27,7 @@
#define NFD_DAEMON_FW_ACCESS_STRATEGY_HPP
#include "strategy.hpp"
-#include "rtt-estimator.hpp"
+#include "core/rtt-estimator.hpp"
#include "retx-suppression-fixed.hpp"
#include <unordered_set>
#include <unordered_map>
@@ -56,11 +56,11 @@
getStrategyName();
public: // triggers
- virtual void
+ void
afterReceiveInterest(const Face& inFace, const Interest& interest,
const shared_ptr<pit::Entry>& pitEntry) override;
- virtual void
+ void
beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
const Face& inFace, const Data& data) override;
diff --git a/daemon/fw/asf-measurements.hpp b/daemon/fw/asf-measurements.hpp
index 0988837..c6ff096 100644
--- a/daemon/fw/asf-measurements.hpp
+++ b/daemon/fw/asf-measurements.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,7 +26,7 @@
#ifndef NFD_DAEMON_FW_ASF_MEASUREMENTS_HPP
#define NFD_DAEMON_FW_ASF_MEASUREMENTS_HPP
-#include "fw/rtt-estimator.hpp"
+#include "core/rtt-estimator.hpp"
#include "fw/strategy-info.hpp"
#include "table/measurements-accessor.hpp"
diff --git a/daemon/fw/rtt-estimator.cpp b/daemon/fw/rtt-estimator.cpp
deleted file mode 100644
index 97b2ab0..0000000
--- a/daemon/fw/rtt-estimator.cpp
+++ /dev/null
@@ -1,79 +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 "rtt-estimator.hpp"
-
-namespace nfd {
-
-RttEstimator::RttEstimator(uint16_t maxMultiplier, Duration minRto, double gain)
- : m_maxMultiplier(maxMultiplier)
- , m_minRto(minRto.count())
- , m_rtt(RttEstimator::getInitialRtt().count())
- , m_gain(gain)
- , m_variance(0)
- , m_multiplier(1)
- , m_nSamples(0)
-{
-}
-
-void
-RttEstimator::addMeasurement(Duration measure)
-{
- double m = static_cast<double>(measure.count());
- if (m_nSamples > 0) {
- double err = m - m_rtt;
- double gErr = err * m_gain;
- m_rtt += gErr;
- double difference = std::abs(err) - m_variance;
- m_variance += difference * m_gain;
- } else {
- m_rtt = m;
- m_variance = m;
- }
- ++m_nSamples;
- m_multiplier = 1;
-}
-
-void
-RttEstimator::incrementMultiplier()
-{
- m_multiplier = std::min(static_cast<uint16_t>(m_multiplier + 1), m_maxMultiplier);
-}
-
-void
-RttEstimator::doubleMultiplier()
-{
- m_multiplier = std::min(static_cast<uint16_t>(m_multiplier * 2), m_maxMultiplier);
-}
-
-RttEstimator::Duration
-RttEstimator::computeRto() const
-{
- double rto = std::max(m_minRto, m_rtt + 4 * m_variance);
- rto *= m_multiplier;
- return Duration(static_cast<Duration::rep>(rto));
-}
-
-} // namespace nfd
diff --git a/daemon/fw/rtt-estimator.hpp b/daemon/fw/rtt-estimator.hpp
deleted file mode 100644
index b692083..0000000
--- a/daemon/fw/rtt-estimator.hpp
+++ /dev/null
@@ -1,83 +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/>.
- */
-
-#ifndef NFD_DAEMON_FW_RTT_ESTIMATOR_HPP
-#define NFD_DAEMON_FW_RTT_ESTIMATOR_HPP
-
-#include "core/common.hpp"
-
-namespace nfd {
-
-/**
- * \brief implements the Mean-Deviation RTT estimator
- *
- * reference: ns3::RttMeanDeviation
- *
- * This RttEstimator algorithm is designed for TCP, which is a continuous stream.
- * NDN Interest-Data traffic is not always a continuous stream,
- * so NDN may need a different RttEstimator.
- * The design of a more suitable RttEstimator is a research question.
- */
-class RttEstimator
-{
-public:
- typedef time::microseconds Duration;
-
- static Duration
- getInitialRtt(void)
- {
- return time::seconds(1);
- }
-
- RttEstimator(uint16_t maxMultiplier = 16,
- Duration minRto = time::milliseconds(1),
- double gain = 0.1);
-
- void
- addMeasurement(Duration measure);
-
- void
- incrementMultiplier();
-
- void
- doubleMultiplier();
-
- Duration
- computeRto() const;
-
-private:
- uint16_t m_maxMultiplier;
- double m_minRto;
-
- double m_rtt;
- double m_gain;
- double m_variance;
- uint16_t m_multiplier;
- uint32_t m_nSamples;
-};
-
-} // namespace nfd
-
-#endif // NFD_DAEMON_FW_RTT_ESTIMATOR_HPP