NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
asf-strategy.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2021, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "asf-strategy.hpp"
27 #include "algorithm.hpp"
28 #include "common/global.hpp"
29 #include "common/logger.hpp"
30 
31 namespace nfd {
32 namespace fw {
33 namespace asf {
34 
37 
38 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_INITIAL(10);
39 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_MAX(250);
40 
42  : Strategy(forwarder)
43  , m_measurements(getMeasurements())
44  , m_probing(m_measurements)
45  , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
46  RetxSuppressionExponential::DEFAULT_MULTIPLIER,
47  RETX_SUPPRESSION_MAX)
48 {
50  if (!parsed.parameters.empty()) {
51  processParams(parsed.parameters);
52  }
53 
54  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
55  NDN_THROW(std::invalid_argument(
56  "AsfStrategy does not support version " + to_string(*parsed.version)));
57  }
59 
60  NFD_LOG_DEBUG("probing-interval=" << m_probing.getProbingInterval()
61  << " max-timeouts=" << m_nMaxTimeouts);
62 }
63 
64 const Name&
66 {
67  static const auto strategyName = Name("/localhost/nfd/strategy/asf").appendVersion(4);
68  return strategyName;
69 }
70 
71 static uint64_t
72 getParamValue(const std::string& param, const std::string& value)
73 {
74  try {
75  if (!value.empty() && value[0] == '-')
76  NDN_THROW(boost::bad_lexical_cast());
77 
78  return boost::lexical_cast<uint64_t>(value);
79  }
80  catch (const boost::bad_lexical_cast&) {
81  NDN_THROW(std::invalid_argument("Value of " + param + " must be a non-negative integer"));
82  }
83 }
84 
85 void
86 AsfStrategy::processParams(const PartialName& parsed)
87 {
88  for (const auto& component : parsed) {
89  std::string parsedStr(reinterpret_cast<const char*>(component.value()), component.value_size());
90  auto n = parsedStr.find("~");
91  if (n == std::string::npos) {
92  NDN_THROW(std::invalid_argument("Format is <parameter>~<value>"));
93  }
94 
95  auto f = parsedStr.substr(0, n);
96  auto s = parsedStr.substr(n + 1);
97  if (f == "probing-interval") {
98  m_probing.setProbingInterval(getParamValue(f, s));
99  }
100  else if (f == "max-timeouts") {
101  m_nMaxTimeouts = getParamValue(f, s);
102  if (m_nMaxTimeouts <= 0)
103  NDN_THROW(std::invalid_argument("max-timeouts should be greater than 0"));
104  }
105  else {
106  NDN_THROW(std::invalid_argument("Parameter should be probing-interval or max-timeouts"));
107  }
108  }
109 }
110 
111 void
113  const shared_ptr<pit::Entry>& pitEntry)
114 {
115  const auto& fibEntry = this->lookupFib(*pitEntry);
116 
117  // Check if the interest is new and, if so, skip the retx suppression check
118  if (!hasPendingOutRecords(*pitEntry)) {
119  auto* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry);
120  if (faceToUse == nullptr) {
121  NFD_LOG_DEBUG(interest << " new-interest from=" << ingress << " no-nexthop");
122  sendNoRouteNack(ingress.face, pitEntry);
123  }
124  else {
125  NFD_LOG_DEBUG(interest << " new-interest from=" << ingress << " forward-to=" << faceToUse->getId());
126  forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
127  sendProbe(interest, ingress, *faceToUse, fibEntry, pitEntry);
128  }
129  return;
130  }
131 
132  auto* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry, false);
133  if (faceToUse != nullptr) {
134  auto suppressResult = m_retxSuppression.decidePerUpstream(*pitEntry, *faceToUse);
135  if (suppressResult == RetxSuppressionResult::SUPPRESS) {
136  // Cannot be sent on this face, interest was received within the suppression window
137  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress
138  << " forward-to=" << faceToUse->getId() << " suppressed");
139  }
140  else {
141  // The retx arrived after the suppression period: forward it but don't probe, because
142  // probing was done earlier for this interest when it was newly received
143  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " forward-to=" << faceToUse->getId());
144  auto* outRecord = forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
145  if (outRecord && suppressResult == RetxSuppressionResult::FORWARD) {
146  m_retxSuppression.incrementIntervalForOutRecord(*outRecord);
147  }
148  }
149  return;
150  }
151 
152  // If all eligible faces have been used (i.e., they all have a pending out-record),
153  // choose the nexthop with the earliest out-record
154  const auto& nexthops = fibEntry.getNextHops();
155  auto it = findEligibleNextHopWithEarliestOutRecord(ingress.face, interest, nexthops, pitEntry);
156  if (it == nexthops.end()) {
157  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " no eligible nexthop");
158  return;
159  }
160  auto& outFace = it->getFace();
161  auto suppressResult = m_retxSuppression.decidePerUpstream(*pitEntry, outFace);
162  if (suppressResult == RetxSuppressionResult::SUPPRESS) {
163  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress
164  << " retry-to=" << outFace.getId() << " suppressed");
165  }
166  else {
167  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " retry-to=" << outFace.getId());
168  // sendInterest() is used here instead of forwardInterest() because the measurements info
169  // were already attached to this face in the previous forwarding
170  auto* outRecord = sendInterest(interest, outFace, pitEntry);
171  if (outRecord && suppressResult == RetxSuppressionResult::FORWARD) {
172  m_retxSuppression.incrementIntervalForOutRecord(*outRecord);
173  }
174  }
175 }
176 
177 void
179  const shared_ptr<pit::Entry>& pitEntry)
180 {
181  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
182  if (namespaceInfo == nullptr) {
183  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-measurements");
184  return;
185  }
186 
187  // Record the RTT between the Interest out to Data in
188  FaceInfo* faceInfo = namespaceInfo->getFaceInfo(ingress.face.getId());
189  if (faceInfo == nullptr) {
190  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-face-info");
191  return;
192  }
193 
194  auto outRecord = pitEntry->getOutRecord(ingress.face);
195  if (outRecord == pitEntry->out_end()) {
196  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-out-record");
197  }
198  else {
199  faceInfo->recordRtt(time::steady_clock::now() - outRecord->getLastRenewed());
200  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress
201  << " rtt=" << faceInfo->getLastRtt() << " srtt=" << faceInfo->getSrtt());
202  }
203 
204  // Extend lifetime for measurements associated with Face
205  namespaceInfo->extendFaceInfoLifetime(*faceInfo, ingress.face.getId());
206  // Extend PIT entry timer to allow slower probes to arrive
207  this->setExpiryTimer(pitEntry, 50_ms);
208  faceInfo->cancelTimeout(data.getName());
209 }
210 
211 void
213  const shared_ptr<pit::Entry>& pitEntry)
214 {
215  NFD_LOG_DEBUG(nack.getInterest() << " nack from=" << ingress << " reason=" << nack.getReason());
216  onTimeoutOrNack(pitEntry->getName(), ingress.face.getId(), true);
217 }
218 
220 AsfStrategy::forwardInterest(const Interest& interest, Face& outFace, const fib::Entry& fibEntry,
221  const shared_ptr<pit::Entry>& pitEntry)
222 {
223  const auto& interestName = interest.getName();
224  auto faceId = outFace.getId();
225 
226  auto* outRecord = sendInterest(interest, outFace, pitEntry);
227 
228  FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interestName, faceId);
229 
230  // Refresh measurements since Face is being used for forwarding
231  NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName);
232  namespaceInfo.extendFaceInfoLifetime(faceInfo, faceId);
233 
234  if (!faceInfo.isTimeoutScheduled()) {
235  auto timeout = faceInfo.scheduleTimeout(interestName,
236  [this, name = interestName, faceId] {
237  onTimeoutOrNack(name, faceId, false);
238  });
239  NFD_LOG_TRACE("Scheduled timeout for " << fibEntry.getPrefix() << " to=" << faceId
240  << " in " << time::duration_cast<time::milliseconds>(timeout));
241  }
242 
243  return outRecord;
244 }
245 
246 void
247 AsfStrategy::sendProbe(const Interest& interest, const FaceEndpoint& ingress, const Face& faceToUse,
248  const fib::Entry& fibEntry, const shared_ptr<pit::Entry>& pitEntry)
249 {
250  if (!m_probing.isProbingNeeded(fibEntry, interest.getName()))
251  return;
252 
253  Face* faceToProbe = m_probing.getFaceToProbe(ingress.face, interest, fibEntry, faceToUse);
254  if (faceToProbe == nullptr)
255  return;
256 
257  Interest probeInterest(interest);
258  probeInterest.refreshNonce();
259  NFD_LOG_TRACE("Sending probe " << probeInterest << " to=" << faceToProbe->getId());
260  forwardInterest(probeInterest, *faceToProbe, fibEntry, pitEntry);
261 
262  m_probing.afterForwardingProbe(fibEntry, interest.getName());
263 }
264 
265 struct FaceStats
266 {
270  uint64_t cost;
271 };
272 
274 {
275  bool
276  operator()(const FaceStats& lhs, const FaceStats& rhs) const
277  {
278  time::nanoseconds lhsValue = getValueForSorting(lhs);
279  time::nanoseconds rhsValue = getValueForSorting(rhs);
280 
281  // Sort by RTT and then by cost
282  return std::tie(lhsValue, lhs.cost) < std::tie(rhsValue, rhs.cost);
283  }
284 
285 private:
286  static time::nanoseconds
287  getValueForSorting(const FaceStats& stats)
288  {
289  // These values allow faces with no measurements to be ranked better than timeouts
290  // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
291  if (stats.rtt == FaceInfo::RTT_TIMEOUT) {
292  return time::nanoseconds::max();
293  }
294  else if (stats.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
295  return time::nanoseconds::max() / 2;
296  }
297  else {
298  return stats.srtt;
299  }
300  }
301 };
302 
303 Face*
304 AsfStrategy::getBestFaceForForwarding(const Interest& interest, const Face& inFace,
305  const fib::Entry& fibEntry, const shared_ptr<pit::Entry>& pitEntry,
306  bool isInterestNew)
307 {
308  std::set<FaceStats, FaceStatsCompare> rankedFaces;
309 
310  auto now = time::steady_clock::now();
311  for (const auto& nh : fibEntry.getNextHops()) {
312  if (!isNextHopEligible(inFace, interest, nh, pitEntry, !isInterestNew, now)) {
313  continue;
314  }
315 
316  const FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest.getName(), nh.getFace().getId());
317  if (info == nullptr) {
318  rankedFaces.insert({&nh.getFace(), FaceInfo::RTT_NO_MEASUREMENT,
319  FaceInfo::RTT_NO_MEASUREMENT, nh.getCost()});
320  }
321  else {
322  rankedFaces.insert({&nh.getFace(), info->getLastRtt(), info->getSrtt(), nh.getCost()});
323  }
324  }
325 
326  auto it = rankedFaces.begin();
327  return it != rankedFaces.end() ? it->face : nullptr;
328 }
329 
330 void
331 AsfStrategy::onTimeoutOrNack(const Name& interestName, FaceId faceId, bool isNack)
332 {
333  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(interestName);
334  if (namespaceInfo == nullptr) {
335  NFD_LOG_TRACE(interestName << " FibEntry has been removed since timeout scheduling");
336  return;
337  }
338 
339  FaceInfo* fiPtr = namespaceInfo->getFaceInfo(faceId);
340  if (fiPtr == nullptr) {
341  NFD_LOG_TRACE(interestName << " FaceInfo id=" << faceId << " has been removed since timeout scheduling");
342  return;
343  }
344 
345  auto& faceInfo = *fiPtr;
346  size_t nTimeouts = faceInfo.getNTimeouts() + 1;
347  faceInfo.setNTimeouts(nTimeouts);
348 
349  if (nTimeouts < m_nMaxTimeouts && !isNack) {
350  NFD_LOG_TRACE(interestName << " face=" << faceId << " timeout-count=" << nTimeouts << " ignoring");
351  // Extend lifetime for measurements associated with Face
352  namespaceInfo->extendFaceInfoLifetime(faceInfo, faceId);
353  faceInfo.cancelTimeout(interestName);
354  }
355  else {
356  NFD_LOG_TRACE(interestName << " face=" << faceId << " timeout-count=" << nTimeouts);
357  faceInfo.recordTimeout(interestName);
358  }
359 }
360 
361 void
362 AsfStrategy::sendNoRouteNack(Face& face, const shared_ptr<pit::Entry>& pitEntry)
363 {
364  lp::NackHeader nackHeader;
365  nackHeader.setReason(lp::NackReason::NO_ROUTE);
366  this->sendNack(nackHeader, face, pitEntry);
367  this->rejectPendingInterest(pitEntry);
368 }
369 
370 } // namespace asf
371 } // namespace fw
372 } // namespace nfd
Interest is retransmission and should be forwarded.
time::nanoseconds rtt
const Name & getPrefix() const
Definition: fib-entry.hpp:60
void afterForwardingProbe(const fib::Entry &fibEntry, const Name &interestName)
static ParsedInstanceName parseInstanceName(const Name &input)
Parse a strategy instance name.
Definition: strategy.cpp:123
time::nanoseconds scheduleTimeout(const Name &interestName, scheduler::EventCallback cb)
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
void afterReceiveNack(const lp::Nack &nack, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after a Nack is received.
static const time::nanoseconds RTT_TIMEOUT
std::string to_string(const T &val)
Definition: backports.hpp:86
NackHeader & setReason(NackReason reason)
set reason code
void afterReceiveInterest(const Interest &interest, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after an Interest is received.
void beforeSatisfyInterest(const Data &data, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry) override
trigger before PIT entry is satisfied
bool isProbingNeeded(const fib::Entry &fibEntry, const Name &interestName)
Represents a face-endpoint pair in the forwarder.
represents a FIB entry
Definition: fib-entry.hpp:53
PartialName parameters
parameter components
Definition: strategy.hpp:390
static time_point now() noexcept
Definition: time.cpp:80
void refreshNonce()
Change nonce value.
Definition: interest.cpp:422
fib::NextHopList::const_iterator findEligibleNextHopWithEarliestOutRecord(const Face &inFace, const Interest &interest, const fib::NextHopList &nexthops, const shared_ptr< pit::Entry > &pitEntry)
pick an eligible NextHop with earliest out-record
Definition: algorithm.cpp:109
NFD_REGISTER_STRATEGY(AsfStrategy)
void extendFaceInfoLifetime(FaceInfo &info, FaceId faceId)
bool operator()(const FaceStats &lhs, const FaceStats &rhs) const
SignatureInfo info
static const Name & getStrategyName()
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:53
RetxSuppressionResult decidePerUpstream(pit::Entry &pitEntry, Face &outFace)
determines whether Interest is a retransmission per upstream and if so, whether it shall be forwarded...
Interest is retransmission and should be suppressed.
static uint64_t getParamValue(const std::string &param, const std::string &value)
void setInstanceName(const Name &name)
Set strategy instance name.
Definition: strategy.hpp:417
Represents an Interest packet.
Definition: interest.hpp:48
Stores strategy information about each face in this namespace.
void recordRtt(time::nanoseconds rtt)
NFD_VIRTUAL_WITH_TESTS void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
Schedule the PIT entry for immediate deletion.
Definition: strategy.hpp:319
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Name &interestName, FaceId faceId)
represents a Network Nack
Definition: nack.hpp:38
void setProbingInterval(size_t probingInterval)
#define NDN_THROW(e)
Definition: exception.hpp:61
NackReason getReason() const
Definition: nack.hpp:90
time::nanoseconds getLastRtt() const
ndn Face
Definition: face-impl.hpp:42
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Name &prefix)
void cancelTimeout(const Name &prefix)
time::milliseconds getProbingInterval() const
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:39
time::nanoseconds srtt
void incrementIntervalForOutRecord(pit::OutRecord &outRecord)
Increment the suppression interval for out record.
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_TRACE
Definition: logger.hpp:37
Name PartialName
Represents an arbitrary sequence of name components.
Definition: name.hpp:36
const Name & getName() const noexcept
Get name.
Definition: data.hpp:127
Represents an absolute name.
Definition: name.hpp:41
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
bool hasPendingOutRecords(const pit::Entry &pitEntry)
determine whether pitEntry has any pending out-records
Definition: algorithm.cpp:85
NFD_VIRTUAL_WITH_TESTS bool sendNack(const lp::NackHeader &header, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send a Nack packet.
Definition: strategy.hpp:335
Strategy information for each face in a namespace.
Represents a forwarding strategy.
Definition: strategy.hpp:38
FaceInfo * getFaceInfo(FaceId faceId)
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:389
NamespaceInfo * getNamespaceInfo(const Name &prefix)
This file contains common algorithms used by forwarding strategies.
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
Performs a FIB lookup, considering Link object if present.
Definition: strategy.cpp:331
const Name & getName() const noexcept
Definition: interest.hpp:172
Contains information about an Interest toward an outgoing face.
bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused, time::steady_clock::time_point now)
Definition: algorithm.cpp:131
time::nanoseconds getSrtt() const
static Name makeInstanceName(const Name &input, const Name &strategyName)
Construct a strategy instance name.
Definition: strategy.cpp:134
void setExpiryTimer(const shared_ptr< pit::Entry > &pitEntry, time::milliseconds duration)
Schedule the PIT entry to be erased after duration.
Definition: strategy.hpp:355
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
NFD_VIRTUAL_WITH_TESTS pit::OutRecord * sendInterest(const Interest &interest, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send an Interest packet.
Definition: strategy.cpp:237
Represents a Data packet.
Definition: data.hpp:37
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
represents a Network NACK header
Definition: nack-header.hpp:57
AsfStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
Adaptive SRTT-based Forwarding Strategy.
uint64_t FaceId
Identifies a face.
Definition: face-common.hpp:44
const Interest & getInterest() const
Definition: nack.hpp:51
boost::chrono::nanoseconds nanoseconds
Definition: time.hpp:50
static const time::nanoseconds RTT_NO_MEASUREMENT
boost::chrono::milliseconds milliseconds
Definition: time.hpp:48