blob: d0b43f16f993f2ed22c56015dd1409c2be6dacf3 [file] [log] [blame]
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (C) 2014 Named Data Networking Project
4 * See COPYING for copyright and distribution information.
5 */
6
7#include "ncc-strategy.hpp"
8
9namespace nfd {
10namespace fw {
11
Junxiao Shif3c07812014-03-11 21:48:49 -070012const Name NccStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/ncc");
13
14NccStrategy::NccStrategy(Forwarder& forwarder, const Name& name)
15 : Strategy(forwarder, name)
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070016{
17}
18
19NccStrategy::~NccStrategy()
20{
21}
22
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -070023const time::nanoseconds NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = time::microseconds(4000);
24const time::nanoseconds NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = time::microseconds(75000);
25const time::nanoseconds NccStrategy::MEASUREMENTS_LIFETIME = time::seconds(16);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070026
27void
28NccStrategy::afterReceiveInterest(const Face& inFace,
29 const Interest& interest,
30 shared_ptr<fib::Entry> fibEntry,
31 shared_ptr<pit::Entry> pitEntry)
32{
33 const fib::NextHopList& nexthops = fibEntry->getNextHops();
34 if (nexthops.size() == 0) {
35 this->rejectPendingInterest(pitEntry);
36 return;
37 }
38
39 shared_ptr<PitEntryInfo> pitEntryInfo =
40 pitEntry->getOrCreateStrategyInfo<PitEntryInfo>();
41 bool isNewInterest = pitEntryInfo->m_isNewInterest;
42 if (!isNewInterest) {
43 return;
44 }
45 pitEntryInfo->m_isNewInterest = false;
46
47 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
48 this->getMeasurementsEntryInfo(pitEntry);
49
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -070050 time::nanoseconds deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
51 time::nanoseconds deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070052 size_t nUpstreams = nexthops.size();
53
54 shared_ptr<Face> bestFace = measurementsEntryInfo->getBestFace();
55 if (static_cast<bool>(bestFace) && fibEntry->hasNextHop(bestFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070056 pitEntry->canForwardTo(*bestFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070057 // TODO Should we use `randlow = 100 + nrand48(h->seed) % 4096U;` ?
58 deferFirst = measurementsEntryInfo->m_prediction;
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -070059 deferRange = time::nanoseconds((deferFirst.count() +
60 static_cast<time::nanoseconds>(time::microseconds(1)).count()) / 2);
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070061 --nUpstreams;
62 this->sendInterest(pitEntry, bestFace);
63 pitEntryInfo->m_bestFaceTimeout = scheduler::schedule(
64 measurementsEntryInfo->m_prediction,
65 bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
66 }
67 else {
68 // use first nexthop
69 this->sendInterest(pitEntry, nexthops.begin()->getFace());
70 // TODO avoid sending to inFace
71 }
72
73 shared_ptr<Face> previousFace = measurementsEntryInfo->m_previousFace.lock();
74 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070075 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070076 --nUpstreams;
77 }
78
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -070079 pitEntryInfo->m_maxInterval = std::max(static_cast<time::nanoseconds>(time::microseconds(1)),
80 time::nanoseconds((2 * deferRange.count() + nUpstreams - 1) / nUpstreams));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070081 pitEntryInfo->m_propagateTimer = scheduler::schedule(deferFirst,
82 bind(&NccStrategy::doPropagate, this,
83 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
84}
85
86void
87NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
88{
89 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
90 if (!static_cast<bool>(pitEntry)) {
91 return;
92 }
93 shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
94 if (!static_cast<bool>(fibEntry)) {
95 return;
96 }
97
98 shared_ptr<PitEntryInfo> pitEntryInfo =
99 pitEntry->getStrategyInfo<PitEntryInfo>();
100 BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
101
102 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
103 this->getMeasurementsEntryInfo(pitEntry);
104
105 shared_ptr<Face> previousFace = measurementsEntryInfo->m_previousFace.lock();
106 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -0700107 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700108 this->sendInterest(pitEntry, previousFace);
109 }
110
111 const fib::NextHopList& nexthops = fibEntry->getNextHops();
112 bool isForwarded = false;
113 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
114 shared_ptr<Face> face = it->getFace();
Junxiao Shi57f0f312014-03-16 11:52:20 -0700115 if (pitEntry->canForwardTo(*face)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700116 isForwarded = true;
117 this->sendInterest(pitEntry, face);
118 break;
119 }
120 }
121
122 if (isForwarded) {
123 static unsigned short seed[3];
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700124 time::nanoseconds deferNext = time::nanoseconds(nrand48(seed) % pitEntryInfo->m_maxInterval.count());
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700125 pitEntryInfo->m_propagateTimer = scheduler::schedule(deferNext,
126 bind(&NccStrategy::doPropagate, this,
127 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
128 }
129}
130
131void
132NccStrategy::timeoutOnBestFace(weak_ptr<pit::Entry> pitEntryWeak)
133{
134 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
135 if (!static_cast<bool>(pitEntry)) {
136 return;
137 }
138 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
139
140 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
141 if (!static_cast<bool>(measurementsEntry)) {
142 // going out of this strategy's namespace
143 return;
144 }
145 this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
146
147 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
148 this->getMeasurementsEntryInfo(measurementsEntry);
149 measurementsEntryInfo->adjustPredictUp();
150
151 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
152 }
153}
154
155void
156NccStrategy::beforeSatisfyPendingInterest(shared_ptr<pit::Entry> pitEntry,
157 const Face& inFace, const Data& data)
158{
159 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*pitEntry);
160
161 for (int i = 0; i < UPDATE_MEASUREMENTS_N_LEVELS; ++i) {
162 if (!static_cast<bool>(measurementsEntry)) {
163 // going out of this strategy's namespace
164 return;
165 }
166 this->getMeasurements().extendLifetime(*measurementsEntry, MEASUREMENTS_LIFETIME);
167
168 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
169 this->getMeasurementsEntryInfo(measurementsEntry);
170 measurementsEntryInfo->updateBestFace(inFace);
171
172 measurementsEntry = this->getMeasurements().getParent(measurementsEntry);
173 }
174
175 shared_ptr<PitEntryInfo> pitEntryInfo =
176 pitEntry->getStrategyInfo<PitEntryInfo>();
177 scheduler::cancel(pitEntryInfo->m_propagateTimer);
178}
179
180shared_ptr<NccStrategy::MeasurementsEntryInfo>
181NccStrategy::getMeasurementsEntryInfo(shared_ptr<pit::Entry> entry)
182{
183 shared_ptr<measurements::Entry> measurementsEntry = this->getMeasurements().get(*entry);
184 return this->getMeasurementsEntryInfo(measurementsEntry);
185}
186
187shared_ptr<NccStrategy::MeasurementsEntryInfo>
188NccStrategy::getMeasurementsEntryInfo(shared_ptr<measurements::Entry> entry)
189{
190 shared_ptr<MeasurementsEntryInfo> info = entry->getStrategyInfo<MeasurementsEntryInfo>();
191 if (static_cast<bool>(info)) {
192 return info;
193 }
194
195 info = make_shared<MeasurementsEntryInfo>();
196 entry->setStrategyInfo(info);
197
198 shared_ptr<measurements::Entry> parentEntry = this->getMeasurements().getParent(entry);
199 if (static_cast<bool>(parentEntry)) {
200 shared_ptr<MeasurementsEntryInfo> parentInfo = this->getMeasurementsEntryInfo(parentEntry);
201 BOOST_ASSERT(static_cast<bool>(parentInfo));
202 info->inheritFrom(*parentInfo);
203 }
204
205 return info;
206}
207
208
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700209const time::nanoseconds NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION =
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700210 time::microseconds(8192);
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700211const time::nanoseconds NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION =
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700212 time::microseconds(127);
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700213const time::nanoseconds NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION =
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700214 time::microseconds(160000);
215
216NccStrategy::MeasurementsEntryInfo::MeasurementsEntryInfo()
217 : m_prediction(INITIAL_PREDICTION)
218{
219}
220
221void
222NccStrategy::MeasurementsEntryInfo::inheritFrom(const MeasurementsEntryInfo& other)
223{
224 this->operator=(other);
225}
226
227shared_ptr<Face>
228NccStrategy::MeasurementsEntryInfo::getBestFace(void) {
229 shared_ptr<Face> best = m_bestFace.lock();
230 if (static_cast<bool>(best)) {
231 return best;
232 }
233 m_bestFace = best = m_previousFace.lock();
234 return best;
235}
236
237void
238NccStrategy::MeasurementsEntryInfo::updateBestFace(const Face& face) {
239 if (m_bestFace.expired()) {
240 m_bestFace = const_cast<Face&>(face).shared_from_this();
241 return;
242 }
243 shared_ptr<Face> bestFace = m_bestFace.lock();
244 if (bestFace.get() == &face) {
245 this->adjustPredictDown();
246 }
247 else {
248 m_previousFace = m_bestFace;
249 m_bestFace = const_cast<Face&>(face).shared_from_this();
250 }
251}
252
253void
254NccStrategy::MeasurementsEntryInfo::adjustPredictDown() {
255 m_prediction = std::max(MIN_PREDICTION,
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700256 time::nanoseconds(m_prediction.count() - (m_prediction.count() >> ADJUST_PREDICT_DOWN_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700257}
258
259void
260NccStrategy::MeasurementsEntryInfo::adjustPredictUp() {
261 m_prediction = std::min(MAX_PREDICTION,
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700262 time::nanoseconds(m_prediction.count() + (m_prediction.count() >> ADJUST_PREDICT_UP_SHIFT)));
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700263}
264
265void
266NccStrategy::MeasurementsEntryInfo::ageBestFace() {
267 m_previousFace = m_bestFace;
268 m_bestFace.reset();
269}
270
271NccStrategy::PitEntryInfo::PitEntryInfo()
272 : m_isNewInterest(true)
273{
274}
275
276NccStrategy::PitEntryInfo::~PitEntryInfo()
277{
278 scheduler::cancel(m_bestFaceTimeout);
279 scheduler::cancel(m_propagateTimer);
280}
281
282} // namespace fw
283} // namespace nfd