NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
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 "core/random.hpp"
28 #include <boost/random/uniform_int_distribution.hpp>
29 
30 namespace nfd {
31 namespace fw {
32 
33 const Name NccStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/ncc/%FD%01");
34 NFD_REGISTER_STRATEGY(NccStrategy);
35 
37  : Strategy(forwarder, name)
38 {
39 }
40 
42 {
43 }
44 
45 const time::microseconds NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = time::microseconds(4000);
46 const time::microseconds NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = time::microseconds(75000);
47 const time::nanoseconds NccStrategy::MEASUREMENTS_LIFETIME = time::seconds(16);
48 
49 void
51  const Interest& interest,
52  shared_ptr<fib::Entry> fibEntry,
53  shared_ptr<pit::Entry> pitEntry)
54 {
55  const fib::NextHopList& nexthops = fibEntry->getNextHops();
56  if (nexthops.size() == 0) {
57  this->rejectPendingInterest(pitEntry);
58  return;
59  }
60 
61  shared_ptr<PitEntryInfo> pitEntryInfo =
62  pitEntry->getOrCreateStrategyInfo<PitEntryInfo>();
63  bool isNewPitEntry = !pitEntry->hasUnexpiredOutRecords();
64  if (!isNewPitEntry) {
65  return;
66  }
67 
68  shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
69  this->getMeasurementsEntryInfo(pitEntry);
70 
71  time::microseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
72  time::microseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
73  size_t nUpstreams = nexthops.size();
74 
75  shared_ptr<Face> bestFace = measurementsEntryInfo->getBestFace();
76  if (static_cast<bool>(bestFace) && fibEntry->hasNextHop(bestFace) &&
77  pitEntry->canForwardTo(*bestFace)) {
78  // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
79  deferFirst = measurementsEntryInfo->prediction;
80  deferRange = time::microseconds((deferFirst.count() + 1) / 2);
81  --nUpstreams;
82  this->sendInterest(pitEntry, bestFace);
83  pitEntryInfo->bestFaceTimeout = scheduler::schedule(
84  measurementsEntryInfo->prediction,
85  bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
86  }
87  else {
88  // use first eligible nexthop
89  auto firstEligibleNexthop = std::find_if(nexthops.begin(), nexthops.end(),
90  [&pitEntry] (const fib::NextHop& nexthop) {
91  return pitEntry->canForwardTo(*nexthop.getFace());
92  });
93  if (firstEligibleNexthop != nexthops.end()) {
94  this->sendInterest(pitEntry, firstEligibleNexthop->getFace());
95  }
96  }
97 
98  shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
99  if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
100  pitEntry->canForwardTo(*previousFace)) {
101  --nUpstreams;
102  }
103 
104  if (nUpstreams > 0) {
105  pitEntryInfo->maxInterval = std::max(time::microseconds(1),
106  time::microseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
107  }
108  else {
109  // Normally, maxInterval is unused if there aren't any face beyond best and previousBest.
110  // However, in case FIB entry gains a new nexthop before doPropagate executes (bug 1853),
111  // this maxInterval would be used to determine when the next doPropagate would happen.
112  pitEntryInfo->maxInterval = deferFirst;
113  }
114  pitEntryInfo->propagateTimer = scheduler::schedule(deferFirst,
115  bind(&NccStrategy::doPropagate, this,
116  weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
117 }
118 
119 void
120 NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
121 {
122  shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
123  if (!static_cast<bool>(pitEntry)) {
124  return;
125  }
126  shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
127  if (!static_cast<bool>(fibEntry)) {
128  return;
129  }
130 
131  shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
132  // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
133  // from a timer set by NccStrategy.
134  BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
135 
136  shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
137  this->getMeasurementsEntryInfo(pitEntry);
138 
139  shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
140  if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
141  pitEntry->canForwardTo(*previousFace)) {
142  this->sendInterest(pitEntry, previousFace);
143  }
144 
145  const fib::NextHopList& nexthops = fibEntry->getNextHops();
146  bool isForwarded = false;
147  for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
148  shared_ptr<Face> face = it->getFace();
149  if (pitEntry->canForwardTo(*face)) {
150  isForwarded = true;
151  this->sendInterest(pitEntry, face);
152  break;
153  }
154  }
155 
156  if (isForwarded) {
157  boost::random::uniform_int_distribution<time::nanoseconds::rep> dist(0,
158  pitEntryInfo->maxInterval.count() - 1);
159  time::nanoseconds deferNext = time::nanoseconds(dist(getGlobalRng()));
160  pitEntryInfo->propagateTimer = scheduler::schedule(deferNext,
161  bind(&NccStrategy::doPropagate, this,
162  weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
163  }
164 }
165 
166 void
167 NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
168 {
169  shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
170  if (!static_cast<bool>(pitEntry)) {
171  return;
172  }
173  shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
174 
175  for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
176  if (!static_cast<bool>(measurementsEntry)) {
177  // going out of this strategy's namespace
178  return;
179  }
180  this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
181 
182  shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
183  this->getMeasurementsEntryInfo(measurementsEntry);
184  measurementsEntryInfo->adjustPredictUp();
185 
186  measurementsEntry = this->getMeasurements().getParent(*measurementsEntry);
187  }
188 }
189 
190 void
191 NccStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
192  const Face& inFace, const Data& data)
193 {
194  if (pitEntry->getInRecords().empty()) {
195  // PIT entry has already been satisfied (and is now waiting for straggler timer to expire)
196  // NCC does not collect measurements for non-best face
197  return;
198  }
199 
200  shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
201 
202  for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
203  if (!static_cast<bool>(measurementsEntry)) {
204  // going out of this strategy's namespace
205  return;
206  }
207  this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
208 
209  shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
210  this->getMeasurementsEntryInfo(measurementsEntry);
211  measurementsEntryInfo->updateBestFace(inFace);
212 
213  measurementsEntry = this->getMeasurements().getParent(*measurementsEntry);
214  }
215 
216  shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
217  if (static_cast<bool>(pitEntryInfo)) {
218  scheduler::cancel(pitEntryInfo->propagateTimer);
219  }
220 }
221 
222 shared_ptr<NccStrategy::MeasurementsEntryInfo>
223 NccStrategy::getMeasurementsEntryInfo(shared_ptr<pit::Entry> entry)
224 {
225  shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*entry);
226  return this->getMeasurementsEntryInfo(measurementsEntry);
227 }
228 
229 shared_ptr<NccStrategy::MeasurementsEntryInfo>
230 NccStrategy::getMeasurementsEntryInfo(shared_ptr<measurements::Entry> entry)
231 {
232  shared_ptr<MeasurementsEntryInfo> info = entry->getStrategyInfo<MeasurementsEntryInfo>();
233  if (static_cast<bool>(info)) {
234  return info;
235  }
236 
237  info = make_shared<MeasurementsEntryInfo>();
238  entry->setStrategyInfo(info);
239 
240  shared_ptr<measurements::Entry> parentEntry = this->getMeasurements().getParent(*entry);
241  if (static_cast<bool>(parentEntry)) {
242  shared_ptr<MeasurementsEntryInfo> parentInfo = this->getMeasurementsEntryInfo(parentEntry);
243  BOOST_ASSERT(static_cast<bool>(parentInfo));
244  info->inheritFrom(*parentInfo);
245  }
246 
247  return info;
248 }
249 
250 
252  time::microseconds(8192);
254  time::microseconds(127);
256  time::microseconds(160000);
257 
259  : prediction(INITIAL_PREDICTION)
260 {
261 }
262 
263 void
265 {
266  this->operator=(other);
267 }
268 
269 shared_ptr<Face>
271  shared_ptr<Face> best = this->bestFace.lock();
272  if (static_cast<bool>(best)) {
273  return best;
274  }
275  this->bestFace = best = this->previousFace.lock();
276  return best;
277 }
278 
279 void
281  if (this->bestFace.expired()) {
282  this->bestFace = const_cast<Face&>(face).shared_from_this();
283  return;
284  }
285  shared_ptr<Face> bestFace = this->bestFace.lock();
286  if (bestFace.get() == &face) {
287  this->adjustPredictDown();
288  }
289  else {
290  this->previousFace = this->bestFace;
291  this->bestFace = const_cast<Face&>(face).shared_from_this();
292  }
293 }
294 
295 void
296 NccStrategy::MeasurementsEntryInfo::adjustPredictDown() {
297  prediction = std::max(MIN_PREDICTION,
298  time::microseconds(prediction.count() - (prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
299 }
300 
301 void
303  prediction = std::min(MAX_PREDICTION,
304  time::microseconds(prediction.count() + (prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
305 }
306 
307 void
308 NccStrategy::MeasurementsEntryInfo::ageBestFace() {
309  this->previousFace = this->bestFace;
310  this->bestFace.reset();
311 }
312 
314 {
315  scheduler::cancel(this->bestFaceTimeout);
316  scheduler::cancel(this->propagateTimer);
317 }
318 
319 } // namespace fw
320 } // namespace nfd
static const time::microseconds DEFER_FIRST_WITHOUT_BEST_FACE
static const Name STRATEGY_NAME
virtual void afterReceiveInterest(const Face &inFace, const Interest &interest, shared_ptr< fib::Entry > fibEntry, shared_ptr< pit::Entry > pitEntry) 1
trigger after Interest is received
StrategyInfo on measurements::Entry.
static const int UPDATE_MEASUREMENTS_N_LEVELS
void cancel(const EventId &eventId)
cancel a scheduled event
Definition: scheduler.cpp:53
static const time::microseconds DEFER_RANGE_WITHOUT_BEST_FACE
main class of NFD
Definition: forwarder.hpp:55
represents an Interest packet
Definition: interest.hpp:45
NccStrategy(Forwarder &forwarder, const Name &name=STRATEGY_NAME)
shared_ptr< measurements::Entry > get(const Name &name)
find or insert a Measurements entry for name
shared_ptr< MeasurementsEntryInfo > getMeasurementsEntryInfo(shared_ptr< measurements::Entry > entry)
static const time::microseconds MIN_PREDICTION
virtual void beforeSatisfyInterest(shared_ptr< pit::Entry > pitEntry, const Face &inFace, const Data &data) 1
trigger before PIT entry is satisfied
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:229
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
void inheritFrom(const MeasurementsEntryInfo &other)
void doPropagate(weak_ptr< pit::Entry > pitEntryWeak, weak_ptr< fib::Entry > fibEntryWeak)
propagate to another upstream
NFD_REGISTER_STRATEGY(AccessStrategy)
std::vector< fib::NextHop > NextHopList
Definition: fib-entry.hpp:48
void timeoutOnBestFace(weak_ptr< pit::Entry > pitEntryWeak)
best face did not reply within prediction
static const time::nanoseconds MEASUREMENTS_LIFETIME
Name abstraction to represent an absolute name.
Definition: name.hpp:46
boost::random::mt19937 & getGlobalRng()
Definition: random.cpp:34
void rejectPendingInterest(shared_ptr< pit::Entry > pitEntry)
decide that a pending Interest cannot be forwarded
Definition: strategy.hpp:216
StrategyInfo on pit::Entry.
represents a forwarding strategy
Definition: strategy.hpp:38
void extendLifetime(measurements::Entry &entry, const time::nanoseconds &lifetime)
extend lifetime of an entry
EventId schedule(const time::nanoseconds &after, const Scheduler::Event &event)
schedule an event
Definition: scheduler.cpp:47
static const time::microseconds INITIAL_PREDICTION
void sendInterest(shared_ptr< pit::Entry > pitEntry, shared_ptr< Face > outFace, bool wantNewNonce=false)
send Interest to outFace
Definition: strategy.hpp:208
represents a Data packet
Definition: data.hpp:39
static const time::microseconds MAX_PREDICTION
shared_ptr< measurements::Entry > getParent(const measurements::Entry &child)
find or insert a Measurements entry for child&#39;s parent
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38