blob: 838dd9a2cbc9a53408e60d5c93aeccad7799feec [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 }
103 pitEntryInfo->propagateTimer = scheduler::schedule(deferFirst,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700104 bind(&NccStrategy::doPropagate, this,
105 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
106}
107
108void
109NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
110{
111 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
112 if (!static_cast<bool>(pitEntry)) {
113 return;
114 }
115 shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
116 if (!static_cast<bool>(fibEntry)) {
117 return;
118 }
119
Junxiao Shi1391d612014-03-27 22:27:20 -0700120 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
121 // pitEntryInfo is guaranteed to exist here, because doPropagate is triggered
122 // from a timer set by NccStrategy.
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700123 BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
124
125 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
126 this->getMeasurementsEntryInfo(pitEntry);
127
Junxiao Shi1391d612014-03-27 22:27:20 -0700128 shared_ptr<Face> previousFace = measurementsEntryInfo->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700129 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -0700130 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700131 this->sendInterest(pitEntry, previousFace);
132 }
133
134 const fib::NextHopList& nexthops = fibEntry->getNextHops();
135 bool isForwarded = false;
136 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
137 shared_ptr<Face> face = it->getFace();
Junxiao Shi57f0f312014-03-16 11:52:20 -0700138 if (pitEntry->canForwardTo(*face)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700139 isForwarded = true;
140 this->sendInterest(pitEntry, face);
141 break;
142 }
143 }
144
145 if (isForwarded) {
Junxiao Shiaf6569a2014-06-14 00:01:34 -0700146 boost::random::uniform_int_distribution<time::nanoseconds::rep> dist(
147 0, pitEntryInfo->maxInterval.count() - 1);
148 time::nanoseconds deferNext = time::nanoseconds(dist(getGlobalRng()));
Junxiao Shi1391d612014-03-27 22:27:20 -0700149 pitEntryInfo->propagateTimer = scheduler::schedule(deferNext,
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700150 bind(&NccStrategy::doPropagate, this,
151 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
152 }
153}
154
155void
156NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
157{
158 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
159 if (!static_cast<bool>(pitEntry)) {
160 return;
161 }
162 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
163
164 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
165 if (!static_cast<bool>(measurementsEntry)) {
166 // going out of this strategy's namespace
167 return;
168 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700169 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700170
171 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
172 this->getMeasurementsEntryInfo(measurementsEntry);
173 measurementsEntryInfo->adjustPredictUp();
174
175 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
176 }
177}
178
179void
180NccStrategy::beforeSatisfyPendingInterest(shared_ptr<pit::Entry> pitEntry,
181 const Face& inFace, const Data& data)
182{
183 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
184
185 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
186 if (!static_cast<bool>(measurementsEntry)) {
187 // going out of this strategy's namespace
188 return;
189 }
Junxiao Shiee5a4442014-07-27 17:13:43 -0700190 this->getMeasurements().extendLifetime(measurementsEntry, MEASUREMENTS_LIFETIME);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700191
192 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
193 this->getMeasurementsEntryInfo(measurementsEntry);
194 measurementsEntryInfo->updateBestFace(inFace);
195
196 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
197 }
198
Junxiao Shi1391d612014-03-27 22:27:20 -0700199 shared_ptr<PitEntryInfo> pitEntryInfo = pitEntry->getStrategyInfo<PitEntryInfo>();
200 if (static_cast<bool>(pitEntryInfo)) {
201 scheduler::cancel(pitEntryInfo->propagateTimer);
202 }
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700203}
204
205shared_ptr<NccStrategy::MeasurementsEntryInfo>
206NccStrategy::getMeasurementsEntryInfo(shared_ptr<pit::Entry> entry)
207{
208 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*entry);
209 return this->getMeasurementsEntryInfo(measurementsEntry);
210}
211
212shared_ptr<NccStrategy::MeasurementsEntryInfo>
213NccStrategy::getMeasurementsEntryInfo(shared_ptr<measurements::Entry> entry)
214{
215 shared_ptr<MeasurementsEntryInfo> info = entry->getStrategyInfo<MeasurementsEntryInfo>();
216 if (static_cast<bool>(info)) {
217 return info;
218 }
219
220 info = make_shared<MeasurementsEntryInfo>();
221 entry->setStrategyInfo(info);
222
223 shared_ptr<measurements::Entry> parentEntry = this->getMeasurements().getParent(entry);
224 if (static_cast<bool>(parentEntry)) {
225 shared_ptr<MeasurementsEntryInfo> parentInfo = this->getMeasurementsEntryInfo(parentEntry);
226 BOOST_ASSERT(static_cast<bool>(parentInfo));
227 info->inheritFrom(*parentInfo);
228 }
229
230 return info;
231}
232
233
Junxiao Shi1391d612014-03-27 22:27:20 -0700234const time::microseconds NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION =
235 time::microseconds(8192);
236const time::microseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION =
237 time::microseconds(127);
238const time::microseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION =
239 time::microseconds(160000);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700240
241NccStrategy::MeasurementsEntryInfo::MeasurementsEntryInfo()
Junxiao Shi1391d612014-03-27 22:27:20 -0700242 : prediction(INITIAL_PREDICTION)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700243{
244}
245
246void
247NccStrategy::MeasurementsEntryInfo::inheritFrom(const MeasurementsEntryInfo& other)
248{
249 this->operator=(other);
250}
251
252shared_ptr<Face>
253NccStrategy::MeasurementsEntryInfo::getBestFace(void) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700254 shared_ptr<Face> best = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700255 if (static_cast<bool>(best)) {
256 return best;
257 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700258 this->bestFace = best = this->previousFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700259 return best;
260}
261
262void
263NccStrategy::MeasurementsEntryInfo::updateBestFace(const Face& face) {
Junxiao Shi1391d612014-03-27 22:27:20 -0700264 if (this->bestFace.expired()) {
265 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700266 return;
267 }
Junxiao Shi1391d612014-03-27 22:27:20 -0700268 shared_ptr<Face> bestFace = this->bestFace.lock();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700269 if (bestFace.get() == &face) {
270 this->adjustPredictDown();
271 }
272 else {
Junxiao Shi1391d612014-03-27 22:27:20 -0700273 this->previousFace = this->bestFace;
274 this->bestFace = const_cast<Face&>(face).shared_from_this();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700275 }
276}
277
278void
279NccStrategy::MeasurementsEntryInfo::adjustPredictDown() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700280 prediction = std::max(MIN_PREDICTION,
281 time::microseconds(prediction.count() - (prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700282}
283
284void
285NccStrategy::MeasurementsEntryInfo::adjustPredictUp() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700286 prediction = std::min(MAX_PREDICTION,
287 time::microseconds(prediction.count() + (prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700288}
289
290void
291NccStrategy::MeasurementsEntryInfo::ageBestFace() {
Junxiao Shi1391d612014-03-27 22:27:20 -0700292 this->previousFace = this->bestFace;
293 this->bestFace.reset();
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700294}
295
296NccStrategy::PitEntryInfo::PitEntryInfo()
Junxiao Shi1391d612014-03-27 22:27:20 -0700297 : isNewInterest(true)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700298{
299}
300
301NccStrategy::PitEntryInfo::~PitEntryInfo()
302{
Junxiao Shi1391d612014-03-27 22:27:20 -0700303 scheduler::cancel(this->bestFaceTimeout);
304 scheduler::cancel(this->propagateTimer);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700305}
306
307} // namespace fw
308} // namespace nfd