blob: a465a5b4ae63aefd5d78154a5b4693a8f1789e11 [file] [log] [blame]
Vince Lehman8a4c29e2016-07-11 08:49:35 +00001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Ashlesh Gawande92e4ea52017-07-19 11:38:12 -05002/*
Davide Pesavento2c9d2ca2024-01-27 16:36:51 -05003 * Copyright (c) 2014-2024, Regents of the University of California,
Vince Lehman8a4c29e2016-07-11 08:49:35 +00004 * 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"
Ashlesh Gawande2a73f352016-12-01 15:37:03 +000027#include "algorithm.hpp"
Davide Pesavento2cae8ca2019-04-18 20:48:05 -040028#include "common/global.hpp"
Davide Pesavento972de802024-02-16 18:42:55 -050029#include "face/face.hpp"
Vince Lehman8a4c29e2016-07-11 08:49:35 +000030
Davide Pesaventob8bd5ee2019-02-03 22:53:40 -050031#include <ndn-cxx/util/random.hpp>
32
Davide Pesaventoe422f9e2022-06-03 01:30:23 -040033namespace nfd::fw::asf {
Vince Lehman8a4c29e2016-07-11 08:49:35 +000034
Davide Pesaventoa3a7a4e2022-05-29 16:06:22 -040035static_assert(ProbingModule::DEFAULT_PROBING_INTERVAL < AsfMeasurements::MEASUREMENTS_LIFETIME);
Vince Lehman8a4c29e2016-07-11 08:49:35 +000036
37ProbingModule::ProbingModule(AsfMeasurements& measurements)
38 : m_probingInterval(DEFAULT_PROBING_INTERVAL)
39 , m_measurements(measurements)
40{
41}
42
43void
Davide Pesaventoa6f637a2019-08-28 23:23:20 -040044ProbingModule::scheduleProbe(const fib::Entry& fibEntry, time::milliseconds interval)
Vince Lehman8a4c29e2016-07-11 08:49:35 +000045{
Junxiao Shifc021862016-08-25 21:51:18 +000046 Name prefix = fibEntry.getPrefix();
Vince Lehman8a4c29e2016-07-11 08:49:35 +000047
48 // Set the probing flag for the namespace to true after passed interval of time
Davide Pesavento3dade002019-03-19 11:29:56 -060049 getScheduler().schedule(interval, [this, prefix] {
Junxiao Shifc021862016-08-25 21:51:18 +000050 NamespaceInfo* info = m_measurements.getNamespaceInfo(prefix);
Vince Lehman8a4c29e2016-07-11 08:49:35 +000051 if (info == nullptr) {
Davide Pesaventoa6f637a2019-08-28 23:23:20 -040052 // FIB entry with the passed prefix has been removed or
53 // it has a name that is not controlled by the AsfStrategy
Vince Lehman8a4c29e2016-07-11 08:49:35 +000054 }
55 else {
56 info->setIsProbingDue(true);
57 }
58 });
59}
60
awlane5fdcbec2023-12-15 14:56:05 -060061static auto
62getFaceRankForProbing(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
96bool
97ProbingModule::FaceStatsProbingCompare::operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept
98{
99 return getFaceRankForProbing(lhs) < getFaceRankForProbing(rhs);
100}
101
102static Face*
103chooseFace(const ProbingModule::FaceStatsProbingSet& rankedFaces)
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
Junxiao Shia6de4292016-07-12 02:08:10 +0000141Face*
Davide Pesavento3dade002019-03-19 11:29:56 -0600142ProbingModule::getFaceToProbe(const Face& inFace, const Interest& interest,
143 const fib::Entry& fibEntry, const Face& faceUsed)
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000144{
awlane5fdcbec2023-12-15 14:56:05 -0600145 FaceStatsProbingSet rankedFaces;
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000146
awlane5fdcbec2023-12-15 14:56:05 -0600147 // 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.
Davide Pesavento3dade002019-03-19 11:29:56 -0600149 for (const auto& hop : fibEntry.getNextHops()) {
Junxiao Shia6de4292016-07-12 02:08:10 +0000150 Face& hopFace = hop.getFace();
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000151
152 // Don't send probe Interest back to the incoming face or use the same face
Ashlesh Gawande2a73f352016-12-01 15:37:03 +0000153 // 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)) {
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000156 continue;
157 }
158
Saurab Dulal432be572021-01-26 12:09:29 -0600159 FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest.getName(), hopFace.getId());
Davide Pesaventoa6f637a2019-08-28 23:23:20 -0400160 if (info == nullptr || info->getLastRtt() == FaceInfo::RTT_NO_MEASUREMENT) {
awlane5fdcbec2023-12-15 14:56:05 -0600161 rankedFaces.insert({&hopFace, FaceInfo::RTT_NO_MEASUREMENT,
162 FaceInfo::RTT_NO_MEASUREMENT, hop.getCost()});
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000163 }
awlane5fdcbec2023-12-15 14:56:05 -0600164 else {
165 rankedFaces.insert({&hopFace, info->getLastRtt(), info->getSrtt(), hop.getCost()});
166 }
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000167 }
168
169 if (rankedFaces.empty()) {
170 // No Face to probe
171 return nullptr;
172 }
173
awlane5fdcbec2023-12-15 14:56:05 -0600174 // 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
Davide Pesaventoa6f637a2019-08-28 23:23:20 -0400179 return chooseFace(rankedFaces);
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000180}
181
182bool
Saurab Dulal432be572021-01-26 12:09:29 -0600183ProbingModule::isProbingNeeded(const fib::Entry& fibEntry, const Name& interestName)
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000184{
185 // Return the probing status flag for a namespace
Saurab Dulal432be572021-01-26 12:09:29 -0600186 NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName);
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000187
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
Davide Pesaventoa6f637a2019-08-28 23:23:20 -0400191 static std::uniform_int_distribution<> randDist(0, 5000);
awlane5fdcbec2023-12-15 14:56:05 -0600192 static auto& rng = ndn::random::getRandomNumberEngine();
193 auto interval = randDist(rng);
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000194 scheduleProbe(fibEntry, time::milliseconds(interval));
Davide Pesaventoa6f637a2019-08-28 23:23:20 -0400195 info.setIsFirstProbeScheduled(true);
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000196 }
197
198 return info.isProbingDue();
199}
200
201void
Saurab Dulal432be572021-01-26 12:09:29 -0600202ProbingModule::afterForwardingProbe(const fib::Entry& fibEntry, const Name& interestName)
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000203{
204 // After probing is done, need to set probing flag to false and
205 // schedule another future probe
Saurab Dulal432be572021-01-26 12:09:29 -0600206 NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName);
Vince Lehman8a4c29e2016-07-11 08:49:35 +0000207 info.setIsProbingDue(false);
208
209 scheduleProbe(fibEntry, m_probingInterval);
210}
211
Ashlesh Gawande92e4ea52017-07-19 11:38:12 -0500212void
Ashlesh Gawande1ef93d02022-04-08 00:25:06 -0400213ProbingModule::setProbingInterval(time::milliseconds probingInterval)
Ashlesh Gawande92e4ea52017-07-19 11:38:12 -0500214{
Ashlesh Gawande1ef93d02022-04-08 00:25:06 -0400215 if (probingInterval >= MIN_PROBING_INTERVAL) {
216 m_probingInterval = probingInterval;
Ashlesh Gawande92e4ea52017-07-19 11:38:12 -0500217 }
218 else {
Davide Pesaventoa6f637a2019-08-28 23:23:20 -0400219 NDN_THROW(std::invalid_argument("Probing interval must be >= " +
Davide Pesavento2c9d2ca2024-01-27 16:36:51 -0500220 std::to_string(MIN_PROBING_INTERVAL.count()) + " milliseconds"));
Ashlesh Gawande92e4ea52017-07-19 11:38:12 -0500221 }
222}
223
Davide Pesaventoe422f9e2022-06-03 01:30:23 -0400224} // namespace nfd::fw::asf