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-2019, 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 
35 NFD_LOG_INIT(AsfStrategy);
36 NFD_REGISTER_STRATEGY(AsfStrategy);
37 
38 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_INITIAL(10);
39 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_MAX(250);
40 
41 AsfStrategy::AsfStrategy(Forwarder& forwarder, const Name& name)
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  << " n-silent-timeouts=" << m_maxSilentTimeouts);
62 }
63 
64 const Name&
66 {
67  static Name strategyName("/localhost/nfd/strategy/asf/%FD%03");
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 == "n-silent-timeouts") {
101  m_maxSilentTimeouts = getParamValue(f, s);
102  }
103  else {
104  NDN_THROW(std::invalid_argument("Parameter should be probing-interval or n-silent-timeouts"));
105  }
106  }
107 }
108 
109 void
110 AsfStrategy::afterReceiveInterest(const FaceEndpoint& ingress, const Interest& interest,
111  const shared_ptr<pit::Entry>& pitEntry)
112 {
113  // Should the Interest be suppressed?
114  auto suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
115  if (suppressResult == RetxSuppressionResult::SUPPRESS) {
116  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " suppressed");
117  return;
118  }
119 
120  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
121  const fib::NextHopList& nexthops = fibEntry.getNextHops();
122 
123  if (suppressResult == RetxSuppressionResult::NEW) {
124  if (nexthops.size() == 0) {
125  NFD_LOG_DEBUG(interest << " new-interest from=" << ingress << " no-nexthop");
126  sendNoRouteNack(ingress, pitEntry);
127  return;
128  }
129 
130  Face* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry);
131  if (faceToUse != nullptr) {
132  NFD_LOG_DEBUG(interest << " new-interest from=" << ingress << " forward-to=" << faceToUse->getId());
133  forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
134 
135  // If necessary, send probe
136  sendProbe(interest, ingress, *faceToUse, fibEntry, pitEntry);
137  }
138  else {
139  NFD_LOG_DEBUG(interest << " new-interest from=" << ingress << " no-nexthop");
140  sendNoRouteNack(ingress, pitEntry);
141  }
142  return;
143  }
144 
145  Face* faceToUse = getBestFaceForForwarding(interest, ingress.face, fibEntry, pitEntry, false);
146  // if unused face not found, select nexthop with earliest out record
147  if (faceToUse != nullptr) {
148  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " forward-to=" << faceToUse->getId());
149  forwardInterest(interest, *faceToUse, fibEntry, pitEntry);
150  // avoid probing in case of forwarding
151  return;
152  }
153 
154  // find an eligible upstream that is used earliest
155  auto it = nexthops.end();
156  it = findEligibleNextHopWithEarliestOutRecord(ingress.face, interest, nexthops, pitEntry);
157  if (it == nexthops.end()) {
158  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " no-nexthop");
159  }
160  else {
161  auto egress = FaceEndpoint(it->getFace(), 0);
162  NFD_LOG_DEBUG(interest << " retx-interest from=" << ingress << " retry-to=" << egress);
163  this->sendInterest(pitEntry, egress, interest);
164  }
165 }
166 
167 void
168 AsfStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
169  const FaceEndpoint& ingress, const Data& data)
170 {
171  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
172  if (namespaceInfo == nullptr) {
173  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-measurements");
174  return;
175  }
176 
177  // Record the RTT between the Interest out to Data in
178  FaceInfo* faceInfo = namespaceInfo->getFaceInfo(ingress.face.getId());
179  if (faceInfo == nullptr) {
180  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-face-info");
181  return;
182  }
183 
184  auto outRecord = pitEntry->getOutRecord(ingress.face);
185  if (outRecord == pitEntry->out_end()) {
186  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress << " no-out-record");
187  }
188  else {
189  faceInfo->recordRtt(time::steady_clock::now() - outRecord->getLastRenewed());
190  NFD_LOG_DEBUG(pitEntry->getName() << " data from=" << ingress
191  << " rtt=" << faceInfo->getLastRtt() << " srtt=" << faceInfo->getSrtt());
192  }
193 
194  // Extend lifetime for measurements associated with Face
195  namespaceInfo->extendFaceInfoLifetime(*faceInfo, ingress.face.getId());
196 
197  faceInfo->cancelTimeout(data.getName());
198 }
199 
200 void
201 AsfStrategy::afterReceiveNack(const FaceEndpoint& ingress, const lp::Nack& nack,
202  const shared_ptr<pit::Entry>& pitEntry)
203 {
204  NFD_LOG_DEBUG(nack.getInterest() << " nack from=" << ingress << " reason=" << nack.getReason());
205  onTimeout(pitEntry->getName(), ingress.face.getId());
206 }
207 
208 void
209 AsfStrategy::forwardInterest(const Interest& interest, Face& outFace, const fib::Entry& fibEntry,
210  const shared_ptr<pit::Entry>& pitEntry, bool wantNewNonce)
211 {
212  auto egress = FaceEndpoint(outFace, 0);
213  if (wantNewNonce) {
214  // Send probe: interest with new Nonce
215  Interest probeInterest(interest);
216  probeInterest.refreshNonce();
217  NFD_LOG_TRACE("Sending probe for " << probeInterest << " to=" << egress);
218  this->sendInterest(pitEntry, egress, probeInterest);
219  }
220  else {
221  this->sendInterest(pitEntry, egress, interest);
222  }
223 
224  FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interest, egress.face.getId());
225 
226  // Refresh measurements since Face is being used for forwarding
227  NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
228  namespaceInfo.extendFaceInfoLifetime(faceInfo, egress.face.getId());
229 
230  if (!faceInfo.isTimeoutScheduled()) {
231  auto timeout = faceInfo.scheduleTimeout(interest.getName(),
232  [this, name = interest.getName(), faceId = egress.face.getId()] {
233  onTimeout(name, faceId);
234  });
235  NFD_LOG_TRACE("Scheduled timeout for " << fibEntry.getPrefix() << " to=" << egress
236  << " in " << time::duration_cast<time::milliseconds>(timeout) << " ms");
237  }
238 }
239 
240 void
241 AsfStrategy::sendProbe(const Interest& interest, const FaceEndpoint& ingress, const Face& faceToUse,
242  const fib::Entry& fibEntry, const shared_ptr<pit::Entry>& pitEntry)
243 {
244  if (!m_probing.isProbingNeeded(fibEntry, interest))
245  return;
246 
247  Face* faceToProbe = m_probing.getFaceToProbe(ingress.face, interest, fibEntry, faceToUse);
248  if (faceToProbe == nullptr)
249  return;
250 
251  forwardInterest(interest, *faceToProbe, fibEntry, pitEntry, true);
252  m_probing.afterForwardingProbe(fibEntry, interest);
253 }
254 
255 struct FaceStats
256 {
257  Face* face;
258  time::nanoseconds rtt;
259  time::nanoseconds srtt;
260  uint64_t cost;
261 };
262 
263 struct FaceStatsCompare
264 {
265  bool
266  operator()(const FaceStats& lhs, const FaceStats& rhs) const
267  {
268  time::nanoseconds lhsValue = getValueForSorting(lhs);
269  time::nanoseconds rhsValue = getValueForSorting(rhs);
270 
271  // Sort by RTT and then by cost
272  return std::tie(lhsValue, lhs.cost) < std::tie(rhsValue, rhs.cost);
273  }
274 
275 private:
276  static time::nanoseconds
277  getValueForSorting(const FaceStats& stats)
278  {
279  // These values allow faces with no measurements to be ranked better than timeouts
280  // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
281  if (stats.rtt == FaceInfo::RTT_TIMEOUT) {
282  return time::nanoseconds::max();
283  }
284  else if (stats.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
285  return time::nanoseconds::max() / 2;
286  }
287  else {
288  return stats.srtt;
289  }
290  }
291 };
292 
293 Face*
294 AsfStrategy::getBestFaceForForwarding(const Interest& interest, const Face& inFace,
295  const fib::Entry& fibEntry, const shared_ptr<pit::Entry>& pitEntry,
296  bool isInterestNew)
297 {
298  std::set<FaceStats, FaceStatsCompare> rankedFaces;
299 
300  auto now = time::steady_clock::now();
301  for (const auto& nh : fibEntry.getNextHops()) {
302  if (!isNextHopEligible(inFace, interest, nh, pitEntry, !isInterestNew, now)) {
303  continue;
304  }
305 
306  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, nh.getFace().getId());
307  if (info == nullptr) {
308  rankedFaces.insert({&nh.getFace(), FaceInfo::RTT_NO_MEASUREMENT,
309  FaceInfo::RTT_NO_MEASUREMENT, nh.getCost()});
310  }
311  else {
312  rankedFaces.insert({&nh.getFace(), info->getLastRtt(), info->getSrtt(), nh.getCost()});
313  }
314  }
315 
316  auto it = rankedFaces.begin();
317  return it != rankedFaces.end() ? it->face : nullptr;
318 }
319 
320 void
321 AsfStrategy::onTimeout(const Name& interestName, FaceId faceId)
322 {
323  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(interestName);
324  if (namespaceInfo == nullptr) {
325  NFD_LOG_TRACE(interestName << " FibEntry has been removed since timeout scheduling");
326  return;
327  }
328 
329  FaceInfo* fiPtr = namespaceInfo->getFaceInfo(faceId);
330  if (fiPtr == nullptr) {
331  NFD_LOG_TRACE(interestName << " FaceInfo id=" << faceId << " has been removed since timeout scheduling");
332  return;
333  }
334 
335  auto& faceInfo = *fiPtr;
336  size_t nTimeouts = faceInfo.getNSilentTimeouts() + 1;
337  faceInfo.setNSilentTimeouts(nTimeouts);
338 
339  if (nTimeouts <= m_maxSilentTimeouts) {
340  NFD_LOG_TRACE(interestName << " face=" << faceId << " timeout-count=" << nTimeouts << " ignoring");
341  // Extend lifetime for measurements associated with Face
342  namespaceInfo->extendFaceInfoLifetime(faceInfo, faceId);
343  faceInfo.cancelTimeout(interestName);
344  }
345  else {
346  NFD_LOG_TRACE(interestName << " face=" << faceId << " timeout-count=" << nTimeouts);
347  faceInfo.recordTimeout(interestName);
348  }
349 }
350 
351 void
352 AsfStrategy::sendNoRouteNack(const FaceEndpoint& ingress, const shared_ptr<pit::Entry>& pitEntry)
353 {
354  lp::NackHeader nackHeader;
355  nackHeader.setReason(lp::NackReason::NO_ROUTE);
356  this->sendNack(pitEntry, ingress, nackHeader);
357  this->rejectPendingInterest(pitEntry);
358 }
359 
360 } // namespace asf
361 } // namespace fw
362 } // namespace nfd
void cancelTimeout(const Name &prefix)
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:51
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:382
static const time::nanoseconds RTT_NO_MEASUREMENT
static const time::nanoseconds RTT_TIMEOUT
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
void extendFaceInfoLifetime(FaceInfo &info, FaceId faceId)
static const Name & getStrategyName()
NamespaceInfo * getNamespaceInfo(const Name &prefix)
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const lp::NackHeader &header)
send Nack to egress
Definition: strategy.hpp:302
represents a FIB entry
Definition: fib-entry.hpp:53
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:132
NFD_REGISTER_STRATEGY(AsfStrategy)
#define NFD_LOG_TRACE
Definition: logger.hpp:37
void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data) override
trigger before PIT entry is satisfied
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Interest &interest, FaceId faceId)
Interest is retransmission and should be suppressed.
static uint64_t getParamValue(const std::string &param, const std::string &value)
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:134
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const Interest &interest)
send Interest to egress
Definition: strategy.cpp:197
void afterReceiveNack(const FaceEndpoint &ingress, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
const Name & getPrefix() const
Definition: fib-entry.hpp:60
Represents a face-endpoint pair in the forwarder.
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Interest is new (not a retransmission)
time::nanoseconds scheduleTimeout(const Name &interestName, scheduler::EventCallback cb)
bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused, time::steady_clock::TimePoint now)
determines whether a NextHop is eligible i.e.
Definition: algorithm.cpp:154
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
time::nanoseconds getLastRtt() const
time::nanoseconds getSrtt() const
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
Represents a collection of nexthops.
Definition: fib-entry.hpp:39
PartialName parameters
parameter components
Definition: strategy.hpp:355
bool isTimeoutScheduled() const
time::milliseconds getProbingInterval() const
Stores strategy information about each face in this namespace.
RetxSuppressionResult decidePerPitEntry(pit::Entry &pitEntry)
determines whether Interest is a retransmission per pit entry and if so, whether it shall be forwarde...
represents a forwarding strategy
Definition: strategy.hpp:37
This file contains common algorithms used by forwarding strategies.
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:123
void setProbingInterval(size_t probingInterval)
size_t getNSilentTimeouts() const
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
void afterReceiveInterest(const FaceEndpoint &ingress, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
void recordRtt(time::nanoseconds rtt)
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
uint64_t FaceId
Identifies a face.
Definition: face-common.hpp:44
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
schedule the PIT entry for immediate deletion
Definition: strategy.hpp:289
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:288
Strategy information for each face in a namespace.
AsfStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:354
FaceInfo * getFaceInfo(FaceId faceId)