blob: 6b06d109c614234190c2614bcbd1037d43ac85d3 [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)
HangZhangad4afd12014-03-01 11:03:08 +080039 , m_fib(m_nameTree)
Haowei Yuan78c84d12014-02-27 15:35:13 -060040 , m_pit(m_nameTree)
HangZhangc85a23c2014-03-01 15:55:55 +080041 , m_measurements(m_nameTree)
Junxiao Shif3c07812014-03-11 21:48:49 -070042 , m_strategyChoice(m_nameTree, fw::makeDefaultStrategy(*this))
Alexander Afanasyev33b72772014-01-26 23:22:58 -080043{
Junxiao Shif3c07812014-03-11 21:48:49 -070044 fw::installStrategies(*this);
Alexander Afanasyev33b72772014-01-26 23:22:58 -080045}
46
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060047Forwarder::~Forwarder()
48{
49
50}
51
Alexander Afanasyev33b72772014-01-26 23:22:58 -080052void
Junxiao Shid3c792f2014-01-30 00:46:13 -070053Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
54{
55 // receive Interest
Junxiao Shif3c07812014-03-11 21:48:49 -070056 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
57 " interest=" << interest.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -070058 const_cast<Interest&>(interest).setIncomingFaceId(inFace.getId());
Junxiao Shi6e694322014-04-03 10:27:13 -070059 m_counters.getNInInterests() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -070060
Junxiao Shi88884492014-02-15 15:57:43 -070061 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -070062 bool isViolatingLocalhost = !inFace.isLocal() &&
63 LOCALHOST_NAME.isPrefixOf(interest.getName());
64 if (isViolatingLocalhost) {
65 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
66 " interest=" << interest.getName() << " violates /localhost");
67 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -070068 return;
69 }
Junxiao Shic041ca32014-02-25 20:01:15 -070070
Junxiao Shid3c792f2014-01-30 00:46:13 -070071 // PIT insert
Junxiao Shi40631842014-03-01 13:52:37 -070072 shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
Junxiao Shic041ca32014-02-25 20:01:15 -070073
Junxiao Shid3c792f2014-01-30 00:46:13 -070074 // detect loop and record Nonce
75 bool isLoop = ! pitEntry->addNonce(interest.getNonce());
76 if (isLoop) {
77 // goto Interest loop pipeline
78 this->onInterestLoop(inFace, interest, pitEntry);
79 return;
80 }
Junxiao Shic041ca32014-02-25 20:01:15 -070081
Junxiao Shid3c792f2014-01-30 00:46:13 -070082 // cancel unsatisfy & straggler timer
83 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070084
Junxiao Shif3c07812014-03-11 21:48:49 -070085 // is pending?
Junxiao Shid3c792f2014-01-30 00:46:13 -070086 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
Junxiao Shie17349a2014-03-25 00:55:38 -070087 bool isPending = inRecords.begin() != inRecords.end();
Junxiao Shid3c792f2014-01-30 00:46:13 -070088 if (!isPending) {
89 // CS lookup
90 const Data* csMatch = m_cs.find(interest);
91 if (csMatch != 0) {
92 // XXX should we lookup PIT for other Interests that also match csMatch?
93
94 // goto outgoing Data pipeline
95 this->onOutgoingData(*csMatch, inFace);
96 return;
97 }
98 }
Junxiao Shic041ca32014-02-25 20:01:15 -070099
Junxiao Shid3c792f2014-01-30 00:46:13 -0700100 // insert InRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700101 pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700102
Junxiao Shid3c792f2014-01-30 00:46:13 -0700103 // FIB lookup
Junxiao Shi40631842014-03-01 13:52:37 -0700104 shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700105
Junxiao Shid3c792f2014-01-30 00:46:13 -0700106 // dispatch to strategy
Junxiao Shif3c07812014-03-11 21:48:49 -0700107 this->dispatchToStrategy(pitEntry, bind(&Strategy::afterReceiveInterest, _1,
108 boost::cref(inFace), boost::cref(interest), fibEntry, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700109}
110
111void
112Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
113 shared_ptr<pit::Entry> pitEntry)
114{
Junxiao Shif3c07812014-03-11 21:48:49 -0700115 NFD_LOG_DEBUG("onInterestLoop face=" << inFace.getId() <<
116 " interest=" << interest.getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700117
Junxiao Shif3c07812014-03-11 21:48:49 -0700118 // (drop)
119}
120
121/** \brief compare two InRecords for picking outgoing Interest
122 * \return true if b is preferred over a
123 *
124 * This function should be passed to std::max_element over InRecordCollection.
125 * The outgoing Interest picked is the last incoming Interest
126 * that does not come from outFace.
127 * If all InRecords come from outFace, it's fine to pick that. This happens when
128 * there's only one InRecord that comes from outFace. The legit use is for
129 * vehicular network; otherwise, strategy shouldn't send to the sole inFace.
130 */
131static inline bool
132compare_pickInterest(const pit::InRecord& a, const pit::InRecord& b, const Face* outFace)
133{
134 bool isOutFaceA = a.getFace().get() == outFace;
135 bool isOutFaceB = b.getFace().get() == outFace;
136
137 if (!isOutFaceA && isOutFaceB) {
138 return false;
139 }
140 if (isOutFaceA && !isOutFaceB) {
141 return true;
142 }
143
144 return a.getLastRenewed() > b.getLastRenewed();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700145}
146
147void
148Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
149{
Junxiao Shif3c07812014-03-11 21:48:49 -0700150 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
151 " interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700152
Junxiao Shi57f0f312014-03-16 11:52:20 -0700153 // scope control
154 if (pitEntry->violatesScope(outFace)) {
Junxiao Shif3c07812014-03-11 21:48:49 -0700155 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
Junxiao Shi57f0f312014-03-16 11:52:20 -0700156 " interest=" << pitEntry->getName() << " violates scope");
Junxiao Shi11bd9c22014-03-13 20:44:13 -0700157 return;
158 }
159
Junxiao Shid3c792f2014-01-30 00:46:13 -0700160 // pick Interest
Junxiao Shif3c07812014-03-11 21:48:49 -0700161 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
162 pit::InRecordCollection::const_iterator pickedInRecord = std::max_element(
163 inRecords.begin(), inRecords.end(), bind(&compare_pickInterest, _1, _2, &outFace));
164 BOOST_ASSERT(pickedInRecord != inRecords.end());
165 const Interest& interest = pickedInRecord->getInterest();
Junxiao Shic041ca32014-02-25 20:01:15 -0700166
Junxiao Shid3c792f2014-01-30 00:46:13 -0700167 // insert OutRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700168 pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700169
Junxiao Shid3c792f2014-01-30 00:46:13 -0700170 // set PIT unsatisfy timer
171 this->setUnsatisfyTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700172
Junxiao Shid3c792f2014-01-30 00:46:13 -0700173 // send Interest
174 outFace.sendInterest(interest);
Junxiao Shi6e694322014-04-03 10:27:13 -0700175 m_counters.getNOutInterests() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700176}
177
178void
Junxiao Shi09498f02014-02-26 19:41:08 -0700179Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
Junxiao Shid3c792f2014-01-30 00:46:13 -0700180{
Junxiao Shi09498f02014-02-26 19:41:08 -0700181 NFD_LOG_DEBUG("onInterestReject interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700182
Junxiao Shid3c792f2014-01-30 00:46:13 -0700183 // set PIT straggler timer
184 this->setStragglerTimer(pitEntry);
185}
186
187void
188Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
189{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700190 NFD_LOG_DEBUG("onInterestUnsatisfied interest=" << pitEntry->getName());
191
Junxiao Shid3c792f2014-01-30 00:46:13 -0700192 // invoke PIT unsatisfied callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700193 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
194 pitEntry));
Junxiao Shic041ca32014-02-25 20:01:15 -0700195
Junxiao Shif3c07812014-03-11 21:48:49 -0700196 // PIT delete
Haowei Yuan78c84d12014-02-27 15:35:13 -0600197 m_pit.erase(pitEntry);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700198}
199
200void
201Forwarder::onIncomingData(Face& inFace, const Data& data)
202{
203 // receive Data
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700204 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() << " data=" << data.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -0700205 const_cast<Data&>(data).setIncomingFaceId(inFace.getId());
Junxiao Shi6e694322014-04-03 10:27:13 -0700206 m_counters.getNInDatas() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -0700207
Junxiao Shi88884492014-02-15 15:57:43 -0700208 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700209 bool isViolatingLocalhost = !inFace.isLocal() &&
210 LOCALHOST_NAME.isPrefixOf(data.getName());
211 if (isViolatingLocalhost) {
212 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() <<
213 " data=" << data.getName() << " violates /localhost");
214 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -0700215 return;
216 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700217
Junxiao Shid3c792f2014-01-30 00:46:13 -0700218 // PIT match
219 shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
220 if (pitMatches->begin() == pitMatches->end()) {
221 // goto Data unsolicited pipeline
222 this->onDataUnsolicited(inFace, data);
223 return;
224 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700225
Junxiao Shid3c792f2014-01-30 00:46:13 -0700226 // CS insert
227 m_cs.insert(data);
Junxiao Shic041ca32014-02-25 20:01:15 -0700228
Junxiao Shid3c792f2014-01-30 00:46:13 -0700229 std::set<shared_ptr<Face> > pendingDownstreams;
230 // foreach PitEntry
231 for (pit::DataMatchResult::iterator it = pitMatches->begin();
232 it != pitMatches->end(); ++it) {
233 shared_ptr<pit::Entry> pitEntry = *it;
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700234 NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
Junxiao Shic041ca32014-02-25 20:01:15 -0700235
Junxiao Shid3c792f2014-01-30 00:46:13 -0700236 // cancel unsatisfy & straggler timer
237 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700238
Junxiao Shid3c792f2014-01-30 00:46:13 -0700239 // remember pending downstreams
240 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
241 for (pit::InRecordCollection::const_iterator it = inRecords.begin();
242 it != inRecords.end(); ++it) {
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700243 if (it->getExpiry() > time::steady_clock::now()) {
Junxiao Shid3c792f2014-01-30 00:46:13 -0700244 pendingDownstreams.insert(it->getFace());
245 }
246 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700247
Junxiao Shid3c792f2014-01-30 00:46:13 -0700248 // mark PIT satisfied
249 pitEntry->deleteInRecords();
250 pitEntry->deleteOutRecord(inFace.shared_from_this());
Junxiao Shic041ca32014-02-25 20:01:15 -0700251
Junxiao Shid3c792f2014-01-30 00:46:13 -0700252 // set PIT straggler timer
253 this->setStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700254
Junxiao Shid3c792f2014-01-30 00:46:13 -0700255 // invoke PIT satisfy callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700256 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyPendingInterest, _1,
257 pitEntry, boost::cref(inFace), boost::cref(data)));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700258 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700259
Junxiao Shid3c792f2014-01-30 00:46:13 -0700260 // foreach pending downstream
261 for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
262 it != pendingDownstreams.end(); ++it) {
263 // goto outgoing Data pipeline
264 this->onOutgoingData(data, **it);
265 }
266}
267
268void
269Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
270{
271 // accept to cache?
Junxiao Shif3c07812014-03-11 21:48:49 -0700272 bool acceptToCache = inFace.isLocal();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700273 if (acceptToCache) {
274 // CS insert
Junxiao Shif3c07812014-03-11 21:48:49 -0700275 m_cs.insert(data, true);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700276 }
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700277
Junxiao Shif3c07812014-03-11 21:48:49 -0700278 NFD_LOG_DEBUG("onDataUnsolicited face=" << inFace.getId() <<
279 " data=" << data.getName() <<
280 (acceptToCache ? " cached" : " not cached"));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700281}
282
283void
284Forwarder::onOutgoingData(const Data& data, Face& outFace)
285{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700286 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() << " data=" << data.getName());
287
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700288 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700289 bool isViolatingLocalhost = !outFace.isLocal() &&
290 LOCALHOST_NAME.isPrefixOf(data.getName());
291 if (isViolatingLocalhost) {
292 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() <<
293 " data=" << data.getName() << " violates /localhost");
294 // (drop)
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700295 return;
296 }
297
Junxiao Shif3c07812014-03-11 21:48:49 -0700298 // TODO traffic manager
Junxiao Shic041ca32014-02-25 20:01:15 -0700299
Junxiao Shid3c792f2014-01-30 00:46:13 -0700300 // send Data
301 outFace.sendData(data);
Junxiao Shi6e694322014-04-03 10:27:13 -0700302 m_counters.getNOutDatas() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700303}
304
305static inline bool
306compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
307{
308 return a.getExpiry() < b.getExpiry();
309}
310
311void
312Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
313{
314 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
315 pit::InRecordCollection::const_iterator lastExpiring =
316 std::max_element(inRecords.begin(), inRecords.end(),
317 &compare_InRecord_expiry);
318
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700319 time::steady_clock::TimePoint lastExpiry = lastExpiring->getExpiry();
320 time::nanoseconds lastExpiryFromNow = lastExpiry - time::steady_clock::now();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700321 if (lastExpiryFromNow <= time::seconds(0)) {
322 // TODO all InRecords are already expired; will this happen?
323 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700324
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700325 scheduler::cancel(pitEntry->m_unsatisfyTimer);
Junxiao Shic041ca32014-02-25 20:01:15 -0700326 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
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700341 scheduler::cancel(pitEntry->m_stragglerTimer);
Junxiao Shic041ca32014-02-25 20:01:15 -0700342 pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
Haowei Yuan78c84d12014-02-27 15:35:13 -0600343 bind(&Pit::erase, &m_pit, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700344}
345
346void
347Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
348{
Junxiao Shic041ca32014-02-25 20:01:15 -0700349 scheduler::cancel(pitEntry->m_unsatisfyTimer);
350 scheduler::cancel(pitEntry->m_stragglerTimer);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700351}
352
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800353} // namespace nfd