blob: 925a3cf96b759da43adc9d003d148ee7af9bca89 [file] [log] [blame]
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Junxiao Shiaf6569a2014-06-14 00:01:34 -07003 * Copyright (c) 2014, 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
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
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/>.
Junxiao Shiaf6569a2014-06-14 00:01:34 -070024 */
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070025
26#include "ncc-strategy.hpp"
Junxiao Shiaf6569a2014-06-14 00:01:34 -070027#include "core/random.hpp"
28#include <boost/random/uniform_int_distribution.hpp>
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070029
30namespace nfd {
31namespace fw {
32
Junxiao Shif3c07812014-03-11 21:48:49 -070033const Name NccStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/ncc");
34
35NccStrategy::NccStrategy(Forwarder& forwarder, const Name& name)
36 : Strategy(forwarder, name)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070037{
38}
39
40NccStrategy::~NccStrategy()
41{
42}
43
Junxiao Shi1391d612014-03-27 22:27:20 -070044const time::microseconds NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = time::microseconds(4000);
45const time::microseconds NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = time::microseconds(75000);
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -070046const time::nanoseconds NccStrategy::MEASUREMENTS_LIFETIME = time::seconds(16);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070047
48void
49NccStrategy::afterReceiveInterest(const Face& inFace,
50 const Interest& interest,
51 shared_ptr<fib::Entry> fibEntry,
52 shared_ptr<pit::Entry> pitEntry)
53{
54 const fib::NextHopList& nexthops = fibEntry->getNextHops();
55 if (nexthops.size() == 0) {
56 this->rejectPendingInterest(pitEntry);
57 return;
58 }
59
60 shared_ptr<PitEntryInfo> pitEntryInfo =
61 pitEntry->getOrCreateStrategyInfo<PitEntryInfo>();
Junxiao Shi1391d612014-03-27 22:27:20 -070062 bool isNewInterest = pitEntryInfo->isNewInterest;
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070063 if (!isNewInterest) {
64 return;
65 }
Junxiao Shi1391d612014-03-27 22:27:20 -070066 pitEntryInfo->isNewInterest = false;
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070067
68 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
69 this->getMeasurementsEntryInfo(pitEntry);
70
Junxiao Shi1391d612014-03-27 22:27:20 -070071 time::microseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
72 time::microseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070073 size_t nUpstreams = nexthops.size();
74
75 shared_ptr<Face> bestFace = measurementsEntryInfo->getBestFace();
76 if (static_cast<bool>(bestFace) && fibEntry->hasNextHop(bestFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070077 pitEntry->canForwardTo(*bestFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070078 // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
Junxiao Shi1391d612014-03-27 22:27:20 -070079 deferFirst = measurementsEntryInfo->prediction;
80 deferRange = time::microseconds((deferFirst.count() + 1) / 2);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070081 --nUpstreams;
82 this->sendInterest(pitEntry, bestFace);
Junxiao Shi1391d612014-03-27 22:27:20 -070083 pitEntryInfo->bestFaceTimeout = scheduler::schedule(
84 measurementsEntryInfo->prediction,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070085 bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
86 }
87 else {
88 // use first nexthop
89 this->sendInterest(pitEntry, nexthops.begin()->getFace());
90 // TODO avoid sending to inFace
91 }
92
Junxiao Shi1391d612014-03-27 22:27:20 -070093 shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070094 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070095 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070096 --nUpstreams;
97 }
98
Junxiao Shi1391d612014-03-27 22:27:20 -070099 if (nUpstreams > 0) {
100 pitEntryInfo->maxInterval = std::max(time::microseconds(1),
101 time::microseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
102 }
Junxiao Shicbb490a2014-08-13 12:24:24 -0700103 else {
104 // Normally, maxInterval is unused if there aren't any face beyond best and previousBest.
105 // However, in case FIB entry gains a new nexthop before doPropagate executes (bug 1853),
106 // this maxInterval would be used to determine when the next doPropagate would happen.
107 pitEntryInfo->maxInterval = deferFirst;
108 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700109 pitEntryInfo->propagateTimer = scheduler::schedule(deferFirst,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700110 bind(&NccStrategy::doPropagate, this,
111 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
112}
113
114void
115NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
116{
117 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
118 if (!static_cast<bool>(pitEntry)) {
119 return;
120 }
121 shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
122 if (!static_cast<bool>(fibEntry)) {
123 return;
124 }
125
Junxiao Shi1391d612014-03-27 22:27:20 -0700126 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
127 // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
128 // from a timer set by NccStrategy.
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700129 BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
130
131 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
132 this->getMeasurementsEntryInfo(pitEntry);
133
Junxiao Shi1391d612014-03-27 22:27:20 -0700134 shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700135 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -0700136 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700137 this->sendInterest(pitEntry, previousFace);
138 }
139
140 const fib::NextHopList& nexthops = fibEntry->getNextHops();
141 bool isForwarded = false;
142 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
143 shared_ptr<Face> face = it->getFace();
Junxiao Shi57f0f312014-03-16 11:52:20 -0700144 if (pitEntry->canForwardTo(*face)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700145 isForwarded = true;
146 this->sendInterest(pitEntry, face);
147 break;
148 }
149 }
150
151 if (isForwarded) {
Junxiao Shicbb490a2014-08-13 12:24:24 -0700152 boost::random::uniform_int_distribution<time::nanoseconds::rep> dist(0,
153 pitEntryInfo->maxInterval.count() - 1);
Junxiao Shiaf6569a2014-06-14 00:01:34 -0700154 time::nanoseconds deferNext = time::nanoseconds(dist(getGlobalRng()));
Junxiao Shi1391d612014-03-27 22:27:20 -0700155 pitEntryInfo->propagateTimer = scheduler::schedule(deferNext,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700156 bind(&NccStrategy::doPropagate, this,
157 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
158 }
159}
160
161void
162NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
163{
164 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
165 if (!static_cast<bool>(pitEntry)) {
166 return;
167 }
168 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
169
170 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
171 if (!static_cast<bool>(measurementsEntry)) {
172 // going out of this strategy's namespace
173 return;
174 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700175 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700176
177 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
178 this->getMeasurementsEntryInfo(measurementsEntry);
179 measurementsEntryInfo->adjustPredictUp();
180
181 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
182 }
183}
184
185void
Junxiao Shi82e7f582014-09-07 15:15:40 -0700186NccStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
187 const Face& inFace, const Data& data)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700188{
Junxiao Shi82e7f582014-09-07 15:15:40 -0700189 if (pitEntry->getInRecords().empty()) {
190 // PIT entry has already been satisfied (and is now waiting for straggler timer to expire)
191 // NCC does not collect measurements for non-best face
192 return;
193 }
194
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700195 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
196
197 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
198 if (!static_cast<bool>(measurementsEntry)) {
199 // going out of this strategy's namespace
200 return;
201 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700202 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700203
204 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
205 this->getMeasurementsEntryInfo(measurementsEntry);
206 measurementsEntryInfo->updateBestFace(inFace);
207
208 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
209 }
210
Junxiao Shi1391d612014-03-27 22:27:20 -0700211 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
212 if (static_cast<bool>(pitEntryInfo)) {
213 scheduler::cancel(pitEntryInfo->propagateTimer);
214 }
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700215}
216
217shared_ptr<NccStrategy::MeasurementsEntryInfo>
218NccStrategy::getMeasurementsEntryInfo(shared_ptr<pit::Entry> entry)
219{
220 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*entry);
221 return this->getMeasurementsEntryInfo(measurementsEntry);
222}
223
224shared_ptr<NccStrategy::MeasurementsEntryInfo>
225NccStrategy::getMeasurementsEntryInfo(shared_ptr<measurements::Entry> entry)
226{
227 shared_ptr<MeasurementsEntryInfo> info = entry->getStrategyInfo<MeasurementsEntryInfo>();
228 if (static_cast<bool>(info)) {
229 return info;
230 }
231
232 info = make_shared<MeasurementsEntryInfo>();
233 entry->setStrategyInfo(info);
234
235 shared_ptr<measurements::Entry> parentEntry = this->getMeasurements().getParent(entry);
236 if (static_cast<bool>(parentEntry)) {
237 shared_ptr<MeasurementsEntryInfo> parentInfo = this->getMeasurementsEntryInfo(parentEntry);
238 BOOST_ASSERT(static_cast<bool>(parentInfo));
239 info->inheritFrom(*parentInfo);
240 }
241
242 return info;
243}
244
245
Junxiao Shi1391d612014-03-27 22:27:20 -0700246const time::microseconds NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION =
247 time::microseconds(8192);
248const time::microseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION =
249 time::microseconds(127);
250const time::microseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION =
251 time::microseconds(160000);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700252
253NccStrategy::MeasurementsEntryInfo::MeasurementsEntryInfo()
Junxiao Shi1391d612014-03-27 22:27:20 -0700254 : prediction(INITIAL_PREDICTION)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700255{
256}
257
258void
259NccStrategy::MeasurementsEntryInfo::inheritFrom(const MeasurementsEntryInfo& other)
260{
261 this->operator=(other);
262}
263
264shared_ptr<Face>
265NccStrategy::MeasurementsEntryInfo::getBestFace(void) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700266 shared_ptr<Face> best = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700267 if (static_cast<bool>(best)) {
268 return best;
269 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700270 this->bestFace = best = this->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700271 return best;
272}
273
274void
275NccStrategy::MeasurementsEntryInfo::updateBestFace(const Face& face) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700276 if (this->bestFace.expired()) {
277 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700278 return;
279 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700280 shared_ptr<Face> bestFace = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700281 if (bestFace.get() == &face) {
282 this->adjustPredictDown();
283 }
284 else {
Junxiao Shi1391d612014-03-27 22:27:20 -0700285 this->previousFace = this->bestFace;
286 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700287 }
288}
289
290void
291NccStrategy::MeasurementsEntryInfo::adjustPredictDown() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700292 prediction = std::max(MIN_PREDICTION,
293 time::microseconds(prediction.count() - (prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700294}
295
296void
297NccStrategy::MeasurementsEntryInfo::adjustPredictUp() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700298 prediction = std::min(MAX_PREDICTION,
299 time::microseconds(prediction.count() + (prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700300}
301
302void
303NccStrategy::MeasurementsEntryInfo::ageBestFace() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700304 this->previousFace = this->bestFace;
305 this->bestFace.reset();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700306}
307
308NccStrategy::PitEntryInfo::PitEntryInfo()
Junxiao Shi1391d612014-03-27 22:27:20 -0700309 : isNewInterest(true)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700310{
311}
312
313NccStrategy::PitEntryInfo::~PitEntryInfo()
314{
Junxiao Shi1391d612014-03-27 22:27:20 -0700315 scheduler::cancel(this->bestFaceTimeout);
316 scheduler::cancel(this->propagateTimer);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700317}
318
319} // namespace fw
320} // namespace nfd