Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
Ashlesh Gawande | 92e4ea5 | 2017-07-19 11:38:12 -0500 | [diff] [blame] | 2 | /* |
Davide Pesavento | 2c9d2ca | 2024-01-27 16:36:51 -0500 | [diff] [blame] | 3 | * Copyright (c) 2014-2024, Regents of the University of California, |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 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" |
Ashlesh Gawande | 2a73f35 | 2016-12-01 15:37:03 +0000 | [diff] [blame] | 27 | #include "algorithm.hpp" |
Davide Pesavento | 2cae8ca | 2019-04-18 20:48:05 -0400 | [diff] [blame] | 28 | #include "common/global.hpp" |
Davide Pesavento | 972de80 | 2024-02-16 18:42:55 -0500 | [diff] [blame] | 29 | #include "face/face.hpp" |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 30 | |
Davide Pesavento | b8bd5ee | 2019-02-03 22:53:40 -0500 | [diff] [blame] | 31 | #include <ndn-cxx/util/random.hpp> |
| 32 | |
Davide Pesavento | e422f9e | 2022-06-03 01:30:23 -0400 | [diff] [blame] | 33 | namespace nfd::fw::asf { |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 34 | |
Davide Pesavento | a3a7a4e | 2022-05-29 16:06:22 -0400 | [diff] [blame] | 35 | static_assert(ProbingModule::DEFAULT_PROBING_INTERVAL < AsfMeasurements::MEASUREMENTS_LIFETIME); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 36 | |
| 37 | ProbingModule::ProbingModule(AsfMeasurements& measurements) |
| 38 | : m_probingInterval(DEFAULT_PROBING_INTERVAL) |
| 39 | , m_measurements(measurements) |
| 40 | { |
| 41 | } |
| 42 | |
| 43 | void |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 44 | ProbingModule::scheduleProbe(const fib::Entry& fibEntry, time::milliseconds interval) |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 45 | { |
Junxiao Shi | fc02186 | 2016-08-25 21:51:18 +0000 | [diff] [blame] | 46 | Name prefix = fibEntry.getPrefix(); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 47 | |
| 48 | // Set the probing flag for the namespace to true after passed interval of time |
Davide Pesavento | 3dade00 | 2019-03-19 11:29:56 -0600 | [diff] [blame] | 49 | getScheduler().schedule(interval, [this, prefix] { |
Junxiao Shi | fc02186 | 2016-08-25 21:51:18 +0000 | [diff] [blame] | 50 | NamespaceInfo* info = m_measurements.getNamespaceInfo(prefix); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 51 | if (info == nullptr) { |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 52 | // FIB entry with the passed prefix has been removed or |
| 53 | // it has a name that is not controlled by the AsfStrategy |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 54 | } |
| 55 | else { |
| 56 | info->setIsProbingDue(true); |
| 57 | } |
| 58 | }); |
| 59 | } |
| 60 | |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 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 |
| 97 | ProbingModule::FaceStatsProbingCompare::operator()(const FaceStats& lhs, const FaceStats& rhs) const noexcept |
| 98 | { |
| 99 | return getFaceRankForProbing(lhs) < getFaceRankForProbing(rhs); |
| 100 | } |
| 101 | |
| 102 | static Face* |
| 103 | chooseFace(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 Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 141 | Face* |
Davide Pesavento | 3dade00 | 2019-03-19 11:29:56 -0600 | [diff] [blame] | 142 | ProbingModule::getFaceToProbe(const Face& inFace, const Interest& interest, |
| 143 | const fib::Entry& fibEntry, const Face& faceUsed) |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 144 | { |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 145 | FaceStatsProbingSet rankedFaces; |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 146 | |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 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. |
Davide Pesavento | 3dade00 | 2019-03-19 11:29:56 -0600 | [diff] [blame] | 149 | for (const auto& hop : fibEntry.getNextHops()) { |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 150 | Face& hopFace = hop.getFace(); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 151 | |
| 152 | // Don't send probe Interest back to the incoming face or use the same face |
Ashlesh Gawande | 2a73f35 | 2016-12-01 15:37:03 +0000 | [diff] [blame] | 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)) { |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 156 | continue; |
| 157 | } |
| 158 | |
Saurab Dulal | 432be57 | 2021-01-26 12:09:29 -0600 | [diff] [blame] | 159 | FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest.getName(), hopFace.getId()); |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 160 | if (info == nullptr || info->getLastRtt() == FaceInfo::RTT_NO_MEASUREMENT) { |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 161 | rankedFaces.insert({&hopFace, FaceInfo::RTT_NO_MEASUREMENT, |
| 162 | FaceInfo::RTT_NO_MEASUREMENT, hop.getCost()}); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 163 | } |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 164 | else { |
| 165 | rankedFaces.insert({&hopFace, info->getLastRtt(), info->getSrtt(), hop.getCost()}); |
| 166 | } |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 167 | } |
| 168 | |
| 169 | if (rankedFaces.empty()) { |
| 170 | // No Face to probe |
| 171 | return nullptr; |
| 172 | } |
| 173 | |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 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 | |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 179 | return chooseFace(rankedFaces); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 180 | } |
| 181 | |
| 182 | bool |
Saurab Dulal | 432be57 | 2021-01-26 12:09:29 -0600 | [diff] [blame] | 183 | ProbingModule::isProbingNeeded(const fib::Entry& fibEntry, const Name& interestName) |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 184 | { |
| 185 | // Return the probing status flag for a namespace |
Saurab Dulal | 432be57 | 2021-01-26 12:09:29 -0600 | [diff] [blame] | 186 | NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 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 |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 191 | static std::uniform_int_distribution<> randDist(0, 5000); |
awlane | 5fdcbec | 2023-12-15 14:56:05 -0600 | [diff] [blame] | 192 | static auto& rng = ndn::random::getRandomNumberEngine(); |
| 193 | auto interval = randDist(rng); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 194 | scheduleProbe(fibEntry, time::milliseconds(interval)); |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 195 | info.setIsFirstProbeScheduled(true); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 196 | } |
| 197 | |
| 198 | return info.isProbingDue(); |
| 199 | } |
| 200 | |
| 201 | void |
Saurab Dulal | 432be57 | 2021-01-26 12:09:29 -0600 | [diff] [blame] | 202 | ProbingModule::afterForwardingProbe(const fib::Entry& fibEntry, const Name& interestName) |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 203 | { |
| 204 | // After probing is done, need to set probing flag to false and |
| 205 | // schedule another future probe |
Saurab Dulal | 432be57 | 2021-01-26 12:09:29 -0600 | [diff] [blame] | 206 | NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interestName); |
Vince Lehman | 8a4c29e | 2016-07-11 08:49:35 +0000 | [diff] [blame] | 207 | info.setIsProbingDue(false); |
| 208 | |
| 209 | scheduleProbe(fibEntry, m_probingInterval); |
| 210 | } |
| 211 | |
Ashlesh Gawande | 92e4ea5 | 2017-07-19 11:38:12 -0500 | [diff] [blame] | 212 | void |
Ashlesh Gawande | 1ef93d0 | 2022-04-08 00:25:06 -0400 | [diff] [blame] | 213 | ProbingModule::setProbingInterval(time::milliseconds probingInterval) |
Ashlesh Gawande | 92e4ea5 | 2017-07-19 11:38:12 -0500 | [diff] [blame] | 214 | { |
Ashlesh Gawande | 1ef93d0 | 2022-04-08 00:25:06 -0400 | [diff] [blame] | 215 | if (probingInterval >= MIN_PROBING_INTERVAL) { |
| 216 | m_probingInterval = probingInterval; |
Ashlesh Gawande | 92e4ea5 | 2017-07-19 11:38:12 -0500 | [diff] [blame] | 217 | } |
| 218 | else { |
Davide Pesavento | a6f637a | 2019-08-28 23:23:20 -0400 | [diff] [blame] | 219 | NDN_THROW(std::invalid_argument("Probing interval must be >= " + |
Davide Pesavento | 2c9d2ca | 2024-01-27 16:36:51 -0500 | [diff] [blame] | 220 | std::to_string(MIN_PROBING_INTERVAL.count()) + " milliseconds")); |
Ashlesh Gawande | 92e4ea5 | 2017-07-19 11:38:12 -0500 | [diff] [blame] | 221 | } |
| 222 | } |
| 223 | |
Davide Pesavento | e422f9e | 2022-06-03 01:30:23 -0400 | [diff] [blame] | 224 | } // namespace nfd::fw::asf |