asf-probing-module.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2024, 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 "asf-probing-module.hpp"
27 #include "algorithm.hpp"
28 #include "common/global.hpp"
29 #include "face/face.hpp"
30 
31 #include <ndn-cxx/util/random.hpp>
32 
33 namespace nfd::fw::asf {
34 
36 
38  : m_probingInterval(DEFAULT_PROBING_INTERVAL)
39  , m_measurements(measurements)
40 {
41 }
42 
43 void
44 ProbingModule::scheduleProbe(const fib::Entry& fibEntry, time::milliseconds interval)
45 {
46  Name prefix = fibEntry.getPrefix();
47 
48  // Set the probing flag for the namespace to true after passed interval of time
49  getScheduler().schedule(interval, [this, prefix] {
50  NamespaceInfo* info = m_measurements.getNamespaceInfo(prefix);
51  if (info == nullptr) {
52  // FIB entry with the passed prefix has been removed or
53  // it has a name that is not controlled by the AsfStrategy
54  }
55  else {
56  info->setIsProbingDue(true);
57  }
58  });
59 }
60 
61 static auto
62 getFaceRankForProbing(const FaceStats& fs) noexcept
63 {
64  // The RTT is used to store the status of the face:
65  // - A positive value indicates data was received and is assumed to indicate a working face (group 1),
66  // - RTT_NO_MEASUREMENT indicates a face is unmeasured (group 2),
67  // - RTT_TIMEOUT indicates a face is timed out (group 3).
68  // These groups are defined in the technical report.
69  //
70  // Unlike during forwarding, we adjust the ranking such that unmeasured faces (group 2)
71  // are prioritized before working faces (group 1), and working faces are prioritized
72  // before timed out faces (group 3). We assign each group a priority value from 1-3
73  // to ensure lowest-to-highest ordering consistent with this logic.
74  // Additionally, unmeasured faces will always be chosen to probe if they exist.
75 
76  // Working faces are ranked second in priority; if RTT is not
77  // a special value, we assume the face to be in this group.
78  int priority = 2;
79  if (fs.rtt == FaceInfo::RTT_NO_MEASUREMENT) {
80  priority = 1;
81  }
82  else if (fs.rtt == FaceInfo::RTT_TIMEOUT) {
83  priority = 3;
84  }
85 
86  // We set SRTT by default to the max value; if a face is working, we instead set it to the actual value.
87  // Unmeasured and timed out faces are not sorted by SRTT.
88  auto srtt = priority == 2 ? fs.srtt : time::nanoseconds::max();
89 
90  // For ranking, group takes the priority over SRTT (if present) or cost, SRTT (if present)
91  // takes priority over cost, and cost takes priority over FaceId.
92  // FaceId is included to ensure all unique entries are included in the ranking (see #5310).
93  return std::tuple(priority, srtt, fs.cost, fs.face->getId());
94 }
95 
96 bool
98 {
100 }
101 
102 static Face*
104 {
105  static std::uniform_real_distribution<> randDist;
106  static auto& rng = ndn::random::getRandomNumberEngine();
107  const double randomNumber = randDist(rng);
108 
109  const auto nFaces = rankedFaces.size();
110  const double rankSum = (nFaces + 1) * nFaces / 2;
111  size_t rank = 1;
112  double offset = 0.0;
113 
114  for (const auto& faceStat : rankedFaces) {
115  // n + 1 - j
116  // p = ---------
117  // sum(ranks)
118  double probability = static_cast<double>(nFaces + 1 - rank) / rankSum;
119  rank++;
120 
121  // Is the random number within the bounds of this face's probability + the previous faces'
122  // probability?
123  //
124  // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
125  // randomNumber = 0.92
126  //
127  // The face with FaceId: 3 should be picked
128  // (0.68 < 0.5 + 0.33 + 0.17) == true
129  //
130  offset += probability;
131  if (randomNumber <= offset) {
132  // Found face to probe
133  return faceStat.face;
134  }
135  }
136 
137  // Given a set of Faces, this method should always select a Face to probe
138  NDN_CXX_UNREACHABLE;
139 }
140 
141 Face*
142 ProbingModule::getFaceToProbe(const Face& inFace, const Interest& interest,
143  const fib::Entry& fibEntry, const Face& faceUsed)
144 {
145  FaceStatsProbingSet rankedFaces;
146 
147  // Put eligible faces into rankedFaces. If one or more faces do not have an RTT measurement,
148  // the lowest ranked one will always be returned.
149  for (const auto& hop : fibEntry.getNextHops()) {
150  Face& hopFace = hop.getFace();
151 
152  // Don't send probe Interest back to the incoming face or use the same face
153  // as the forwarded Interest or use a face that violates scope
154  if (hopFace.getId() == inFace.getId() || hopFace.getId() == faceUsed.getId() ||
155  wouldViolateScope(inFace, interest, hopFace)) {
156  continue;
157  }
158 
159  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest.getName(), hopFace.getId());
160  if (info == nullptr || info->getLastRtt() == FaceInfo::RTT_NO_MEASUREMENT) {
161  rankedFaces.insert({&hopFace, FaceInfo::RTT_NO_MEASUREMENT,
162  FaceInfo::RTT_NO_MEASUREMENT, hop.getCost()});
163  }
164  else {
165  rankedFaces.insert({&hopFace, info->getLastRtt(), info->getSrtt(), hop.getCost()});
166  }
167  }
168 
169  if (rankedFaces.empty()) {
170  // No Face to probe
171  return nullptr;
172  }
173 
174  // If the top face is unmeasured, immediately return it.
175  if (rankedFaces.begin()->rtt == FaceInfo::RTT_NO_MEASUREMENT) {
176  return rankedFaces.begin()->face;
177  }
178 
179  return chooseFace(rankedFaces);
180 }
181 
182 bool
183 ProbingModule::isProbingNeeded(const fib::Entry& fibEntry, const Name& interestName)
184 {
185  // Return the probing status flag for a namespace
186  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName);
187 
188  // If a first probe has not been scheduled for a namespace
189  if (!info.isFirstProbeScheduled()) {
190  // Schedule first probe between 0 and 5 seconds
191  static std::uniform_int_distribution<> randDist(0, 5000);
192  static auto& rng = ndn::random::getRandomNumberEngine();
193  auto interval = randDist(rng);
194  scheduleProbe(fibEntry, time::milliseconds(interval));
195  info.setIsFirstProbeScheduled(true);
196  }
197 
198  return info.isProbingDue();
199 }
200 
201 void
202 ProbingModule::afterForwardingProbe(const fib::Entry& fibEntry, const Name& interestName)
203 {
204  // After probing is done, need to set probing flag to false and
205  // schedule another future probe
206  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName);
207  info.setIsProbingDue(false);
208 
209  scheduleProbe(fibEntry, m_probingInterval);
210 }
211 
212 void
213 ProbingModule::setProbingInterval(time::milliseconds probingInterval)
214 {
215  if (probingInterval >= MIN_PROBING_INTERVAL) {
216  m_probingInterval = probingInterval;
217  }
218  else {
219  NDN_THROW(std::invalid_argument("Probing interval must be >= " +
220  std::to_string(MIN_PROBING_INTERVAL.count()) + " milliseconds"));
221  }
222 }
223 
224 } // namespace nfd::fw::asf
This file contains common algorithms used by forwarding strategies.
Generalization of a network interface.
Definition: face.hpp:118
FaceId getId() const noexcept
Returns the face ID.
Definition: face.hpp:195
Represents an entry in the FIB.
Definition: fib-entry.hpp:91
const NextHopList & getNextHops() const noexcept
Definition: fib-entry.hpp:103
const Name & getPrefix() const noexcept
Definition: fib-entry.hpp:97
Helper class to retrieve and create strategy measurements.
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Name &prefix)
static constexpr time::microseconds MEASUREMENTS_LIFETIME
FaceInfo * getFaceInfo(const fib::Entry &fibEntry, const Name &interestName, FaceId faceId)
NamespaceInfo * getNamespaceInfo(const Name &prefix)
Strategy information for each face in a namespace.
static constexpr time::nanoseconds RTT_TIMEOUT
static constexpr time::nanoseconds RTT_NO_MEASUREMENT
time::nanoseconds getSrtt() const
time::nanoseconds getLastRtt() const
Stores strategy information about each face in this namespace.
void setIsFirstProbeScheduled(bool isScheduled)
void setIsProbingDue(bool isProbingDue)
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
bool isProbingNeeded(const fib::Entry &fibEntry, const Name &interestName)
static constexpr time::milliseconds MIN_PROBING_INTERVAL
std::set< FaceStats, FaceStatsProbingCompare > FaceStatsProbingSet
void afterForwardingProbe(const fib::Entry &fibEntry, const Name &interestName)
void setProbingInterval(time::milliseconds probingInterval)
void scheduleProbe(const fib::Entry &fibEntry, time::milliseconds interval)
ProbingModule(AsfMeasurements &measurements)
static constexpr time::milliseconds DEFAULT_PROBING_INTERVAL
static auto getFaceRankForProbing(const FaceStats &fs) noexcept
static Face * chooseFace(const ProbingModule::FaceStatsProbingSet &rankedFaces)
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:33
ndn::Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:45
Container for ranking-related values.
bool operator()(const FaceStats &lhs, const FaceStats &rhs) const noexcept