NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.3: 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-2017, 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 "core/logger.hpp"
29 #include "core/random.hpp"
30 #include <boost/range/adaptor/map.hpp>
31 #include <boost/range/algorithm/copy.hpp>
32 
33 namespace nfd {
34 namespace fw {
35 
36 NFD_LOG_INIT("Strategy");
37 
38 Strategy::Registry&
39 Strategy::getRegistry()
40 {
41  static Registry registry;
42  return registry;
43 }
44 
45 Strategy::Registry::const_iterator
46 Strategy::find(const Name& instanceName)
47 {
48  const Registry& registry = getRegistry();
49  ParsedInstanceName parsed = parseInstanceName(instanceName);
50 
51  if (parsed.version) {
52  // specified version: find exact or next higher version
53 
54  auto found = registry.lower_bound(parsed.strategyName);
55  if (found != registry.end()) {
56  if (parsed.strategyName.getPrefix(-1).isPrefixOf(found->first)) {
57  NFD_LOG_TRACE("find " << instanceName << " versioned found=" << found->first);
58  return found;
59  }
60  }
61 
62  NFD_LOG_TRACE("find " << instanceName << " versioned not-found");
63  return registry.end();
64  }
65 
66  // no version specified: find highest version
67 
68  if (!parsed.strategyName.empty()) { // Name().getSuccessor() would be invalid
69  auto found = registry.lower_bound(parsed.strategyName.getSuccessor());
70  if (found != registry.begin()) {
71  --found;
72  if (parsed.strategyName.isPrefixOf(found->first)) {
73  NFD_LOG_TRACE("find " << instanceName << " unversioned found=" << found->first);
74  return found;
75  }
76  }
77  }
78 
79  NFD_LOG_TRACE("find " << instanceName << " unversioned not-found");
80  return registry.end();
81 }
82 
83 bool
84 Strategy::canCreate(const Name& instanceName)
85 {
86  return Strategy::find(instanceName) != getRegistry().end();
87 }
88 
89 unique_ptr<Strategy>
90 Strategy::create(const Name& instanceName, Forwarder& forwarder)
91 {
92  auto found = Strategy::find(instanceName);
93  if (found == getRegistry().end()) {
94  NFD_LOG_DEBUG("create " << instanceName << " not-found");
95  return nullptr;
96  }
97 
98  unique_ptr<Strategy> instance = found->second(forwarder, instanceName);
99  NFD_LOG_DEBUG("create " << instanceName << " found=" << found->first <<
100  " created=" << instance->getInstanceName());
101  BOOST_ASSERT(!instance->getInstanceName().empty());
102  return instance;
103 }
104 
105 bool
106 Strategy::areSameType(const Name& instanceNameA, const Name& instanceNameB)
107 {
108  return Strategy::find(instanceNameA) == Strategy::find(instanceNameB);
109 }
110 
111 std::set<Name>
113 {
114  std::set<Name> strategyNames;
115  boost::copy(getRegistry() | boost::adaptors::map_keys,
116  std::inserter(strategyNames, strategyNames.end()));
117  return strategyNames;
118 }
119 
122 {
123  for (ssize_t i = input.size() - 1; i > 0; --i) {
124  if (input[i].isVersion()) {
125  return {input.getPrefix(i + 1), input[i].toVersion(), input.getSubName(i + 1)};
126  }
127  }
128  return {input, ndn::nullopt, PartialName()};
129 }
130 
131 Name
132 Strategy::makeInstanceName(const Name& input, const Name& strategyName)
133 {
134  BOOST_ASSERT(strategyName.at(-1).isVersion());
135 
136  bool hasVersion = std::any_of(input.rbegin(), input.rend(),
137  [] (const name::Component& comp) { return comp.isVersion(); });
138  return hasVersion ? input : Name(input).append(strategyName.at(-1));
139 }
140 
142  : afterAddFace(forwarder.getFaceTable().afterAdd)
143  , beforeRemoveFace(forwarder.getFaceTable().beforeRemove)
144  , m_forwarder(forwarder)
145  , m_measurements(m_forwarder.getMeasurements(), m_forwarder.getStrategyChoice(), *this)
146 {
147 }
148 
149 Strategy::~Strategy() = default;
150 
151 void
152 Strategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
153  const Face& inFace, const Data& data)
154 {
155  NFD_LOG_DEBUG("beforeSatisfyInterest pitEntry=" << pitEntry->getName() <<
156  " inFace=" << inFace.getId() << " data=" << data.getName());
157 }
158 
159 void
160 Strategy::beforeExpirePendingInterest(const shared_ptr<pit::Entry>& pitEntry)
161 {
162  NFD_LOG_DEBUG("beforeExpirePendingInterest pitEntry=" << pitEntry->getName());
163 }
164 
165 void
166 Strategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
167  const shared_ptr<pit::Entry>& pitEntry)
168 {
169  NFD_LOG_DEBUG("afterReceiveNack inFace=" << inFace.getId() <<
170  " pitEntry=" << pitEntry->getName());
171 }
172 
173 void
174 Strategy::sendNacks(const shared_ptr<pit::Entry>& pitEntry, const lp::NackHeader& header,
175  std::initializer_list<const Face*> exceptFaces)
176 {
177  // populate downstreams with all downstreams faces
178  std::unordered_set<const Face*> downstreams;
179  std::transform(pitEntry->in_begin(), pitEntry->in_end(), std::inserter(downstreams, downstreams.end()),
180  [] (const pit::InRecord& inR) { return &inR.getFace(); });
181 
182  // delete excluded faces
183  // .erase in a loop is more efficient than std::set_difference because that requires sorted range
184  for (const Face* exceptFace : exceptFaces) {
185  downstreams.erase(exceptFace);
186  }
187 
188  // send Nacks
189  for (const Face* downstream : downstreams) {
190  this->sendNack(pitEntry, *downstream, header);
191  }
192  // warning: don't loop on pitEntry->getInRecords(), because in-record is deleted when sending Nack
193 }
194 
195 const fib::Entry&
196 Strategy::lookupFib(const pit::Entry& pitEntry) const
197 {
198  const Fib& fib = m_forwarder.getFib();
199 
200  const Interest& interest = pitEntry.getInterest();
201  // has forwarding hint?
202  if (interest.getForwardingHint().empty()) {
203  // FIB lookup with Interest name
204  const fib::Entry& fibEntry = fib.findLongestPrefixMatch(pitEntry);
205  NFD_LOG_TRACE("lookupFib noForwardingHint found=" << fibEntry.getPrefix());
206  return fibEntry;
207  }
208 
209  const DelegationList& fh = interest.getForwardingHint();
210  // Forwarding hint should have been stripped by incoming Interest pipeline when reaching producer region
211  BOOST_ASSERT(!m_forwarder.getNetworkRegionTable().isInProducerRegion(fh));
212 
213  const fib::Entry* fibEntry = nullptr;
214  for (const Delegation& del : fh) {
215  fibEntry = &fib.findLongestPrefixMatch(del.name);
216  if (fibEntry->hasNextHops()) {
217  if (fibEntry->getPrefix().size() == 0) {
218  // in consumer region, return the default route
219  NFD_LOG_TRACE("lookupFib inConsumerRegion found=" << fibEntry->getPrefix());
220  }
221  else {
222  // in default-free zone, use the first delegation that finds a FIB entry
223  NFD_LOG_TRACE("lookupFib delegation=" << del.name << " found=" << fibEntry->getPrefix());
224  }
225  return *fibEntry;
226  }
227  BOOST_ASSERT(fibEntry->getPrefix().size() == 0); // only ndn:/ FIB entry can have zero nexthop
228  }
229  BOOST_ASSERT(fibEntry != nullptr && fibEntry->getPrefix().size() == 0);
230  return *fibEntry; // only occurs if no delegation finds a FIB nexthop
231 }
232 
233 } // namespace fw
234 } // namespace nfd
constexpr nullopt_t nullopt
Declares the global pseudorandom number generator (PRNG) for NFD.
signal::Signal< FaceTable, Face & > & afterAddFace
Definition: strategy.hpp:306
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:121
static std::set< Name > listRegistered()
Definition: strategy.cpp:112
represents a FIB entry
Definition: fib-entry.hpp:51
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const Face &outFace, const lp::NackHeader &header)
send Nack to outFace
Definition: strategy.hpp:217
void sendNacks(const shared_ptr< pit::Entry > &pitEntry, const lp::NackHeader &header, std::initializer_list< const Face * > exceptFaces=std::initializer_list< const Face * >())
send Nack to every face that has an in-record, except those in exceptFaces
Definition: strategy.cpp:174
contains information about an Interest from an incoming face
Fib & getFib()
Definition: forwarder.hpp:146
const FaceTable & getFaceTable() const
Definition: strategy.hpp:253
Strategy(Forwarder &forwarder)
construct a strategy instance
Definition: strategy.cpp:141
virtual void beforeExpirePendingInterest(const shared_ptr< pit::Entry > &pitEntry)
trigger before PIT entry expires
Definition: strategy.cpp:160
main class of NFD
Definition: forwarder.hpp:54
represents an Interest packet
Definition: interest.hpp:42
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:55
represents a delegation
Definition: delegation.hpp:32
Face & getFace() const
represents a Network Nack
Definition: nack.hpp:40
virtual void afterReceiveNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry)
trigger after Nack is received
Definition: strategy.cpp:166
virtual ~Strategy()
ndn Face
Definition: face-impl.hpp:41
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:54
bool isVersion() const
Check if the component is version per NDN naming conventions.
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
const_reverse_iterator rend() const
Reverse end iterator.
Definition: name.hpp:246
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:241
an Interest table entry
Definition: pit-entry.hpp:57
const Interest & getInterest() const
Definition: pit-entry.hpp:69
Name PartialName
Represents an arbitrary sequence of name components.
Definition: name.hpp:38
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:196
size_t size() const
Get number of components.
Definition: name.hpp:154
virtual void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data)
trigger before PIT entry is satisfied
Definition: strategy.cpp:152
Represents an absolute name.
Definition: name.hpp:42
signal::Signal< FaceTable, Face & > & beforeRemoveFace
Definition: strategy.hpp:307
const Component & at(ssize_t i) const
Get the component at the given index.
Definition: name.cpp:185
const_reverse_iterator rbegin() const
Reverse begin iterator.
Definition: name.hpp:238
const DelegationList & getForwardingHint() const
Definition: interest.hpp:196
const Name & getName() const
Get name.
Definition: data.hpp:121
static unique_ptr< Strategy > create(const Name &instanceName, Forwarder &forwarder)
Definition: strategy.cpp:90
Component holds a read-only name component value.
bool empty() const noexcept
NetworkRegionTable & getNetworkRegionTable()
Definition: forwarder.hpp:182
represents a list of Delegations
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:132
PartialName getSubName(ssize_t iStartComponent, size_t nComponents=npos) const
Extract some components as a sub-name (PartialName)
Definition: name.cpp:199
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix of the name.
Definition: name.hpp:210
static bool canCreate(const Name &instanceName)
Definition: strategy.cpp:84
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
Represents a Data packet.
Definition: data.hpp:35
represents a Network NACK header
Definition: nack-header.hpp:59
bool isInProducerRegion(const DelegationList &forwardingHint) const
determines whether an Interest has reached a producer region
const Name & getPrefix() const
Definition: fib-entry.hpp:58
static bool areSameType(const Name &instanceNameA, const Name &instanceNameB)
Definition: strategy.cpp:106