access-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 "access-strategy.hpp"
27 #include "algorithm.hpp"
28 #include "core/logger.hpp"
29 
30 namespace nfd {
31 namespace fw {
32 
33 NFD_LOG_INIT("AccessStrategy");
35 
36 AccessStrategy::AccessStrategy(Forwarder& forwarder, const Name& name)
37  : Strategy(forwarder)
38  , m_removeFaceInfoConn(this->beforeRemoveFace.connect(
39  bind(&AccessStrategy::removeFaceInfo, this, _1)))
40 {
42  if (!parsed.parameters.empty()) {
43  BOOST_THROW_EXCEPTION(std::invalid_argument("AccessStrategy does not accept parameters"));
44  }
45  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
46  BOOST_THROW_EXCEPTION(std::invalid_argument(
47  "AccessStrategy does not support version " + std::to_string(*parsed.version)));
48  }
50 }
51 
52 const Name&
54 {
55  static Name strategyName("/localhost/nfd/strategy/access/%FD%01");
56  return strategyName;
57 }
58 
59 void
60 AccessStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
61  const shared_ptr<pit::Entry>& pitEntry)
62 {
63  RetxSuppressionResult suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
64  switch (suppressResult) {
66  this->afterReceiveNewInterest(inFace, interest, pitEntry);
67  break;
69  this->afterReceiveRetxInterest(inFace, interest, pitEntry);
70  break;
72  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-suppress");
73  break;
74  default:
75  BOOST_ASSERT(false);
76  break;
77  }
78 }
79 
80 void
81 AccessStrategy::afterReceiveNewInterest(const Face& inFace, const Interest& interest,
82  const shared_ptr<pit::Entry>& pitEntry)
83 {
84  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
85  Name miName;
86  MtInfo* mi = nullptr;
87  std::tie(miName, mi) = this->findPrefixMeasurements(*pitEntry);
88 
89  // has measurements for Interest Name?
90  if (mi != nullptr) {
91  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
92  " new-interest mi=" << miName);
93 
94  // send to last working nexthop
95  bool isSentToLastNexthop = this->sendToLastNexthop(inFace, interest, pitEntry, *mi, fibEntry);
96 
97  if (isSentToLastNexthop) {
98  return;
99  }
100  }
101  else {
102  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
103  " new-interest no-mi");
104  }
105 
106  // no measurements, or last working nexthop unavailable
107 
108  // multicast to all nexthops except incoming face
109  int nMulticastSent = this->multicast(inFace, interest, pitEntry, fibEntry);
110 
111  if (nMulticastSent < 1) {
112  this->rejectPendingInterest(pitEntry);
113  }
114 }
115 
116 void
117 AccessStrategy::afterReceiveRetxInterest(const Face& inFace, const Interest& interest,
118  const shared_ptr<pit::Entry>& pitEntry)
119 {
120  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
121  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-forward");
122  this->multicast(inFace, interest, pitEntry, fibEntry);
123 }
124 
125 bool
126 AccessStrategy::sendToLastNexthop(const Face& inFace, const Interest& interest,
127  const shared_ptr<pit::Entry>& pitEntry, MtInfo& mi,
128  const fib::Entry& fibEntry)
129 {
130  if (mi.lastNexthop == face::INVALID_FACEID) {
131  NFD_LOG_DEBUG(pitEntry->getInterest() << " no-last-nexthop");
132  return false;
133  }
134 
135  if (mi.lastNexthop == inFace.getId()) {
136  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-is-downstream");
137  return false;
138  }
139 
140  Face* outFace = this->getFace(mi.lastNexthop);
141  if (outFace == nullptr || !fibEntry.hasNextHop(*outFace)) {
142  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-gone");
143  return false;
144  }
145 
146  if (wouldViolateScope(inFace, interest, *outFace)) {
147  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-violates-scope");
148  return false;
149  }
150 
151  RttEstimator::Duration rto = mi.rtt.computeRto();
152  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << mi.lastNexthop <<
153  " last-nexthop rto=" << time::duration_cast<time::microseconds>(rto).count());
154 
155  this->sendInterest(pitEntry, *outFace, interest);
156 
157  // schedule RTO timeout
158  PitInfo* pi = pitEntry->insertStrategyInfo<PitInfo>().first;
159  pi->rtoTimer = scheduler::schedule(rto,
160  bind(&AccessStrategy::afterRtoTimeout, this, weak_ptr<pit::Entry>(pitEntry),
161  inFace.getId(), mi.lastNexthop));
162 
163  return true;
164 }
165 
166 void
167 AccessStrategy::afterRtoTimeout(weak_ptr<pit::Entry> pitWeak, FaceId inFaceId, FaceId firstOutFaceId)
168 {
169  shared_ptr<pit::Entry> pitEntry = pitWeak.lock();
170  BOOST_ASSERT(pitEntry != nullptr);
171  // if pitEntry is gone, RTO timer should have been cancelled
172 
173  Face* inFace = this->getFace(inFaceId);
174  if (inFace == nullptr) {
175  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFaceId <<
176  " inFace-gone " << inFaceId);
177  return;
178  }
179 
180  pit::InRecordCollection::iterator inRecord = pitEntry->getInRecord(*inFace);
181  BOOST_ASSERT(inRecord != pitEntry->in_end());
182  // in-record is erased only if Interest is satisfied, and RTO timer should have been cancelled
183  // note: if this strategy is extended to send Nacks, that would also erase in-record,
184  // and RTO timer should be cancelled in that case as well
185 
186  const Interest& interest = inRecord->getInterest();
187 
188  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
189 
190  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFaceId <<
191  " multicast-except " << firstOutFaceId);
192  this->multicast(*inFace, interest, pitEntry, fibEntry, firstOutFaceId);
193 }
194 
195 int
196 AccessStrategy::multicast(const Face& inFace, const Interest& interest,
197  const shared_ptr<pit::Entry>& pitEntry, const fib::Entry& fibEntry,
198  FaceId exceptFace)
199 {
200  int nSent = 0;
201  for (const fib::NextHop& nexthop : fibEntry.getNextHops()) {
202  Face& outFace = nexthop.getFace();
203  if (&outFace == &inFace || outFace.getId() == exceptFace ||
204  wouldViolateScope(inFace, interest, outFace)) {
205  continue;
206  }
207  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << outFace.getId() <<
208  " multicast");
209  this->sendInterest(pitEntry, outFace, interest);
210  ++nSent;
211  }
212  return nSent;
213 }
214 
215 void
216 AccessStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
217  const Face& inFace, const Data& data)
218 {
219  PitInfo* pi = pitEntry->getStrategyInfo<PitInfo>();
220  if (pi != nullptr) {
221  pi->rtoTimer.cancel();
222  }
223 
224  if (!pitEntry->hasInRecords()) { // already satisfied by another upstream
225  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
226  " not-fastest");
227  return;
228  }
229 
230  pit::OutRecordCollection::iterator outRecord = pitEntry->getOutRecord(inFace);
231  if (outRecord == pitEntry->out_end()) { // no out-record
232  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
233  " no-out-record");
234  return;
235  }
236 
237  time::steady_clock::Duration rtt = time::steady_clock::now() - outRecord->getLastRenewed();
238  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
239  " rtt=" << time::duration_cast<time::microseconds>(rtt).count());
240  this->updateMeasurements(inFace, data, time::duration_cast<RttEstimator::Duration>(rtt));
241 }
242 
243 void
244 AccessStrategy::updateMeasurements(const Face& inFace, const Data& data,
245  const RttEstimator::Duration& rtt)
246 {
248  FaceInfo& fi = m_fit[inFace.getId()];
249  fi.rtt.addMeasurement(rtt);
250 
251  MtInfo* mi = this->addPrefixMeasurements(data);
252  if (mi->lastNexthop != inFace.getId()) {
253  mi->lastNexthop = inFace.getId();
254  mi->rtt = fi.rtt;
255  }
256  else {
257  mi->rtt.addMeasurement(rtt);
258  }
259 }
260 
261 AccessStrategy::MtInfo::MtInfo()
262  : lastNexthop(face::INVALID_FACEID)
263  , rtt(1, time::milliseconds(1), 0.1)
264 {
265 }
266 
267 std::tuple<Name, AccessStrategy::MtInfo*>
268 AccessStrategy::findPrefixMeasurements(const pit::Entry& pitEntry)
269 {
270  measurements::Entry* me = this->getMeasurements().findLongestPrefixMatch(pitEntry);
271  if (me == nullptr) {
272  return std::make_tuple(Name(), nullptr);
273  }
274 
275  MtInfo* mi = me->getStrategyInfo<MtInfo>();
276  BOOST_ASSERT(mi != nullptr);
277  // XXX after runtime strategy change, it's possible that me exists but mi doesn't exist;
278  // this case needs another longest prefix match until mi is found
279  return std::make_tuple(me->getName(), mi);
280 }
281 
282 AccessStrategy::MtInfo*
283 AccessStrategy::addPrefixMeasurements(const Data& data)
284 {
285  measurements::Entry* me = nullptr;
286  if (!data.getName().empty()) {
287  me = this->getMeasurements().get(data.getName().getPrefix(-1));
288  }
289  if (me == nullptr) { // parent of Data Name is not in this strategy, or Data Name is empty
290  me = this->getMeasurements().get(data.getName());
291  // Data Name must be in this strategy
292  BOOST_ASSERT(me != nullptr);
293  }
294 
295  static const time::nanoseconds ME_LIFETIME = time::seconds(8);
296  this->getMeasurements().extendLifetime(*me, ME_LIFETIME);
297 
298  return me->insertStrategyInfo<MtInfo>().first;
299 }
300 
301 AccessStrategy::FaceInfo::FaceInfo()
302  : rtt(1, time::milliseconds(1), 0.1)
303 {
304 }
305 
306 void
307 AccessStrategy::removeFaceInfo(const Face& face)
308 {
309  m_fit.erase(face.getId());
310 }
311 
312 } // namespace fw
313 } // namespace nfd
bool hasNextHop(const Face &face) const
Definition: fib-entry.cpp:47
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
const Name & getName() const
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:161
represents a Measurements entry
time::microseconds Duration
represents a FIB entry
Definition: fib-entry.hpp:51
RetxSuppressionResult decidePerPitEntry(pit::Entry &pitEntry) const
determines whether Interest is a retransmission, and if so, whether it shall be forwarded or suppress...
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:191
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
std::pair< T *, bool > insertStrategyInfo(A &&...args)
insert a StrategyInfo item
AccessStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data) override
trigger before PIT entry is satisfied
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:241
#define NFD_REGISTER_STRATEGY(S)
registers a strategy
Definition: strategy.hpp:328
Table::const_iterator iterator
Definition: cs-internal.hpp:41
an Interest table entry
Definition: pit-entry.hpp:57
Access Router Strategy version 1.
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
Interest is new (not a retransmission)
PartialName parameters
parameter components
Definition: strategy.hpp:263
ndn::optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:262
represents a forwarding strategy
Definition: strategy.hpp:37
This file contains common algorithms used by forwarding strategies.
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
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
T * getStrategyInfo() const
get a StrategyInfo item
static const Name & getStrategyName()
uint64_t FaceId
identifies a face
Definition: face.hpp:39
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
const FaceId INVALID_FACEID
indicates an invalid FaceId
Definition: face.hpp:42
Face * getFace(FaceId id) const
Definition: strategy.hpp:247
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