ncc-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-2020, 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 "ncc-strategy.hpp"
27 #include "algorithm.hpp"
28 #include "common/global.hpp"
29 
30 #include <ndn-cxx/util/random.hpp>
31 
32 namespace nfd {
33 namespace fw {
34 
35 NFD_REGISTER_STRATEGY(NccStrategy);
36 
37 const time::microseconds NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = 4_ms;
38 const time::microseconds NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = 75_ms;
39 const time::nanoseconds NccStrategy::MEASUREMENTS_LIFETIME = 16_s;
40 
41 NccStrategy::NccStrategy(Forwarder& forwarder, const Name& name)
42  : Strategy(forwarder)
43 {
45  if (!parsed.parameters.empty()) {
46  NDN_THROW(std::invalid_argument("NccStrategy does not accept parameters"));
47  }
48  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
49  NDN_THROW(std::invalid_argument(
50  "NccStrategy does not support version " + to_string(*parsed.version)));
51  }
53 }
54 
55 const Name&
57 {
58  static Name strategyName("/localhost/nfd/strategy/ncc/%FD%01");
59  return strategyName;
60 }
61 
62 void
63 NccStrategy::afterReceiveInterest(const FaceEndpoint& ingress, const Interest& interest,
64  const shared_ptr<pit::Entry>& pitEntry)
65 {
66  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
67  const fib::NextHopList& nexthops = fibEntry.getNextHops();
68  if (nexthops.size() == 0) {
69  this->rejectPendingInterest(pitEntry);
70  return;
71  }
72 
73  PitEntryInfo* pitEntryInfo = pitEntry->insertStrategyInfo<PitEntryInfo>().first;
74  bool isNewPitEntry = !hasPendingOutRecords(*pitEntry);
75  if (!isNewPitEntry) {
76  return;
77  }
78 
79  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(pitEntry);
80 
81  time::microseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
82  time::microseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
83  size_t nUpstreams = nexthops.size();
84 
85  shared_ptr<Face> bestFace = meInfo.getBestFace();
86  if (bestFace != nullptr && fibEntry.hasNextHop(*bestFace) &&
87  !wouldViolateScope(ingress.face, interest, *bestFace) &&
88  canForwardToLegacy(*pitEntry, *bestFace)) {
89  // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
90  deferFirst = meInfo.prediction;
91  deferRange = time::microseconds((deferFirst.count() + 1) / 2);
92  --nUpstreams;
93  this->sendInterest(pitEntry, *bestFace, interest);
94  pitEntryInfo->bestFaceTimeout = getScheduler().schedule(meInfo.prediction,
95  bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
96  }
97  else {
98  // use first eligible nexthop
99  auto firstEligibleNexthop = std::find_if(nexthops.begin(), nexthops.end(),
100  [&] (const fib::NextHop& nexthop) {
101  Face& outFace = nexthop.getFace();
102  return !wouldViolateScope(ingress.face, interest, outFace) &&
103  canForwardToLegacy(*pitEntry, outFace);
104  });
105  if (firstEligibleNexthop != nexthops.end()) {
106  this->sendInterest(pitEntry, firstEligibleNexthop->getFace(), interest);
107  }
108  else {
109  this->rejectPendingInterest(pitEntry);
110  return;
111  }
112  }
113 
114  shared_ptr<Face> previousFace = meInfo.previousFace.lock();
115  if (previousFace != nullptr && fibEntry.hasNextHop(*previousFace) &&
116  !wouldViolateScope(ingress.face, interest, *previousFace) &&
117  canForwardToLegacy(*pitEntry, *previousFace)) {
118  --nUpstreams;
119  }
120 
121  if (nUpstreams > 0) {
122  pitEntryInfo->maxInterval = std::max(1_us,
123  time::microseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
124  }
125  else {
126  // Normally, maxInterval is unused if there aren't any face beyond best and previousBest.
127  // However, in case FIB entry gains a new nexthop before doPropagate executes (bug 1853),
128  // this maxInterval would be used to determine when the next doPropagate would happen.
129  pitEntryInfo->maxInterval = deferFirst;
130  }
131  pitEntryInfo->propagateTimer = getScheduler().schedule(deferFirst,
132  bind(&NccStrategy::doPropagate, this, ingress.face.getId(), weak_ptr<pit::Entry>(pitEntry)));
133 }
134 
135 void
136 NccStrategy::doPropagate(FaceId inFaceId, weak_ptr<pit::Entry> pitEntryWeak)
137 {
138  Face* inFace = this->getFace(inFaceId);
139  if (inFace == nullptr) {
140  return;
141  }
142  shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
143  if (pitEntry == nullptr) {
144  return;
145  }
146  auto inRecord = pitEntry->getInRecord(*inFace);
147  if (inRecord == pitEntry->in_end()) {
148  return;
149  }
150  const Interest& interest = inRecord->getInterest();
151  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
152 
153  PitEntryInfo* pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
154  // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
155  // from a timer set by NccStrategy.
156  BOOST_ASSERT(pitEntryInfo != nullptr);
157 
158  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(pitEntry);
159 
160  shared_ptr<Face> previousFace = meInfo.previousFace.lock();
161  if (previousFace != nullptr && fibEntry.hasNextHop(*previousFace) &&
162  !wouldViolateScope(*inFace, interest, *previousFace) &&
163  canForwardToLegacy(*pitEntry, *previousFace)) {
164  this->sendInterest(pitEntry, *previousFace, interest);
165  }
166 
167  bool isForwarded = false;
168  for (const auto& nexthop : fibEntry.getNextHops()) {
169  Face& face = nexthop.getFace();
170  if (!wouldViolateScope(*inFace, interest, face) &&
171  canForwardToLegacy(*pitEntry, face)) {
172  isForwarded = true;
173  this->sendInterest(pitEntry, face, interest);
174  break;
175  }
176  }
177 
178  if (isForwarded) {
179  std::uniform_int_distribution<time::nanoseconds::rep> dist(0, pitEntryInfo->maxInterval.count() - 1);
180  time::nanoseconds deferNext(dist(ndn::random::getRandomNumberEngine()));
181  pitEntryInfo->propagateTimer = getScheduler().schedule(deferNext,
182  bind(&NccStrategy::doPropagate, this, inFaceId, weak_ptr<pit::Entry>(pitEntry)));
183  }
184 }
185 
186 void
187 NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
188 {
189  shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
190  if (pitEntry == nullptr) {
191  return;
192  }
193  measurements::Entry* measurementsEntry = this->getMeasurements().get(*pitEntry);
194 
195  for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
196  if (measurementsEntry == nullptr) {
197  // going out of this strategy's namespace
198  break;
199  }
200  this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
201 
202  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(measurementsEntry);
203  meInfo.adjustPredictUp();
204 
205  measurementsEntry = this->getMeasurements().getParent(*measurementsEntry);
206  }
207 }
208 
209 void
210 NccStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
211  const FaceEndpoint& ingress, const Data& data)
212 {
213  if (!pitEntry->hasInRecords()) {
214  // PIT entry has already been satisfied (and is now waiting for straggler timer to expire)
215  // NCC does not collect measurements for non-best face
216  return;
217  }
218 
219  measurements::Entry* measurementsEntry = this->getMeasurements().get(*pitEntry);
220 
221  for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
222  if (measurementsEntry == nullptr) {
223  // going out of this strategy's namespace
224  return;
225  }
226  this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
227 
228  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(measurementsEntry);
229  meInfo.updateBestFace(ingress.face);
230 
231  measurementsEntry = this->getMeasurements().getParent(*measurementsEntry);
232  }
233 
234  PitEntryInfo* pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
235  if (pitEntryInfo != nullptr) {
236  pitEntryInfo->propagateTimer.cancel();
237 
238  // Verify that the best face satisfied the interest before canceling the timeout call
239  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(pitEntry);
240  shared_ptr<Face> bestFace = meInfo.getBestFace();
241 
242  if (bestFace.get() == &ingress.face)
243  pitEntryInfo->bestFaceTimeout.cancel();
244  }
245 }
246 
248 NccStrategy::getMeasurementsEntryInfo(const shared_ptr<pit::Entry>& entry)
249 {
250  measurements::Entry* measurementsEntry = this->getMeasurements().get(*entry);
251  return this->getMeasurementsEntryInfo(measurementsEntry);
252 }
253 
256 {
257  BOOST_ASSERT(entry != nullptr);
258  MeasurementsEntryInfo* info = nullptr;
259  bool isNew = false;
260  std::tie(info, isNew) = entry->insertStrategyInfo<MeasurementsEntryInfo>();
261  if (!isNew) {
262  return *info;
263  }
264 
265  measurements::Entry* parentEntry = this->getMeasurements().getParent(*entry);
266  if (parentEntry != nullptr) {
267  MeasurementsEntryInfo& parentInfo = this->getMeasurementsEntryInfo(parentEntry);
268  info->inheritFrom(parentInfo);
269  }
270 
271  return *info;
272 }
273 
274 const time::microseconds NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION = 8192_us;
275 const time::microseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION = 127_us;
276 const time::microseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION = 160_ms;
277 
279  : prediction(INITIAL_PREDICTION)
280 {
281 }
282 
283 void
285 {
286  this->operator=(other);
287 }
288 
289 shared_ptr<Face>
291 {
292  shared_ptr<Face> best = this->bestFace.lock();
293  if (best != nullptr) {
294  return best;
295  }
296  this->bestFace = best = this->previousFace.lock();
297  return best;
298 }
299 
300 void
302 {
303  if (this->bestFace.expired()) {
304  this->bestFace = const_cast<Face&>(face).shared_from_this();
305  return;
306  }
307  shared_ptr<Face> bestFace = this->bestFace.lock();
308  if (bestFace.get() == &face) {
309  this->adjustPredictDown();
310  }
311  else {
312  this->previousFace = this->bestFace;
313  this->bestFace = const_cast<Face&>(face).shared_from_this();
314  }
315 }
316 
317 void
318 NccStrategy::MeasurementsEntryInfo::adjustPredictDown()
319 {
320  prediction = std::max(MIN_PREDICTION,
321  time::microseconds(prediction.count() - (prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
322 }
323 
324 void
326 {
327  prediction = std::min(MAX_PREDICTION,
328  time::microseconds(prediction.count() + (prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
329 }
330 
331 void
332 NccStrategy::MeasurementsEntryInfo::ageBestFace()
333 {
334  this->previousFace = this->bestFace;
335  this->bestFace.reset();
336 }
337 
339 {
340  bestFaceTimeout.cancel();
341  propagateTimer.cancel();
342 }
343 
344 } // namespace fw
345 } // namespace nfd
bool canForwardToLegacy(const pit::Entry &pitEntry, const Face &face)
decide whether Interest can be forwarded to face
Definition: algorithm.cpp:54
static const int ADJUST_PREDICT_UP_SHIFT
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:51
void timeoutOnBestFace(weak_ptr< pit::Entry > pitEntryWeak)
best face did not reply within prediction
void setInstanceName(const Name &name)
Set strategy instance name.
Definition: strategy.hpp:386
time::microseconds maxInterval
maximum interval between forwarding to two nexthops except best and previous
void extendLifetime(Entry &entry, const time::nanoseconds &lifetime)
extend lifetime of an entry
weak_ptr< Face > bestFace
std::pair< T *, bool > insertStrategyInfo(A &&... args)
Insert a StrategyInfo item.
weak_ptr< Face > previousFace
Represents a Measurements entry.
static const int UPDATE_MEASUREMENTS_N_LEVELS
time::microseconds prediction
represents a FIB entry
Definition: fib-entry.hpp:53
void adjustPredictUp()
scheduler::EventId bestFaceTimeout
timer that expires when best face does not respond within predicted time
static const time::nanoseconds MEASUREMENTS_LIFETIME
StrategyInfo on pit::Entry.
static Name makeInstanceName(const Name &input, const Name &strategyName)
Construct a strategy instance name.
Definition: strategy.cpp:134
void doPropagate(FaceId inFaceId, weak_ptr< pit::Entry > pitEntryWeak)
propagate to another upstream
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
Performs a FIB lookup, considering Link object if present.
Definition: strategy.cpp:282
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:337
shared_ptr< Face > getBestFace()
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:45
bool hasNextHop(const Face &face) const
Definition: fib-entry.cpp:46
MeasurementsEntryInfo & getMeasurementsEntryInfo(measurements::Entry *entry)
scheduler::EventId propagateTimer
timer for propagating to another face
void inheritFrom(const MeasurementsEntryInfo &other)
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
static const time::microseconds DEFER_RANGE_WITHOUT_BEST_FACE
NccStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
void updateBestFace(const Face &face)
Entry * getParent(const Entry &child)
find or insert a Measurements entry for child&#39;s parent
static const time::microseconds MIN_PREDICTION
void afterReceiveInterest(const FaceEndpoint &ingress, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after Interest is received.
generalization of a network interface
Definition: face.hpp:54
MeasurementsEntryInfo()
Represents a collection of nexthops.
Definition: fib-entry.hpp:39
PartialName parameters
parameter components
Definition: strategy.hpp:359
bool hasPendingOutRecords(const pit::Entry &pitEntry)
determine whether pitEntry has any pending out-records
Definition: algorithm.cpp:108
FaceId getId() const
Definition: face.hpp:239
static const int ADJUST_PREDICT_DOWN_SHIFT
Represents a forwarding strategy.
Definition: strategy.hpp:37
This file contains common algorithms used by forwarding strategies.
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
static ParsedInstanceName parseInstanceName(const Name &input)
Parse a strategy instance name.
Definition: strategy.cpp:123
static const Name & getStrategyName()
void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data) override
Trigger before PIT entry is satisfied.
static const time::microseconds INITIAL_PREDICTION
StrategyInfo on measurements::Entry.
static const time::microseconds DEFER_FIRST_WITHOUT_BEST_FACE
~PitEntryInfo() override
NFD_REGISTER_STRATEGY(SelfLearningStrategy)
Represents a nexthop record in a FIB entry.
Definition: fib-nexthop.hpp:37
static const time::microseconds MAX_PREDICTION
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:32
uint64_t FaceId
Identifies a face.
Definition: face-common.hpp:44
Face * getFace(FaceId id) const
Definition: strategy.hpp:343
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
Schedule the PIT entry for immediate deletion.
Definition: strategy.hpp:291
pit::OutRecord * sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &egress, const Interest &interest)
Send an Interest packet.
Definition: strategy.cpp:197
Entry * get(const Name &name)
find or insert a Measurements entry for name
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:358