face: deduplicate received LpPackets with reliability
refs #5079
Change-Id: I19ad959ba736253a750997fa468d419c93425686
diff --git a/daemon/face/generic-link-service.cpp b/daemon/face/generic-link-service.cpp
index 1fecdb6..7e32fc7 100644
--- a/daemon/face/generic-link-service.cpp
+++ b/daemon/face/generic-link-service.cpp
@@ -125,6 +125,14 @@
}
void
+GenericLinkService::assignSequences(std::vector<lp::Packet>& pkts)
+{
+ std::for_each(pkts.begin(), pkts.end(), [this] (lp::Packet& pkt) {
+ pkt.set<lp::SequenceField>(++m_lastSeqNo);
+ });
+}
+
+void
GenericLinkService::encodeLpFields(const ndn::PacketBase& netPkt, lp::Packet& lpPacket)
{
if (m_options.allowLocalFields) {
@@ -200,8 +208,8 @@
BOOST_ASSERT(!frags.front().has<lp::FragCountField>());
}
- // Only assign sequences to fragments if packet contains more than 1 fragment
- if (frags.size() > 1) {
+ // Only assign sequences to fragments if reliability enabled or if packet contains >1 fragment
+ if (m_options.reliabilityOptions.isEnabled || frags.size() > 1) {
// Assign sequences to all fragments
this->assignSequences(frags);
}
@@ -216,18 +224,6 @@
}
void
-GenericLinkService::assignSequence(lp::Packet& pkt)
-{
- pkt.set<lp::SequenceField>(++m_lastSeqNo);
-}
-
-void
-GenericLinkService::assignSequences(std::vector<lp::Packet>& pkts)
-{
- std::for_each(pkts.begin(), pkts.end(), [this] (auto& pkt) { this->assignSequence(pkt); });
-}
-
-void
GenericLinkService::checkCongestionLevel(lp::Packet& pkt)
{
ssize_t sendQueueLength = getTransport()->getSendQueueLength();
@@ -279,7 +275,11 @@
lp::Packet pkt(packet);
if (m_options.reliabilityOptions.isEnabled) {
- m_reliability.processIncomingPacket(pkt);
+ if (!m_reliability.processIncomingPacket(pkt)) {
+ NFD_LOG_FACE_TRACE("received duplicate fragment: DROP");
+ ++this->nDuplicateSequence;
+ return;
+ }
}
if (!pkt.has<lp::FragmentField>()) {
diff --git a/daemon/face/generic-link-service.hpp b/daemon/face/generic-link-service.hpp
index 3137555..e30a3e6 100644
--- a/daemon/face/generic-link-service.hpp
+++ b/daemon/face/generic-link-service.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2019, Regents of the University of California,
+ * Copyright (c) 2014-2020, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -81,6 +81,10 @@
*/
PacketCounter nRetxExhausted;
+ /** \brief count of LpPackets dropped due to duplicate Sequence numbers
+ */
+ PacketCounter nDuplicateSequence;
+
/** \brief count of outgoing LpPackets that were marked with congestion marks
*/
PacketCounter nCongestionMarked;
@@ -199,6 +203,11 @@
void
doSendNack(const ndn::lp::Nack& nack, const EndpointId& endpointId) OVERRIDE_WITH_TESTS_ELSE_FINAL;
+ /** \brief assign consecutive sequence numbers to LpPackets
+ */
+ void
+ assignSequences(std::vector<lp::Packet>& pkts);
+
private: // send path
/** \brief encode link protocol fields from tags onto an outgoing LpPacket
* \param netPkt network-layer packet to extract tags from
@@ -215,16 +224,6 @@
void
sendNetPacket(lp::Packet&& pkt, const EndpointId& endpointId, bool isInterest);
- /** \brief assign a sequence number to an LpPacket
- */
- void
- assignSequence(lp::Packet& pkt);
-
- /** \brief assign consecutive sequence numbers to LpPackets
- */
- void
- assignSequences(std::vector<lp::Packet>& pkts);
-
/** \brief if the send queue is found to be congested, add a congestion mark to the packet
* according to CoDel
* \sa https://tools.ietf.org/html/rfc8289
diff --git a/daemon/face/lp-reliability.cpp b/daemon/face/lp-reliability.cpp
index e9a4914..21189be 100644
--- a/daemon/face/lp-reliability.cpp
+++ b/daemon/face/lp-reliability.cpp
@@ -73,6 +73,9 @@
netPkt->unackedFrags.reserve(frags.size());
for (lp::Packet& frag : frags) {
+ // Non-IDLE packets are required to have assigned Sequence numbers with LpReliability enabled
+ BOOST_ASSERT(frag.has<lp::SequenceField>());
+
// Assign TxSequence number
lp::Sequence txSeq = assignTxSequence(frag);
@@ -83,11 +86,11 @@
std::forward_as_tuple(frag));
unackedFragsIt->second.sendTime = sendTime;
auto rto = m_rttEst.getEstimatedRto();
- NFD_LOG_FACE_TRACE("transmitting txseq=" << txSeq << ", rto=" <<
+ lp::Sequence seq = frag.get<lp::SequenceField>();
+ NFD_LOG_FACE_TRACE("transmitting seq=" << seq << ", txseq=" << txSeq << ", rto=" <<
time::duration_cast<time::milliseconds>(rto).count() << "ms");
unackedFragsIt->second.rtoTimer = getScheduler().schedule(rto, [=] {
- NFD_LOG_FACE_TRACE("rto timer expired for txseq=" << txSeq);
- onLpPacketLost(txSeq);
+ onLpPacketLost(txSeq, true);
});
unackedFragsIt->second.netPkt = netPkt;
@@ -100,19 +103,20 @@
}
}
-void
+bool
LpReliability::processIncomingPacket(const lp::Packet& pkt)
{
BOOST_ASSERT(m_options.isEnabled);
+ bool isDuplicate = false;
auto now = time::steady_clock::now();
// Extract and parse Acks
- for (lp::Sequence ackSeq : pkt.list<lp::AckField>()) {
- auto fragIt = m_unackedFrags.find(ackSeq);
+ for (lp::Sequence ackTxSeq : pkt.list<lp::AckField>()) {
+ auto fragIt = m_unackedFrags.find(ackTxSeq);
if (fragIt == m_unackedFrags.end()) {
// Ignore an Ack for an unknown TxSequence number
- NFD_LOG_FACE_DEBUG("received ack for unknown txseq=" << ackSeq);
+ NFD_LOG_FACE_DEBUG("received ack for unknown txseq=" << ackTxSeq);
continue;
}
auto& frag = fragIt->second;
@@ -121,17 +125,19 @@
frag.rtoTimer.cancel();
if (frag.retxCount == 0) {
- NFD_LOG_FACE_TRACE("received ack for txseq=" << ackSeq << ", retx=0, rtt=" <<
+ NFD_LOG_FACE_TRACE("received ack for seq=" << frag.pkt.get<lp::SequenceField>() << ", txseq=" <<
+ ackTxSeq << ", retx=0, rtt=" <<
time::duration_cast<time::milliseconds>(now - frag.sendTime).count() << "ms");
// This sequence had no retransmissions, so use it to estimate the RTO
m_rttEst.addMeasurement(now - frag.sendTime);
}
else {
- NFD_LOG_FACE_TRACE("received ack for txseq=" << ackSeq << ", retx=" << frag.retxCount);
+ NFD_LOG_FACE_TRACE("received ack for seq=" << frag.pkt.get<lp::SequenceField>() << ", txseq=" <<
+ ackTxSeq << ", retx=" << frag.retxCount);
}
- // Look for frags with TxSequence numbers < ackSeq (allowing for wraparound) and consider them
- // lost if a configurable number of Acks containing greater TxSequence numbers have been
+ // Look for frags with TxSequence numbers < ackTxSeq (allowing for wraparound) and consider
+ // them lost if a configurable number of Acks containing greater TxSequence numbers have been
// received.
auto lostLpPackets = findLostLpPackets(fragIt);
@@ -148,9 +154,8 @@
// Resend or fail fragments considered lost. Potentially increment the start of the window.
for (lp::Sequence txSeq : lostLpPackets) {
if (removedLpPackets.find(txSeq) == removedLpPackets.end()) {
- NFD_LOG_FACE_TRACE("txseq=" << txSeq << " considered lost from acks for more recent txseqs");
- auto removedThisTxSeq = onLpPacketLost(txSeq);
- for (auto removedTxSeq : removedThisTxSeq) {
+ auto removedTxSeqs = onLpPacketLost(txSeq, false);
+ for (auto removedTxSeq : removedTxSeqs) {
removedLpPackets.insert(removedTxSeq);
}
}
@@ -161,8 +166,27 @@
if (pkt.has<lp::FragmentField>() && pkt.has<lp::TxSequenceField>()) {
NFD_LOG_FACE_TRACE("queueing ack for remote txseq=" << pkt.get<lp::TxSequenceField>());
m_ackQueue.push(pkt.get<lp::TxSequenceField>());
+
+ // Check for received frames with duplicate Sequences
+ if (pkt.has<lp::SequenceField>()) {
+ lp::Sequence pktSequence = pkt.get<lp::SequenceField>();
+ isDuplicate = m_recentRecvSeqs.count(pktSequence) > 0;
+ // Check for recent received Sequences to remove
+ auto now = time::steady_clock::now();
+ auto rto = m_rttEst.getEstimatedRto();
+ while (m_recentRecvSeqsQueue.size() > 0 &&
+ now > m_recentRecvSeqs[m_recentRecvSeqsQueue.front()] + rto) {
+ m_recentRecvSeqs.erase(m_recentRecvSeqsQueue.front());
+ m_recentRecvSeqsQueue.pop();
+ }
+ m_recentRecvSeqs.emplace(pktSequence, now);
+ m_recentRecvSeqsQueue.push(pktSequence);
+ }
+
startIdleAckTimer();
}
+
+ return !isDuplicate;
}
void
@@ -179,7 +203,7 @@
remainingSpace -= pktSize;
while (!m_ackQueue.empty()) {
- lp::Sequence ackSeq = m_ackQueue.front();
+ lp::Sequence ackTxSeq = m_ackQueue.front();
// Ack size = Ack TLV-TYPE (3 octets) + TLV-LENGTH (1 octet) + lp::Sequence (8 octets)
const ssize_t ackSize = tlv::sizeOfVarNumber(lp::tlv::Ack) +
tlv::sizeOfVarNumber(sizeof(lp::Sequence)) +
@@ -189,9 +213,9 @@
break;
}
- NFD_LOG_FACE_TRACE("piggybacking ack for remote txseq=" << ackSeq);
+ NFD_LOG_FACE_TRACE("piggybacking ack for remote txseq=" << ackTxSeq);
- pkt.add<lp::AckField>(ackSeq);
+ pkt.add<lp::AckField>(ackTxSeq);
m_ackQueue.pop();
remainingSpace -= ackSize;
}
@@ -239,8 +263,8 @@
auto& unackedFrag = it->second;
unackedFrag.nGreaterSeqAcks++;
- NFD_LOG_FACE_TRACE("received ack=" << ackIt->first << ", out-of-order for txseq=" <<
- it->first << ", out-of-order count=" << unackedFrag.nGreaterSeqAcks);
+ NFD_LOG_FACE_TRACE("received ack=" << ackIt->first << " before=" << it->first <<
+ ", before count=" << unackedFrag.nGreaterSeqAcks);
if (unackedFrag.nGreaterSeqAcks >= m_options.seqNumLossThreshold) {
lostLpPackets.push_back(it->first);
@@ -251,7 +275,7 @@
}
std::vector<lp::Sequence>
-LpReliability::onLpPacketLost(lp::Sequence txSeq)
+LpReliability::onLpPacketLost(lp::Sequence txSeq, bool isTimeout)
{
BOOST_ASSERT(m_unackedFrags.count(txSeq) > 0);
auto txSeqIt = m_unackedFrags.find(txSeq);
@@ -260,10 +284,19 @@
txFrag.rtoTimer.cancel();
auto netPkt = txFrag.netPkt;
std::vector<lp::Sequence> removedThisTxSeq;
+ lp::Sequence seq = txFrag.pkt.get<lp::SequenceField>();
+
+ if (isTimeout) {
+ NFD_LOG_FACE_TRACE("rto timer expired for seq=" << seq << ", txseq=" << txSeq);
+ }
+ else { // lost due to out-of-order TxSeqs
+ NFD_LOG_FACE_TRACE("seq=" << seq << ", txseq=" << txSeq <<
+ " considered lost from acks for more recent txseqs");
+ }
// Check if maximum number of retransmissions exceeded
if (txFrag.retxCount >= m_options.maxRetx) {
- NFD_LOG_FACE_DEBUG("txseq=" << txSeq << " exceeded allowed retransmissions: DROP");
+ NFD_LOG_FACE_DEBUG("seq=" << seq << " exceeded allowed retransmissions: DROP");
// Delete all LpPackets of NetPkt from m_unackedFrags (except this one)
for (size_t i = 0; i < netPkt->unackedFrags.size(); i++) {
if (netPkt->unackedFrags[i] != txSeqIt) {
@@ -316,14 +349,13 @@
m_linkService->sendLpPacket(lp::Packet(newTxFrag.pkt), 0);
auto rto = m_rttEst.getEstimatedRto();
- NFD_LOG_FACE_TRACE("retransmitting txseq=" << txSeq << " as " << newTxSeq << ", retx=" <<
+ NFD_LOG_FACE_TRACE("retransmitting seq=" << seq << ", txseq=" << newTxSeq << ", retx=" <<
txFrag.retxCount << ", rto=" <<
time::duration_cast<time::milliseconds>(rto).count() << "ms");
// Start RTO timer for this sequence
newTxFrag.rtoTimer = getScheduler().schedule(rto, [=] {
- NFD_LOG_FACE_TRACE("rto timer expired for txseq=" << newTxSeq);
- onLpPacketLost(newTxSeq);
+ onLpPacketLost(newTxSeq, true);
});
}
diff --git a/daemon/face/lp-reliability.hpp b/daemon/face/lp-reliability.hpp
index ad7c968..1ea2b9a 100644
--- a/daemon/face/lp-reliability.hpp
+++ b/daemon/face/lp-reliability.hpp
@@ -93,8 +93,9 @@
/** \brief extract and parse all Acks and add Ack for contained Fragment (if any) to AckQueue
* \param pkt incoming LpPacket
+ * \return whether incoming LpPacket is new and not a duplicate
*/
- void
+ bool
processIncomingPacket(const lp::Packet& pkt);
/** \brief called by GenericLinkService to attach Acks onto an outgoing LpPacket
@@ -139,7 +140,7 @@
* \return vector of the TxSequences of fragments removed due to a network packet being removed
*/
std::vector<lp::Sequence>
- onLpPacketLost(lp::Sequence txSeq);
+ onLpPacketLost(lp::Sequence txSeq, bool isTimeout);
/** \brief remove the fragment with the given sequence number from the map of unacknowledged
* fragments, as well as its associated network packet (if any)
@@ -210,6 +211,8 @@
*/
UnackedFrags::iterator m_firstUnackedFrag;
std::queue<lp::Sequence> m_ackQueue;
+ std::map<lp::Sequence, time::steady_clock::TimePoint> m_recentRecvSeqs;
+ std::queue<lp::Sequence> m_recentRecvSeqsQueue;
lp::Sequence m_lastTxSeqNo;
scheduler::ScopedEventId m_idleAckTimer;
ndn::util::RttEstimator m_rttEst;
diff --git a/tests/daemon/face/generic-link-service.t.cpp b/tests/daemon/face/generic-link-service.t.cpp
index 693d393..e6b85d1 100644
--- a/tests/daemon/face/generic-link-service.t.cpp
+++ b/tests/daemon/face/generic-link-service.t.cpp
@@ -496,6 +496,33 @@
BOOST_CHECK(nack1pkt.has<lp::TxSequenceField>());
}
+BOOST_AUTO_TEST_CASE(DropDuplicatePacket)
+{
+ // Initialize with Options that enables reliability
+ GenericLinkService::Options options;
+ options.allowLocalFields = false;
+ options.reliabilityOptions.isEnabled = true;
+ initialize(options);
+
+ Interest interest("/test/prefix");
+ interest.setCanBePrefix(false);
+ lp::Packet pkt1;
+ pkt1.add<lp::FragmentField>({interest.wireEncode().begin(), interest.wireEncode().end()});
+ pkt1.add<lp::SequenceField>(7);
+ pkt1.add<lp::TxSequenceField>(12);
+ transport->receivePacket(pkt1.wireEncode());
+ BOOST_CHECK_EQUAL(service->getCounters().nInInterests, 1);
+ BOOST_CHECK_EQUAL(service->getCounters().nDuplicateSequence, 0);
+
+ lp::Packet pkt2;
+ pkt2.add<lp::FragmentField>({interest.wireEncode().begin(), interest.wireEncode().end()});
+ pkt2.add<lp::SequenceField>(7);
+ pkt2.add<lp::TxSequenceField>(13);
+ transport->receivePacket(pkt2.wireEncode());
+ BOOST_CHECK_EQUAL(service->getCounters().nInInterests, 1);
+ BOOST_CHECK_EQUAL(service->getCounters().nDuplicateSequence, 1);
+}
+
BOOST_AUTO_TEST_SUITE_END() // Reliability
// congestion detection and marking
diff --git a/tests/daemon/face/lp-reliability.t.cpp b/tests/daemon/face/lp-reliability.t.cpp
index 91bf094..9c14997 100644
--- a/tests/daemon/face/lp-reliability.t.cpp
+++ b/tests/daemon/face/lp-reliability.t.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2019, Regents of the University of California,
+ * Copyright (c) 2014-2020, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -57,6 +57,7 @@
interest.setCanBePrefix(false);
lp::Packet pkt;
pkt.add<lp::FragmentField>({interest.wireEncode().begin(), interest.wireEncode().end()});
+ assignSequences(frags);
m_reliability.handleOutgoing(frags, std::move(pkt), true);
}
@@ -118,18 +119,18 @@
}
/** \brief make an LpPacket with fragment of specified size
- * \param pktNo packet identifier, which can be extracted with \p getPktNo
+ * \param pktNum packet identifier, which can be extracted with \p getPktNum
* \param payloadSize total payload size; if this is less than 4, 4 will be used
*/
static lp::Packet
- makeFrag(uint32_t pktNo, size_t payloadSize = 4)
+ makeFrag(uint32_t pktNum, size_t payloadSize = 4)
{
payloadSize = std::max(payloadSize, static_cast<size_t>(4));
BOOST_ASSERT(payloadSize <= 255);
lp::Packet pkt;
ndn::Buffer buf(payloadSize);
- std::memcpy(buf.data(), &pktNo, sizeof(pktNo));
+ std::memcpy(buf.data(), &pktNum, sizeof(pktNum));
pkt.set<lp::FragmentField>({buf.cbegin(), buf.cend()});
return pkt;
}
@@ -138,7 +139,7 @@
* \retval 0 packet identifier cannot be extracted
*/
static uint32_t
- getPktNo(const lp::Packet& pkt)
+ getPktNum(const lp::Packet& pkt)
{
BOOST_ASSERT(pkt.has<lp::FragmentField>());
@@ -185,10 +186,10 @@
BOOST_REQUIRE_EQUAL(transport->sentPackets.size(), 1);
lp::Packet cached1(transport->sentPackets.front().packet);
BOOST_REQUIRE(cached1.has<lp::TxSequenceField>());
- BOOST_CHECK(!cached1.has<lp::SequenceField>());
+ BOOST_CHECK(cached1.has<lp::SequenceField>());
lp::Sequence firstTxSeq = cached1.get<lp::TxSequenceField>();
BOOST_CHECK_EQUAL(firstTxSeq, 2);
- BOOST_CHECK_EQUAL(getPktNo(cached1), 1024);
+ BOOST_CHECK_EQUAL(getPktNum(cached1), 1024);
BOOST_CHECK_EQUAL(linkService->getCounters().nAcknowledged, 0);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetransmitted, 0);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetxExhausted, 0);
@@ -316,15 +317,18 @@
lp::Packet cached1(transport->sentPackets.at(0).packet);
BOOST_REQUIRE(cached1.has<lp::TxSequenceField>());
BOOST_CHECK_EQUAL(cached1.get<lp::TxSequenceField>(), 2);
- BOOST_CHECK_EQUAL(getPktNo(cached1), 2048);
+ BOOST_CHECK(cached1.has<lp::SequenceField>());
+ BOOST_CHECK_EQUAL(getPktNum(cached1), 2048);
lp::Packet cached2(transport->sentPackets.at(1).packet);
BOOST_REQUIRE(cached2.has<lp::TxSequenceField>());
BOOST_CHECK_EQUAL(cached2.get<lp::TxSequenceField>(), 3);
- BOOST_CHECK_EQUAL(getPktNo(cached2), 2049);
+ BOOST_CHECK(cached2.has<lp::SequenceField>());
+ BOOST_CHECK_EQUAL(getPktNum(cached2), 2049);
lp::Packet cached3(transport->sentPackets.at(2).packet);
BOOST_REQUIRE(cached3.has<lp::TxSequenceField>());
BOOST_CHECK_EQUAL(cached3.get<lp::TxSequenceField>(), 4);
- BOOST_CHECK_EQUAL(getPktNo(cached3), 2050);
+ BOOST_CHECK(cached3.has<lp::SequenceField>());
+ BOOST_CHECK_EQUAL(getPktNum(cached3), 2050);
BOOST_CHECK_EQUAL(linkService->getCounters().nAcknowledged, 0);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetransmitted, 0);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetxExhausted, 0);
@@ -338,9 +342,9 @@
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(2), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(3), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(4), 1);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(2).pkt), 2048);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(3).pkt), 2049);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(4).pkt), 2050);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(2).pkt), 2048);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(3).pkt), 2049);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(4).pkt), 2050);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(2).retxCount, 0);
BOOST_REQUIRE(reliability->m_unackedFrags.at(2).netPkt);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(3).retxCount, 0);
@@ -366,15 +370,15 @@
// 2049 rto: 1000ms, txSeq: 5, started T+250ms, retx 1
// 2050 rto: 1000ms, txSeq: 4, started T+0ms, retx 0
advanceClocks(1_ms, 250);
- reliability->onLpPacketLost(3);
+ reliability->onLpPacketLost(3, true);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(2), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(3), 0);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(5), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(4), 1);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(2).pkt), 2048);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(5).pkt), 2049);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(4).pkt), 2050);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(2).pkt), 2048);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(5).pkt), 2049);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(4).pkt), 2050);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(2).retxCount, 0);
BOOST_REQUIRE(reliability->m_unackedFrags.at(2).netPkt);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(5).retxCount, 1);
@@ -400,15 +404,15 @@
// 2049 rto: 1000ms, txSeq: 6, started T+500ms, retx 2
// 2050 rto: 1000ms, txSeq: 4, started T+0ms, retx 0
advanceClocks(1_ms, 250);
- reliability->onLpPacketLost(5);
+ reliability->onLpPacketLost(5, true);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(2), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(5), 0);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(6), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(4), 1);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(2).pkt), 2048);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(6).pkt), 2049);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(4).pkt), 2050);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(2).pkt), 2048);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(6).pkt), 2049);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(4).pkt), 2050);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(2).retxCount, 0);
BOOST_REQUIRE(reliability->m_unackedFrags.at(2).netPkt);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(6).retxCount, 2);
@@ -434,15 +438,15 @@
// 2049 rto: 1000ms, txSeq: 7, started T+750ms, retx 3
// 2050 rto: 1000ms, txSeq: 4, started T+0ms, retx 0
advanceClocks(1_ms, 250);
- reliability->onLpPacketLost(6);
+ reliability->onLpPacketLost(6, true);
BOOST_REQUIRE_EQUAL(reliability->m_unackedFrags.count(2), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(6), 0);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(7), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(4), 1);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(2).pkt), 2048);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(7).pkt), 2049);
- BOOST_CHECK_EQUAL(getPktNo(reliability->m_unackedFrags.at(4).pkt), 2050);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(2).pkt), 2048);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(7).pkt), 2049);
+ BOOST_CHECK_EQUAL(getPktNum(reliability->m_unackedFrags.at(4).pkt), 2050);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(2).retxCount, 0);
BOOST_REQUIRE(reliability->m_unackedFrags.at(2).netPkt);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(7).retxCount, 3);
@@ -468,7 +472,7 @@
// 2049 rto: expired, removed
// 2050 rto: expired, removed
advanceClocks(1_ms, 100);
- reliability->onLpPacketLost(7);
+ reliability->onLpPacketLost(7, true);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 0);
BOOST_CHECK_EQUAL(reliability->m_ackQueue.size(), 0);
@@ -494,7 +498,7 @@
lp::Packet ackPkt;
ackPkt.add<lp::AckField>(10101010);
- reliability->processIncomingPacket(ackPkt);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(2), 1);
@@ -543,7 +547,7 @@
BOOST_CHECK_EQUAL(transport->sentPackets.size(), 5);
- reliability->processIncomingPacket(ackPkt1);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt1));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 4);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(0xFFFFFFFFFFFFFFFF), 1); // pkt1
@@ -572,7 +576,7 @@
BOOST_CHECK_EQUAL(transport->sentPackets.size(), 5);
- reliability->processIncomingPacket(ackPkt2);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt2));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 3);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(0xFFFFFFFFFFFFFFFF), 1); // pkt1
@@ -599,7 +603,7 @@
BOOST_CHECK_EQUAL(transport->sentPackets.size(), 5);
- reliability->processIncomingPacket(ackPkt3);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt3));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 2);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(0xFFFFFFFFFFFFFFFF), 0); // pkt1 old TxSeq
@@ -618,7 +622,7 @@
BOOST_REQUIRE(sentRetxPkt.has<lp::TxSequenceField>());
BOOST_CHECK_EQUAL(sentRetxPkt.get<lp::TxSequenceField>(), 4);
BOOST_REQUIRE(sentRetxPkt.has<lp::FragmentField>());
- BOOST_CHECK_EQUAL(getPktNo(sentRetxPkt), 1);
+ BOOST_CHECK_EQUAL(getPktNum(sentRetxPkt), 1);
BOOST_CHECK_EQUAL(linkService->getCounters().nAcknowledged, 3);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetransmitted, 0);
BOOST_CHECK_EQUAL(linkService->getCounters().nRetxExhausted, 0);
@@ -629,7 +633,7 @@
BOOST_CHECK_EQUAL(transport->sentPackets.size(), 6);
- reliability->processIncomingPacket(ackPkt4);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt4));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 1);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.count(0xFFFFFFFFFFFFFFFF), 0); // pkt1 old TxSeq
@@ -671,7 +675,7 @@
lp::Packet ackPkt1;
ackPkt1.add<lp::AckField>(firstTxSeq + 4);
ackPkt1.add<lp::AckField>(firstTxSeq + 3);
- reliability->processIncomingPacket(ackPkt1);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt1));
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 3);
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.at(firstTxSeq).nGreaterSeqAcks, 2);
@@ -681,7 +685,7 @@
// This triggers a "loss by greater Acks" for packets 5001 and 5002
lp::Packet ackPkt2;
ackPkt2.add<lp::AckField>(firstTxSeq + 2);
- reliability->processIncomingPacket(ackPkt2); // tests crash/assert reported in bug #4479
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt2)); // tests crash/assert reported in bug #4479
BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 0);
}
@@ -700,7 +704,7 @@
lp::Packet ackPkt;
ackPkt.add<lp::AckField>(1);
- reliability->processIncomingPacket(ackPkt);
+ BOOST_CHECK(reliability->processIncomingPacket(ackPkt));
advanceClocks(1_ms, 1000);
@@ -716,23 +720,30 @@
BOOST_CHECK_EQUAL(reliability->m_ackQueue.size(), 0);
lp::Packet pkt1 = makeFrag(100, 40);
+ pkt1.add<lp::SequenceField>(123456);
pkt1.add<lp::TxSequenceField>(765432);
- reliability->processIncomingPacket(pkt1);
+ BOOST_CHECK(reliability->processIncomingPacket(pkt1));
BOOST_CHECK(reliability->m_idleAckTimer);
BOOST_REQUIRE_EQUAL(reliability->m_ackQueue.size(), 1);
BOOST_CHECK_EQUAL(reliability->m_ackQueue.front(), 765432);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(123456), 1);
lp::Packet pkt2 = makeFrag(276, 40);
+ pkt2.add<lp::SequenceField>(654321);
pkt2.add<lp::TxSequenceField>(234567);
- reliability->processIncomingPacket(pkt2);
+ BOOST_CHECK(reliability->processIncomingPacket(pkt2));
BOOST_CHECK(reliability->m_idleAckTimer);
BOOST_REQUIRE_EQUAL(reliability->m_ackQueue.size(), 2);
BOOST_CHECK_EQUAL(reliability->m_ackQueue.front(), 765432);
BOOST_CHECK_EQUAL(reliability->m_ackQueue.back(), 234567);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(123456), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(654321), 1);
// T+5ms
advanceClocks(1_ms, 5);
@@ -762,9 +773,9 @@
BOOST_AUTO_TEST_CASE(PiggybackAcksMtu)
{
- // MTU is 1500, payload has 60 octets plus 6 octets for LpPacket and Fragment TL and 10 octets for
- // TxSequence, leaving 1426 octets for piggybacking. Each Ack header is 12 octets, so each
- // LpPacket can carry 118 Acks, and it takes 9 LpPackets for 1000 Acks.
+ // MTU is 1500, payload has 60 octets plus 6 octets for LpPacket and Fragment TL and 10 octets
+ // each for Sequence and TxSequence, leaving 1414 octets for piggybacking. Each Ack header is 12
+ // octets, so each LpPacket can carry 117 Acks, and it takes 9 LpPackets for 1000 Acks.
transport->setMtu(1500);
@@ -780,7 +791,7 @@
BOOST_REQUIRE_EQUAL(transport->sentPackets.size(), i);
lp::Packet sentPkt(transport->sentPackets.back().packet);
- BOOST_CHECK_EQUAL(getPktNo(sentPkt), i);
+ BOOST_CHECK_EQUAL(getPktNum(sentPkt), i);
BOOST_CHECK(sentPkt.has<lp::AckField>());
for (lp::Sequence ack : sentPkt.list<lp::AckField>()) {
@@ -794,9 +805,9 @@
BOOST_AUTO_TEST_CASE(PiggybackAcksMtuNoSpace)
{
- // MTU is 64, payload has 44 octets plus 4 octets for LpPacket and Fragment TL and 10 octets for
- // TxSequence, leaving 6 octets for piggybacking. Each Ack header is 12 octets, so there's no room
- // to piggyback any Ack in LpPacket.
+ // MTU is 64, payload has 34 octets plus 4 octets for LpPacket and Fragment TL and 10 octets each
+ // for Sequence and TxSequence, leaving 6 octets for piggybacking. Each Ack header is 12 octets,
+ // so there's no room to piggyback any Ack in LpPacket.
transport->setMtu(Transport::MIN_MTU);
@@ -804,12 +815,12 @@
reliability->m_ackQueue.push(i);
}
- lp::Packet pkt = makeFrag(1, 44);
+ lp::Packet pkt = makeFrag(1, 34);
linkService->sendLpPackets({pkt});
BOOST_REQUIRE_EQUAL(transport->sentPackets.size(), 1);
lp::Packet sentPkt(transport->sentPackets.back().packet);
- BOOST_CHECK_EQUAL(getPktNo(sentPkt), 1);
+ BOOST_CHECK_EQUAL(getPktNum(sentPkt), 1);
BOOST_CHECK(!sentPkt.has<lp::AckField>());
BOOST_CHECK_EQUAL(reliability->m_ackQueue.size(), 100);
@@ -820,8 +831,9 @@
BOOST_CHECK(!reliability->m_idleAckTimer);
lp::Packet pkt1 = makeFrag(1, 100);
+ pkt1.add<lp::SequenceField>(1);
pkt1.add<lp::TxSequenceField>(12);
- reliability->processIncomingPacket({pkt1});
+ BOOST_CHECK(reliability->processIncomingPacket({pkt1}));
BOOST_CHECK(reliability->m_idleAckTimer);
// T+1ms
@@ -829,8 +841,9 @@
BOOST_CHECK(reliability->m_idleAckTimer);
lp::Packet pkt2 = makeFrag(2, 100);
+ pkt2.add<lp::SequenceField>(2);
pkt2.add<lp::TxSequenceField>(13);
- reliability->processIncomingPacket({pkt2});
+ BOOST_CHECK(reliability->processIncomingPacket({pkt2}));
BOOST_CHECK(reliability->m_idleAckTimer);
// T+5ms
@@ -838,8 +851,9 @@
BOOST_CHECK(!reliability->m_idleAckTimer);
lp::Packet pkt3 = makeFrag(3, 100);
+ pkt3.add<lp::SequenceField>(3);
pkt3.add<lp::TxSequenceField>(15);
- reliability->processIncomingPacket({pkt3});
+ BOOST_CHECK(reliability->processIncomingPacket({pkt3}));
BOOST_CHECK(reliability->m_idleAckTimer);
// T+9ms
@@ -927,6 +941,111 @@
BOOST_CHECK(expectedAcks.empty());
}
+BOOST_AUTO_TEST_CASE(TrackRecentReceivedLpPackets)
+{
+ lp::Packet pkt1 = makeFrag(1, 100);
+ pkt1.add<lp::SequenceField>(7);
+ pkt1.add<lp::TxSequenceField>(12);
+ BOOST_CHECK(reliability->processIncomingPacket({pkt1}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.front(), 7);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(7), 1);
+
+ // T+500ms
+ // Estimated RTO starts at 1000ms and we are not adding any measurements, so it should remain
+ // this value throughout the test case
+ advanceClocks(500_ms, 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(7), 1);
+ lp::Packet pkt2 = makeFrag(1, 100);
+ pkt2.add<lp::SequenceField>(23);
+ pkt2.add<lp::TxSequenceField>(13);
+ BOOST_CHECK(reliability->processIncomingPacket({pkt2}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.front(), 7);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(7), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(23), 1);
+
+ // T+1250ms
+ // First received sequence should be removed after next received packet, but second should remain
+ advanceClocks(750_ms, 1);
+ lp::Packet pkt3 = makeFrag(1, 100);
+ pkt3.add<lp::SequenceField>(24);
+ pkt3.add<lp::TxSequenceField>(14);
+ BOOST_CHECK(reliability->processIncomingPacket({pkt3}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.front(), 23);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(23), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(24), 1);
+
+ // T+1750ms
+ // Second received sequence should be removed
+ advanceClocks(500_ms, 1);
+ lp::Packet pkt4 = makeFrag(1, 100);
+ pkt4.add<lp::SequenceField>(25);
+ pkt4.add<lp::TxSequenceField>(15);
+ BOOST_CHECK(reliability->processIncomingPacket({pkt4}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqsQueue.front(), 24);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(24), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(25), 1);
+}
+
+BOOST_AUTO_TEST_CASE(DropDuplicateReceivedSequence)
+{
+ Interest interest("/test/prefix");
+ interest.setCanBePrefix(false);
+ lp::Packet pkt1;
+ pkt1.add<lp::FragmentField>({interest.wireEncode().begin(), interest.wireEncode().end()});
+ pkt1.add<lp::SequenceField>(7);
+ pkt1.add<lp::TxSequenceField>(12);
+ BOOST_CHECK(reliability->processIncomingPacket({pkt1}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(7), 1);
+
+ lp::Packet pkt2;
+ pkt2.add<lp::FragmentField>({interest.wireEncode().begin(), interest.wireEncode().end()});
+ pkt2.add<lp::SequenceField>(7);
+ pkt2.add<lp::TxSequenceField>(13);
+ BOOST_CHECK(!reliability->processIncomingPacket({pkt2}));
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_recentRecvSeqs.count(7), 1);
+}
+
+BOOST_AUTO_TEST_CASE(DropDuplicateAckForRetx)
+{
+ lp::Packet pkt1 = makeFrag(1024, 50);
+ linkService->sendLpPackets({pkt1});
+
+ // Will send out a single fragment
+ BOOST_CHECK_EQUAL(transport->sentPackets.size(), 1);
+ BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 1);
+ lp::Sequence firstTxSeq = reliability->m_firstUnackedFrag->first;
+
+ // RTO is initially 1 second, so will time out and retx
+ advanceClocks(1250_ms, 1);
+ BOOST_CHECK_EQUAL(transport->sentPackets.size(), 2);
+ BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 1);
+
+ // Acknowledge first transmission (RTO underestimation)
+ // Ack will be dropped because unknown
+ lp::Packet ackPkt1;
+ ackPkt1.add<lp::AckField>(firstTxSeq);
+ reliability->processIncomingPacket(ackPkt1);
+ BOOST_REQUIRE_EQUAL(reliability->m_unackedFrags.size(), 1); // Required because collection used below
+
+ // Acknowledge second transmission
+ // Ack will acknowledge retx and remove unacked frag
+ lp::Packet ackPkt2;
+ ackPkt2.add<lp::AckField>(reliability->m_firstUnackedFrag->first);
+ reliability->processIncomingPacket(ackPkt2);
+ BOOST_CHECK_EQUAL(reliability->m_unackedFrags.size(), 0);
+}
+
BOOST_AUTO_TEST_SUITE_END() // TestLpReliability
BOOST_AUTO_TEST_SUITE_END() // Face