NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
access-strategy.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "access-strategy.hpp"
27 #include "core/logger.hpp"
28 
29 namespace nfd {
30 namespace fw {
31 
32 NFD_LOG_INIT("AccessStrategy");
33 
34 const Name AccessStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/access/%FD%01");
36 
38  : Strategy(forwarder, name)
39  , m_removeFaceInfoConn(this->beforeRemoveFace.connect(
40  bind(&AccessStrategy::removeFaceInfo, this, _1)))
41 {
42 }
43 
45 {
46 }
47 
48 void
50  const Interest& interest,
51  shared_ptr<fib::Entry> fibEntry,
52  shared_ptr<pit::Entry> pitEntry)
53 {
54  RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
55  switch (suppressResult) {
57  this->afterReceiveNewInterest(inFace, interest, fibEntry, pitEntry);
58  break;
60  this->afterReceiveRetxInterest(inFace, interest, fibEntry, pitEntry);
61  break;
63  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-suppress");
64  break;
65  default:
66  BOOST_ASSERT(false);
67  break;
68  }
69 }
70 
71 void
72 AccessStrategy::afterReceiveNewInterest(const Face& inFace,
73  const Interest& interest,
74  shared_ptr<fib::Entry> fibEntry,
75  shared_ptr<pit::Entry> pitEntry)
76 {
77  Name miName;
78  shared_ptr<MtInfo> mi;
79  std::tie(miName, mi) = this->findPrefixMeasurements(*pitEntry);
80 
81  // has measurements for Interest Name?
82  if (mi != nullptr) {
83  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
84  " new-interest mi=" << miName);
85 
86  // send to last working nexthop
87  bool isSentToLastNexthop = this->sendToLastNexthop(inFace, pitEntry, *mi, fibEntry);
88 
89  if (isSentToLastNexthop) {
90  return;
91  }
92  }
93  else {
94  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() <<
95  " new-interest no-mi");
96  }
97 
98  // no measurements, or last working nexthop unavailable
99 
100  // multicast to all nexthops except incoming face
101  this->multicast(pitEntry, fibEntry, {inFace.getId()});
102 }
103 
104 void
105 AccessStrategy::afterReceiveRetxInterest(const Face& inFace,
106  const Interest& interest,
107  shared_ptr<fib::Entry> fibEntry,
108  shared_ptr<pit::Entry> pitEntry)
109 {
110  NFD_LOG_DEBUG(interest << " interestFrom " << inFace.getId() << " retx-forward");
111  this->multicast(pitEntry, fibEntry, {inFace.getId()});
112 }
113 
114 bool
115 AccessStrategy::sendToLastNexthop(const Face& inFace, shared_ptr<pit::Entry> pitEntry, MtInfo& mi,
116  shared_ptr<fib::Entry> fibEntry)
117 {
118  if (mi.lastNexthop == face::INVALID_FACEID) {
119  NFD_LOG_DEBUG(pitEntry->getInterest() << " no-last-nexthop");
120  return false;
121  }
122 
123  if (mi.lastNexthop == inFace.getId()) {
124  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-is-downstream");
125  return false;
126  }
127 
128  shared_ptr<Face> face = this->getFace(mi.lastNexthop);
129  if (face == nullptr || !fibEntry->hasNextHop(face)) {
130  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-gone");
131  return false;
132  }
133 
134  if (pitEntry->violatesScope(*face)) {
135  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-violates-scope");
136  return false;
137  }
138 
139  RttEstimator::Duration rto = mi.rtt.computeRto();
140  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << mi.lastNexthop <<
141  " last-nexthop rto=" << time::duration_cast<time::microseconds>(rto).count());
142 
143  this->sendInterest(pitEntry, face);
144 
145  // schedule RTO timeout
146  shared_ptr<PitInfo> pi = pitEntry->getOrCreateStrategyInfo<PitInfo>();
147  pi->rtoTimer = scheduler::schedule(rto,
148  bind(&AccessStrategy::afterRtoTimeout, this, weak_ptr<pit::Entry>(pitEntry),
149  weak_ptr<fib::Entry>(fibEntry), inFace.getId(), mi.lastNexthop));
150 
151  return true;
152 }
153 
154 void
155 AccessStrategy::afterRtoTimeout(weak_ptr<pit::Entry> pitWeak, weak_ptr<fib::Entry> fibWeak,
156  FaceId inFace, FaceId firstOutFace)
157 {
158  shared_ptr<pit::Entry> pitEntry = pitWeak.lock();
159  BOOST_ASSERT(pitEntry != nullptr);
160  // pitEntry can't become nullptr, because RTO timer should be cancelled upon pitEntry destruction
161 
162  shared_ptr<fib::Entry> fibEntry = fibWeak.lock();
163  if (fibEntry == nullptr) {
164  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFace << " fib-gone");
165  return;
166  }
167 
168  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFace <<
169  " multicast-except " << inFace << ',' << firstOutFace);
170  this->multicast(pitEntry, fibEntry, {inFace, firstOutFace});
171 }
172 
173 void
174 AccessStrategy::multicast(shared_ptr<pit::Entry> pitEntry, shared_ptr<fib::Entry> fibEntry,
175  std::unordered_set<FaceId> exceptFaces)
176 {
177  for (const fib::NextHop& nexthop : fibEntry->getNextHops()) {
178  shared_ptr<Face> face = nexthop.getFace();
179  if (exceptFaces.count(face->getId()) > 0) {
180  continue;
181  }
182  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << face->getId() <<
183  " multicast");
184  this->sendInterest(pitEntry, face);
185  }
186 }
187 
188 void
189 AccessStrategy::beforeSatisfyInterest(shared_ptr<pit::Entry> pitEntry,
190  const Face& inFace, const Data& data)
191 {
192  shared_ptr<PitInfo> pi = pitEntry->getStrategyInfo<PitInfo>();
193  if (pi != nullptr) {
194  pi->rtoTimer.cancel();
195  }
196 
197  if (pitEntry->getInRecords().empty()) { // already satisfied by another upstream
198  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
199  " not-fastest");
200  return;
201  }
202 
203  pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(inFace);
204  if (outRecord == pitEntry->getOutRecords().end()) { // no OutRecord
205  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
206  " no-out-record");
207  return;
208  }
209 
210  time::steady_clock::Duration rtt = time::steady_clock::now() - outRecord->getLastRenewed();
211  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << inFace.getId() <<
212  " rtt=" << time::duration_cast<time::microseconds>(rtt).count());
213  this->updateMeasurements(inFace, data, time::duration_cast<RttEstimator::Duration>(rtt));
214 }
215 
216 void
217 AccessStrategy::updateMeasurements(const Face& inFace, const Data& data,
218  const RttEstimator::Duration& rtt)
219 {
220  FaceInfo& fi = m_fit[inFace.getId()];
221  fi.rtt.addMeasurement(rtt);
222 
223  shared_ptr<MtInfo> mi = this->addPrefixMeasurements(data);
224  if (mi->lastNexthop != inFace.getId()) {
225  mi->lastNexthop = inFace.getId();
226  mi->rtt = fi.rtt;
227  }
228  else {
229  mi->rtt.addMeasurement(rtt);
230  }
231 }
232 
233 AccessStrategy::MtInfo::MtInfo()
234  : lastNexthop(face::INVALID_FACEID)
235  , rtt(1, time::milliseconds(1), 0.1)
236 {
237 }
238 
239 std::tuple<Name, shared_ptr<AccessStrategy::MtInfo>>
240 AccessStrategy::findPrefixMeasurements(const pit::Entry& pitEntry)
241 {
242  shared_ptr<measurements::Entry> me = this->getMeasurements().findLongestPrefixMatch(pitEntry);
243  if (me == nullptr) {
244  return std::forward_as_tuple(Name(), nullptr);
245  }
246 
247  shared_ptr<MtInfo> mi = me->getStrategyInfo<MtInfo>();
248  BOOST_ASSERT(mi != nullptr);
249  // XXX after runtime strategy change, it's possible that me exists but mi doesn't exist;
250  // this case needs another longest prefix match until mi is found
251  return std::forward_as_tuple(me->getName(), mi);
252 }
253 
254 shared_ptr<AccessStrategy::MtInfo>
255 AccessStrategy::addPrefixMeasurements(const Data& data)
256 {
257  shared_ptr<measurements::Entry> me;
258  if (data.getName().size() >= 1) {
259  me = this->getMeasurements().get(data.getName().getPrefix(-1));
260  }
261  if (me == nullptr) { // parent of Data Name is not in this strategy, or Data Name is empty
262  me = this->getMeasurements().get(data.getName());
263  // Data Name must be in this strategy
264  BOOST_ASSERT(me != nullptr);
265  }
266 
267  static const time::nanoseconds ME_LIFETIME = time::seconds(8);
268  this->getMeasurements().extendLifetime(*me, ME_LIFETIME);
269 
270  return me->getOrCreateStrategyInfo<MtInfo>();
271 }
272 
273 AccessStrategy::FaceInfo::FaceInfo()
274  : rtt(1, time::milliseconds(1), 0.1)
275 {
276 }
277 
278 void
279 AccessStrategy::removeFaceInfo(shared_ptr<Face> face)
280 {
281  m_fit.erase(face->getId());
282 }
283 
284 } // namespace fw
285 } // namespace nfd
time::microseconds Duration
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:55
virtual Result decide(const Face &inFace, const Interest &interest, pit::Entry &pitEntry) const 1
determines whether Interest is a retransmission, and if so, whether it shall be forwarded or suppress...
AccessStrategy(Forwarder &forwarder, const Name &name=STRATEGY_NAME)
static time_point now() noexcept
Definition: time.cpp:79
const Name & getName() const
Get name of the Data packet.
Definition: data.hpp:360
Interest is retransmission and should be suppressed.
main class of NFD
Definition: forwarder.hpp:55
represents an Interest packet
Definition: interest.hpp:45
static const Name STRATEGY_NAME
shared_ptr< measurements::Entry > get(const Name &name)
find or insert a Measurements entry for name
virtual void afterReceiveInterest(const Face &inFace, const Interest &interest, shared_ptr< fib::Entry > fibEntry, shared_ptr< pit::Entry > pitEntry) 1
trigger after Interest is received
Interest is new (not a retransmission)
shared_ptr< Face > getFace(FaceId id)
Definition: strategy.hpp:235
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:229
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
represents a PIT entry
Definition: pit-entry.hpp:69
NFD_REGISTER_STRATEGY(AccessStrategy)
virtual void beforeSatisfyInterest(shared_ptr< pit::Entry > pitEntry, const Face &inFace, const Data &data) 1
trigger before PIT entry is satisfied
Name abstraction to represent an absolute name.
Definition: name.hpp:46
size_t size() const
Get the number of components.
Definition: name.hpp:408
represents a forwarding strategy
Definition: strategy.hpp:38
void extendLifetime(measurements::Entry &entry, const time::nanoseconds &lifetime)
extend lifetime of an entry
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
EventId schedule(const time::nanoseconds &after, const Scheduler::Event &event)
schedule an event
Definition: scheduler.cpp:47
Interest is retransmission and should be forwarded.
void sendInterest(shared_ptr< pit::Entry > pitEntry, shared_ptr< Face > outFace, bool wantNewNonce=false)
send Interest to outFace
Definition: strategy.hpp:208
Access Router Strategy version 1.
uint64_t FaceId
identifies a face
Definition: face.hpp:39
represents a Data packet
Definition: data.hpp:39
const FaceId INVALID_FACEID
indicates an invalid FaceId
Definition: face.hpp:42
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38
shared_ptr< measurements::Entry > findLongestPrefixMatch(const Name &name, const measurements::EntryPredicate &pred=measurements::AnyEntry()) const
perform a longest prefix match for name