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-2018, 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 
29 #include "core/logger.hpp"
30 
31 namespace nfd {
32 namespace fw {
33 namespace asf {
34 
35 NFD_LOG_INIT("AsfStrategy");
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_maxSilentTimeouts(0)
46  , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
47  RetxSuppressionExponential::DEFAULT_MULTIPLIER,
48  RETX_SUPPRESSION_MAX)
49 {
51  if (!parsed.parameters.empty()) {
52  processParams(parsed.parameters);
53  }
54 
55  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
56  BOOST_THROW_EXCEPTION(std::invalid_argument(
57  "AsfStrategy does not support version " + to_string(*parsed.version)));
58  }
60 
61  NFD_LOG_DEBUG("Probing interval=" << m_probing.getProbingInterval()
62  << ", Num silent timeouts=" << m_maxSilentTimeouts);
63 }
64 
65 const Name&
67 {
68  static Name strategyName("/localhost/nfd/strategy/asf/%FD%03");
69  return strategyName;
70 }
71 
72 void
73 AsfStrategy::processParams(const PartialName& parsed)
74 {
75  for (const auto& component : parsed) {
76  std::string parsedStr(reinterpret_cast<const char*>(component.value()), component.value_size());
77  auto n = parsedStr.find("~");
78  if (n == std::string::npos) {
79  BOOST_THROW_EXCEPTION(std::invalid_argument("Format is <parameter>~<value>"));
80  }
81 
82  auto f = parsedStr.substr(0, n);
83  auto s = parsedStr.substr(n + 1);
84  if (f == "probing-interval") {
85  m_probing.setProbingInterval(getParamValue(f, s));
86  }
87  else if (f == "n-silent-timeouts") {
88  m_maxSilentTimeouts = getParamValue(f, s);
89  }
90  else {
91  BOOST_THROW_EXCEPTION(std::invalid_argument("Parameter should be probing-interval or n-silent-timeouts"));
92  }
93  }
94 }
95 
96 uint64_t
97 AsfStrategy::getParamValue(const std::string& param, const std::string& value)
98 {
99  try {
100  if (!value.empty() && value[0] == '-')
101  BOOST_THROW_EXCEPTION(boost::bad_lexical_cast());
102 
103  return boost::lexical_cast<uint64_t>(value);
104  }
105  catch (const boost::bad_lexical_cast&) {
106  BOOST_THROW_EXCEPTION(std::invalid_argument("Value of " + param + " must be a non-negative integer"));
107  }
108 }
109 
110 void
111 AsfStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
112  const shared_ptr<pit::Entry>& pitEntry)
113 {
114  // Should the Interest be suppressed?
115  RetxSuppressionResult suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
116 
117  switch (suppressResult) {
120  break;
122  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
123  return;
124  }
125 
126  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
127  const fib::NextHopList& nexthops = fibEntry.getNextHops();
128 
129  if (nexthops.size() == 0) {
130  sendNoRouteNack(inFace, interest, pitEntry);
131  this->rejectPendingInterest(pitEntry);
132  return;
133  }
134 
135  Face* faceToUse = getBestFaceForForwarding(fibEntry, interest, inFace);
136 
137  if (faceToUse == nullptr) {
138  sendNoRouteNack(inFace, interest, pitEntry);
139  this->rejectPendingInterest(pitEntry);
140  return;
141  }
142 
143  NFD_LOG_TRACE("Forwarding interest to face: " << faceToUse->getId());
144 
145  forwardInterest(interest, fibEntry, pitEntry, *faceToUse);
146 
147  // If necessary, send probe
148  if (m_probing.isProbingNeeded(fibEntry, interest)) {
149  Face* faceToProbe = m_probing.getFaceToProbe(inFace, interest, fibEntry, *faceToUse);
150 
151  if (faceToProbe != nullptr) {
152  bool wantNewNonce = true;
153  forwardInterest(interest, fibEntry, pitEntry, *faceToProbe, wantNewNonce);
154  m_probing.afterForwardingProbe(fibEntry, interest);
155  }
156  }
157 }
158 
159 void
160 AsfStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
161  const Face& inFace, const Data& data)
162 {
163  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
164 
165  if (namespaceInfo == nullptr) {
166  NFD_LOG_TRACE("Could not find measurements entry for " << pitEntry->getName());
167  return;
168  }
169 
170  // Record the RTT between the Interest out to Data in
171  FaceInfo* faceInfo = namespaceInfo->get(inFace.getId());
172  if (faceInfo == nullptr) {
173  return;
174  }
175  faceInfo->recordRtt(pitEntry, inFace);
176 
177  // Extend lifetime for measurements associated with Face
178  namespaceInfo->extendFaceInfoLifetime(*faceInfo, inFace.getId());
179 
180  if (faceInfo->isTimeoutScheduled()) {
181  faceInfo->cancelTimeoutEvent(data.getName());
182  }
183 }
184 
185 void
186 AsfStrategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
187  const shared_ptr<pit::Entry>& pitEntry)
188 {
189  NFD_LOG_DEBUG("Nack for " << nack.getInterest() << " from=" << inFace.getId() << ": " << nack.getReason());
190  onTimeout(pitEntry->getName(), inFace.getId());
191 }
192 
195 
196 void
197 AsfStrategy::forwardInterest(const Interest& interest,
198  const fib::Entry& fibEntry,
199  const shared_ptr<pit::Entry>& pitEntry,
200  Face& outFace,
201  bool wantNewNonce)
202 {
203  if (wantNewNonce) {
204  //Send probe: interest with new Nonce
205  Interest probeInterest(interest);
206  probeInterest.refreshNonce();
207  NFD_LOG_TRACE("Sending probe for " << probeInterest << probeInterest.getNonce()
208  << " to FaceId: " << outFace.getId());
209  this->sendInterest(pitEntry, outFace, probeInterest);
210  }
211  else {
212  this->sendInterest(pitEntry, outFace, interest);
213  }
214 
215  FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interest, outFace.getId());
216 
217  // Refresh measurements since Face is being used for forwarding
218  NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
219  namespaceInfo.extendFaceInfoLifetime(faceInfo, outFace.getId());
220 
221  if (!faceInfo.isTimeoutScheduled()) {
222  // Estimate and schedule timeout
223  RttEstimator::Duration timeout = faceInfo.computeRto();
224 
225  NFD_LOG_TRACE("Scheduling timeout for " << fibEntry.getPrefix()
226  << " FaceId: " << outFace.getId()
227  << " in " << time::duration_cast<time::milliseconds>(timeout) << " ms");
228 
230  bind(&AsfStrategy::onTimeout, this, interest.getName(), outFace.getId()));
231 
232  faceInfo.setTimeoutEvent(id, interest.getName());
233  }
234 }
235 
236 struct FaceStats
237 {
241  uint64_t cost;
242 };
243 
244 double
246 {
247  // These values allow faces with no measurements to be ranked better than timeouts
248  // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
249  static const RttStats::Rtt SORTING_RTT_TIMEOUT = time::microseconds::max();
250  static const RttStats::Rtt SORTING_RTT_NO_MEASUREMENT = SORTING_RTT_TIMEOUT / 2;
251 
252  if (stats.rtt == RttStats::RTT_TIMEOUT) {
253  return SORTING_RTT_TIMEOUT.count();
254  }
255  else if (stats.rtt == RttStats::RTT_NO_MEASUREMENT) {
256  return SORTING_RTT_NO_MEASUREMENT.count();
257  }
258  else {
259  return stats.srtt.count();
260  }
261 }
262 
263 Face*
264 AsfStrategy::getBestFaceForForwarding(const fib::Entry& fibEntry, const Interest& interest,
265  const Face& inFace)
266 {
267  NFD_LOG_TRACE("Looking for best face for " << fibEntry.getPrefix());
268 
269  typedef std::function<bool(const FaceStats&, const FaceStats&)> FaceStatsPredicate;
270  typedef std::set<FaceStats, FaceStatsPredicate> FaceStatsSet;
271 
272  FaceStatsSet rankedFaces(
273  [] (const FaceStats& lhs, const FaceStats& rhs) -> bool {
274  // Sort by RTT and then by cost
275  double lhsValue = getValueForSorting(lhs);
276  double rhsValue = getValueForSorting(rhs);
277 
278  if (lhsValue < rhsValue) {
279  return true;
280  }
281  else if (lhsValue == rhsValue) {
282  return lhs.cost < rhs.cost;
283  }
284  else {
285  return false;
286  }
287  });
288 
289  for (const fib::NextHop& hop : fibEntry.getNextHops()) {
290  Face& hopFace = hop.getFace();
291 
292  if ((hopFace.getId() == inFace.getId() && hopFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
293  wouldViolateScope(inFace, interest, hopFace)) {
294  continue;
295  }
296 
297  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, hopFace.getId());
298 
299  if (info == nullptr) {
300  FaceStats stats = {&hopFace,
303  hop.getCost()};
304 
305  rankedFaces.insert(stats);
306  }
307  else {
308  FaceStats stats = {&hopFace, info->getRtt(), info->getSrtt(), hop.getCost()};
309  rankedFaces.insert(stats);
310  }
311  }
312 
313  FaceStatsSet::iterator it = rankedFaces.begin();
314 
315  if (it != rankedFaces.end()) {
316  return it->face;
317  }
318  else {
319  return nullptr;
320  }
321 }
322 
323 void
324 AsfStrategy::onTimeout(const Name& interestName, const face::FaceId faceId)
325 {
326  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(interestName);
327 
328  if (namespaceInfo == nullptr) {
329  NFD_LOG_TRACE("FibEntry for " << interestName << " has been removed since timeout scheduling");
330  return;
331  }
332 
333  FaceInfoTable::iterator it = namespaceInfo->find(faceId);
334 
335  if (it == namespaceInfo->end()) {
336  it = namespaceInfo->insert(faceId);
337  }
338 
339  FaceInfo& faceInfo = it->second;
340 
341  faceInfo.setNSilentTimeouts(faceInfo.getNSilentTimeouts() + 1);
342 
343  if (faceInfo.getNSilentTimeouts() <= m_maxSilentTimeouts) {
344  NFD_LOG_TRACE("FaceId " << faceId << " for " << interestName << " has timed-out "
345  << faceInfo.getNSilentTimeouts() << " time(s), ignoring");
346  // Extend lifetime for measurements associated with Face
347  namespaceInfo->extendFaceInfoLifetime(faceInfo, faceId);
348 
349  if (faceInfo.isTimeoutScheduled()) {
350  faceInfo.cancelTimeoutEvent(interestName);
351  }
352  }
353  else {
354  NFD_LOG_TRACE("FaceId " << faceId << " for " << interestName << " has timed-out");
355  faceInfo.recordTimeout(interestName);
356  }
357 }
358 
359 void
360 AsfStrategy::sendNoRouteNack(const Face& inFace, const Interest& interest,
361  const shared_ptr<pit::Entry>& pitEntry)
362 {
363  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
364 
365  lp::NackHeader nackHeader;
366  nackHeader.setReason(lp::NackReason::NO_ROUTE);
367  this->sendNack(pitEntry, inFace, nackHeader);
368 }
369 
370 } // namespace asf
371 } // namespace fw
372 } // namespace nfd
void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data) override
trigger before PIT entry is satisfied
time::microseconds Duration
Opaque handle for a scheduled event.
Interest is retransmission and should be forwarded.
const Name & getPrefix() const
Definition: fib-entry.hpp:58
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:121
FaceInfo * get(FaceId faceId)
const Name & getName() const
Get name.
Definition: data.hpp:128
void recordRtt(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace)
NackHeader & setReason(NackReason reason)
set reason code
generalization of a network interface
Definition: face.hpp:67
represents a FIB entry
Definition: fib-entry.hpp:51
PartialName parameters
parameter components
Definition: strategy.hpp:340
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const Face &outFace, const lp::NackHeader &header)
send Nack to outFace
Definition: strategy.hpp:286
NFD_REGISTER_STRATEGY(AsfStrategy)
void extendFaceInfoLifetime(FaceInfo &info, FaceId faceId)
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Interest &interest, FaceId faceId)
static const Name & getStrategyName()
main class of NFD
Definition: forwarder.hpp:54
Interest is retransmission and should be suppressed.
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:367
Represents an Interest packet.
Definition: interest.hpp:42
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:55
stores stategy information about each face in this namespace
static const Rtt RTT_TIMEOUT
Represents a collection of nexthops.
void cancelTimeoutEvent(const Name &prefix)
represents a Network Nack
Definition: nack.hpp:40
void setProbingInterval(size_t probingInterval)
NackReason getReason() const
Definition: nack.hpp:92
Table::const_iterator iterator
Definition: cs-internal.hpp:41
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
ndn Face
Definition: face-impl.hpp:42
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:54
time::milliseconds getProbingInterval() const
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
Interest is new (not a retransmission)
FaceId getId() const
Definition: face.hpp:233
Name PartialName
Represents an arbitrary sequence of name components.
Definition: name.hpp:38
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
static const Rtt RTT_NO_MEASUREMENT
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
schedule the PIT entry for immediate deletion
Definition: strategy.hpp:273
Represents an absolute name.
Definition: name.hpp:42
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
Strategy information for each face in a namespace.
represents a forwarding strategy
Definition: strategy.hpp:37
void afterReceiveNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:339
void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
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:252
EventId schedule(time::nanoseconds after, const EventCallback &event)
Schedule an event.
Definition: scheduler.cpp:48
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:132
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
FaceInfo * getFaceInfo(const fib::Entry &fibEntry, const Interest &interest, FaceId faceId)
std::string to_string(const V &v)
Definition: backports.hpp:107
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
double getValueForSorting(const FaceStats &stats)
uint64_t FaceId
identifies a face
Definition: face.hpp:39
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
Represents a Data packet.
Definition: data.hpp:35
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
represents a Network NACK header
Definition: nack-header.hpp:59
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:241
AsfStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
bool wouldViolateScope(const Face &inFace, const Interest &interest, const Face &outFace)
determine whether forwarding the Interest in pitEntry to outFace would violate scope ...
Definition: algorithm.cpp:37
Adaptive SRTT-based Forwarding Strategy.
RetxSuppressionResult decidePerPitEntry(pit::Entry &pitEntry)
determines whether Interest is a retransmission per pit entry and if so, whether it shall be forwarde...
const Interest & getInterest() const
Definition: nack.hpp:53
time::duration< double, boost::micro > Rtt
const Name & getName() const
Definition: interest.hpp:137