best-route-strategy2.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 "best-route-strategy2.hpp"
27 #include "algorithm.hpp"
28 #include "core/logger.hpp"
29 
30 namespace nfd {
31 namespace fw {
32 
33 NFD_LOG_INIT("BestRouteStrategy2");
34 NFD_REGISTER_STRATEGY(BestRouteStrategy2);
35 
36 const time::milliseconds BestRouteStrategy2::RETX_SUPPRESSION_INITIAL(10);
37 const time::milliseconds BestRouteStrategy2::RETX_SUPPRESSION_MAX(250);
38 
40  : Strategy(forwarder)
41  , ProcessNackTraits(this)
42  , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
43  RetxSuppressionExponential::DEFAULT_MULTIPLIER,
44  RETX_SUPPRESSION_MAX)
45 {
47  if (!parsed.parameters.empty()) {
48  BOOST_THROW_EXCEPTION(std::invalid_argument("BestRouteStrategy2 does not accept parameters"));
49  }
50  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
51  BOOST_THROW_EXCEPTION(std::invalid_argument(
52  "BestRouteStrategy2 does not support version " + std::to_string(*parsed.version)));
53  }
55 }
56 
57 const Name&
59 {
60  static Name strategyName("/localhost/nfd/strategy/best-route/%FD%05");
61  return strategyName;
62 }
63 
72 static inline bool
73 isNextHopEligible(const Face& inFace, const Interest& interest,
74  const fib::NextHop& nexthop,
75  const shared_ptr<pit::Entry>& pitEntry,
76  bool wantUnused = false,
77  time::steady_clock::TimePoint now = time::steady_clock::TimePoint::min())
78 {
79  const Face& outFace = nexthop.getFace();
80 
81  // do not forward back to the same face, unless it is ad hoc
82  if (outFace.getId() == inFace.getId() && outFace.getLinkType() != ndn::nfd::LINK_TYPE_AD_HOC)
83  return false;
84 
85  // forwarding would violate scope
86  if (wouldViolateScope(inFace, interest, outFace))
87  return false;
88 
89  if (wantUnused) {
90  // nexthop must not have unexpired out-record
91  pit::OutRecordCollection::iterator outRecord = pitEntry->getOutRecord(outFace);
92  if (outRecord != pitEntry->out_end() && outRecord->getExpiry() > now) {
93  return false;
94  }
95  }
96 
97  return true;
98 }
99 
103 static inline fib::NextHopList::const_iterator
104 findEligibleNextHopWithEarliestOutRecord(const Face& inFace, const Interest& interest,
105  const fib::NextHopList& nexthops,
106  const shared_ptr<pit::Entry>& pitEntry)
107 {
108  fib::NextHopList::const_iterator found = nexthops.end();
109  time::steady_clock::TimePoint earliestRenewed = time::steady_clock::TimePoint::max();
110  for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
111  if (!isNextHopEligible(inFace, interest, *it, pitEntry))
112  continue;
113  pit::OutRecordCollection::iterator outRecord = pitEntry->getOutRecord(it->getFace());
114  BOOST_ASSERT(outRecord != pitEntry->out_end());
115  if (outRecord->getLastRenewed() < earliestRenewed) {
116  found = it;
117  earliestRenewed = outRecord->getLastRenewed();
118  }
119  }
120  return found;
121 }
122 
123 void
124 BestRouteStrategy2::afterReceiveInterest(const Face& inFace, const Interest& interest,
125  const shared_ptr<pit::Entry>& pitEntry)
126 {
127  RetxSuppressionResult suppression = m_retxSuppression.decidePerPitEntry(*pitEntry);
128  if (suppression == RetxSuppressionResult::SUPPRESS) {
129  NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
130  << " suppressed");
131  return;
132  }
133 
134  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
135  const fib::NextHopList& nexthops = fibEntry.getNextHops();
136  fib::NextHopList::const_iterator it = nexthops.end();
137 
138  if (suppression == RetxSuppressionResult::NEW) {
139  // forward to nexthop with lowest cost except downstream
140  it = std::find_if(nexthops.begin(), nexthops.end(),
141  bind(&isNextHopEligible, cref(inFace), interest, _1, pitEntry,
142  false, time::steady_clock::TimePoint::min()));
143 
144  if (it == nexthops.end()) {
145  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
146 
147  lp::NackHeader nackHeader;
148  nackHeader.setReason(lp::NackReason::NO_ROUTE);
149  this->sendNack(pitEntry, inFace, nackHeader);
150 
151  this->rejectPendingInterest(pitEntry);
152  return;
153  }
154 
155  Face& outFace = it->getFace();
156  this->sendInterest(pitEntry, outFace, interest);
157  NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
158  << " newPitEntry-to=" << outFace.getId());
159  return;
160  }
161 
162  // find an unused upstream with lowest cost except downstream
163  it = std::find_if(nexthops.begin(), nexthops.end(),
164  bind(&isNextHopEligible, cref(inFace), interest, _1, pitEntry,
165  true, time::steady_clock::now()));
166  if (it != nexthops.end()) {
167  Face& outFace = it->getFace();
168  this->sendInterest(pitEntry, outFace, interest);
169  NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
170  << " retransmit-unused-to=" << outFace.getId());
171  return;
172  }
173 
174  // find an eligible upstream that is used earliest
175  it = findEligibleNextHopWithEarliestOutRecord(inFace, interest, nexthops, pitEntry);
176  if (it == nexthops.end()) {
177  NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " retransmitNoNextHop");
178  }
179  else {
180  Face& outFace = it->getFace();
181  this->sendInterest(pitEntry, outFace, interest);
182  NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
183  << " retransmit-retry-to=" << outFace.getId());
184  }
185 }
186 
187 void
188 BestRouteStrategy2::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
189  const shared_ptr<pit::Entry>& pitEntry)
190 {
191  this->processNack(inFace, nack, pitEntry);
192 }
193 
194 } // namespace fw
195 } // namespace nfd
main class of NFD
Definition: forwarder.hpp:52
void setInstanceName(const Name &name)
set strategy instance name
Definition: strategy.hpp:290
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:161
represents a FIB entry
Definition: fib-entry.hpp:51
static const Name & getStrategyName()
void sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &outFace, const Interest &interest)
send Interest to outFace
Definition: strategy.hpp:191
void sendNack(const shared_ptr< pit::Entry > &pitEntry, const Face &outFace, const lp::NackHeader &header)
send Nack to outFace
Definition: strategy.hpp:217
static bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused=false, time::steady_clock::TimePoint now=time::steady_clock::TimePoint::min())
determines whether a NextHop is eligible
BestRouteStrategy2(Forwarder &forwarder, const Name &name=getStrategyName())
Interest is retransmission and should be suppressed.
static Name makeInstanceName(const Name &input, const Name &strategyName)
construct a strategy instance name
Definition: strategy.cpp:132
#define NFD_REGISTER_STRATEGY(S)
registers a strategy
Definition: strategy.hpp:328
Table::const_iterator iterator
Definition: cs-internal.hpp:41
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Interest is new (not a retransmission)
Face & getFace() const
Definition: fib-nexthop.hpp:45
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
std::vector< fib::NextHop > NextHopList
Definition: fib-entry.hpp:47
void afterReceiveNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Nack is received
PartialName parameters
parameter components
Definition: strategy.hpp:263
void afterReceiveInterest(const Face &inFace, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
trigger after Interest is received
ndn::optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:262
RetxSuppressionResult decidePerPitEntry(pit::Entry &pitEntry)
determines whether Interest is a retransmission per pit entry and if so, whether it shall be forwarde...
represents a forwarding strategy
Definition: strategy.hpp:37
This file contains common algorithms used by forwarding strategies.
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
static fib::NextHopList::const_iterator findEligibleNextHopWithEarliestOutRecord(const Face &inFace, const Interest &interest, const fib::NextHopList &nexthops, const shared_ptr< pit::Entry > &pitEntry)
pick an eligible NextHop with earliest out-record
static ParsedInstanceName parseInstanceName(const Name &input)
parse a strategy instance name
Definition: strategy.cpp:121
void processNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry)
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38
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:37
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
decide that a pending Interest cannot be forwarded
Definition: strategy.hpp:204
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
performs a FIB lookup, considering Link object if present
Definition: strategy.cpp:196