NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
self-learning-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 
27 #include "algorithm.hpp"
28 
29 #include "common/global.hpp"
30 #include "common/logger.hpp"
31 #include "rib/service.hpp"
32 
35 #include <ndn-cxx/lp/tags.hpp>
36 
37 #include <boost/range/adaptor/reversed.hpp>
38 
39 namespace nfd {
40 namespace fw {
41 
44 
45 const time::milliseconds SelfLearningStrategy::ROUTE_RENEW_LIFETIME(10_min);
46 
48  : Strategy(forwarder)
49 {
51  if (!parsed.parameters.empty()) {
52  NDN_THROW(std::invalid_argument("SelfLearningStrategy does not accept parameters"));
53  }
54  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
55  NDN_THROW(std::invalid_argument(
56  "SelfLearningStrategy does not support version " + to_string(*parsed.version)));
57  }
59 }
60 
61 const Name&
63 {
64  static Name strategyName("/localhost/nfd/strategy/self-learning/%FD%01");
65  return strategyName;
66 }
67 
68 void
70  const shared_ptr<pit::Entry>& pitEntry)
71 {
72  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
73  const fib::NextHopList& nexthops = fibEntry.getNextHops();
74 
75  bool isNonDiscovery = interest.getTag<lp::NonDiscoveryTag>() != nullptr;
76  auto inRecordInfo = pitEntry->getInRecord(ingress.face)->insertStrategyInfo<InRecordInfo>().first;
77  if (isNonDiscovery) { // "non-discovery" Interest
78  inRecordInfo->isNonDiscoveryInterest = true;
79  if (nexthops.empty()) { // return NACK if no matching FIB entry exists
80  NFD_LOG_DEBUG("NACK non-discovery Interest=" << interest << " from=" << ingress << " noNextHop");
81  lp::NackHeader nackHeader;
82  nackHeader.setReason(lp::NackReason::NO_ROUTE);
83  this->sendNack(pitEntry, ingress, nackHeader);
84  this->rejectPendingInterest(pitEntry);
85  }
86  else { // multicast it if matching FIB entry exists
87  multicastInterest(interest, ingress.face, pitEntry, nexthops);
88  }
89  }
90  else { // "discovery" Interest
91  inRecordInfo->isNonDiscoveryInterest = false;
92  if (nexthops.empty()) { // broadcast it if no matching FIB entry exists
93  broadcastInterest(interest, ingress.face, pitEntry);
94  }
95  else { // multicast it with "non-discovery" mark if matching FIB entry exists
96  interest.setTag(make_shared<lp::NonDiscoveryTag>(lp::EmptyValue{}));
97  multicastInterest(interest, ingress.face, pitEntry, nexthops);
98  }
99  }
100 }
101 
102 void
103 SelfLearningStrategy::afterReceiveData(const shared_ptr<pit::Entry>& pitEntry,
104  const FaceEndpoint& ingress, const Data& data)
105 {
106  auto outRecord = pitEntry->getOutRecord(ingress.face);
107  if (outRecord == pitEntry->out_end()) {
108  NFD_LOG_DEBUG("Data " << data.getName() << " from=" << ingress << " no out-record");
109  return;
110  }
111 
112  OutRecordInfo* outRecordInfo = outRecord->getStrategyInfo<OutRecordInfo>();
113  if (outRecordInfo && outRecordInfo->isNonDiscoveryInterest) { // outgoing Interest was non-discovery
114  if (!needPrefixAnn(pitEntry)) { // no need to attach a PA (common cases)
115  sendDataToAll(pitEntry, ingress, data);
116  }
117  else { // needs a PA (to respond discovery Interest)
118  asyncProcessData(pitEntry, ingress.face, data);
119  }
120  }
121  else { // outgoing Interest was discovery
122  auto paTag = data.getTag<lp::PrefixAnnouncementTag>();
123  if (paTag != nullptr) {
124  addRoute(pitEntry, ingress.face, data, *paTag->get().getPrefixAnn());
125  }
126  else { // Data contains no PrefixAnnouncement, upstreams do not support self-learning
127  }
128  sendDataToAll(pitEntry, ingress, data);
129  }
130 }
131 
132 void
134  const shared_ptr<pit::Entry>& pitEntry)
135 {
136  NFD_LOG_DEBUG("Nack for " << nack.getInterest() << " from=" << ingress
137  << " reason=" << nack.getReason());
138  if (nack.getReason() == lp::NackReason::NO_ROUTE) { // remove FIB entries
139  BOOST_ASSERT(this->lookupFib(*pitEntry).hasNextHops());
140  NFD_LOG_DEBUG("Send NACK to all downstreams");
141  this->sendNacks(pitEntry, nack.getHeader());
142  renewRoute(nack.getInterest().getName(), ingress.face.getId(), 0_ms);
143  }
144 }
145 
146 void
147 SelfLearningStrategy::broadcastInterest(const Interest& interest, const Face& inFace,
148  const shared_ptr<pit::Entry>& pitEntry)
149 {
150  for (auto& outFace : this->getFaceTable() | boost::adaptors::reversed) {
151  if ((outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
152  wouldViolateScope(inFace, interest, outFace) || outFace.getScope() == ndn::nfd::FACE_SCOPE_LOCAL) {
153  continue;
154  }
155  this->sendInterest(pitEntry, FaceEndpoint(outFace, 0), interest);
156  pitEntry->getOutRecord(outFace)->insertStrategyInfo<OutRecordInfo>().first->isNonDiscoveryInterest = false;
157  NFD_LOG_DEBUG("send discovery Interest=" << interest << " from="
158  << inFace.getId() << " to=" << outFace.getId());
159  }
160 }
161 
162 void
163 SelfLearningStrategy::multicastInterest(const Interest& interest, const Face& inFace,
164  const shared_ptr<pit::Entry>& pitEntry,
165  const fib::NextHopList& nexthops)
166 {
167  for (const auto& nexthop : nexthops) {
168  Face& outFace = nexthop.getFace();
169  if ((outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC) ||
170  wouldViolateScope(inFace, interest, outFace)) {
171  continue;
172  }
173  this->sendInterest(pitEntry, FaceEndpoint(outFace, 0), interest);
174  pitEntry->getOutRecord(outFace)->insertStrategyInfo<OutRecordInfo>().first->isNonDiscoveryInterest = true;
175  NFD_LOG_DEBUG("send non-discovery Interest=" << interest << " from="
176  << inFace.getId() << " to=" << outFace.getId());
177  }
178 }
179 
180 void
181 SelfLearningStrategy::asyncProcessData(const shared_ptr<pit::Entry>& pitEntry, const Face& inFace, const Data& data)
182 {
183  // Given that this processing is asynchronous, the PIT entry's expiry timer is extended first
184  // to ensure that the entry will not be removed before the whole processing is finished
185  // (the PIT entry's expiry timer was set to 0 before dispatching)
186  this->setExpiryTimer(pitEntry, 1_s);
187 
188  runOnRibIoService([pitEntryWeak = weak_ptr<pit::Entry>{pitEntry}, inFaceId = inFace.getId(), data, this] {
189  rib::Service::get().getRibManager().slFindAnn(data.getName(),
190  [pitEntryWeak, inFaceId, data, this] (optional<ndn::PrefixAnnouncement> paOpt) {
191  if (paOpt) {
192  runOnMainIoService([pitEntryWeak, inFaceId, data, pa = std::move(*paOpt), this] {
193  auto pitEntry = pitEntryWeak.lock();
194  auto inFace = this->getFace(inFaceId);
195  if (pitEntry && inFace) {
196  NFD_LOG_DEBUG("found PrefixAnnouncement=" << pa.getAnnouncedName());
197  data.setTag(make_shared<lp::PrefixAnnouncementTag>(lp::PrefixAnnouncementHeader(pa)));
198  this->sendDataToAll(pitEntry, FaceEndpoint(*inFace, 0), data);
199  this->setExpiryTimer(pitEntry, 0_ms);
200  }
201  else {
202  NFD_LOG_DEBUG("PIT entry or Face no longer exists");
203  }
204  });
205  }
206  });
207  });
208 }
209 
210 bool
211 SelfLearningStrategy::needPrefixAnn(const shared_ptr<pit::Entry>& pitEntry)
212 {
213  bool hasDiscoveryInterest = false;
214  bool directToConsumer = true;
215 
216  auto now = time::steady_clock::now();
217  for (const auto& inRecord : pitEntry->getInRecords()) {
218  if (inRecord.getExpiry() > now) {
219  InRecordInfo* inRecordInfo = inRecord.getStrategyInfo<InRecordInfo>();
220  if (inRecordInfo && !inRecordInfo->isNonDiscoveryInterest) {
221  hasDiscoveryInterest = true;
222  }
223  if (inRecord.getFace().getScope() != ndn::nfd::FACE_SCOPE_LOCAL) {
224  directToConsumer = false;
225  }
226  }
227  }
228  return hasDiscoveryInterest && !directToConsumer;
229 }
230 
231 void
232 SelfLearningStrategy::addRoute(const shared_ptr<pit::Entry>& pitEntry, const Face& inFace,
233  const Data& data, const ndn::PrefixAnnouncement& pa)
234 {
235  runOnRibIoService([pitEntryWeak = weak_ptr<pit::Entry>{pitEntry}, inFaceId = inFace.getId(), data, pa] {
236  rib::Service::get().getRibManager().slAnnounce(pa, inFaceId, ROUTE_RENEW_LIFETIME,
238  NFD_LOG_DEBUG("Add route via PrefixAnnouncement with result=" << res);
239  });
240  });
241 }
242 
243 void
244 SelfLearningStrategy::renewRoute(const Name& name, FaceId inFaceId, time::milliseconds maxLifetime)
245 {
246  // renew route with PA or ignore PA (if route has no PA)
247  runOnRibIoService([name, inFaceId, maxLifetime] {
248  rib::Service::get().getRibManager().slRenew(name, inFaceId, maxLifetime,
250  NFD_LOG_DEBUG("Renew route with result=" << res);
251  });
252  });
253 }
254 
255 } // namespace fw
256 } // namespace nfd
nfd::fw::Strategy::sendNacks
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:274
nfd::RibManager::slRenew
void slRenew(const Name &name, uint64_t faceId, time::milliseconds maxLifetime, const SlAnnounceCallback &cb)
Renew a route created by prefix announcement from self-learning strategy.
Definition: rib-manager.cpp:382
self-learning-strategy.hpp
global.hpp
nfd::FaceEndpoint::face
Face & face
Definition: face-endpoint.hpp:46
ndn::lp::NackHeader::setReason
NackHeader & setReason(NackReason reason)
set reason code
Definition: nack-header.cpp:135
ndn::lp::NackHeader
represents a Network NACK header
Definition: nack-header.hpp:58
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
nfd::RibManager::slAnnounce
void slAnnounce(const ndn::PrefixAnnouncement &pa, uint64_t faceId, time::milliseconds maxLifetime, const SlAnnounceCallback &cb)
Insert a route by prefix announcement from self-learning strategy.
Definition: rib-manager.cpp:357
ndn::SimpleTag
provides a tag type for simple types
Definition: tag.hpp:59
nfd::fw::SelfLearningStrategy::SelfLearningStrategy
SelfLearningStrategy(Forwarder &forwarder, const Name &name=getStrategyName())
Definition: self-learning-strategy.cpp:47
ndn::time::steady_clock::now
static time_point now() noexcept
Definition: time.cpp:80
ndn::nfd::LINK_TYPE_AD_HOC
@ LINK_TYPE_AD_HOC
link is ad hoc
Definition: nfd-constants.hpp:61
empty-value.hpp
nfd::fw::SelfLearningStrategy::OutRecordInfo::isNonDiscoveryInterest
bool isNonDiscoveryInterest
Definition: self-learning-strategy.hpp:79
ndn::TagHost::setTag
void setTag(shared_ptr< T > tag) const
set a tag item
Definition: tag-host.hpp:79
nfd::runOnRibIoService
void runOnRibIoService(const std::function< void()> &f)
Run a function on the RIB io_service instance.
Definition: global.cpp:86
nfd::fw::NFD_REGISTER_STRATEGY
NFD_REGISTER_STRATEGY(AccessStrategy)
ndn::TagHost::getTag
shared_ptr< T > getTag() const
get a tag item
Definition: tag-host.hpp:66
ndn::Data::getName
const Name & getName() const
Get name.
Definition: data.hpp:124
ndn::PrefixAnnouncement
A prefix announcement object that represents an application's intent of registering a prefix toward i...
Definition: prefix-announcement.hpp:34
nfd::rib::Service::getRibManager
RibManager & getRibManager()
Definition: service.hpp:71
nfd::fw::SelfLearningStrategy::afterReceiveNack
void afterReceiveNack(const FaceEndpoint &ingress, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
Definition: self-learning-strategy.cpp:133
ndn::Name
Represents an absolute name.
Definition: name.hpp:44
nfd::fw::SelfLearningStrategy::afterReceiveData
void afterReceiveData(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &ingress, const Data &data) override
trigger after Data is received
Definition: self-learning-strategy.cpp:103
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
ndn::lp::Nack::getReason
NackReason getReason() const
Definition: nack.hpp:90
nfd::face::FaceId
uint64_t FaceId
Identifies a face.
Definition: face-common.hpp:44
nfd::face::Face
generalization of a network interface
Definition: face.hpp:53
nfd::fw::Strategy::setInstanceName
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:395
NDN_THROW
#define NDN_THROW(e)
Definition: exception.hpp:61
nfd::RibManager::SlAnnounceResult
SlAnnounceResult
Definition: rib-manager.hpp:93
nfd::fw::Strategy::sendNack
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const FaceEndpoint &egress, const lp::NackHeader &header)
send Nack to egress
Definition: strategy.hpp:315
nfd::fib::Entry::getNextHops
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
nfd::FaceEndpoint
Represents a face-endpoint pair in the forwarder.
Definition: face-endpoint.hpp:37
nfd::fw::SelfLearningStrategy
Self-learning strategy.
Definition: self-learning-strategy.hpp:46
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::fw::Strategy::setExpiryTimer
void setExpiryTimer(const shared_ptr< pit::Entry > &pitEntry, time::milliseconds duration)
Schedule the PIT entry to be erased after duration.
Definition: strategy.hpp:334
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::fib::NextHopList
std::vector< NextHop > NextHopList
Definition: fib-entry.hpp:49
nfd::fib::Entry
represents a FIB entry
Definition: fib-entry.hpp:54
nfd::RibManager::slFindAnn
void slFindAnn(const Name &name, const SlFindAnnCallback &cb) const
Retrieve an outgoing prefix announcement for self-learning strategy.
Definition: rib-manager.cpp:407
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::Forwarder
Main class of NFD's forwarding engine.
Definition: forwarder.hpp:52
nfd::fw::SelfLearningStrategy::InRecordInfo
StrategyInfo on pit::InRecord.
Definition: self-learning-strategy.hpp:56
Face
ndn Face
Definition: face-impl.hpp:41
ndn::tlv::Data
@ Data
Definition: tlv.hpp:66
ndn::lp::Nack::getHeader
const NackHeader & getHeader() const
Definition: nack.hpp:63
nfd::fw::Strategy::getFaceTable
const FaceTable & getFaceTable() const
Definition: strategy.hpp:358
nfd::fw::Strategy::sendDataToAll
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:251
ndn::nfd::FACE_SCOPE_LOCAL
@ FACE_SCOPE_LOCAL
face is local
Definition: nfd-constants.hpp:37
ndn::lp::Nack
represents a Network Nack
Definition: nack.hpp:39
ndn::to_string
std::string to_string(const T &val)
Definition: backports.hpp:102
algorithm.hpp
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::fw::SelfLearningStrategy::OutRecordInfo
StrategyInfo on pit::OutRecord.
Definition: self-learning-strategy.hpp:70
ndn::Interest::getName
const Name & getName() const noexcept
Definition: interest.hpp:121
prefix-announcement-header.hpp
tags.hpp
nfd::fw::Strategy::ParsedInstanceName::version
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:367
nfd::fw::Strategy::ParsedInstanceName::parameters
PartialName parameters
parameter components
Definition: strategy.hpp:368
service.hpp
ndn::lp::EmptyValue
represents a zero-length TLV-VALUE
Definition: empty-value.hpp:34
ndn::lp::Nack::getInterest
const Interest & getInterest() const
Definition: nack.hpp:51
nfd::fw::Strategy::ParsedInstanceName
Definition: strategy.hpp:365
nfd::fw::SelfLearningStrategy::getStrategyName
static const Name & getStrategyName()
Definition: self-learning-strategy.cpp:62
NFD_LOG_INIT
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
nfd::rib::Service::get
static Service & get()
Get a reference to the only instance of this class.
Definition: service.cpp:90
logger.hpp
nfd::fw::SelfLearningStrategy::afterReceiveInterest
void afterReceiveInterest(const FaceEndpoint &ingress, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
Definition: self-learning-strategy.cpp:69
nfd::fib::Entry::hasNextHops
bool hasNextHops() const
Definition: fib-entry.hpp:74