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 "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 
38 NFD_LOG_INIT(Strategy);
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 
123 Strategy::parseInstanceName(const Name& input)
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 name::Component& 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 void
154 Strategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
155  const FaceEndpoint& ingress, const Data& data)
156 {
157  NFD_LOG_DEBUG("beforeSatisfyInterest pitEntry=" << pitEntry->getName()
158  << " in=" << ingress << " data=" << data.getName());
159 }
160 
161 void
162 Strategy::afterContentStoreHit(const shared_ptr<pit::Entry>& pitEntry,
163  const FaceEndpoint& ingress, const Data& data)
164 {
165  NFD_LOG_DEBUG("afterContentStoreHit pitEntry=" << pitEntry->getName()
166  << " in=" << ingress << " data=" << data.getName());
167 
168  this->sendData(pitEntry, data, ingress);
169 }
170 
171 void
172 Strategy::afterReceiveData(const shared_ptr<pit::Entry>& pitEntry,
173  const FaceEndpoint& ingress, const Data& data)
174 {
175  NFD_LOG_DEBUG("afterReceiveData pitEntry=" << pitEntry->getName()
176  << " in=" << ingress << " data=" << data.getName());
177 
178  this->beforeSatisfyInterest(pitEntry, ingress, data);
179 
180  this->sendDataToAll(pitEntry, ingress, data);
181 }
182 
183 void
184 Strategy::afterReceiveNack(const FaceEndpoint& ingress, const lp::Nack& nack,
185  const shared_ptr<pit::Entry>& pitEntry)
186 {
187  NFD_LOG_DEBUG("afterReceiveNack in=" << ingress << " pitEntry=" << pitEntry->getName());
188 }
189 
190 void
191 Strategy::onDroppedInterest(const FaceEndpoint& egress, const Interest& interest)
192 {
193  NFD_LOG_DEBUG("onDroppedInterest out=" << egress << " name=" << interest.getName());
194 }
195 
196 void
197 Strategy::sendInterest(const shared_ptr<pit::Entry>& pitEntry,
198  const FaceEndpoint& egress, const Interest& interest)
199 {
200  if (interest.getTag<lp::PitToken>() != nullptr) {
201  Interest interest2 = interest; // make a copy to preserve tag on original packet
202  interest2.removeTag<lp::PitToken>();
203  m_forwarder.onOutgoingInterest(pitEntry, egress, interest2);
204  return;
205  }
206  m_forwarder.onOutgoingInterest(pitEntry, egress, interest);
207 }
208 
209 void
210 Strategy::afterNewNextHop(const fib::NextHop& nextHop, const shared_ptr<pit::Entry>& pitEntry)
211 {
212  NFD_LOG_DEBUG("afterNewNextHop pitEntry=" << pitEntry->getName()
213  << " nexthop=" << nextHop.getFace().getId());
214 }
215 
216 void
217 Strategy::sendData(const shared_ptr<pit::Entry>& pitEntry, const Data& data,
218  const FaceEndpoint& egress)
219 {
220  BOOST_ASSERT(pitEntry->getInterest().matchesData(data));
221 
222  shared_ptr<lp::PitToken> pitToken;
223  auto inRecord = pitEntry->getInRecord(egress.face);
224  if (inRecord != pitEntry->in_end()) {
225  pitToken = inRecord->getInterest().getTag<lp::PitToken>();
226  }
227 
228  // delete the PIT entry's in-record based on egress,
229  // since Data is sent to face and endpoint from which the Interest was received
230  pitEntry->deleteInRecord(egress.face);
231 
232  if (pitToken != nullptr) {
233  Data data2 = data; // make a copy so each downstream can get a different PIT token
234  data2.setTag(pitToken);
235  m_forwarder.onOutgoingData(data2, egress);
236  return;
237  }
238  m_forwarder.onOutgoingData(data, egress);
239 }
240 
241 void
242 Strategy::sendDataToAll(const shared_ptr<pit::Entry>& pitEntry,
243  const FaceEndpoint& ingress, const Data& data)
244 {
245  std::set<Face*> pendingDownstreams;
246  auto now = time::steady_clock::now();
247 
248  // remember pending downstreams
249  for (const pit::InRecord& inRecord : pitEntry->getInRecords()) {
250  if (inRecord.getExpiry() > now) {
251  if (inRecord.getFace().getId() == ingress.face.getId() &&
252  inRecord.getFace().getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) {
253  continue;
254  }
255  pendingDownstreams.emplace(&inRecord.getFace());
256  }
257  }
258 
259  for (const auto& pendingDownstream : pendingDownstreams) {
260  this->sendData(pitEntry, data, FaceEndpoint(*pendingDownstream, 0));
261  }
262 }
263 
264 void
265 Strategy::sendNacks(const shared_ptr<pit::Entry>& pitEntry, const lp::NackHeader& header,
266  std::initializer_list<FaceEndpoint> exceptFaceEndpoints)
267 {
268  // populate downstreams with all downstreams faces
269  std::set<Face*> downstreams;
270  std::transform(pitEntry->in_begin(), pitEntry->in_end(), std::inserter(downstreams, downstreams.end()),
271  [] (const pit::InRecord& inR) {
272  return &inR.getFace();
273  });
274 
275  // delete excluded faces
276  for (const auto& exceptFaceEndpoint : exceptFaceEndpoints) {
277  downstreams.erase(&exceptFaceEndpoint.face);
278  }
279 
280  // send Nacks
281  for (const auto& downstream : downstreams) {
282  this->sendNack(pitEntry, FaceEndpoint(*downstream, 0), header);
283  }
284  // warning: don't loop on pitEntry->getInRecords(), because in-record is deleted when sending Nack
285 }
286 
287 const fib::Entry&
288 Strategy::lookupFib(const pit::Entry& pitEntry) const
289 {
290  const Fib& fib = m_forwarder.getFib();
291 
292  const Interest& interest = pitEntry.getInterest();
293  // has forwarding hint?
294  if (interest.getForwardingHint().empty()) {
295  // FIB lookup with Interest name
296  const fib::Entry& fibEntry = fib.findLongestPrefixMatch(pitEntry);
297  NFD_LOG_TRACE("lookupFib noForwardingHint found=" << fibEntry.getPrefix());
298  return fibEntry;
299  }
300 
301  const DelegationList& fh = interest.getForwardingHint();
302  // Forwarding hint should have been stripped by incoming Interest pipeline when reaching producer region
303  BOOST_ASSERT(!m_forwarder.getNetworkRegionTable().isInProducerRegion(fh));
304 
305  const fib::Entry* fibEntry = nullptr;
306  for (const Delegation& del : fh) {
307  fibEntry = &fib.findLongestPrefixMatch(del.name);
308  if (fibEntry->hasNextHops()) {
309  if (fibEntry->getPrefix().size() == 0) {
310  // in consumer region, return the default route
311  NFD_LOG_TRACE("lookupFib inConsumerRegion found=" << fibEntry->getPrefix());
312  }
313  else {
314  // in default-free zone, use the first delegation that finds a FIB entry
315  NFD_LOG_TRACE("lookupFib delegation=" << del.name << " found=" << fibEntry->getPrefix());
316  }
317  return *fibEntry;
318  }
319  BOOST_ASSERT(fibEntry->getPrefix().size() == 0); // only ndn:/ FIB entry can have zero nexthop
320  }
321  BOOST_ASSERT(fibEntry != nullptr && fibEntry->getPrefix().size() == 0);
322  return *fibEntry; // only occurs if no delegation finds a FIB nexthop
323 }
324 
325 } // namespace fw
326 } // namespace nfd
virtual void afterNewNextHop(const fib::NextHop &nextHop, const shared_ptr< pit::Entry > &pitEntry)
trigger after new nexthop is added
Definition: strategy.cpp:210
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:51
Strategy(Forwarder &forwarder)
Construct a strategy instance.
Definition: strategy.cpp:143
Fib & getFib()
Definition: forwarder.hpp:127
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const lp::NackHeader &header)
send Nack to egress
Definition: strategy.hpp:302
represents a FIB entry
Definition: fib-entry.hpp:53
signal::Signal< FaceTable, Face > & beforeRemoveFace
Definition: strategy.hpp:408
void sendDataToAll(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data)
send data to all matched and qualified face-endpoint pairs
Definition: strategy.cpp:242
#define NFD_LOG_TRACE
Definition: logger.hpp:37
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:134
static bool canCreate(const Name &instanceName)
Definition: strategy.cpp:86
MeasurementsAccessor & getMeasurements()
Definition: strategy.hpp:333
virtual void afterReceiveNack(const FaceEndpoint &ingress, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry)
trigger after Nack is received
Definition: strategy.cpp:184
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const Interest &interest)
send Interest to egress
Definition: strategy.cpp:197
static bool areSameType(const Name &instanceNameA, const Name &instanceNameB)
Definition: strategy.cpp:108
An Interest table entry.
Definition: pit-entry.hpp:58
const Name & getPrefix() const
Definition: fib-entry.hpp:60
Represents a face-endpoint pair in the forwarder.
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Contains information about an Interest from an incoming face.
Face & getFace() const
Definition: fib-nexthop.hpp:47
Face & getFace() const
const Interest & getInterest() const
Definition: pit-entry.hpp:70
static unique_ptr< Strategy > create(const Name &instanceName, Forwarder &forwarder)
Definition: strategy.cpp:92
virtual void afterContentStoreHit(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data)
trigger after a Data is matched in CS
Definition: strategy.cpp:162
void sendData(const shared_ptr< pit::Entry > &pitEntry, const Data &data, const FaceEndpoint &egress)
send data to egress
Definition: strategy.cpp:217
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
virtual void afterReceiveData(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data)
trigger after Data is received
Definition: strategy.cpp:172
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:123
static std::set< Name > listRegistered()
Definition: strategy.cpp:114
bool isInProducerRegion(const DelegationList &forwardingHint) const
determines whether an Interest has reached a producer region
signal::Signal< FaceTable, Face > & afterAddFace
Definition: strategy.hpp:407
Represents a nexthop record in a FIB entry.
Definition: fib-nexthop.hpp:37
void sendNacks(const shared_ptr< pit::Entry > &pitEntry, const lp::NackHeader &header, std::initializer_list< FaceEndpoint > exceptFaceEndpoints={})
send Nack to every face-endpoint pair that has an in-record, except those in exceptFaceEndpoints ...
Definition: strategy.cpp:265
virtual ~Strategy()
virtual void onDroppedInterest(const FaceEndpoint &egress, const Interest &interest)
trigger after Interest dropped for exceeding allowed retransmissions
Definition: strategy.cpp:191
virtual void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data)
trigger before PIT entry is satisfied
Definition: strategy.cpp:154
NetworkRegionTable & getNetworkRegionTable()
Definition: forwarder.hpp:163
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:288