blob: 749e97c8a97c7aa72d1d202704bd1a246fd71342 [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 Shie93d6a32014-09-07 16:13:22 -070033const Name NccStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/ncc/%FD%01");
Junxiao Shif3c07812014-03-11 21:48:49 -070034
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 Shi8bfd56d2014-10-08 10:06:00 -070062 bool isNewPitEntry = !pitEntry->hasUnexpiredOutRecords();
63 if (!isNewPitEntry) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070064 return;
65 }
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070066
67 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
68 this->getMeasurementsEntryInfo(pitEntry);
69
Junxiao Shi1391d612014-03-27 22:27:20 -070070 time::microseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
71 time::microseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070072 size_t nUpstreams = nexthops.size();
73
74 shared_ptr<Face> bestFace = measurementsEntryInfo->getBestFace();
75 if (static_cast<bool>(bestFace) && fibEntry->hasNextHop(bestFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070076 pitEntry->canForwardTo(*bestFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070077 // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
Junxiao Shi1391d612014-03-27 22:27:20 -070078 deferFirst = measurementsEntryInfo->prediction;
79 deferRange = time::microseconds((deferFirst.count() + 1) / 2);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070080 --nUpstreams;
81 this->sendInterest(pitEntry, bestFace);
Junxiao Shi1391d612014-03-27 22:27:20 -070082 pitEntryInfo->bestFaceTimeout = scheduler::schedule(
83 measurementsEntryInfo->prediction,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070084 bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
85 }
86 else {
87 // use first nexthop
88 this->sendInterest(pitEntry, nexthops.begin()->getFace());
89 // TODO avoid sending to inFace
90 }
91
Junxiao Shi1391d612014-03-27 22:27:20 -070092 shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070093 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070094 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070095 --nUpstreams;
96 }
97
Junxiao Shi1391d612014-03-27 22:27:20 -070098 if (nUpstreams > 0) {
99 pitEntryInfo->maxInterval = std::max(time::microseconds(1),
100 time::microseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
101 }
Junxiao Shicbb490a2014-08-13 12:24:24 -0700102 else {
103 // Normally, maxInterval is unused if there aren't any face beyond best and previousBest.
104 // However, in case FIB entry gains a new nexthop before doPropagate executes (bug 1853),
105 // this maxInterval would be used to determine when the next doPropagate would happen.
106 pitEntryInfo->maxInterval = deferFirst;
107 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700108 pitEntryInfo->propagateTimer = scheduler::schedule(deferFirst,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700109 bind(&NccStrategy::doPropagate, this,
110 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
111}
112
113void
114NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
115{
116 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
117 if (!static_cast<bool>(pitEntry)) {
118 return;
119 }
120 shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
121 if (!static_cast<bool>(fibEntry)) {
122 return;
123 }
124
Junxiao Shi1391d612014-03-27 22:27:20 -0700125 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
126 // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
127 // from a timer set by NccStrategy.
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700128 BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
129
130 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
131 this->getMeasurementsEntryInfo(pitEntry);
132
Junxiao Shi1391d612014-03-27 22:27:20 -0700133 shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700134 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -0700135 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700136 this->sendInterest(pitEntry, previousFace);
137 }
138
139 const fib::NextHopList& nexthops = fibEntry->getNextHops();
140 bool isForwarded = false;
141 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
142 shared_ptr<Face> face = it->getFace();
Junxiao Shi57f0f312014-03-16 11:52:20 -0700143 if (pitEntry->canForwardTo(*face)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700144 isForwarded = true;
145 this->sendInterest(pitEntry, face);
146 break;
147 }
148 }
149
150 if (isForwarded) {
Junxiao Shicbb490a2014-08-13 12:24:24 -0700151 boost::random::uniform_int_distribution<time::nanoseconds::rep> dist(0,
152 pitEntryInfo->maxInterval.count() - 1);
Junxiao Shiaf6569a2014-06-14 00:01:34 -0700153 time::nanoseconds deferNext = time::nanoseconds(dist(getGlobalRng()));
Junxiao Shi1391d612014-03-27 22:27:20 -0700154 pitEntryInfo->propagateTimer = scheduler::schedule(deferNext,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700155 bind(&NccStrategy::doPropagate, this,
156 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
157 }
158}
159
160void
161NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
162{
163 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
164 if (!static_cast<bool>(pitEntry)) {
165 return;
166 }
167 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
168
169 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
170 if (!static_cast<bool>(measurementsEntry)) {
171 // going out of this strategy's namespace
172 return;
173 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700174 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700175
176 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
177 this->getMeasurementsEntryInfo(measurementsEntry);
178 measurementsEntryInfo->adjustPredictUp();
179
180 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
181 }
182}
183
184void
Junxiao Shi82e7f582014-09-07 15:15:40 -0700185NccStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
186 const Face& inFace, const Data& data)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700187{
Junxiao Shi82e7f582014-09-07 15:15:40 -0700188 if (pitEntry->getInRecords().empty()) {
189 // PIT entry has already been satisfied (and is now waiting for straggler timer to expire)
190 // NCC does not collect measurements for non-best face
191 return;
192 }
193
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700194 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
195
196 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
197 if (!static_cast<bool>(measurementsEntry)) {
198 // going out of this strategy's namespace
199 return;
200 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700201 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700202
203 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
204 this->getMeasurementsEntryInfo(measurementsEntry);
205 measurementsEntryInfo->updateBestFace(inFace);
206
207 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
208 }
209
Junxiao Shi1391d612014-03-27 22:27:20 -0700210 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
211 if (static_cast<bool>(pitEntryInfo)) {
212 scheduler::cancel(pitEntryInfo->propagateTimer);
213 }
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700214}
215
216shared_ptr<NccStrategy::MeasurementsEntryInfo>
217NccStrategy::getMeasurementsEntryInfo(shared_ptr<pit::Entry> entry)
218{
219 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*entry);
220 return this->getMeasurementsEntryInfo(measurementsEntry);
221}
222
223shared_ptr<NccStrategy::MeasurementsEntryInfo>
224NccStrategy::getMeasurementsEntryInfo(shared_ptr<measurements::Entry> entry)
225{
226 shared_ptr<MeasurementsEntryInfo> info = entry->getStrategyInfo<MeasurementsEntryInfo>();
227 if (static_cast<bool>(info)) {
228 return info;
229 }
230
231 info = make_shared<MeasurementsEntryInfo>();
232 entry->setStrategyInfo(info);
233
234 shared_ptr<measurements::Entry> parentEntry = this->getMeasurements().getParent(entry);
235 if (static_cast<bool>(parentEntry)) {
236 shared_ptr<MeasurementsEntryInfo> parentInfo = this->getMeasurementsEntryInfo(parentEntry);
237 BOOST_ASSERT(static_cast<bool>(parentInfo));
238 info->inheritFrom(*parentInfo);
239 }
240
241 return info;
242}
243
244
Junxiao Shi1391d612014-03-27 22:27:20 -0700245const time::microseconds NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION =
246 time::microseconds(8192);
247const time::microseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION =
248 time::microseconds(127);
249const time::microseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION =
250 time::microseconds(160000);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700251
252NccStrategy::MeasurementsEntryInfo::MeasurementsEntryInfo()
Junxiao Shi1391d612014-03-27 22:27:20 -0700253 : prediction(INITIAL_PREDICTION)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700254{
255}
256
257void
258NccStrategy::MeasurementsEntryInfo::inheritFrom(const MeasurementsEntryInfo& other)
259{
260 this->operator=(other);
261}
262
263shared_ptr<Face>
264NccStrategy::MeasurementsEntryInfo::getBestFace(void) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700265 shared_ptr<Face> best = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700266 if (static_cast<bool>(best)) {
267 return best;
268 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700269 this->bestFace = best = this->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700270 return best;
271}
272
273void
274NccStrategy::MeasurementsEntryInfo::updateBestFace(const Face& face) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700275 if (this->bestFace.expired()) {
276 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700277 return;
278 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700279 shared_ptr<Face> bestFace = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700280 if (bestFace.get() == &face) {
281 this->adjustPredictDown();
282 }
283 else {
Junxiao Shi1391d612014-03-27 22:27:20 -0700284 this->previousFace = this->bestFace;
285 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700286 }
287}
288
289void
290NccStrategy::MeasurementsEntryInfo::adjustPredictDown() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700291 prediction = std::max(MIN_PREDICTION,
292 time::microseconds(prediction.count() - (prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700293}
294
295void
296NccStrategy::MeasurementsEntryInfo::adjustPredictUp() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700297 prediction = std::min(MAX_PREDICTION,
298 time::microseconds(prediction.count() + (prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700299}
300
301void
302NccStrategy::MeasurementsEntryInfo::ageBestFace() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700303 this->previousFace = this->bestFace;
304 this->bestFace.reset();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700305}
306
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700307NccStrategy::PitEntryInfo::~PitEntryInfo()
308{
Junxiao Shi1391d612014-03-27 22:27:20 -0700309 scheduler::cancel(this->bestFaceTimeout);
310 scheduler::cancel(this->propagateTimer);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700311}
312
313} // namespace fw
314} // namespace nfd