NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
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-2022, 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 "strategy.hpp"
27 #include "forwarder.hpp"
28 #include "common/logger.hpp"
29 
30 #include <ndn-cxx/lp/pit-token.hpp>
31 
32 #include <boost/range/adaptor/map.hpp>
33 #include <boost/range/algorithm/copy.hpp>
34 
35 namespace nfd {
36 namespace fw {
37 
39 
40 Strategy::Registry&
41 Strategy::getRegistry()
42 {
43  static Registry registry;
44  return registry;
45 }
46 
47 Strategy::Registry::const_iterator
48 Strategy::find(const Name& instanceName)
49 {
50  const Registry& registry = getRegistry();
51  ParsedInstanceName parsed = parseInstanceName(instanceName);
52 
53  if (parsed.version) {
54  // specified version: find exact or next higher version
55 
56  auto found = registry.lower_bound(parsed.strategyName);
57  if (found != registry.end()) {
58  if (parsed.strategyName.getPrefix(-1).isPrefixOf(found->first)) {
59  NFD_LOG_TRACE("find " << instanceName << " versioned found=" << found->first);
60  return found;
61  }
62  }
63 
64  NFD_LOG_TRACE("find " << instanceName << " versioned not-found");
65  return registry.end();
66  }
67 
68  // no version specified: find highest version
69 
70  if (!parsed.strategyName.empty()) { // Name().getSuccessor() would be invalid
71  auto found = registry.lower_bound(parsed.strategyName.getSuccessor());
72  if (found != registry.begin()) {
73  --found;
74  if (parsed.strategyName.isPrefixOf(found->first)) {
75  NFD_LOG_TRACE("find " << instanceName << " unversioned found=" << found->first);
76  return found;
77  }
78  }
79  }
80 
81  NFD_LOG_TRACE("find " << instanceName << " unversioned not-found");
82  return registry.end();
83 }
84 
85 bool
86 Strategy::canCreate(const Name& instanceName)
87 {
88  return Strategy::find(instanceName) != getRegistry().end();
89 }
90 
91 unique_ptr<Strategy>
92 Strategy::create(const Name& instanceName, Forwarder& forwarder)
93 {
94  auto found = Strategy::find(instanceName);
95  if (found == getRegistry().end()) {
96  NFD_LOG_DEBUG("create " << instanceName << " not-found");
97  return nullptr;
98  }
99 
100  unique_ptr<Strategy> instance = found->second(forwarder, instanceName);
101  NFD_LOG_DEBUG("create " << instanceName << " found=" << found->first
102  << " created=" << instance->getInstanceName());
103  BOOST_ASSERT(!instance->getInstanceName().empty());
104  return instance;
105 }
106 
107 bool
108 Strategy::areSameType(const Name& instanceNameA, const Name& instanceNameB)
109 {
110  return Strategy::find(instanceNameA) == Strategy::find(instanceNameB);
111 }
112 
113 std::set<Name>
115 {
116  std::set<Name> strategyNames;
117  boost::copy(getRegistry() | boost::adaptors::map_keys,
118  std::inserter(strategyNames, strategyNames.end()));
119  return strategyNames;
120 }
121 
124 {
125  for (ssize_t i = input.size() - 1; i > 0; --i) {
126  if (input[i].isVersion()) {
127  return {input.getPrefix(i + 1), input[i].toVersion(), input.getSubName(i + 1)};
128  }
129  }
130  return {input, nullopt, PartialName()};
131 }
132 
133 Name
134 Strategy::makeInstanceName(const Name& input, const Name& strategyName)
135 {
136  BOOST_ASSERT(strategyName.at(-1).isVersion());
137 
138  bool hasVersion = std::any_of(input.rbegin(), input.rend(),
139  [] (const auto& comp) { return comp.isVersion(); });
140  return hasVersion ? input : Name(input).append(strategyName.at(-1));
141 }
142 
144  : afterAddFace(forwarder.m_faceTable.afterAdd)
145  , beforeRemoveFace(forwarder.m_faceTable.beforeRemove)
146  , m_forwarder(forwarder)
147  , m_measurements(m_forwarder.getMeasurements(), m_forwarder.getStrategyChoice(), *this)
148 {
149 }
150 
151 Strategy::~Strategy() = default;
152 
153 
154 void
156  pit::Entry& pitEntry)
157 {
158  NFD_LOG_DEBUG("afterReceiveLoopedInterest pitEntry=" << pitEntry.getName()
159  << " in=" << ingress);
160 }
161 
162 void
164  const shared_ptr<pit::Entry>& pitEntry)
165 {
166  NFD_LOG_DEBUG("beforeSatisfyInterest pitEntry=" << pitEntry->getName()
167  << " in=" << ingress << " data=" << data.getName());
168 }
169 
170 void
171 Strategy::satisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
172  const FaceEndpoint& ingress, const Data& data,
173  std::set<std::pair<Face*, EndpointId>>& satisfiedDownstreams,
174  std::set<std::pair<Face*, EndpointId>>& unsatisfiedDownstreams)
175 {
176  NFD_LOG_DEBUG("satisfyInterest pitEntry=" << pitEntry->getName()
177  << " in=" << ingress << " data=" << data.getName());
178 
179  NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
180 
181  auto now = time::steady_clock::now();
182 
183  // remember pending downstreams
184  for (const pit::InRecord& inRecord : pitEntry->getInRecords()) {
185  if (inRecord.getExpiry() > now) {
186  satisfiedDownstreams.emplace(&inRecord.getFace(), 0);
187  }
188  }
189 
190  // invoke PIT satisfy callback
191  beforeSatisfyInterest(data, ingress, pitEntry);
192 }
193 
194 
195 void
197  const shared_ptr<pit::Entry>& pitEntry)
198 {
199  NFD_LOG_DEBUG("afterContentStoreHit pitEntry=" << pitEntry->getName()
200  << " in=" << ingress << " data=" << data.getName());
201 
202  this->sendData(data, ingress.face, pitEntry);
203 }
204 
205 void
206 Strategy::afterReceiveData(const Data& data, const FaceEndpoint& ingress,
207  const shared_ptr<pit::Entry>& pitEntry)
208 {
209  NFD_LOG_DEBUG("afterReceiveData pitEntry=" << pitEntry->getName()
210  << " in=" << ingress << " data=" << data.getName());
211 
212  this->beforeSatisfyInterest(data, ingress, pitEntry);
213  this->sendDataToAll(data, pitEntry, ingress.face);
214 }
215 
216 void
218  const shared_ptr<pit::Entry>& pitEntry)
219 {
220  NFD_LOG_DEBUG("afterReceiveNack in=" << ingress << " pitEntry=" << pitEntry->getName());
221 }
222 
223 void
224 Strategy::onDroppedInterest(const Interest& interest, Face& egress)
225 {
226  NFD_LOG_DEBUG("onDroppedInterest out=" << egress.getId() << " name=" << interest.getName());
227 }
228 
229 void
230 Strategy::afterNewNextHop(const fib::NextHop& nextHop, const shared_ptr<pit::Entry>& pitEntry)
231 {
232  NFD_LOG_DEBUG("afterNewNextHop pitEntry=" << pitEntry->getName()
233  << " nexthop=" << nextHop.getFace().getId());
234 }
235 
237 Strategy::sendInterest(const Interest& interest, Face& egress, const shared_ptr<pit::Entry>& pitEntry)
238 {
239  if (interest.getTag<lp::PitToken>() != nullptr) {
240  Interest interest2 = interest; // make a copy to preserve tag on original packet
241  interest2.removeTag<lp::PitToken>();
242  return m_forwarder.onOutgoingInterest(interest2, egress, pitEntry);
243  }
244  return m_forwarder.onOutgoingInterest(interest, egress, pitEntry);
245 }
246 
247 bool
248 Strategy::sendData(const Data& data, Face& egress, const shared_ptr<pit::Entry>& pitEntry)
249 {
250  BOOST_ASSERT(pitEntry->getInterest().matchesData(data));
251 
252  shared_ptr<lp::PitToken> pitToken;
253  auto inRecord = pitEntry->getInRecord(egress);
254  if (inRecord != pitEntry->in_end()) {
255  pitToken = inRecord->getInterest().getTag<lp::PitToken>();
256  }
257 
258  // delete the PIT entry's in-record based on egress,
259  // since the Data is sent to the face from which the Interest was received
260  pitEntry->deleteInRecord(egress);
261 
262  if (pitToken != nullptr) {
263  Data data2 = data; // make a copy so each downstream can get a different PIT token
264  data2.setTag(pitToken);
265  return m_forwarder.onOutgoingData(data2, egress);
266  }
267  m_forwarder.onOutgoingData(data, egress);
268 
269  if (pitEntry->getInRecords().empty()) { // if nothing left, "closing down" the entry
270  // set PIT expiry timer to now
271  m_forwarder.setExpiryTimer(pitEntry, 0_ms);
272 
273  // mark PIT satisfied
274  pitEntry->isSatisfied = true;
275  }
276 }
277 
278 void
279 Strategy::sendDataToAll(const Data& data, const shared_ptr<pit::Entry>& pitEntry, const Face& inFace)
280 {
281  std::set<Face*> pendingDownstreams;
282  auto now = time::steady_clock::now();
283 
284  // remember pending downstreams
285  for (const auto& inRecord : pitEntry->getInRecords()) {
286  if (inRecord.getExpiry() > now) {
287  if (inRecord.getFace().getId() == inFace.getId() &&
288  inRecord.getFace().getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) {
289  continue;
290  }
291  pendingDownstreams.emplace(&inRecord.getFace());
292  }
293  }
294 
295  for (const auto& pendingDownstream : pendingDownstreams) {
296  this->sendData(data, *pendingDownstream, pitEntry);
297  }
298 
299  pitEntry->clearInRecords();
300 
301  // set PIT expiry timer to now
302  m_forwarder.setExpiryTimer(pitEntry, 0_ms);
303 
304  // mark PIT satisfied
305  pitEntry->isSatisfied = true;
306 }
307 
308 void
309 Strategy::sendNacks(const lp::NackHeader& header, const shared_ptr<pit::Entry>& pitEntry,
310  std::initializer_list<const Face*> exceptFaces)
311 {
312  // populate downstreams with all downstreams faces
313  std::unordered_set<Face*> downstreams;
314  std::transform(pitEntry->in_begin(), pitEntry->in_end(),
315  std::inserter(downstreams, downstreams.end()),
316  [] (const auto& inR) { return &inR.getFace(); });
317 
318  // remove excluded faces
319  for (auto exceptFace : exceptFaces) {
320  downstreams.erase(const_cast<Face*>(exceptFace));
321  }
322 
323  // send Nacks
324  for (auto downstream : downstreams) {
325  this->sendNack(header, *downstream, pitEntry);
326  }
327  // warning: don't loop on pitEntry->getInRecords(), because in-record is deleted when sending Nack
328 }
329 
330 const fib::Entry&
331 Strategy::lookupFib(const pit::Entry& pitEntry) const
332 {
333  const Fib& fib = m_forwarder.getFib();
334 
335  const Interest& interest = pitEntry.getInterest();
336  // has forwarding hint?
337  if (interest.getForwardingHint().empty()) {
338  // FIB lookup with Interest name
339  const fib::Entry& fibEntry = fib.findLongestPrefixMatch(pitEntry);
340  NFD_LOG_TRACE("lookupFib noForwardingHint found=" << fibEntry.getPrefix());
341  return fibEntry;
342  }
343 
344  const auto& fh = interest.getForwardingHint();
345  // Forwarding hint should have been stripped by incoming Interest pipeline when reaching producer region
346  BOOST_ASSERT(!m_forwarder.getNetworkRegionTable().isInProducerRegion(fh));
347 
348  const fib::Entry* fibEntry = nullptr;
349  for (const auto& delegation : fh) {
350  fibEntry = &fib.findLongestPrefixMatch(delegation);
351  if (fibEntry->hasNextHops()) {
352  if (fibEntry->getPrefix().size() == 0) {
353  // in consumer region, return the default route
354  NFD_LOG_TRACE("lookupFib inConsumerRegion found=" << fibEntry->getPrefix());
355  }
356  else {
357  // in default-free zone, use the first delegation that finds a FIB entry
358  NFD_LOG_TRACE("lookupFib delegation=" << delegation << " found=" << fibEntry->getPrefix());
359  }
360  return *fibEntry;
361  }
362  BOOST_ASSERT(fibEntry->getPrefix().size() == 0); // only ndn:/ FIB entry can have zero nexthop
363  }
364  BOOST_ASSERT(fibEntry != nullptr && fibEntry->getPrefix().size() == 0);
365  return *fibEntry; // only occurs if no delegation finds a FIB nexthop
366 }
367 
368 } // namespace fw
369 } // namespace nfd
virtual void satisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data, std::set< std::pair< Face *, EndpointId >> &satisfiedDownstreams, std::set< std::pair< Face *, EndpointId >> &unsatisfiedDownstreams)
Definition: strategy.cpp:171
void setTag(shared_ptr< T > tag) const
set a tag item
Definition: tag-host.hpp:79
PartialName getPrefix(ssize_t nComponents) const
Returns a prefix of the name.
Definition: name.hpp:209
virtual void afterNewNextHop(const fib::NextHop &nextHop, const shared_ptr< pit::Entry > &pitEntry)
Trigger after a new nexthop is added.
Definition: strategy.cpp:230
const Name & getPrefix() const
Definition: fib-entry.hpp:60
signal::Signal< FaceTable, Face > & beforeRemoveFace
Definition: strategy.hpp:434
static ParsedInstanceName parseInstanceName(const Name &input)
Parse a strategy instance name.
Definition: strategy.cpp:123
shared_ptr< T > getTag() const
get a tag item
Definition: tag-host.hpp:66
void removeTag() const
remove tag item
Definition: tag-host.hpp:93
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
static std::set< Name > listRegistered()
Definition: strategy.cpp:114
span< const Name > getForwardingHint() const noexcept
Definition: interest.hpp:222
void sendNacks(const lp::NackHeader &header, const shared_ptr< pit::Entry > &pitEntry, std::initializer_list< const Face *> exceptFaces={})
Send Nack to every face that has an in-record, except those in exceptFaces.
Definition: strategy.cpp:309
Represents a face-endpoint pair in the forwarder.
represents a FIB entry
Definition: fib-entry.hpp:53
static time_point now() noexcept
Definition: time.cpp:80
Contains information about an Interest from an incoming face.
Fib & getFib()
Definition: forwarder.hpp:88
Strategy(Forwarder &forwarder)
Construct a strategy instance.
Definition: strategy.cpp:143
const_reverse_iterator rend() const
Reverse end iterator.
Definition: name.hpp:245
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:53
Represents an Interest packet.
Definition: interest.hpp:48
const_reverse_iterator rbegin() const
Reverse begin iterator.
Definition: name.hpp:237
NFD_VIRTUAL_WITH_TESTS bool sendData(const Data &data, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send a Data packet.
Definition: strategy.cpp:248
const Entry & findLongestPrefixMatch(const Name &prefix) const
Performs a longest prefix match.
Definition: fib.cpp:62
NFD_VIRTUAL_WITH_TESTS pit::OutRecord * onOutgoingInterest(const Interest &interest, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
outgoing Interest pipeline
Definition: forwarder.cpp:260
virtual void afterContentStoreHit(const Data &data, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry)
trigger after a Data is matched in CS
Definition: strategy.cpp:196
bool isInProducerRegion(span< const Name > forwardingHint) const
determines whether an Interest has reached a producer region
represents a Network Nack
Definition: nack.hpp:38
virtual void afterReceiveLoopedInterest(const FaceEndpoint &ingress, const Interest &interest, pit::Entry &pitEntry)
trigger after a looped Interest is received
Definition: strategy.cpp:155
virtual ~Strategy()
const Component & at(ssize_t i) const
Returns an immutable reference to the component at the specified index, with bounds checking...
Definition: name.cpp:171
ndn Face
Definition: face-impl.hpp:42
NFD_VIRTUAL_WITH_TESTS bool onOutgoingData(const Data &data, Face &egress)
outgoing Data pipeline
Definition: forwarder.cpp:419
NFD_VIRTUAL_WITH_TESTS void sendDataToAll(const Data &data, const shared_ptr< pit::Entry > &pitEntry, const Face &inFace)
Send a Data packet to all matched and qualified faces.
Definition: strategy.cpp:279
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:39
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:368
An Interest table entry.
Definition: pit-entry.hpp:58
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
Represents the Forwarding Information Base (FIB)
Definition: fib.hpp:47
#define NFD_LOG_TRACE
Definition: logger.hpp:37
Name PartialName
Represents an arbitrary sequence of name components.
Definition: name.hpp:36
virtual void afterReceiveNack(const lp::Nack &nack, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry)
Trigger after a Nack is received.
Definition: strategy.cpp:217
const Name & getName() const noexcept
Get name.
Definition: data.hpp:127
Represents an absolute name.
Definition: name.hpp:41
NFD_VIRTUAL_WITH_TESTS bool sendNack(const lp::NackHeader &header, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send a Nack packet.
Definition: strategy.hpp:335
const Interest & getInterest() const
Definition: pit-entry.hpp:70
size_t size() const
Returns the number of components.
Definition: name.hpp:151
Represents a forwarding strategy.
Definition: strategy.hpp:38
static unique_ptr< Strategy > create(const Name &instanceName, Forwarder &forwarder)
Definition: strategy.cpp:92
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
Performs a FIB lookup, considering Link object if present.
Definition: strategy.cpp:331
signal::Signal< FaceTable, Face > & afterAddFace
Definition: strategy.hpp:433
const Name & getName() const noexcept
Definition: interest.hpp:172
const Name & getName() const
Definition: pit-entry.hpp:78
NetworkRegionTable & getNetworkRegionTable()
Definition: forwarder.hpp:124
Contains information about an Interest toward an outgoing face.
static Name makeInstanceName(const Name &input, const Name &strategyName)
Construct a strategy instance name.
Definition: strategy.cpp:134
bool isVersion() const
Check if the component is a version per NDN naming conventions.
static bool canCreate(const Name &instanceName)
Definition: strategy.cpp:86
NFD_VIRTUAL_WITH_TESTS pit::OutRecord * sendInterest(const Interest &interest, Face &egress, const shared_ptr< pit::Entry > &pitEntry)
Send an Interest packet.
Definition: strategy.cpp:237
Represents a Data packet.
Definition: data.hpp:37
represents a Network NACK header
Definition: nack-header.hpp:57
virtual void onDroppedInterest(const Interest &interest, Face &egress)
Trigger after an Interest is dropped (e.g., for exceeding allowed retransmissions).
Definition: strategy.cpp:224
PartialName getSubName(ssize_t iStartComponent, size_t nComponents=npos) const
Extracts some components as a sub-name (PartialName).
Definition: name.cpp:185
const nullopt_t nullopt((nullopt_t::init()))
virtual void beforeSatisfyInterest(const Data &data, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry)
trigger before PIT entry is satisfied
Definition: strategy.cpp:163
Face & getFace() const
Definition: fib-nexthop.hpp:47
static bool areSameType(const Name &instanceNameA, const Name &instanceNameB)
Definition: strategy.cpp:108
virtual void afterReceiveData(const Data &data, const FaceEndpoint &ingress, const shared_ptr< pit::Entry > &pitEntry)
trigger after Data is received
Definition: strategy.cpp:206
represent a PIT token field
Definition: pit-token.hpp:34
Represents a nexthop record in a FIB entry.
Definition: fib-nexthop.hpp:37