blob: 8ffda2f2e9b20e8cad07eba0e8b6564c423f6715 [file] [log] [blame]
Alexander Afanasyev33b72772014-01-26 23:22:58 -08001/* -*- 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 "forwarder.hpp"
Junxiao Shif3c07812014-03-11 21:48:49 -07008#include "available-strategies.hpp"
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -06009#include "core/logger.hpp"
Alexander Afanasyev33b72772014-01-26 23:22:58 -080010
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080011namespace nfd {
Alexander Afanasyev33b72772014-01-26 23:22:58 -080012
Junxiao Shi8c8d2182014-01-30 22:33:00 -070013NFD_LOG_INIT("Forwarder");
14
Junxiao Shif3c07812014-03-11 21:48:49 -070015using fw::Strategy;
16
Junxiao Shif3c07812014-03-11 21:48:49 -070017const Name Forwarder::LOCALHOST_NAME("ndn:/localhost");
Junxiao Shi88884492014-02-15 15:57:43 -070018
Junxiao Shic041ca32014-02-25 20:01:15 -070019Forwarder::Forwarder()
Junxiao Shia4f2be82014-03-02 22:56:41 -070020 : m_faceTable(*this)
Haowei Yuan78c84d12014-02-27 15:35:13 -060021 , m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
HangZhangad4afd12014-03-01 11:03:08 +080022 , m_fib(m_nameTree)
Haowei Yuan78c84d12014-02-27 15:35:13 -060023 , m_pit(m_nameTree)
HangZhangc85a23c2014-03-01 15:55:55 +080024 , m_measurements(m_nameTree)
Junxiao Shif3c07812014-03-11 21:48:49 -070025 , m_strategyChoice(m_nameTree, fw::makeDefaultStrategy(*this))
Alexander Afanasyev33b72772014-01-26 23:22:58 -080026{
Junxiao Shif3c07812014-03-11 21:48:49 -070027 fw::installStrategies(*this);
Alexander Afanasyev33b72772014-01-26 23:22:58 -080028}
29
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060030Forwarder::~Forwarder()
31{
32
33}
34
Alexander Afanasyev33b72772014-01-26 23:22:58 -080035void
Junxiao Shid3c792f2014-01-30 00:46:13 -070036Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
37{
38 // receive Interest
Junxiao Shif3c07812014-03-11 21:48:49 -070039 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
40 " interest=" << interest.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -070041 const_cast<Interest&>(interest).setIncomingFaceId(inFace.getId());
Junxiao Shib289cc12014-03-15 12:19:05 -070042 m_counters.getInInterest() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -070043
Junxiao Shi88884492014-02-15 15:57:43 -070044 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -070045 bool isViolatingLocalhost = !inFace.isLocal() &&
46 LOCALHOST_NAME.isPrefixOf(interest.getName());
47 if (isViolatingLocalhost) {
48 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
49 " interest=" << interest.getName() << " violates /localhost");
50 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -070051 return;
52 }
Junxiao Shic041ca32014-02-25 20:01:15 -070053
Junxiao Shid3c792f2014-01-30 00:46:13 -070054 // PIT insert
Junxiao Shi40631842014-03-01 13:52:37 -070055 shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
Junxiao Shic041ca32014-02-25 20:01:15 -070056
Junxiao Shid3c792f2014-01-30 00:46:13 -070057 // detect loop and record Nonce
58 bool isLoop = ! pitEntry->addNonce(interest.getNonce());
59 if (isLoop) {
60 // goto Interest loop pipeline
61 this->onInterestLoop(inFace, interest, pitEntry);
62 return;
63 }
Junxiao Shic041ca32014-02-25 20:01:15 -070064
Junxiao Shid3c792f2014-01-30 00:46:13 -070065 // cancel unsatisfy & straggler timer
66 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070067
Junxiao Shif3c07812014-03-11 21:48:49 -070068 // is pending?
Junxiao Shid3c792f2014-01-30 00:46:13 -070069 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
Junxiao Shie17349a2014-03-25 00:55:38 -070070 bool isPending = inRecords.begin() != inRecords.end();
Junxiao Shid3c792f2014-01-30 00:46:13 -070071 if (!isPending) {
72 // CS lookup
73 const Data* csMatch = m_cs.find(interest);
74 if (csMatch != 0) {
75 // XXX should we lookup PIT for other Interests that also match csMatch?
76
77 // goto outgoing Data pipeline
78 this->onOutgoingData(*csMatch, inFace);
79 return;
80 }
81 }
Junxiao Shic041ca32014-02-25 20:01:15 -070082
Junxiao Shid3c792f2014-01-30 00:46:13 -070083 // insert InRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -070084 pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -070085
Junxiao Shid3c792f2014-01-30 00:46:13 -070086 // FIB lookup
Junxiao Shi40631842014-03-01 13:52:37 -070087 shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070088
Junxiao Shid3c792f2014-01-30 00:46:13 -070089 // dispatch to strategy
Junxiao Shif3c07812014-03-11 21:48:49 -070090 this->dispatchToStrategy(pitEntry, bind(&Strategy::afterReceiveInterest, _1,
91 boost::cref(inFace), boost::cref(interest), fibEntry, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -070092}
93
94void
95Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
96 shared_ptr<pit::Entry> pitEntry)
97{
Junxiao Shif3c07812014-03-11 21:48:49 -070098 NFD_LOG_DEBUG("onInterestLoop face=" << inFace.getId() <<
99 " interest=" << interest.getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700100
Junxiao Shif3c07812014-03-11 21:48:49 -0700101 // (drop)
102}
103
104/** \brief compare two InRecords for picking outgoing Interest
105 * \return true if b is preferred over a
106 *
107 * This function should be passed to std::max_element over InRecordCollection.
108 * The outgoing Interest picked is the last incoming Interest
109 * that does not come from outFace.
110 * If all InRecords come from outFace, it's fine to pick that. This happens when
111 * there's only one InRecord that comes from outFace. The legit use is for
112 * vehicular network; otherwise, strategy shouldn't send to the sole inFace.
113 */
114static inline bool
115compare_pickInterest(const pit::InRecord& a, const pit::InRecord& b, const Face* outFace)
116{
117 bool isOutFaceA = a.getFace().get() == outFace;
118 bool isOutFaceB = b.getFace().get() == outFace;
119
120 if (!isOutFaceA && isOutFaceB) {
121 return false;
122 }
123 if (isOutFaceA && !isOutFaceB) {
124 return true;
125 }
126
127 return a.getLastRenewed() > b.getLastRenewed();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700128}
129
130void
131Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
132{
Junxiao Shif3c07812014-03-11 21:48:49 -0700133 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
134 " interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700135
Junxiao Shi57f0f312014-03-16 11:52:20 -0700136 // scope control
137 if (pitEntry->violatesScope(outFace)) {
Junxiao Shif3c07812014-03-11 21:48:49 -0700138 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
Junxiao Shi57f0f312014-03-16 11:52:20 -0700139 " interest=" << pitEntry->getName() << " violates scope");
Junxiao Shi11bd9c22014-03-13 20:44:13 -0700140 return;
141 }
142
Junxiao Shid3c792f2014-01-30 00:46:13 -0700143 // pick Interest
Junxiao Shif3c07812014-03-11 21:48:49 -0700144 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
145 pit::InRecordCollection::const_iterator pickedInRecord = std::max_element(
146 inRecords.begin(), inRecords.end(), bind(&compare_pickInterest, _1, _2, &outFace));
147 BOOST_ASSERT(pickedInRecord != inRecords.end());
148 const Interest& interest = pickedInRecord->getInterest();
Junxiao Shic041ca32014-02-25 20:01:15 -0700149
Junxiao Shid3c792f2014-01-30 00:46:13 -0700150 // insert OutRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700151 pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700152
Junxiao Shid3c792f2014-01-30 00:46:13 -0700153 // set PIT unsatisfy timer
154 this->setUnsatisfyTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700155
Junxiao Shid3c792f2014-01-30 00:46:13 -0700156 // send Interest
157 outFace.sendInterest(interest);
Junxiao Shib289cc12014-03-15 12:19:05 -0700158 m_counters.getOutInterest() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700159}
160
161void
Junxiao Shi09498f02014-02-26 19:41:08 -0700162Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
Junxiao Shid3c792f2014-01-30 00:46:13 -0700163{
Junxiao Shi09498f02014-02-26 19:41:08 -0700164 NFD_LOG_DEBUG("onInterestReject interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700165
Junxiao Shid3c792f2014-01-30 00:46:13 -0700166 // set PIT straggler timer
167 this->setStragglerTimer(pitEntry);
168}
169
170void
171Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
172{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700173 NFD_LOG_DEBUG("onInterestUnsatisfied interest=" << pitEntry->getName());
174
Junxiao Shid3c792f2014-01-30 00:46:13 -0700175 // invoke PIT unsatisfied callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700176 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
177 pitEntry));
Junxiao Shic041ca32014-02-25 20:01:15 -0700178
Junxiao Shif3c07812014-03-11 21:48:49 -0700179 // PIT delete
Haowei Yuan78c84d12014-02-27 15:35:13 -0600180 m_pit.erase(pitEntry);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700181}
182
183void
184Forwarder::onIncomingData(Face& inFace, const Data& data)
185{
186 // receive Data
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700187 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() << " data=" << data.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -0700188 const_cast<Data&>(data).setIncomingFaceId(inFace.getId());
Junxiao Shib289cc12014-03-15 12:19:05 -0700189 m_counters.getInData() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -0700190
Junxiao Shi88884492014-02-15 15:57:43 -0700191 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700192 bool isViolatingLocalhost = !inFace.isLocal() &&
193 LOCALHOST_NAME.isPrefixOf(data.getName());
194 if (isViolatingLocalhost) {
195 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() <<
196 " data=" << data.getName() << " violates /localhost");
197 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -0700198 return;
199 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700200
Junxiao Shid3c792f2014-01-30 00:46:13 -0700201 // PIT match
202 shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
203 if (pitMatches->begin() == pitMatches->end()) {
204 // goto Data unsolicited pipeline
205 this->onDataUnsolicited(inFace, data);
206 return;
207 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700208
Junxiao Shid3c792f2014-01-30 00:46:13 -0700209 // CS insert
210 m_cs.insert(data);
Junxiao Shic041ca32014-02-25 20:01:15 -0700211
Junxiao Shid3c792f2014-01-30 00:46:13 -0700212 std::set<shared_ptr<Face> > pendingDownstreams;
213 // foreach PitEntry
214 for (pit::DataMatchResult::iterator it = pitMatches->begin();
215 it != pitMatches->end(); ++it) {
216 shared_ptr<pit::Entry> pitEntry = *it;
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700217 NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
Junxiao Shic041ca32014-02-25 20:01:15 -0700218
Junxiao Shid3c792f2014-01-30 00:46:13 -0700219 // cancel unsatisfy & straggler timer
220 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700221
Junxiao Shid3c792f2014-01-30 00:46:13 -0700222 // remember pending downstreams
223 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
224 for (pit::InRecordCollection::const_iterator it = inRecords.begin();
225 it != inRecords.end(); ++it) {
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700226 if (it->getExpiry() > time::steady_clock::now()) {
Junxiao Shid3c792f2014-01-30 00:46:13 -0700227 pendingDownstreams.insert(it->getFace());
228 }
229 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700230
Junxiao Shid3c792f2014-01-30 00:46:13 -0700231 // mark PIT satisfied
232 pitEntry->deleteInRecords();
233 pitEntry->deleteOutRecord(inFace.shared_from_this());
Junxiao Shic041ca32014-02-25 20:01:15 -0700234
Junxiao Shid3c792f2014-01-30 00:46:13 -0700235 // set PIT straggler timer
236 this->setStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700237
Junxiao Shid3c792f2014-01-30 00:46:13 -0700238 // invoke PIT satisfy callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700239 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyPendingInterest, _1,
240 pitEntry, boost::cref(inFace), boost::cref(data)));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700241 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700242
Junxiao Shid3c792f2014-01-30 00:46:13 -0700243 // foreach pending downstream
244 for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
245 it != pendingDownstreams.end(); ++it) {
246 // goto outgoing Data pipeline
247 this->onOutgoingData(data, **it);
248 }
249}
250
251void
252Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
253{
254 // accept to cache?
Junxiao Shif3c07812014-03-11 21:48:49 -0700255 bool acceptToCache = inFace.isLocal();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700256 if (acceptToCache) {
257 // CS insert
Junxiao Shif3c07812014-03-11 21:48:49 -0700258 m_cs.insert(data, true);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700259 }
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700260
Junxiao Shif3c07812014-03-11 21:48:49 -0700261 NFD_LOG_DEBUG("onDataUnsolicited face=" << inFace.getId() <<
262 " data=" << data.getName() <<
263 (acceptToCache ? " cached" : " not cached"));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700264}
265
266void
267Forwarder::onOutgoingData(const Data& data, Face& outFace)
268{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700269 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() << " data=" << data.getName());
270
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700271 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700272 bool isViolatingLocalhost = !outFace.isLocal() &&
273 LOCALHOST_NAME.isPrefixOf(data.getName());
274 if (isViolatingLocalhost) {
275 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() <<
276 " data=" << data.getName() << " violates /localhost");
277 // (drop)
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700278 return;
279 }
280
Junxiao Shif3c07812014-03-11 21:48:49 -0700281 // TODO traffic manager
Junxiao Shic041ca32014-02-25 20:01:15 -0700282
Junxiao Shid3c792f2014-01-30 00:46:13 -0700283 // send Data
284 outFace.sendData(data);
Junxiao Shib289cc12014-03-15 12:19:05 -0700285 m_counters.getOutData() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700286}
287
288static inline bool
289compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
290{
291 return a.getExpiry() < b.getExpiry();
292}
293
294void
295Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
296{
297 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
298 pit::InRecordCollection::const_iterator lastExpiring =
299 std::max_element(inRecords.begin(), inRecords.end(),
300 &compare_InRecord_expiry);
301
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700302 time::steady_clock::TimePoint lastExpiry = lastExpiring->getExpiry();
303 time::nanoseconds lastExpiryFromNow = lastExpiry - time::steady_clock::now();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700304 if (lastExpiryFromNow <= time::seconds(0)) {
305 // TODO all InRecords are already expired; will this happen?
306 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700307
308 pitEntry->m_unsatisfyTimer = scheduler::schedule(lastExpiryFromNow,
Junxiao Shid3c792f2014-01-30 00:46:13 -0700309 bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
310}
311
312void
313Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
314{
Junxiao Shi57f0f312014-03-16 11:52:20 -0700315 if (pitEntry->hasUnexpiredOutRecords()) {
316 NFD_LOG_DEBUG("setStragglerTimer " << pitEntry->getName() <<
317 " cannot set StragglerTimer when an OutRecord is pending");
318 return;
319 }
320
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700321 time::nanoseconds stragglerTime = time::milliseconds(100);
Junxiao Shic041ca32014-02-25 20:01:15 -0700322
323 pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
Haowei Yuan78c84d12014-02-27 15:35:13 -0600324 bind(&Pit::erase, &m_pit, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700325}
326
327void
328Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
329{
Junxiao Shic041ca32014-02-25 20:01:15 -0700330 scheduler::cancel(pitEntry->m_unsatisfyTimer);
331 scheduler::cancel(pitEntry->m_stragglerTimer);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700332}
333
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800334} // namespace nfd