blob: 79d8b1a41db5cfc73d89822ab1acc0415ba45f18 [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
23const time::Duration NccStrategy::DEFER_FIRST_WITHOUT_BEST_FACE = time::microseconds(4000);
24const time::Duration NccStrategy::DEFER_RANGE_WITHOUT_BEST_FACE = time::microseconds(75000);
25const time::Duration NccStrategy::MEASUREMENTS_LIFETIME = time::seconds(16);
26
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
50 time::Duration deferFirst = DEFER_FIRST_WITHOUT_BEST_FACE;
51 time::Duration deferRange = DEFER_RANGE_WITHOUT_BEST_FACE;
52 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;
59 deferRange = static_cast<time::Duration>((deferFirst + time::microseconds(1)) / 2);
60 --nUpstreams;
61 this->sendInterest(pitEntry, bestFace);
62 pitEntryInfo->m_bestFaceTimeout = scheduler::schedule(
63 measurementsEntryInfo->m_prediction,
64 bind(&NccStrategy::timeoutOnBestFace, this, weak_ptr<pit::Entry>(pitEntry)));
65 }
66 else {
67 // use first nexthop
68 this->sendInterest(pitEntry, nexthops.begin()->getFace());
69 // TODO avoid sending to inFace
70 }
71
72 shared_ptr<Face> previousFace = measurementsEntryInfo->m_previousFace.lock();
73 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -070074 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -070075 --nUpstreams;
76 }
77
78 pitEntryInfo->m_maxInterval = std::max(time::microseconds(1),
79 static_cast<time::Duration>((2 * deferRange + nUpstreams - 1) / nUpstreams));
80 pitEntryInfo->m_propagateTimer = scheduler::schedule(deferFirst,
81 bind(&NccStrategy::doPropagate, this,
82 weak_ptr<pit::Entry>(pitEntry), weak_ptr<fib::Entry>(fibEntry)));
83}
84
85void
86NccStrategy::doPropagate(weak_ptr<pit::Entry> pitEntryWeak, weak_ptr<fib::Entry> fibEntryWeak)
87{
88 shared_ptr<pit::Entry> pitEntry = pitEntryWeak.lock();
89 if (!static_cast<bool>(pitEntry)) {
90 return;
91 }
92 shared_ptr<fib::Entry> fibEntry = fibEntryWeak.lock();
93 if (!static_cast<bool>(fibEntry)) {
94 return;
95 }
96
97 shared_ptr<PitEntryInfo> pitEntryInfo =
98 pitEntry->getStrategyInfo<PitEntryInfo>();
99 BOOST_ASSERT(static_cast<bool>(pitEntryInfo));
100
101 shared_ptr<MeasurementsEntryInfo> measurementsEntryInfo =
102 this->getMeasurementsEntryInfo(pitEntry);
103
104 shared_ptr<Face> previousFace = measurementsEntryInfo->m_previousFace.lock();
105 if (static_cast<bool>(previousFace) && fibEntry->hasNextHop(previousFace) &&
Junxiao Shi57f0f312014-03-16 11:52:20 -0700106 pitEntry->canForwardTo(*previousFace)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700107 this->sendInterest(pitEntry, previousFace);
108 }
109
110 const fib::NextHopList& nexthops = fibEntry->getNextHops();
111 bool isForwarded = false;
112 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
113 shared_ptr<Face> face = it->getFace();
Junxiao Shi57f0f312014-03-16 11:52:20 -0700114 if (pitEntry->canForwardTo(*face)) {
Junxiao Shi0b5fbbb2014-02-20 15:54:03 -0700115 isForwarded = true;
116 this->sendInterest(pitEntry, face);
117 break;
118 }
119 }
120
121 if (isForwarded) {
122 static unsigned short seed[3];
123 time::Duration deferNext = static_cast<time::Duration>(
124 nrand48(seed) % pitEntryInfo->m_maxInterval);
125 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
209const time::Duration NccStrategy::MeasurementsEntryInfo::INITIAL_PREDICTION =
210 time::microseconds(8192);
211const time::Duration NccStrategy::MeasurementsEntryInfo::MIN_PREDICTION =
212 time::microseconds(127);
213const time::Duration NccStrategy::MeasurementsEntryInfo::MAX_PREDICTION =
214 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,
256 static_cast<time::Duration>(m_prediction - (m_prediction >> ADJUST_PREDICT_DOWN_SHIFT)));
257}
258
259void
260NccStrategy::MeasurementsEntryInfo::adjustPredictUp() {
261 m_prediction = std::min(MAX_PREDICTION,
262 static_cast<time::Duration>(m_prediction + (m_prediction >> ADJUST_PREDICT_UP_SHIFT)));
263}
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