blob: 58ce5a39761697499ec5bfdf492a9d50257008b4 [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"
Alexander Afanasyev33b72772014-01-26 23:22:58 -08009
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080010namespace nfd {
Alexander Afanasyev33b72772014-01-26 23:22:58 -080011
Junxiao Shi8c8d2182014-01-30 22:33:00 -070012NFD_LOG_INIT("Forwarder");
13
Junxiao Shif3c07812014-03-11 21:48:49 -070014using fw::Strategy;
15
Junxiao Shif3c07812014-03-11 21:48:49 -070016const Name Forwarder::LOCALHOST_NAME("ndn:/localhost");
Junxiao Shi88884492014-02-15 15:57:43 -070017
Junxiao Shic041ca32014-02-25 20:01:15 -070018Forwarder::Forwarder()
Junxiao Shia4f2be82014-03-02 22:56:41 -070019 : m_faceTable(*this)
Haowei Yuan78c84d12014-02-27 15:35:13 -060020 , m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
HangZhangad4afd12014-03-01 11:03:08 +080021 , m_fib(m_nameTree)
Haowei Yuan78c84d12014-02-27 15:35:13 -060022 , m_pit(m_nameTree)
HangZhangc85a23c2014-03-01 15:55:55 +080023 , m_measurements(m_nameTree)
Junxiao Shif3c07812014-03-11 21:48:49 -070024 , m_strategyChoice(m_nameTree, fw::makeDefaultStrategy(*this))
Alexander Afanasyev33b72772014-01-26 23:22:58 -080025{
Junxiao Shif3c07812014-03-11 21:48:49 -070026 fw::installStrategies(*this);
Alexander Afanasyev33b72772014-01-26 23:22:58 -080027}
28
29void
Junxiao Shid3c792f2014-01-30 00:46:13 -070030Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
31{
32 // receive Interest
Junxiao Shif3c07812014-03-11 21:48:49 -070033 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
34 " interest=" << interest.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -070035 const_cast<Interest&>(interest).setIncomingFaceId(inFace.getId());
Junxiao Shib289cc12014-03-15 12:19:05 -070036 m_counters.getInInterest() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -070037
Junxiao Shi88884492014-02-15 15:57:43 -070038 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -070039 bool isViolatingLocalhost = !inFace.isLocal() &&
40 LOCALHOST_NAME.isPrefixOf(interest.getName());
41 if (isViolatingLocalhost) {
42 NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
43 " interest=" << interest.getName() << " violates /localhost");
44 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -070045 return;
46 }
Junxiao Shic041ca32014-02-25 20:01:15 -070047
Junxiao Shid3c792f2014-01-30 00:46:13 -070048 // PIT insert
Junxiao Shi40631842014-03-01 13:52:37 -070049 shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
Junxiao Shic041ca32014-02-25 20:01:15 -070050
Junxiao Shid3c792f2014-01-30 00:46:13 -070051 // detect loop and record Nonce
52 bool isLoop = ! pitEntry->addNonce(interest.getNonce());
53 if (isLoop) {
54 // goto Interest loop pipeline
55 this->onInterestLoop(inFace, interest, pitEntry);
56 return;
57 }
Junxiao Shic041ca32014-02-25 20:01:15 -070058
Junxiao Shid3c792f2014-01-30 00:46:13 -070059 // cancel unsatisfy & straggler timer
60 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070061
Junxiao Shif3c07812014-03-11 21:48:49 -070062 // is pending?
Junxiao Shid3c792f2014-01-30 00:46:13 -070063 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
Junxiao Shie17349a2014-03-25 00:55:38 -070064 bool isPending = inRecords.begin() != inRecords.end();
Junxiao Shid3c792f2014-01-30 00:46:13 -070065 if (!isPending) {
66 // CS lookup
67 const Data* csMatch = m_cs.find(interest);
68 if (csMatch != 0) {
69 // XXX should we lookup PIT for other Interests that also match csMatch?
70
71 // goto outgoing Data pipeline
72 this->onOutgoingData(*csMatch, inFace);
73 return;
74 }
75 }
Junxiao Shic041ca32014-02-25 20:01:15 -070076
Junxiao Shid3c792f2014-01-30 00:46:13 -070077 // insert InRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -070078 pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -070079
Junxiao Shid3c792f2014-01-30 00:46:13 -070080 // FIB lookup
Junxiao Shi40631842014-03-01 13:52:37 -070081 shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -070082
Junxiao Shid3c792f2014-01-30 00:46:13 -070083 // dispatch to strategy
Junxiao Shif3c07812014-03-11 21:48:49 -070084 this->dispatchToStrategy(pitEntry, bind(&Strategy::afterReceiveInterest, _1,
85 boost::cref(inFace), boost::cref(interest), fibEntry, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -070086}
87
88void
89Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
90 shared_ptr<pit::Entry> pitEntry)
91{
Junxiao Shif3c07812014-03-11 21:48:49 -070092 NFD_LOG_DEBUG("onInterestLoop face=" << inFace.getId() <<
93 " interest=" << interest.getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -070094
Junxiao Shif3c07812014-03-11 21:48:49 -070095 // (drop)
96}
97
98/** \brief compare two InRecords for picking outgoing Interest
99 * \return true if b is preferred over a
100 *
101 * This function should be passed to std::max_element over InRecordCollection.
102 * The outgoing Interest picked is the last incoming Interest
103 * that does not come from outFace.
104 * If all InRecords come from outFace, it's fine to pick that. This happens when
105 * there's only one InRecord that comes from outFace. The legit use is for
106 * vehicular network; otherwise, strategy shouldn't send to the sole inFace.
107 */
108static inline bool
109compare_pickInterest(const pit::InRecord& a, const pit::InRecord& b, const Face* outFace)
110{
111 bool isOutFaceA = a.getFace().get() == outFace;
112 bool isOutFaceB = b.getFace().get() == outFace;
113
114 if (!isOutFaceA && isOutFaceB) {
115 return false;
116 }
117 if (isOutFaceA && !isOutFaceB) {
118 return true;
119 }
120
121 return a.getLastRenewed() > b.getLastRenewed();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700122}
123
124void
125Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
126{
Junxiao Shif3c07812014-03-11 21:48:49 -0700127 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
128 " interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700129
Junxiao Shi57f0f312014-03-16 11:52:20 -0700130 // scope control
131 if (pitEntry->violatesScope(outFace)) {
Junxiao Shif3c07812014-03-11 21:48:49 -0700132 NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
Junxiao Shi57f0f312014-03-16 11:52:20 -0700133 " interest=" << pitEntry->getName() << " violates scope");
Junxiao Shi11bd9c22014-03-13 20:44:13 -0700134 return;
135 }
136
Junxiao Shid3c792f2014-01-30 00:46:13 -0700137 // pick Interest
Junxiao Shif3c07812014-03-11 21:48:49 -0700138 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
139 pit::InRecordCollection::const_iterator pickedInRecord = std::max_element(
140 inRecords.begin(), inRecords.end(), bind(&compare_pickInterest, _1, _2, &outFace));
141 BOOST_ASSERT(pickedInRecord != inRecords.end());
142 const Interest& interest = pickedInRecord->getInterest();
Junxiao Shic041ca32014-02-25 20:01:15 -0700143
Junxiao Shid3c792f2014-01-30 00:46:13 -0700144 // insert OutRecord
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700145 pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
Junxiao Shic041ca32014-02-25 20:01:15 -0700146
Junxiao Shid3c792f2014-01-30 00:46:13 -0700147 // set PIT unsatisfy timer
148 this->setUnsatisfyTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700149
Junxiao Shid3c792f2014-01-30 00:46:13 -0700150 // send Interest
151 outFace.sendInterest(interest);
Junxiao Shib289cc12014-03-15 12:19:05 -0700152 m_counters.getOutInterest() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700153}
154
155void
Junxiao Shi09498f02014-02-26 19:41:08 -0700156Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
Junxiao Shid3c792f2014-01-30 00:46:13 -0700157{
Junxiao Shi09498f02014-02-26 19:41:08 -0700158 NFD_LOG_DEBUG("onInterestReject interest=" << pitEntry->getName());
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700159
Junxiao Shid3c792f2014-01-30 00:46:13 -0700160 // set PIT straggler timer
161 this->setStragglerTimer(pitEntry);
162}
163
164void
165Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
166{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700167 NFD_LOG_DEBUG("onInterestUnsatisfied interest=" << pitEntry->getName());
168
Junxiao Shid3c792f2014-01-30 00:46:13 -0700169 // invoke PIT unsatisfied callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700170 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
171 pitEntry));
Junxiao Shic041ca32014-02-25 20:01:15 -0700172
Junxiao Shif3c07812014-03-11 21:48:49 -0700173 // PIT delete
Haowei Yuan78c84d12014-02-27 15:35:13 -0600174 m_pit.erase(pitEntry);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700175}
176
177void
178Forwarder::onIncomingData(Face& inFace, const Data& data)
179{
180 // receive Data
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700181 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() << " data=" << data.getName());
Junxiao Shi06887ac2014-02-13 20:15:42 -0700182 const_cast<Data&>(data).setIncomingFaceId(inFace.getId());
Junxiao Shib289cc12014-03-15 12:19:05 -0700183 m_counters.getInData() ++;
Junxiao Shic041ca32014-02-25 20:01:15 -0700184
Junxiao Shi88884492014-02-15 15:57:43 -0700185 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700186 bool isViolatingLocalhost = !inFace.isLocal() &&
187 LOCALHOST_NAME.isPrefixOf(data.getName());
188 if (isViolatingLocalhost) {
189 NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() <<
190 " data=" << data.getName() << " violates /localhost");
191 // (drop)
Junxiao Shi88884492014-02-15 15:57:43 -0700192 return;
193 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700194
Junxiao Shid3c792f2014-01-30 00:46:13 -0700195 // PIT match
196 shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
197 if (pitMatches->begin() == pitMatches->end()) {
198 // goto Data unsolicited pipeline
199 this->onDataUnsolicited(inFace, data);
200 return;
201 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700202
Junxiao Shid3c792f2014-01-30 00:46:13 -0700203 // CS insert
204 m_cs.insert(data);
Junxiao Shic041ca32014-02-25 20:01:15 -0700205
Junxiao Shid3c792f2014-01-30 00:46:13 -0700206 std::set<shared_ptr<Face> > pendingDownstreams;
207 // foreach PitEntry
208 for (pit::DataMatchResult::iterator it = pitMatches->begin();
209 it != pitMatches->end(); ++it) {
210 shared_ptr<pit::Entry> pitEntry = *it;
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700211 NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
Junxiao Shic041ca32014-02-25 20:01:15 -0700212
Junxiao Shid3c792f2014-01-30 00:46:13 -0700213 // cancel unsatisfy & straggler timer
214 this->cancelUnsatisfyAndStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700215
Junxiao Shid3c792f2014-01-30 00:46:13 -0700216 // remember pending downstreams
217 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
218 for (pit::InRecordCollection::const_iterator it = inRecords.begin();
219 it != inRecords.end(); ++it) {
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700220 if (it->getExpiry() > time::steady_clock::now()) {
Junxiao Shid3c792f2014-01-30 00:46:13 -0700221 pendingDownstreams.insert(it->getFace());
222 }
223 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700224
Junxiao Shid3c792f2014-01-30 00:46:13 -0700225 // mark PIT satisfied
226 pitEntry->deleteInRecords();
227 pitEntry->deleteOutRecord(inFace.shared_from_this());
Junxiao Shic041ca32014-02-25 20:01:15 -0700228
Junxiao Shid3c792f2014-01-30 00:46:13 -0700229 // set PIT straggler timer
230 this->setStragglerTimer(pitEntry);
Junxiao Shic041ca32014-02-25 20:01:15 -0700231
Junxiao Shid3c792f2014-01-30 00:46:13 -0700232 // invoke PIT satisfy callback
Junxiao Shif3c07812014-03-11 21:48:49 -0700233 this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyPendingInterest, _1,
234 pitEntry, boost::cref(inFace), boost::cref(data)));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700235 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700236
Junxiao Shid3c792f2014-01-30 00:46:13 -0700237 // foreach pending downstream
238 for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
239 it != pendingDownstreams.end(); ++it) {
240 // goto outgoing Data pipeline
241 this->onOutgoingData(data, **it);
242 }
243}
244
245void
246Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
247{
248 // accept to cache?
Junxiao Shif3c07812014-03-11 21:48:49 -0700249 bool acceptToCache = inFace.isLocal();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700250 if (acceptToCache) {
251 // CS insert
Junxiao Shif3c07812014-03-11 21:48:49 -0700252 m_cs.insert(data, true);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700253 }
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700254
Junxiao Shif3c07812014-03-11 21:48:49 -0700255 NFD_LOG_DEBUG("onDataUnsolicited face=" << inFace.getId() <<
256 " data=" << data.getName() <<
257 (acceptToCache ? " cached" : " not cached"));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700258}
259
260void
261Forwarder::onOutgoingData(const Data& data, Face& outFace)
262{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700263 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() << " data=" << data.getName());
264
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700265 // /localhost scope control
Junxiao Shif3c07812014-03-11 21:48:49 -0700266 bool isViolatingLocalhost = !outFace.isLocal() &&
267 LOCALHOST_NAME.isPrefixOf(data.getName());
268 if (isViolatingLocalhost) {
269 NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() <<
270 " data=" << data.getName() << " violates /localhost");
271 // (drop)
Junxiao Shi9b27bd22014-02-26 20:29:58 -0700272 return;
273 }
274
Junxiao Shif3c07812014-03-11 21:48:49 -0700275 // TODO traffic manager
Junxiao Shic041ca32014-02-25 20:01:15 -0700276
Junxiao Shid3c792f2014-01-30 00:46:13 -0700277 // send Data
278 outFace.sendData(data);
Junxiao Shib289cc12014-03-15 12:19:05 -0700279 m_counters.getOutData() ++;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700280}
281
282static inline bool
283compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
284{
285 return a.getExpiry() < b.getExpiry();
286}
287
288void
289Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
290{
291 const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
292 pit::InRecordCollection::const_iterator lastExpiring =
293 std::max_element(inRecords.begin(), inRecords.end(),
294 &compare_InRecord_expiry);
295
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700296 time::steady_clock::TimePoint lastExpiry = lastExpiring->getExpiry();
297 time::nanoseconds lastExpiryFromNow = lastExpiry - time::steady_clock::now();
Junxiao Shid3c792f2014-01-30 00:46:13 -0700298 if (lastExpiryFromNow <= time::seconds(0)) {
299 // TODO all InRecords are already expired; will this happen?
300 }
Junxiao Shic041ca32014-02-25 20:01:15 -0700301
302 pitEntry->m_unsatisfyTimer = scheduler::schedule(lastExpiryFromNow,
Junxiao Shid3c792f2014-01-30 00:46:13 -0700303 bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
304}
305
306void
307Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
308{
Junxiao Shi57f0f312014-03-16 11:52:20 -0700309 if (pitEntry->hasUnexpiredOutRecords()) {
310 NFD_LOG_DEBUG("setStragglerTimer " << pitEntry->getName() <<
311 " cannot set StragglerTimer when an OutRecord is pending");
312 return;
313 }
314
Alexander Afanasyeveb3197f2014-03-17 19:28:18 -0700315 time::nanoseconds stragglerTime = time::milliseconds(100);
Junxiao Shic041ca32014-02-25 20:01:15 -0700316
317 pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
Haowei Yuan78c84d12014-02-27 15:35:13 -0600318 bind(&Pit::erase, &m_pit, pitEntry));
Junxiao Shid3c792f2014-01-30 00:46:13 -0700319}
320
321void
322Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
323{
Junxiao Shic041ca32014-02-25 20:01:15 -0700324 scheduler::cancel(pitEntry->m_unsatisfyTimer);
325 scheduler::cancel(pitEntry->m_stragglerTimer);
Junxiao Shid3c792f2014-01-30 00:46:13 -0700326}
327
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800328} // namespace nfd