NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: 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; -*- */
2 /*
3  * Copyright (c) 2014-2019, 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  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "access-strategy.hpp"
27 #include "algorithm.hpp"
28 #include "common/global.hpp"
29 #include "common/logger.hpp"
30 
31 namespace nfd {
32 namespace fw {
33 
36 
38  : Strategy(forwarder)
39  , m_rttEstimatorOpts(make_shared<RttEstimator::Options>()) // use the default options
40  , m_removeFaceConn(beforeRemoveFace.connect([this] (const Face& face) { m_fit.erase(face.getId()); }))
41 {
42  ParsedInstanceName parsed = parseInstanceName(name);
43  if (!parsed.parameters.empty()) {
44  NDN_THROW(std::invalid_argument("AccessStrategy does not accept parameters"));
45  }
46  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
47  NDN_THROW(std::invalid_argument("AccessStrategy does not support version " + to_string(*parsed.version)));
48  }
50 }
51 
52 const Name&
54 {
55  static Name strategyName("/localhost/nfd/strategy/access/%FD%01");
56  return strategyName;
57 }
58 
59 void
61  const shared_ptr<pit::Entry>& pitEntry)
62 {
63  auto suppressResult = m_retxSuppression.decidePerPitEntry(*pitEntry);
64  switch (suppressResult) {
66  return afterReceiveNewInterest(ingress, interest, pitEntry);
68  return afterReceiveRetxInterest(ingress, interest, pitEntry);
70  NFD_LOG_DEBUG(interest << " interestFrom " << ingress << " retx-suppress");
71  return;
72  }
73 }
74 
75 void
76 AccessStrategy::afterReceiveNewInterest(const FaceEndpoint& ingress, const Interest& interest,
77  const shared_ptr<pit::Entry>& pitEntry)
78 {
79  const auto& fibEntry = this->lookupFib(*pitEntry);
80  Name miName;
81  MtInfo* mi = nullptr;
82  std::tie(miName, mi) = this->findPrefixMeasurements(*pitEntry);
83 
84  // has measurements for Interest Name?
85  if (mi != nullptr) {
86  NFD_LOG_DEBUG(interest << " interestFrom " << ingress << " new-interest mi=" << miName);
87 
88  // send to last working nexthop
89  bool isSentToLastNexthop = this->sendToLastNexthop(ingress, interest, pitEntry, *mi, fibEntry);
90  if (isSentToLastNexthop) {
91  return;
92  }
93  }
94  else {
95  NFD_LOG_DEBUG(interest << " interestFrom " << ingress << " new-interest no-mi");
96  }
97 
98  // no measurements, or last working nexthop unavailable
99 
100  // multicast to all nexthops except incoming face
101  size_t nMulticastSent = this->multicast(ingress.face, interest, pitEntry, fibEntry);
102 
103  if (nMulticastSent == 0) {
104  this->rejectPendingInterest(pitEntry);
105  }
106 }
107 
108 void
109 AccessStrategy::afterReceiveRetxInterest(const FaceEndpoint& ingress, const Interest& interest,
110  const shared_ptr<pit::Entry>& pitEntry)
111 {
112  const auto& fibEntry = this->lookupFib(*pitEntry);
113  NFD_LOG_DEBUG(interest << " interestFrom " << ingress << " retx-forward");
114  this->multicast(ingress.face, interest, pitEntry, fibEntry);
115 }
116 
117 bool
118 AccessStrategy::sendToLastNexthop(const FaceEndpoint& ingress, const Interest& interest,
119  const shared_ptr<pit::Entry>& pitEntry, MtInfo& mi,
120  const fib::Entry& fibEntry)
121 {
122  if (mi.lastNexthop == face::INVALID_FACEID) {
123  NFD_LOG_DEBUG(pitEntry->getInterest() << " no-last-nexthop");
124  return false;
125  }
126 
127  if (mi.lastNexthop == ingress.face.getId()) {
128  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-is-downstream");
129  return false;
130  }
131 
132  Face* outFace = this->getFace(mi.lastNexthop);
133  if (outFace == nullptr || !fibEntry.hasNextHop(*outFace)) {
134  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-gone");
135  return false;
136  }
137 
138  if (wouldViolateScope(ingress.face, interest, *outFace)) {
139  NFD_LOG_DEBUG(pitEntry->getInterest() << " last-nexthop-violates-scope");
140  return false;
141  }
142 
143  auto rto = mi.rtt.getEstimatedRto();
144  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << mi.lastNexthop
145  << " last-nexthop rto=" << time::duration_cast<time::microseconds>(rto).count());
146 
147  this->sendInterest(pitEntry, FaceEndpoint(*outFace, 0), interest);
148 
149  // schedule RTO timeout
150  PitInfo* pi = pitEntry->insertStrategyInfo<PitInfo>().first;
151  pi->rtoTimer = getScheduler().schedule(rto,
152  [this, pitWeak = weak_ptr<pit::Entry>(pitEntry), face = ingress.face.getId(),
153  endpoint = ingress.endpoint, lastNexthop = mi.lastNexthop] {
154  afterRtoTimeout(pitWeak, face, endpoint, lastNexthop);
155  });
156 
157  return true;
158 }
159 
160 void
161 AccessStrategy::afterRtoTimeout(const weak_ptr<pit::Entry>& pitWeak,
162  FaceId inFaceId, EndpointId inEndpointId, FaceId firstOutFaceId)
163 {
164  shared_ptr<pit::Entry> pitEntry = pitWeak.lock();
165  // if PIT entry is gone, RTO timer should have been cancelled
166  BOOST_ASSERT(pitEntry != nullptr);
167 
168  Face* inFace = this->getFace(inFaceId);
169  if (inFace == nullptr) {
170  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFaceId
171  << " inFace-gone " << inFaceId);
172  return;
173  }
174 
175  auto inRecord = pitEntry->getInRecord(*inFace);
176  // in-record is erased only if Interest is satisfied, and RTO timer should have been cancelled
177  // note: if this strategy is extended to send Nacks, that would also erase the in-record,
178  // and the RTO timer should be cancelled in that case as well
179  BOOST_ASSERT(inRecord != pitEntry->in_end());
180 
181  const Interest& interest = inRecord->getInterest();
182  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
183 
184  NFD_LOG_DEBUG(pitEntry->getInterest() << " timeoutFrom " << firstOutFaceId
185  << " multicast-except " << firstOutFaceId);
186  this->multicast(*inFace, interest, pitEntry, fibEntry, firstOutFaceId);
187 }
188 
189 size_t
190 AccessStrategy::multicast(const Face& inFace, const Interest& interest,
191  const shared_ptr<pit::Entry>& pitEntry, const fib::Entry& fibEntry,
192  FaceId exceptFace)
193 {
194  size_t nSent = 0;
195  for (const auto& nexthop : fibEntry.getNextHops()) {
196  Face& outFace = nexthop.getFace();
197  if (&outFace == &inFace || outFace.getId() == exceptFace ||
198  wouldViolateScope(inFace, interest, outFace)) {
199  continue;
200  }
201  NFD_LOG_DEBUG(pitEntry->getInterest() << " interestTo " << outFace.getId() << " multicast");
202  this->sendInterest(pitEntry, FaceEndpoint(outFace, 0), interest);
203  ++nSent;
204  }
205  return nSent;
206 }
207 
208 void
209 AccessStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
210  const FaceEndpoint& ingress, const Data& data)
211 {
212  PitInfo* pi = pitEntry->getStrategyInfo<PitInfo>();
213  if (pi != nullptr) {
214  pi->rtoTimer.cancel();
215  }
216 
217  if (!pitEntry->hasInRecords()) { // already satisfied by another upstream
218  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << ingress << " not-fastest");
219  return;
220  }
221 
222  auto outRecord = pitEntry->getOutRecord(ingress.face);
223  if (outRecord == pitEntry->out_end()) { // no out-record
224  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << ingress << " no-out-record");
225  return;
226  }
227 
228  auto rtt = time::steady_clock::now() - outRecord->getLastRenewed();
229  NFD_LOG_DEBUG(pitEntry->getInterest() << " dataFrom " << ingress
230  << " rtt=" << time::duration_cast<time::microseconds>(rtt).count());
231  this->updateMeasurements(ingress.face, data, rtt);
232 }
233 
234 void
235 AccessStrategy::updateMeasurements(const Face& inFace, const Data& data, time::nanoseconds rtt)
236 {
237  auto ret = m_fit.emplace(std::piecewise_construct,
238  std::forward_as_tuple(inFace.getId()),
239  std::forward_as_tuple(m_rttEstimatorOpts));
240  FaceInfo& fi = ret.first->second;
241  fi.rtt.addMeasurement(rtt);
242 
243  MtInfo* mi = this->addPrefixMeasurements(data);
244  if (mi->lastNexthop != inFace.getId()) {
245  mi->lastNexthop = inFace.getId();
246  mi->rtt = fi.rtt;
247  }
248  else {
249  mi->rtt.addMeasurement(rtt);
250  }
251 }
252 
253 std::tuple<Name, AccessStrategy::MtInfo*>
254 AccessStrategy::findPrefixMeasurements(const pit::Entry& pitEntry)
255 {
256  measurements::Entry* me = this->getMeasurements().findLongestPrefixMatch(pitEntry);
257  if (me == nullptr) {
258  return std::make_tuple(Name(), nullptr);
259  }
260 
261  MtInfo* mi = me->getStrategyInfo<MtInfo>();
262  BOOST_ASSERT(mi != nullptr);
263  // XXX after runtime strategy change, it's possible that me exists but mi doesn't exist;
264  // this case needs another longest prefix match until mi is found
265  return std::make_tuple(me->getName(), mi);
266 }
267 
268 AccessStrategy::MtInfo*
269 AccessStrategy::addPrefixMeasurements(const Data& data)
270 {
271  measurements::Entry* me = nullptr;
272  if (!data.getName().empty()) {
273  me = this->getMeasurements().get(data.getName().getPrefix(-1));
274  }
275  if (me == nullptr) { // parent of Data Name is not in this strategy, or Data Name is empty
276  me = this->getMeasurements().get(data.getName());
277  // Data Name must be in this strategy
278  BOOST_ASSERT(me != nullptr);
279  }
280 
281  this->getMeasurements().extendLifetime(*me, 8_s);
282  return me->insertStrategyInfo<MtInfo>(m_rttEstimatorOpts).first;
283 }
284 
285 } // namespace fw
286 } // namespace nfd
nfd::fw::Strategy::getMeasurements
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:346
nfd::fw::AccessStrategy::getStrategyName
static const Name & getStrategyName()
Definition: access-strategy.cpp:53
global.hpp
nfd::fw::AccessStrategy
Access Router Strategy version 1.
Definition: access-strategy.hpp:51
nfd::FaceEndpoint::face
Face & face
Definition: face-endpoint.hpp:46
ndn::tlv::Interest
@ Interest
Definition: tlv.hpp:65
nfd::fw::Strategy::sendInterest
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const Interest &interest)
send Interest to egress
Definition: strategy.cpp:206
ndn::time::steady_clock::now
static time_point now() noexcept
Definition: time.cpp:80
nfd::fw::RetxSuppressionFixed::decidePerPitEntry
RetxSuppressionResult decidePerPitEntry(pit::Entry &pitEntry) const
determines whether Interest is a retransmission, and if so, whether it shall be forwarded or suppress...
Definition: retx-suppression-fixed.cpp:40
nfd::fw::NFD_REGISTER_STRATEGY
NFD_REGISTER_STRATEGY(AccessStrategy)
nfd::measurements::MeasurementsAccessor::extendLifetime
void extendLifetime(Entry &entry, const time::nanoseconds &lifetime)
extend lifetime of an entry
Definition: measurements-accessor.hpp:166
access-strategy.hpp
ndn::Name
Represents an absolute name.
Definition: name.hpp:44
ns3::ndn::Name
Name
Definition: ndn-common.cpp:25
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
nfd::face::INVALID_FACEID
const FaceId INVALID_FACEID
indicates an invalid FaceId
Definition: face-common.hpp:47
nfd::face::FaceId
uint64_t FaceId
Identifies a face.
Definition: face-common.hpp:44
nfd::fw::Strategy::setInstanceName
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:395
nfd::face::Face
generalization of a network interface
Definition: face.hpp:53
NDN_THROW
#define NDN_THROW(e)
Definition: exception.hpp:61
nfd::getScheduler
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:70
nfd::FaceEndpoint
Represents a face-endpoint pair in the forwarder.
Definition: face-endpoint.hpp:37
nfd::fw::wouldViolateScope
bool wouldViolateScope(const Face &inFace, const Interest &interest, const Face &outFace)
determine whether forwarding the Interest in pitEntry to outFace would violate scope
Definition: algorithm.cpp:32
nfd::fw::Strategy::lookupFib
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:297
ndn::Interest
Represents an Interest packet.
Definition: interest.hpp:44
nfd::fw::Strategy::parseInstanceName
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:123
nfd::measurements::MeasurementsAccessor::get
Entry * get(const Name &name)
find or insert a Measurements entry for name
Definition: measurements-accessor.hpp:122
nfd::face::Face::getId
FaceId getId() const
Definition: face.hpp:214
nfd::fw::Strategy::rejectPendingInterest
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
schedule the PIT entry for immediate deletion
Definition: strategy.hpp:302
nfd::measurements::MeasurementsAccessor::findLongestPrefixMatch
Entry * findLongestPrefixMatch(const Name &name, const EntryPredicate &pred=AnyEntry()) const
perform a longest prefix match for name
Definition: measurements-accessor.hpp:146
nfd::fw::AccessStrategy::afterReceiveInterest
void afterReceiveInterest(const FaceEndpoint &ingress, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
Definition: access-strategy.cpp:60
nfd::fw::Strategy::getFace
Face * getFace(FaceId id) const
Definition: strategy.hpp:352
ndn::Data
Represents a Data packet.
Definition: data.hpp:36
nfd::fw::Strategy
represents a forwarding strategy
Definition: strategy.hpp:38
NFD_LOG_DEBUG
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
nfd::fw::RetxSuppressionResult::FORWARD
@ FORWARD
Interest is retransmission and should be forwarded.
nfd::Forwarder
Main class of NFD's forwarding engine.
Definition: forwarder.hpp:52
Face
ndn Face
Definition: face-impl.hpp:41
ndn::tlv::Data
@ Data
Definition: tlv.hpp:66
ndn::to_string
std::string to_string(const T &val)
Definition: backports.hpp:102
algorithm.hpp
ndn::util::RttEstimator
RTT/RTO estimator.
Definition: rtt-estimator.hpp:42
ndn::name
Definition: name-component-types.hpp:33
nfd::fw::Strategy::makeInstanceName
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:134
nfd::face::EndpointId
uint64_t EndpointId
Identifies a remote endpoint on the link.
Definition: face-common.hpp:65
nfd::fw::RetxSuppressionResult::SUPPRESS
@ SUPPRESS
Interest is retransmission and should be suppressed.
NFD_LOG_INIT
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
nfd::fw::AccessStrategy::beforeSatisfyInterest
void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data) override
trigger before PIT entry is satisfied
Definition: access-strategy.cpp:209
nfd::fw::AccessStrategy::AccessStrategy
AccessStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
Definition: access-strategy.cpp:37
logger.hpp
nfd::fw::RetxSuppressionResult::NEW
@ NEW
Interest is new (not a retransmission)