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-2017, 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");
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  BOOST_THROW_EXCEPTION(std::invalid_argument("AsfStrategy does not accept parameters"));
52  }
53  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
54  BOOST_THROW_EXCEPTION(std::invalid_argument(
55  "AsfStrategy does not support version " + std::to_string(*parsed.version)));
56  }
58 }
59 
60 const Name&
62 {
63  static Name strategyName("/localhost/nfd/strategy/asf/%FD%02");
64  return strategyName;
65 }
66 
67 void
68 AsfStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
69  const shared_ptr<pit::Entry>& pitEntry)
70 {
71  // Should the Interest be suppressed?
72  RetxSuppressionResult suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
73 
74  switch (suppressResult) {
77  break;
79  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
80  return;
81  }
82 
83  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
84  const fib::NextHopList& nexthops = fibEntry.getNextHops();
85 
86  if (nexthops.size() == 0) {
87  sendNoRouteNack(inFace, interest, pitEntry);
88  this->rejectPendingInterest(pitEntry);
89  return;
90  }
91 
92  Face* faceToUse = getBestFaceForForwarding(fibEntry, interest, inFace);
93 
94  if (faceToUse == nullptr) {
95  sendNoRouteNack(inFace, interest, pitEntry);
96  this->rejectPendingInterest(pitEntry);
97  return;
98  }
99 
100  NFD_LOG_TRACE("Forwarding interest to face: " << faceToUse->getId());
101 
102  forwardInterest(interest, fibEntry, pitEntry, *faceToUse);
103 
104  // If necessary, send probe
105  if (m_probing.isProbingNeeded(fibEntry, interest)) {
106  Face* faceToProbe = m_probing.getFaceToProbe(inFace, interest, fibEntry, *faceToUse);
107 
108  if (faceToProbe != nullptr) {
109  bool wantNewNonce = true;
110  forwardInterest(interest, fibEntry, pitEntry, *faceToProbe, wantNewNonce);
111  m_probing.afterForwardingProbe(fibEntry, interest);
112  }
113  }
114 }
115 
116 void
117 AsfStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
118  const Face& inFace, const Data& data)
119 {
120  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
121 
122  if (namespaceInfo == nullptr) {
123  NFD_LOG_TRACE("Could not find measurements entry for " << pitEntry->getName());
124  return;
125  }
126 
127  // Record the RTT between the Interest out to Data in
128  FaceInfo* faceInfo = namespaceInfo->get(inFace.getId());
129  if (faceInfo == nullptr) {
130  return;
131  }
132  faceInfo->recordRtt(pitEntry, inFace);
133 
134  // Extend lifetime for measurements associated with Face
135  namespaceInfo->extendFaceInfoLifetime(*faceInfo, inFace);
136 
137  if (faceInfo->isTimeoutScheduled()) {
138  faceInfo->cancelTimeoutEvent(data.getName());
139  }
140 }
141 
142 void
143 AsfStrategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
144  const shared_ptr<pit::Entry>& pitEntry)
145 {
146  NFD_LOG_DEBUG("Nack for " << nack.getInterest() << " from=" << inFace.getId() << ": " << nack.getReason());
147  onTimeout(pitEntry->getName(), inFace.getId());
148 }
149 
152 
153 void
154 AsfStrategy::forwardInterest(const Interest& interest,
155  const fib::Entry& fibEntry,
156  const shared_ptr<pit::Entry>& pitEntry,
157  Face& outFace,
158  bool wantNewNonce)
159 {
160  if (wantNewNonce) {
161  //Send probe: interest with new Nonce
162  Interest probeInterest(interest);
163  probeInterest.refreshNonce();
164  NFD_LOG_TRACE("Sending probe for " << probeInterest << probeInterest.getNonce()
165  << " to FaceId: " << outFace.getId());
166  this->sendInterest(pitEntry, outFace, probeInterest);
167  }
168  else {
169  this->sendInterest(pitEntry, outFace, interest);
170  }
171 
172  FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interest, outFace);
173 
174  // Refresh measurements since Face is being used for forwarding
175  NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
176  namespaceInfo.extendFaceInfoLifetime(faceInfo, outFace);
177 
178  if (!faceInfo.isTimeoutScheduled()) {
179  // Estimate and schedule timeout
180  RttEstimator::Duration timeout = faceInfo.computeRto();
181 
182  NFD_LOG_TRACE("Scheduling timeout for " << fibEntry.getPrefix()
183  << " FaceId: " << outFace.getId()
184  << " in " << time::duration_cast<time::milliseconds>(timeout) << " ms");
185 
186  scheduler::EventId id = scheduler::schedule(timeout,
187  bind(&AsfStrategy::onTimeout, this, interest.getName(), outFace.getId()));
188 
189  faceInfo.setTimeoutEvent(id, interest.getName());
190  }
191 }
192 
193 struct FaceStats
194 {
195  Face* face;
196  RttStats::Rtt rtt;
197  RttStats::Rtt srtt;
198  uint64_t cost;
199 };
200 
201 double
202 getValueForSorting(const FaceStats& stats)
203 {
204  // These values allow faces with no measurements to be ranked better than timeouts
205  // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
206  static const RttStats::Rtt SORTING_RTT_TIMEOUT = time::microseconds::max();
207  static const RttStats::Rtt SORTING_RTT_NO_MEASUREMENT = SORTING_RTT_TIMEOUT / 2;
208 
209  if (stats.rtt == RttStats::RTT_TIMEOUT) {
210  return SORTING_RTT_TIMEOUT.count();
211  }
212  else if (stats.rtt == RttStats::RTT_NO_MEASUREMENT) {
213  return SORTING_RTT_NO_MEASUREMENT.count();
214  }
215  else {
216  return stats.srtt.count();
217  }
218 }
219 
220 Face*
221 AsfStrategy::getBestFaceForForwarding(const fib::Entry& fibEntry, const Interest& interest,
222  const Face& inFace)
223 {
224  NFD_LOG_TRACE("Looking for best face for " << fibEntry.getPrefix());
225 
226  typedef std::function<bool(const FaceStats&, const FaceStats&)> FaceStatsPredicate;
227  typedef std::set<FaceStats, FaceStatsPredicate> FaceStatsSet;
228 
229  FaceStatsSet rankedFaces(
230  [] (const FaceStats& lhs, const FaceStats& rhs) -> bool {
231  // Sort by RTT and then by cost
232  double lhsValue = getValueForSorting(lhs);
233  double rhsValue = getValueForSorting(rhs);
234 
235  if (lhsValue < rhsValue) {
236  return true;
237  }
238  else if (lhsValue == rhsValue) {
239  return lhs.cost < rhs.cost;
240  }
241  else {
242  return false;
243  }
244  });
245 
246  for (const fib::NextHop& hop : fibEntry.getNextHops()) {
247  Face& hopFace = hop.getFace();
248 
249  if ((hopFace.getId() == inFace.getId() && hopFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
250  wouldViolateScope(inFace, interest, hopFace)) {
251  continue;
252  }
253 
254  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, hopFace);
255 
256  if (info == nullptr) {
257  FaceStats stats = {&hopFace,
260  hop.getCost()};
261 
262  rankedFaces.insert(stats);
263  }
264  else {
265  FaceStats stats = {&hopFace, info->getRtt(), info->getSrtt(), hop.getCost()};
266  rankedFaces.insert(stats);
267  }
268  }
269 
270  FaceStatsSet::iterator it = rankedFaces.begin();
271 
272  if (it != rankedFaces.end()) {
273  return it->face;
274  }
275  else {
276  return nullptr;
277  }
278 }
279 
280 void
281 AsfStrategy::onTimeout(const Name& interestName, face::FaceId faceId)
282 {
283  NFD_LOG_TRACE("FaceId: " << faceId << " for " << interestName << " has timed-out");
284 
285  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(interestName);
286 
287  if (namespaceInfo == nullptr) {
288  NFD_LOG_TRACE("FibEntry for " << interestName << " has been removed since timeout scheduling");
289  return;
290  }
291 
292  FaceInfoTable::iterator it = namespaceInfo->find(faceId);
293 
294  if (it == namespaceInfo->end()) {
295  it = namespaceInfo->insert(faceId);
296  }
297 
298  FaceInfo& faceInfo = it->second;
299  faceInfo.recordTimeout(interestName);
300 }
301 
302 void
303 AsfStrategy::sendNoRouteNack(const Face& inFace, const Interest& interest,
304  const shared_ptr<pit::Entry>& pitEntry)
305 {
306  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
307 
308  lp::NackHeader nackHeader;
309  nackHeader.setReason(lp::NackReason::NO_ROUTE);
310  this->sendNack(pitEntry, inFace, nackHeader);
311 }
312 
313 } // namespace asf
314 } // namespace fw
315 } // namespace nfd
const FaceInfoTable::iterator insert(nfd::face::FaceId faceId)
main class of NFD
Definition: forwarder.hpp:52
Interest is retransmission and should be forwarded.
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:290
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:161
RttStats::Rtt getRtt() const
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Interest &interest, const Face &face)
static const Name & getStrategyName()
time::microseconds Duration
NamespaceInfo * getNamespaceInfo(const Name &prefix)
represents a FIB entry
Definition: fib-entry.hpp:51
virtual void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data) override
trigger before PIT entry is satisfied
NFD_REGISTER_STRATEGY(AsfStrategy)
void extendFaceInfoLifetime(FaceInfo &info, const Face &face)
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:191
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const Face &outFace, const lp::NackHeader &header)
send Nack to outFace
Definition: strategy.hpp:217
Interest is retransmission and should be suppressed.
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:132
RttStats::Rtt getSrtt() const
time::duration< double, boost::micro > Rtt
FaceInfoTable::iterator end()
Table::const_iterator iterator
Definition: cs-internal.hpp:41
void cancelTimeoutEvent(const Name &prefix)
const Name & getPrefix() const
Definition: fib-entry.hpp:58
FaceInfo * get(nfd::face::FaceId faceId)
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Interest is new (not a retransmission)
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
std::vector< fib::NextHop > NextHopList
Definition: fib-entry.hpp:47
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
PartialName parameters
parameter components
Definition: strategy.hpp:263
ndn::optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:262
bool isTimeoutScheduled() const
void recordRtt(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace)
stores stategy 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
virtual void afterReceiveNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
void recordTimeout(const Name &interestName)
This file contains common algorithms used by forwarding strategies.
void setTimeoutEvent(const scheduler::EventId &id, const Name &interestName)
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
static const Rtt RTT_TIMEOUT
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:121
EventId schedule(time::nanoseconds after, const EventCallback &event)
schedule an event
Definition: scheduler.cpp:47
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:160
virtual void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
double getValueForSorting(const FaceStats &stats)
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
uint64_t FaceId
identifies a face
Definition: face.hpp:39
RttEstimator::Duration computeRto() const
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38
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
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
decide that a pending Interest cannot be forwarded
Definition: strategy.hpp:204
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:196
FaceInfoTable::iterator find(nfd::face::FaceId faceId)
Strategy information for each face in a namespace.
AsfStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
static const Rtt RTT_NO_MEASUREMENT