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-2019, 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 
30 #include <ndn-cxx/util/random.hpp>
31 
32 namespace nfd {
33 namespace fw {
34 namespace asf {
35 
36 constexpr time::milliseconds ProbingModule::DEFAULT_PROBING_INTERVAL;
37 constexpr time::milliseconds ProbingModule::MIN_PROBING_INTERVAL;
38 
39 static_assert(ProbingModule::DEFAULT_PROBING_INTERVAL < AsfMeasurements::MEASUREMENTS_LIFETIME,
40  "ProbingModule::DEFAULT_PROBING_INTERVAL must be less than AsfMeasurements::MEASUREMENTS_LIFETIME");
41 
43  : m_probingInterval(DEFAULT_PROBING_INTERVAL)
44  , m_measurements(measurements)
45 {
46 }
47 
48 void
49 ProbingModule::scheduleProbe(const fib::Entry& fibEntry, time::milliseconds interval)
50 {
51  Name prefix = fibEntry.getPrefix();
52 
53  // Set the probing flag for the namespace to true after passed interval of time
54  getScheduler().schedule(interval, [this, prefix] {
55  NamespaceInfo* info = m_measurements.getNamespaceInfo(prefix);
56  if (info == nullptr) {
57  // FIB entry with the passed prefix has been removed or
58  // it has a name that is not controlled by the AsfStrategy
59  }
60  else {
61  info->setIsProbingDue(true);
62  }
63  });
64 }
65 
66 Face*
67 ProbingModule::getFaceToProbe(const Face& inFace, const Interest& interest,
68  const fib::Entry& fibEntry, const Face& faceUsed)
69 {
70  FaceInfoFacePairSet rankedFaces;
71 
72  // Put eligible faces into rankedFaces. If a face does not have an RTT measurement,
73  // immediately pick the face for probing
74  for (const auto& hop : fibEntry.getNextHops()) {
75  Face& hopFace = hop.getFace();
76 
77  // Don't send probe Interest back to the incoming face or use the same face
78  // as the forwarded Interest or use a face that violates scope
79  if (hopFace.getId() == inFace.getId() || hopFace.getId() == faceUsed.getId() ||
80  wouldViolateScope(inFace, interest, hopFace)) {
81  continue;
82  }
83 
84  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, hopFace.getId());
85  // If no RTT has been recorded, probe this face
86  if (info == nullptr || info->getLastRtt() == FaceInfo::RTT_NO_MEASUREMENT) {
87  return &hopFace;
88  }
89 
90  // Add FaceInfo to container sorted by RTT
91  rankedFaces.insert({info, &hopFace});
92  }
93 
94  if (rankedFaces.empty()) {
95  // No Face to probe
96  return nullptr;
97  }
98 
99  return chooseFace(rankedFaces);
100 }
101 
102 bool
103 ProbingModule::isProbingNeeded(const fib::Entry& fibEntry, const Interest& interest)
104 {
105  // Return the probing status flag for a namespace
106  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
107 
108  // If a first probe has not been scheduled for a namespace
109  if (!info.isFirstProbeScheduled()) {
110  // Schedule first probe between 0 and 5 seconds
111  static std::uniform_int_distribution<> randDist(0, 5000);
112  auto interval = randDist(ndn::random::getRandomNumberEngine());
113  scheduleProbe(fibEntry, time::milliseconds(interval));
114  info.setIsFirstProbeScheduled(true);
115  }
116 
117  return info.isProbingDue();
118 }
119 
120 void
121 ProbingModule::afterForwardingProbe(const fib::Entry& fibEntry, const Interest& interest)
122 {
123  // After probing is done, need to set probing flag to false and
124  // schedule another future probe
125  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
126  info.setIsProbingDue(false);
127 
128  scheduleProbe(fibEntry, m_probingInterval);
129 }
130 
131 Face*
132 ProbingModule::chooseFace(const FaceInfoFacePairSet& rankedFaces)
133 {
134  static std::uniform_real_distribution<> randDist;
135  double randomNumber = randDist(ndn::random::getRandomNumberEngine());
136  uint64_t rankSum = (rankedFaces.size() + 1) * rankedFaces.size() / 2;
137 
138  uint64_t rank = 1;
139  double offset = 0.0;
140 
141  for (const auto& pair : rankedFaces) {
142  double probability = getProbingProbability(rank++, rankSum, rankedFaces.size());
143 
144  // Is the random number within the bounds of this face's probability + the previous faces'
145  // probability?
146  //
147  // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
148  // randomNumber = 0.92
149  //
150  // The face with FaceId: 3 should be picked
151  // (0.68 < 0.5 + 0.33 + 0.17) == true
152  //
153  if (randomNumber <= offset + probability) {
154  // Found face to probe
155  return pair.second;
156  }
157  offset += probability;
158  }
159 
160  // Given a set of Faces, this method should always select a Face to probe
161  NDN_CXX_UNREACHABLE;
162 }
163 
164 double
165 ProbingModule::getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces)
166 {
167  // p = n + 1 - j ; n: # faces
168  // ---------
169  // sum(ranks)
170  return static_cast<double>(nFaces + 1 - rank) / rankSum;
171 }
172 
173 void
174 ProbingModule::setProbingInterval(size_t probingInterval)
175 {
176  if (time::milliseconds(probingInterval) >= MIN_PROBING_INTERVAL) {
177  m_probingInterval = time::milliseconds(probingInterval);
178  }
179  else {
180  NDN_THROW(std::invalid_argument("Probing interval must be >= " +
181  to_string(MIN_PROBING_INTERVAL.count()) + " milliseconds"));
182  }
183 }
184 
185 } // namespace asf
186 } // namespace fw
187 } // namespace nfd
FaceInfo * getFaceInfo(const fib::Entry &fibEntry, const Interest &interest, FaceId faceId)
static const time::nanoseconds RTT_NO_MEASUREMENT
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
void scheduleProbe(const fib::Entry &fibEntry, time::milliseconds interval)
ProbingModule(AsfMeasurements &measurements)
NamespaceInfo * getNamespaceInfo(const Name &prefix)
represents a FIB entry
Definition: fib-entry.hpp:53
static constexpr time::milliseconds DEFAULT_PROBING_INTERVAL
void setIsProbingDue(bool isProbingDue)
Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.
Definition: global.cpp:45
const Name & getPrefix() const
Definition: fib-entry.hpp:60
static constexpr time::microseconds MEASUREMENTS_LIFETIME
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void setIsFirstProbeScheduled(bool isScheduled)
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
time::nanoseconds getLastRtt() const
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
Stores strategy information about each face in this namespace.
This file contains common algorithms used by forwarding strategies.
static constexpr time::milliseconds MIN_PROBING_INTERVAL
void setProbingInterval(size_t probingInterval)
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
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:32
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:66
Strategy information for each face in a namespace.
Helper class to retrieve and create strategy measurements.