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-2020, 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 "common/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  NDN_THROW(std::invalid_argument("BestRouteStrategy2 does not accept parameters"));
49  }
50  if (parsed.version && *parsed.version != getStrategyName()[-1].toVersion()) {
51  NDN_THROW(std::invalid_argument(
52  "BestRouteStrategy2 does not support version " + 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 
64 void
65 BestRouteStrategy2::afterReceiveInterest(const FaceEndpoint& ingress, const Interest& interest,
66  const shared_ptr<pit::Entry>& pitEntry)
67 {
68  RetxSuppressionResult suppression = m_retxSuppression.decidePerPitEntry(*pitEntry);
69  if (suppression == RetxSuppressionResult::SUPPRESS) {
70  NFD_LOG_DEBUG(interest << " from=" << ingress << " suppressed");
71  return;
72  }
73 
74  const fib::Entry& fibEntry = this->lookupFib(*pitEntry);
75  const fib::NextHopList& nexthops = fibEntry.getNextHops();
76  auto it = nexthops.end();
77 
78  if (suppression == RetxSuppressionResult::NEW) {
79  // forward to nexthop with lowest cost except downstream
80  it = std::find_if(nexthops.begin(), nexthops.end(), [&] (const auto& nexthop) {
81  return isNextHopEligible(ingress.face, interest, nexthop, pitEntry);
82  });
83 
84  if (it == nexthops.end()) {
85  NFD_LOG_DEBUG(interest << " from=" << ingress << " noNextHop");
86 
87  lp::NackHeader nackHeader;
88  nackHeader.setReason(lp::NackReason::NO_ROUTE);
89  this->sendNack(pitEntry, ingress.face, nackHeader);
90 
91  this->rejectPendingInterest(pitEntry);
92  return;
93  }
94 
95  Face& outFace = it->getFace();
96  NFD_LOG_DEBUG(interest << " from=" << ingress << " newPitEntry-to=" << outFace.getId());
97  this->sendInterest(pitEntry, outFace, interest);
98  return;
99  }
100 
101  // find an unused upstream with lowest cost except downstream
102  it = std::find_if(nexthops.begin(), nexthops.end(),
103  [&, now = time::steady_clock::now()] (const auto& nexthop) {
104  return isNextHopEligible(ingress.face, interest, nexthop, pitEntry, true, now);
105  });
106 
107  if (it != nexthops.end()) {
108  Face& outFace = it->getFace();
109  this->sendInterest(pitEntry, outFace, interest);
110  NFD_LOG_DEBUG(interest << " from=" << ingress << " retransmit-unused-to=" << outFace.getId());
111  return;
112  }
113 
114  // find an eligible upstream that is used earliest
115  it = findEligibleNextHopWithEarliestOutRecord(ingress.face, interest, nexthops, pitEntry);
116  if (it == nexthops.end()) {
117  NFD_LOG_DEBUG(interest << " from=" << ingress << " retransmitNoNextHop");
118  }
119  else {
120  Face& outFace = it->getFace();
121  this->sendInterest(pitEntry, outFace, interest);
122  NFD_LOG_DEBUG(interest << " from=" << ingress << " retransmit-retry-to=" << outFace.getId());
123  }
124 }
125 
126 void
127 BestRouteStrategy2::afterReceiveNack(const FaceEndpoint& ingress, const lp::Nack& nack,
128  const shared_ptr<pit::Entry>& pitEntry)
129 {
130  this->processNack(ingress.face, nack, pitEntry);
131 }
132 
133 } // namespace fw
134 } // namespace nfd
Main class of NFD&#39;s forwarding engine.
Definition: forwarder.hpp:51
void setInstanceName(const Name &name)
Set strategy instance name.
Definition: strategy.hpp:386
bool sendNack(const shared_ptr< pit::Entry > &pitEntry, Face &egress, const lp::NackHeader &header)
Send a Nack packet.
Definition: strategy.hpp:306
represents a FIB entry
Definition: fib-entry.hpp:53
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
Definition: algorithm.cpp:132
static const Name & getStrategyName()
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:134
void afterReceiveInterest(const FaceEndpoint &ingress, const Interest &interest, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after Interest is received.
const fib::Entry & lookupFib(const pit::Entry &pitEntry) const
Performs a FIB lookup, considering Link object if present.
Definition: strategy.cpp:282
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
Interest is new (not a retransmission)
void afterReceiveNack(const FaceEndpoint &ingress, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry) override
Trigger after Nack is received.
bool isNextHopEligible(const Face &inFace, const Interest &interest, const fib::NextHop &nexthop, const shared_ptr< pit::Entry > &pitEntry, bool wantUnused, time::steady_clock::TimePoint now)
determines whether a NextHop is eligible i.e.
Definition: algorithm.cpp:154
a retransmission suppression decision algorithm that suppresses retransmissions using exponential bac...
generalization of a network interface
Definition: face.hpp:54
Represents a collection of nexthops.
Definition: fib-entry.hpp:39
PartialName parameters
parameter components
Definition: strategy.hpp:359
FaceId getId() const
Definition: face.hpp:239
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.
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
static ParsedInstanceName parseInstanceName(const Name &input)
Parse a strategy instance name.
Definition: strategy.cpp:123
void processNack(const Face &inFace, const lp::Nack &nack, const shared_ptr< pit::Entry > &pitEntry)
NFD_REGISTER_STRATEGY(SelfLearningStrategy)
void rejectPendingInterest(const shared_ptr< pit::Entry > &pitEntry)
Schedule the PIT entry for immediate deletion.
Definition: strategy.hpp:291
pit::OutRecord * sendInterest(const shared_ptr< pit::Entry > &pitEntry, Face &egress, const Interest &interest)
Send an Interest packet.
Definition: strategy.cpp:197
optional< uint64_t > version
whether strategyName contains a version component
Definition: strategy.hpp:358