ncc-strategy.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "ncc-strategy.hpp"
27 #include "algorithm.hpp"
28 #include "core/random.hpp"
29 
30 namespace nfd {
31 namespace fw {
32 
33 NFD_REGISTER_STRATEGY(NccStrategy);
34 
35 const time::microseconds NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = time::microseconds(4000);
36 const time::microseconds NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = time::microseconds(75000);
37 const time::nanoseconds NccStrategy::MEASUREMENTS_LIFETIME = time::seconds(16);
38 
39 NccStrategy::NccStrategy(Forwarder& forwarder, const Name& name)
40  : Strategy(forwarder)
41 {
43  if (!parsed.parameters.empty()) {
44  BOOST_THROW_EXCEPTION(std::invalid_argument("NccStrategy does not accept parameters"));
45  }
46  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
47  BOOST_THROW_EXCEPTION(std::invalid_argument(
48  "NccStrategy does not support version " + std::to_string(*parsed.version)));
49  }
51 }
52 
53 const Name&
55 {
56  static Name strategyName("/localhost/nfd/strategy/ncc/%FD%01");
57  return strategyName;
58 }
59 
60 void
61 NccStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
62  const shared_ptr<pit::Entry>& pitEntry)
63 {
64  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
65  const fib::NextHopList& nexthops = fibEntry.getNextHops();
66  if (nexthops.size() == 0) {
67  this->rejectPendingInterest(pitEntry);
68  return;
69  }
70 
71  PitEntryInfo* pitEntryInfo = pitEntry->insertStrategyInfo<PitEntryInfo>().first;
72  bool isNewPitEntry = !hasPendingOutRecords(*pitEntry);
73  if (!isNewPitEntry) {
74  return;
75  }
76 
77  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(pitEntry);
78 
79  time::microseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
80  time::microseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
81  size_t nUpstreams = nexthops.size();
82 
83  shared_ptr<Face> bestFace = meInfo.getBestFace();
84  if (bestFace != nullptr && fibEntry.hasNextHop(*bestFace) &&
85  !wouldViolateScope(inFace, interest, *bestFace) &&
86  canForwardToLegacy(*pitEntry, *bestFace)) {
87  // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
88  deferFirst = meInfo.prediction;
89  deferRange = time::microseconds((deferFirst.count() + 1) / 2);
90  --nUpstreams;
91  this->sendInterest(pitEntry, *bestFace, interest);
92  pitEntryInfo->bestFaceTimeout = scheduler::schedule(
93  meInfo.prediction,
94  bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
95  }
96  else {
97  // use first eligible nexthop
98  auto firstEligibleNexthop = std::find_if(nexthops.begin(), nexthops.end(),
99  [&] (const fib::NextHop& nexthop) {
100  Face& outFace = nexthop.getFace();
101  return !wouldViolateScope(inFace, interest, outFace) &&
102  canForwardToLegacy(*pitEntry, outFace);
103  });
104  if (firstEligibleNexthop != nexthops.end()) {
105  this->sendInterest(pitEntry, firstEligibleNexthop->getFace(), interest);
106  }
107  else {
108  this->rejectPendingInterest(pitEntry);
109  return;
110  }
111  }
112 
113  shared_ptr<Face> previousFace = meInfo.previousFace.lock();
114  if (previousFace != nullptr && fibEntry.hasNextHop(*previousFace) &&
115  !wouldViolateScope(inFace, interest, *previousFace) &&
116  canForwardToLegacy(*pitEntry, *previousFace)) {
117  --nUpstreams;
118  }
119 
120  if (nUpstreams > 0) {
121  pitEntryInfo->maxInterval = std::max(time::microseconds(1),
122  time::microseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
123  }
124  else {
125  // Normally, maxInterval is unused if there aren't any face beyond best and previousBest.
126  // However, in case FIB entry gains a new nexthop before doPropagate executes (bug 1853),
127  // this maxInterval would be used to determine when the next doPropagate would happen.
128  pitEntryInfo->maxInterval = deferFirst;
129  }
130  pitEntryInfo->propagateTimer = scheduler::schedule(deferFirst,
131  bind(&NccStrategy::doPropagate, this, inFace.getId(), weak_ptr<pit::Entry>(pitEntry)));
132 }
133 
134 void
135 NccStrategy::doPropagate(FaceId inFaceId, weak_ptr<pit::Entry> pitEntryWeak)
136 {
137  Face* inFace = this->getFace(inFaceId);
138  if (inFace == nullptr) {
139  return;
140  }
141  shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
142  if (pitEntry == nullptr) {
143  return;
144  }
145  pit::InRecordCollection::const_iterator inRecord = pitEntry->getInRecord(*inFace);
146  if (inRecord == pitEntry->in_end()) {
147  return;
148  }
149  const Interest& interest = inRecord->getInterest();
150  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
151 
152  PitEntryInfo* pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
153  // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
154  // from a timer set by NccStrategy.
155  BOOST_ASSERT(pitEntryInfo != nullptr);
156 
157  MeasurementsEntryInfo& meInfo = this->getMeasurementsEntryInfo(pitEntry);
158 
159  shared_ptr<Face> previousFace = meInfo.previousFace.lock();
160  if (previousFace != nullptr && fibEntry.hasNextHop(*previousFace) &&
161  !wouldViolateScope(*inFace, interest, *previousFace) &&
162  canForwardToLegacy(*pitEntry, *previousFace)) {
163  this->sendInterest(pitEntry, *previousFace, interest);
164  }
165 
166  const fib::NextHopList& nexthops = fibEntry.getNextHops();
167  bool isForwarded = false;
168  for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
169  Face& face = it->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 = time::nanoseconds(dist(getGlobalRng()));
181  pitEntryInfo->propagateTimer = scheduler::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 Face& inFace, 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(inFace);
230 
231  measurementsEntry = this->getMeasurements().getParent(*measurementsEntry);
232  }
233 
234  PitEntryInfo* pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
235  if (pitEntryInfo != nullptr) {
236  scheduler::cancel(pitEntryInfo->propagateTimer);
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() == &inFace)
243  scheduler::cancel(pitEntryInfo->bestFaceTimeout);
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 = time::microseconds(8192);
275 const time::microseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION = time::microseconds(127);
276 const time::microseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION = time::milliseconds(160);
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  scheduler::cancel(this->bestFaceTimeout);
341  scheduler::cancel(this->propagateTimer);
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:59
static const int ADJUST_PREDICT_UP_SHIFT
bool hasNextHop(const Face &face) const
Definition: fib-entry.cpp:47
main class of NFD
Definition: forwarder.hpp:52
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:290
time::microseconds maxInterval
maximum interval between forwarding to two nexthops except best and previous
weak_ptr< Face > bestFace
weak_ptr< Face > previousFace
represents a Measurements entry
static const int UPDATE_MEASUREMENTS_N_LEVELS
void cancel(const EventId &eventId)
cancel a scheduled event
Definition: scheduler.cpp:53
time::microseconds prediction
virtual void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data) override
trigger before PIT entry is satisfied
represents a FIB entry
Definition: fib-entry.hpp:51
void adjustPredictUp()
scheduler::EventId bestFaceTimeout
timer that expires when best face does not respond within predicted time
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:191
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:132
std::pair< T *, bool > insertStrategyInfo(A &&...args)
insert a StrategyInfo item
void doPropagate(FaceId inFaceId, weak_ptr< pit::Entry > pitEntryWeak)
propagate to another upstream
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:241
#define NFD_REGISTER_STRATEGY(S)
registers a strategy
Definition: strategy.hpp:328
shared_ptr< Face > getBestFace()
MeasurementsEntryInfo & getMeasurementsEntryInfo(measurements::Entry *entry)
scheduler::EventId propagateTimer
timer for propagating to another face
void inheritFrom(const MeasurementsEntryInfo &other)
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)
std::vector< fib::NextHop > NextHopList
Definition: fib-entry.hpp:47
static const time::microseconds MIN_PREDICTION
MeasurementsEntryInfo()
PartialName parameters
parameter components
Definition: strategy.hpp:263
bool hasPendingOutRecords(const pit::Entry &pitEntry)
determine whether pitEntry has any pending out-records
Definition: algorithm.cpp:113
ndn::optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:262
std::mt19937 & getGlobalRng()
Definition: random.cpp:32
static const int ADJUST_PREDICT_DOWN_SHIFT
represents a forwarding strategy
Definition: strategy.hpp:37
This file contains common algorithms used by forwarding strategies.
Declares the global pseudorandom number generator (PRNG) for NFD.
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
static const Name & getStrategyName()
static const time::microseconds INITIAL_PREDICTION
StrategyInfo on measurements::Entry.
static const time::microseconds DEFER_FIRST_WITHOUT_BEST_FACE
virtual ~PitEntryInfo() override
uint64_t FaceId
identifies a face
Definition: face.hpp:39
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38
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:37
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
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
virtual void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received