NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.3: NDN, CCN, CCNx, content centric networks
API Documentation
asf-strategy.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "asf-strategy.hpp"
27 
28 #include "core/logger.hpp"
29 
30 namespace nfd {
31 namespace fw {
32 namespace asf {
33 
34 NFD_LOG_INIT("AsfStrategy");
35 
36 const Name AsfStrategy::STRATEGY_NAME("ndn:/localhost/nfd/strategy/asf/%FD%01");
37 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_INITIAL(10);
38 const time::milliseconds AsfStrategy::RETX_SUPPRESSION_MAX(250);
39 
41 
43  : Strategy(forwarder, name)
44  , m_measurements(getMeasurements())
45  , m_probing(m_measurements)
46  , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
47  RetxSuppressionExponential::DEFAULT_MULTIPLIER,
48  RETX_SUPPRESSION_MAX)
49 {
50 }
51 
52 void
53 AsfStrategy::afterReceiveInterest(const Face& inFace, const Interest& interest,
54  const shared_ptr<pit::Entry>& pitEntry)
55 {
56  // Should the Interest be suppressed?
57  RetxSuppression::Result suppressResult = m_retxSuppression.decide(inFace, interest, *pitEntry);
58 
59  switch (suppressResult) {
62  break;
64  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " suppressed");
65  return;
66  }
67 
68  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
69  const fib::NextHopList& nexthops = fibEntry.getNextHops();
70 
71  if (nexthops.size() == 0) {
72  sendNoRouteNack(inFace, interest, pitEntry);
73  this->rejectPendingInterest(pitEntry);
74  return;
75  }
76 
77  Face* faceToUse = getBestFaceForForwarding(fibEntry, interest, inFace);
78 
79  if (faceToUse == nullptr) {
80  sendNoRouteNack(inFace, interest, pitEntry);
81  this->rejectPendingInterest(pitEntry);
82  return;
83  }
84 
85  forwardInterest(interest, fibEntry, pitEntry, *faceToUse);
86 
87  // If necessary, send probe
88  if (m_probing.isProbingNeeded(fibEntry, interest)) {
89  Face* faceToProbe = m_probing.getFaceToProbe(inFace, interest, fibEntry, *faceToUse);
90 
91  if (faceToProbe != nullptr) {
92  NFD_LOG_TRACE("Sending probe for " << fibEntry.getPrefix()
93  << " to FaceId: " << faceToProbe->getId());
94 
95  bool wantNewNonce = true;
96  forwardInterest(interest, fibEntry, pitEntry, *faceToProbe, wantNewNonce);
97  m_probing.afterForwardingProbe(fibEntry, interest);
98  }
99  }
100 }
101 
102 void
103 AsfStrategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
104  const Face& inFace, const Data& data)
105 {
106  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(pitEntry->getName());
107 
108  if (namespaceInfo == nullptr) {
109  NFD_LOG_TRACE("Could not find measurements entry for " << pitEntry->getName());
110  return;
111  }
112 
113  // Record the RTT between the Interest out to Data in
114  FaceInfo& faceInfo = namespaceInfo->get(inFace.getId());
115  faceInfo.recordRtt(pitEntry, inFace);
116 
117  // Extend lifetime for measurements associated with Face
118  namespaceInfo->extendFaceInfoLifetime(faceInfo, inFace);
119 
120  if (faceInfo.isTimeoutScheduled()) {
121  faceInfo.cancelTimeoutEvent(data.getName());
122  }
123 }
124 
125 void
126 AsfStrategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
127  const shared_ptr<pit::Entry>& pitEntry)
128 {
129  NFD_LOG_DEBUG("Nack for " << nack.getInterest() << " from=" << inFace.getId() << ": " << nack.getReason());
130  onTimeout(pitEntry->getName(), inFace.getId());
131 }
132 
135 
136 void
137 AsfStrategy::forwardInterest(const Interest& interest,
138  const fib::Entry& fibEntry,
139  const shared_ptr<pit::Entry>& pitEntry,
140  Face& outFace,
141  bool wantNewNonce)
142 {
143  this->sendInterest(pitEntry, outFace, wantNewNonce);
144 
145  FaceInfo& faceInfo = m_measurements.getOrCreateFaceInfo(fibEntry, interest, outFace);
146 
147  // Refresh measurements since Face is being used for forwarding
148  NamespaceInfo& namespaceInfo = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
149  namespaceInfo.extendFaceInfoLifetime(faceInfo, outFace);
150 
151  if (!faceInfo.isTimeoutScheduled()) {
152  // Estimate and schedule timeout
153  RttEstimator::Duration timeout = faceInfo.computeRto();
154 
155  NFD_LOG_TRACE("Scheduling timeout for " << fibEntry.getPrefix()
156  << " FaceId: " << outFace.getId()
157  << " in " << time::duration_cast<time::milliseconds>(timeout) << " ms");
158 
160  bind(&AsfStrategy::onTimeout, this, interest.getName(), outFace.getId()));
161 
162  faceInfo.setTimeoutEvent(id, interest.getName());
163  }
164 }
165 
166 struct FaceStats
167 {
171  uint64_t cost;
172 };
173 
174 double
176 {
177  // These values allow faces with no measurements to be ranked better than timeouts
178  // srtt < RTT_NO_MEASUREMENT < RTT_TIMEOUT
179  static const RttStats::Rtt SORTING_RTT_TIMEOUT = time::microseconds::max();
180  static const RttStats::Rtt SORTING_RTT_NO_MEASUREMENT = SORTING_RTT_TIMEOUT / 2;
181 
182  if (stats.rtt == RttStats::RTT_TIMEOUT) {
183  return SORTING_RTT_TIMEOUT.count();
184  }
185  else if (stats.rtt == RttStats::RTT_NO_MEASUREMENT) {
186  return SORTING_RTT_NO_MEASUREMENT.count();
187  }
188  else {
189  return stats.srtt.count();
190  }
191 }
192 
193 Face*
194 AsfStrategy::getBestFaceForForwarding(const fib::Entry& fibEntry, const Interest& interest,
195  const Face& inFace)
196 {
197  NFD_LOG_TRACE("Looking for best face for " << fibEntry.getPrefix());
198 
199  typedef std::function<bool(const FaceStats&, const FaceStats&)> FaceStatsPredicate;
200  typedef std::set<FaceStats, FaceStatsPredicate> FaceStatsSet;
201 
202  FaceStatsSet rankedFaces(
203  [] (const FaceStats& lhs, const FaceStats& rhs) -> bool {
204  // Sort by RTT and then by cost
205  double lhsValue = getValueForSorting(lhs);
206  double rhsValue = getValueForSorting(rhs);
207 
208  if (lhsValue < rhsValue) {
209  return true;
210  }
211  else if (lhsValue == rhsValue) {
212  return lhs.cost < rhs.cost;
213  }
214  else {
215  return false;
216  }
217  });
218 
219  for (const fib::NextHop& hop : fibEntry.getNextHops()) {
220  Face& hopFace = hop.getFace();
221 
222  if (hopFace.getId() == inFace.getId()) {
223  continue;
224  }
225 
226  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, hopFace);
227 
228  if (info == nullptr) {
229  FaceStats stats = {&hopFace,
232  hop.getCost()};
233 
234  rankedFaces.insert(stats);
235  }
236  else {
237  FaceStats stats = {&hopFace, info->getRtt(), info->getSrtt(), hop.getCost()};
238  rankedFaces.insert(stats);
239  }
240  }
241 
242  FaceStatsSet::iterator it = rankedFaces.begin();
243 
244  if (it != rankedFaces.end()) {
245  return it->face;
246  }
247  else {
248  return nullptr;
249  }
250 }
251 
252 void
253 AsfStrategy::onTimeout(const Name& interestName, face::FaceId faceId)
254 {
255  NFD_LOG_TRACE("FaceId: " << faceId << " for " << interestName << " has timed-out");
256 
257  NamespaceInfo* namespaceInfo = m_measurements.getNamespaceInfo(interestName);
258 
259  if (namespaceInfo == nullptr) {
260  NFD_LOG_TRACE("FibEntry for " << interestName << " has been removed since timeout scheduling");
261  return;
262  }
263 
264  FaceInfoTable::iterator it = namespaceInfo->find(faceId);
265 
266  if (it == namespaceInfo->end()) {
267  it = namespaceInfo->insert(faceId);
268  }
269 
270  FaceInfo& faceInfo = it->second;
271  faceInfo.recordTimeout(interestName);
272 }
273 
274 void
275 AsfStrategy::sendNoRouteNack(const Face& inFace, const Interest& interest,
276  const shared_ptr<pit::Entry>& pitEntry)
277 {
278  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
279 
280  lp::NackHeader nackHeader;
281  nackHeader.setReason(lp::NackReason::NO_ROUTE);
282  this->sendNack(pitEntry, inFace, nackHeader);
283 }
284 
285 } // namespace asf
286 } // namespace fw
287 } // namespace nfd
virtual void beforeSatisfyInterest(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace, const Data &data) override
trigger before PIT entry is satisfied
time::microseconds Duration
const Name & getPrefix() const
Definition: fib-entry.hpp:58
AsfStrategy(Forwarder &forwarder, const Name &name=STRATEGY_NAME)
FaceInfo & getOrCreateFaceInfo(const fib::Entry &fibEntry, const Interest &interest, const Face &face)
void recordRtt(const shared_ptr< pit::Entry > &pitEntry, const Face &inFace)
NackHeader & setReason(NackReason reason)
set reason code
generalization of a network interface
Definition: face.hpp:67
void extendFaceInfoLifetime(FaceInfo &info, const Face &face)
represents a FIB entry
Definition: fib-entry.hpp:51
RttEstimator::Duration computeRto() const
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const Face &outFace, const lp::NackHeader &header)
send Nack to outFace
Definition: strategy.hpp:175
const Name & getName() const
Get name of the Data packet.
Definition: data.hpp:318
NFD_REGISTER_STRATEGY(AsfStrategy)
Interest is retransmission and should be suppressed.
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
stores stategy information about each face in this namespace
static const Rtt RTT_TIMEOUT
void cancelTimeoutEvent(const Name &prefix)
FaceInfoTable::iterator end()
Interest is new (not a retransmission)
represents a Network Nack
Definition: nack.hpp:40
NackReason getReason() const
Definition: nack.hpp:92
Table::const_iterator iterator
Definition: cs-internal.hpp:41
std::shared_ptr< ns3::EventId > EventId
Definition: scheduler.hpp:39
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:54
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
FaceId getId() const
Definition: face.hpp:229
FaceInfoTable::iterator find(nfd::face::FaceId faceId)
FaceInfo & get(nfd::face::FaceId faceId)
std::vector< fib::NextHop > NextHopList
Definition: fib-entry.hpp:47
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
static const Rtt RTT_NO_MEASUREMENT
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
decide that a pending Interest cannot be forwarded
Definition: strategy.hpp:162
static const Name STRATEGY_NAME
virtual Result decide(const Face &inFace, const Interest &interest, pit::Entry &pitEntry) const override
determines whether Interest is a retransmission, and if so, whether it shall be forwarded or suppress...
RttStats::Rtt getRtt() const
Name abstraction to represent an absolute name.
Definition: name.hpp:46
void setTimeoutEvent(const scheduler::EventId &id, const Name &interestName)
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
Strategy information for each face in a namespace.
represents a forwarding strategy
Definition: strategy.hpp:38
const FaceInfoTable::iterator insert(nfd::face::FaceId faceId)
virtual void afterReceiveNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
virtual void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
NamespaceInfo * getNamespaceInfo(const Name &prefix)
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:129
EventId schedule(const time::nanoseconds &after, const Scheduler::Event &event)
schedule an event
Definition: scheduler.cpp:47
Interest is retransmission and should be forwarded.
RttStats::Rtt getSrtt() const
void recordTimeout(const Name &interestName)
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
double getValueForSorting(const FaceStats &stats)
uint64_t FaceId
identifies a face
Definition: face.hpp:39
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
represents a Data packet
Definition: data.hpp:37
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
represents a Network NACK header
Definition: nack-header.hpp:52
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:137
Adaptive SRTT-based Forwarding Strategy.
const Interest & getInterest() const
Definition: nack.hpp:53
time::duration< double, boost::micro > Rtt
const Name & getName() const
Definition: interest.hpp:215
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38