blob: 1e6860049e93da4c825adc95e9fd7007e59ba766 [file] [log] [blame]
Alexander Afanasyev33b72772014-01-26 23:22:58 -08001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -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 *
10 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 **/
Alexander Afanasyev33b72772014-01-26 23:22:58 -080024
25#include "forwarder.hpp"
Junxiao Shif3c07812014-03-11 21:48:49 -070026#include "available-strategies.hpp"
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060027#include "core/logger.hpp"
Alexander Afanasyev33b72772014-01-26 23:22:58 -080028
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080029namespace nfd {
Alexander Afanasyev33b72772014-01-26 23:22:58 -080030
Junxiao Shi8c8d2182014-01-30 22:33:00 -070031NFD_LOG_INIT("Forwarder");
32
Junxiao Shif3c07812014-03-11 21:48:49 -070033using fw::Strategy;
34
Junxiao Shif3c07812014-03-11 21:48:49 -070035const Name Forwarder::LOCALHOST_NAME("ndn:/localhost");
Junxiao Shi88884492014-02-15 15:57:43 -070036
Junxiao Shic041ca32014-02-25 20:01:15 -070037Forwarder::Forwarder()
Junxiao Shia4f2be82014-03-02 22:56:41 -070038 : m_faceTable(*this)
Haowei Yuan78c84d12014-02-27 15:35:13 -060039 , m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
HangZhangad4afd12014-03-01 11:03:08 +080040 , m_fib(m_nameTree)
Haowei Yuan78c84d12014-02-27 15:35:13 -060041 , m_pit(m_nameTree)
HangZhangc85a23c2014-03-01 15:55:55 +080042 , m_measurements(m_nameTree)
Junxiao Shif3c07812014-03-11 21:48:49 -070043 , m_strategyChoice(m_nameTree, fw::makeDefaultStrategy(*this))
Alexander Afanasyev33b72772014-01-26 23:22:58 -080044{
Junxiao Shif3c07812014-03-11 21:48:49 -070045 fw::installStrategies(*this);
Alexander Afanasyev33b72772014-01-26 23:22:58 -080046}
47
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060048Forwarder::~Forwarder()
49{
50
51}
52
Alexander Afanasyev33b72772014-01-26 23:22:58 -080053void
Junxiao Shid3c792f2014-01-30 00:46:13 -070054Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
55{
56 // receive Interest
Junxiao Shif3c07812014-03-11 21:48:49 -070057 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
58 " interest=" << interest.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -070059 const_cast<Interest&>(interest).setIncomingFaceId(inFace.getId());
Junxiao Shi6e694322014-04-03 10:27:13 -070060 m_counters.getNInInterests() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -070061
Junxiao Shi88884492014-02-15 15:57:43 -070062 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -070063 bool isViolatingLocalhost = !inFace.isLocal() &&
64 LOCALHOST_NAME.isPrefixOf(interest.getName());
65 if (isViolatingLocalhost) {
66 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
67 " interest=" << interest.getName() << " violates /localhost");
68 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -070069 return;
70 }
Junxiao Shic041ca32014-02-25 20:01:15 -070071
Junxiao Shid3c792f2014-01-30 00:46:13 -070072 // PIT insert
Junxiao Shi40631842014-03-01 13:52:37 -070073 shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
Junxiao Shic041ca32014-02-25 20:01:15 -070074
Junxiao Shid3c792f2014-01-30 00:46:13 -070075 // detect loop and record Nonce
76 bool isLoop = ! pitEntry->addNonce(interest.getNonce());
77 if (isLoop) {
78 // goto Interest loop pipeline
79 this->onInterestLoop(inFace, interest, pitEntry);
80 return;
81 }
Junxiao Shic041ca32014-02-25 20:01:15 -070082
Junxiao Shid3c792f2014-01-30 00:46:13 -070083 // cancel unsatisfy & straggler timer
84 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070085
Junxiao Shif3c07812014-03-11 21:48:49 -070086 // is pending?
Junxiao Shid3c792f2014-01-30 00:46:13 -070087 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
Junxiao Shie17349a2014-03-25 00:55:38 -070088 bool isPending = inRecords.begin() != inRecords.end();
Junxiao Shid3c792f2014-01-30 00:46:13 -070089 if (!isPending) {
90 // CS lookup
91 const Data* csMatch = m_cs.find(interest);
92 if (csMatch != 0) {
93 // XXX should we lookup PIT for other Interests that also match csMatch?
94
95 // goto outgoing Data pipeline
96 this->onOutgoingData(*csMatch, inFace);
97 return;
98 }
99 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700100
Junxiao Shid3c792f2014-01-30 00:46:13 -0700101 // insert InRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700102 pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700103
Junxiao Shid3c792f2014-01-30 00:46:13 -0700104 // FIB lookup
Junxiao Shi40631842014-03-01 13:52:37 -0700105 shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700106
Junxiao Shid3c792f2014-01-30 00:46:13 -0700107 // dispatch to strategy
Junxiao Shif3c07812014-03-11 21:48:49 -0700108 this->dispatchToStrategy(pitEntry, bind(&Strategy::afterReceiveInterest, _1,
109 boost::cref(inFace), boost::cref(interest), fibEntry, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700110}
111
112void
113Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
114 shared_ptr<pit::Entry> pitEntry)
115{
Junxiao Shif3c07812014-03-11 21:48:49 -0700116 NFD_LOG_DEBUG("onInterestLoop face=" << inFace.getId() <<
117 " interest=" << interest.getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700118
Junxiao Shif3c07812014-03-11 21:48:49 -0700119 // (drop)
120}
121
122/** \brief compare two InRecords for picking outgoing Interest
123 * \return true if b is preferred over a
124 *
125 * This function should be passed to std::max_element over InRecordCollection.
126 * The outgoing Interest picked is the last incoming Interest
127 * that does not come from outFace.
128 * If all InRecords come from outFace, it's fine to pick that. This happens when
129 * there's only one InRecord that comes from outFace. The legit use is for
130 * vehicular network; otherwise, strategy shouldn't send to the sole inFace.
131 */
132static inline bool
133compare_pickInterest(const pit::InRecord& a, const pit::InRecord& b, const Face* outFace)
134{
135 bool isOutFaceA = a.getFace().get() == outFace;
136 bool isOutFaceB = b.getFace().get() == outFace;
137
138 if (!isOutFaceA && isOutFaceB) {
139 return false;
140 }
141 if (isOutFaceA && !isOutFaceB) {
142 return true;
143 }
144
145 return a.getLastRenewed() > b.getLastRenewed();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700146}
147
148void
149Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
150{
Junxiao Shif3c07812014-03-11 21:48:49 -0700151 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
152 " interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700153
Junxiao Shi57f0f312014-03-16 11:52:20 -0700154 // scope control
155 if (pitEntry->violatesScope(outFace)) {
Junxiao Shif3c07812014-03-11 21:48:49 -0700156 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
Junxiao Shi57f0f312014-03-16 11:52:20 -0700157 " interest=" << pitEntry->getName() << " violates scope");
Junxiao Shi11bd9c22014-03-13 20:44:13 -0700158 return;
159 }
160
Junxiao Shid3c792f2014-01-30 00:46:13 -0700161 // pick Interest
Junxiao Shif3c07812014-03-11 21:48:49 -0700162 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
163 pit::InRecordCollection::const_iterator pickedInRecord = std::max_element(
164 inRecords.begin(), inRecords.end(), bind(&compare_pickInterest, _1, _2, &outFace));
165 BOOST_ASSERT(pickedInRecord != inRecords.end());
166 const Interest& interest = pickedInRecord->getInterest();
Junxiao Shic041ca32014-02-25 20:01:15 -0700167
Junxiao Shid3c792f2014-01-30 00:46:13 -0700168 // insert OutRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700169 pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700170
Junxiao Shid3c792f2014-01-30 00:46:13 -0700171 // set PIT unsatisfy timer
172 this->setUnsatisfyTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700173
Junxiao Shid3c792f2014-01-30 00:46:13 -0700174 // send Interest
175 outFace.sendInterest(interest);
Junxiao Shi6e694322014-04-03 10:27:13 -0700176 m_counters.getNOutInterests() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700177}
178
179void
Junxiao Shi09498f02014-02-26 19:41:08 -0700180Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
Junxiao Shid3c792f2014-01-30 00:46:13 -0700181{
Junxiao Shi09498f02014-02-26 19:41:08 -0700182 NFD_LOG_DEBUG("onInterestReject interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700183
Junxiao Shid3c792f2014-01-30 00:46:13 -0700184 // set PIT straggler timer
185 this->setStragglerTimer(pitEntry);
186}
187
188void
189Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
190{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700191 NFD_LOG_DEBUG("onInterestUnsatisfied interest=" << pitEntry->getName());
192
Junxiao Shid3c792f2014-01-30 00:46:13 -0700193 // invoke PIT unsatisfied callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700194 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
195 pitEntry));
Junxiao Shic041ca32014-02-25 20:01:15 -0700196
Junxiao Shif3c07812014-03-11 21:48:49 -0700197 // PIT delete
Haowei Yuan78c84d12014-02-27 15:35:13 -0600198 m_pit.erase(pitEntry);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700199}
200
201void
202Forwarder::onIncomingData(Face& inFace, const Data& data)
203{
204 // receive Data
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700205 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() << " data=" << data.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -0700206 const_cast<Data&>(data).setIncomingFaceId(inFace.getId());
Junxiao Shi6e694322014-04-03 10:27:13 -0700207 m_counters.getNInDatas() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -0700208
Junxiao Shi88884492014-02-15 15:57:43 -0700209 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700210 bool isViolatingLocalhost = !inFace.isLocal() &&
211 LOCALHOST_NAME.isPrefixOf(data.getName());
212 if (isViolatingLocalhost) {
213 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() <<
214 " data=" << data.getName() << " violates /localhost");
215 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -0700216 return;
217 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700218
Junxiao Shid3c792f2014-01-30 00:46:13 -0700219 // PIT match
220 shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
221 if (pitMatches->begin() == pitMatches->end()) {
222 // goto Data unsolicited pipeline
223 this->onDataUnsolicited(inFace, data);
224 return;
225 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700226
Junxiao Shid3c792f2014-01-30 00:46:13 -0700227 // CS insert
228 m_cs.insert(data);
Junxiao Shic041ca32014-02-25 20:01:15 -0700229
Junxiao Shid3c792f2014-01-30 00:46:13 -0700230 std::set<shared_ptr<Face> > pendingDownstreams;
231 // foreach PitEntry
232 for (pit::DataMatchResult::iterator it = pitMatches->begin();
233 it != pitMatches->end(); ++it) {
234 shared_ptr<pit::Entry> pitEntry = *it;
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700235 NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
Junxiao Shic041ca32014-02-25 20:01:15 -0700236
Junxiao Shid3c792f2014-01-30 00:46:13 -0700237 // cancel unsatisfy & straggler timer
238 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700239
Junxiao Shid3c792f2014-01-30 00:46:13 -0700240 // remember pending downstreams
241 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
242 for (pit::InRecordCollection::const_iterator it = inRecords.begin();
243 it != inRecords.end(); ++it) {
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700244 if (it->getExpiry() > time::steady_clock::now()) {
Junxiao Shid3c792f2014-01-30 00:46:13 -0700245 pendingDownstreams.insert(it->getFace());
246 }
247 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700248
Junxiao Shid3c792f2014-01-30 00:46:13 -0700249 // mark PIT satisfied
250 pitEntry->deleteInRecords();
251 pitEntry->deleteOutRecord(inFace.shared_from_this());
Junxiao Shic041ca32014-02-25 20:01:15 -0700252
Junxiao Shid3c792f2014-01-30 00:46:13 -0700253 // set PIT straggler timer
254 this->setStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700255
Junxiao Shid3c792f2014-01-30 00:46:13 -0700256 // invoke PIT satisfy callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700257 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyPendingInterest, _1,
258 pitEntry, boost::cref(inFace), boost::cref(data)));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700259 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700260
Junxiao Shid3c792f2014-01-30 00:46:13 -0700261 // foreach pending downstream
262 for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
263 it != pendingDownstreams.end(); ++it) {
264 // goto outgoing Data pipeline
265 this->onOutgoingData(data, **it);
266 }
267}
268
269void
270Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
271{
272 // accept to cache?
Junxiao Shif3c07812014-03-11 21:48:49 -0700273 bool acceptToCache = inFace.isLocal();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700274 if (acceptToCache) {
275 // CS insert
Junxiao Shif3c07812014-03-11 21:48:49 -0700276 m_cs.insert(data, true);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700277 }
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700278
Junxiao Shif3c07812014-03-11 21:48:49 -0700279 NFD_LOG_DEBUG("onDataUnsolicited face=" << inFace.getId() <<
280 " data=" << data.getName() <<
281 (acceptToCache ? " cached" : " not cached"));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700282}
283
284void
285Forwarder::onOutgoingData(const Data& data, Face& outFace)
286{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700287 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() << " data=" << data.getName());
288
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700289 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700290 bool isViolatingLocalhost = !outFace.isLocal() &&
291 LOCALHOST_NAME.isPrefixOf(data.getName());
292 if (isViolatingLocalhost) {
293 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() <<
294 " data=" << data.getName() << " violates /localhost");
295 // (drop)
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700296 return;
297 }
298
Junxiao Shif3c07812014-03-11 21:48:49 -0700299 // TODO traffic manager
Junxiao Shic041ca32014-02-25 20:01:15 -0700300
Junxiao Shid3c792f2014-01-30 00:46:13 -0700301 // send Data
302 outFace.sendData(data);
Junxiao Shi6e694322014-04-03 10:27:13 -0700303 m_counters.getNOutDatas() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700304}
305
306static inline bool
307compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
308{
309 return a.getExpiry() < b.getExpiry();
310}
311
312void
313Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
314{
315 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
316 pit::InRecordCollection::const_iterator lastExpiring =
317 std::max_element(inRecords.begin(), inRecords.end(),
318 &compare_InRecord_expiry);
319
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700320 time::steady_clock::TimePoint lastExpiry = lastExpiring->getExpiry();
321 time::nanoseconds lastExpiryFromNow = lastExpiry - time::steady_clock::now();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700322 if (lastExpiryFromNow <= time::seconds(0)) {
323 // TODO all InRecords are already expired; will this happen?
324 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700325
326 pitEntry->m_unsatisfyTimer = scheduler::schedule(lastExpiryFromNow,
Junxiao Shid3c792f2014-01-30 00:46:13 -0700327 bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
328}
329
330void
331Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
332{
Junxiao Shi57f0f312014-03-16 11:52:20 -0700333 if (pitEntry->hasUnexpiredOutRecords()) {
334 NFD_LOG_DEBUG("setStragglerTimer " << pitEntry->getName() <<
335 " cannot set StragglerTimer when an OutRecord is pending");
336 return;
337 }
338
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700339 time::nanoseconds stragglerTime = time::milliseconds(100);
Junxiao Shic041ca32014-02-25 20:01:15 -0700340
341 pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
Haowei Yuan78c84d12014-02-27 15:35:13 -0600342 bind(&Pit::erase, &m_pit, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700343}
344
345void
346Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
347{
Junxiao Shic041ca32014-02-25 20:01:15 -0700348 scheduler::cancel(pitEntry->m_unsatisfyTimer);
349 scheduler::cancel(pitEntry->m_stragglerTimer);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700350}
351
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800352} // namespace nfd