NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
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-2018, 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 "core/random.hpp"
28 #include "algorithm.hpp"
29 
30 namespace nfd {
31 namespace fw {
32 namespace asf {
33 
34 constexpr time::milliseconds ProbingModule::DEFAULT_PROBING_INTERVAL;
35 constexpr time::milliseconds ProbingModule::MIN_PROBING_INTERVAL;
36 
38  "ProbingModule::DEFAULT_PROBING_INTERVAL must be less than AsfMeasurements::MEASUREMENTS_LIFETIME");
39 
41  : m_probingInterval(DEFAULT_PROBING_INTERVAL)
42  , m_measurements(measurements)
43 {
44 }
45 
46 void
47 ProbingModule::scheduleProbe(const fib::Entry& fibEntry, const time::milliseconds& interval)
48 {
49  Name prefix = fibEntry.getPrefix();
50 
51  // Set the probing flag for the namespace to true after passed interval of time
52  scheduler::schedule(interval, [this, prefix] {
53  NamespaceInfo* info = m_measurements.getNamespaceInfo(prefix);
54 
55  if (info == nullptr) {
56  // fib::Entry with the passed prefix has been removed or the fib::Entry has
57  // a name that is not controlled by the AsfStrategy
58  return;
59  }
60  else {
61  info->setIsProbingDue(true);
62  }
63  });
64 }
65 
66 Face*
68  const Interest& interest,
69  const fib::Entry& fibEntry,
70  const Face& faceUsed)
71 {
72  FaceInfoFacePairSet rankedFaces(
73  [] (const auto& pairLhs, const auto& pairRhs) -> bool {
74  // Sort by RTT
75  // If a face has timed-out, rank it behind non-timed-out faces
76  FaceInfo& lhs = *pairLhs.first;
77  FaceInfo& rhs = *pairRhs.first;
78 
79  return (!lhs.isTimeout() && rhs.isTimeout()) ||
80  (lhs.isTimeout() == rhs.isTimeout() && lhs.getSrtt() < rhs.getSrtt());
81  });
82 
83  // Put eligible faces into rankedFaces. If a face does not have an RTT measurement,
84  // immediately pick the face for probing
85  for (const fib::NextHop& hop : fibEntry.getNextHops()) {
86  Face& hopFace = hop.getFace();
87 
88  // Don't send probe Interest back to the incoming face or use the same face
89  // as the forwarded Interest or use a face that violates scope
90  if (hopFace.getId() == inFace.getId() || hopFace.getId() == faceUsed.getId() ||
91  wouldViolateScope(inFace, interest, hopFace)) {
92  continue;
93  }
94 
95  FaceInfo* info = m_measurements.getFaceInfo(fibEntry, interest, hopFace.getId());
96  // If no RTT has been recorded, probe this face
97  if (info == nullptr || !info->hasSrttMeasurement()) {
98  return &hopFace;
99  }
100 
101  // Add FaceInfo to container sorted by RTT
102  rankedFaces.insert({info, &hopFace});
103  }
104 
105  if (rankedFaces.empty()) {
106  // No Face to probe
107  return nullptr;
108  }
109 
110  return getFaceBasedOnProbability(rankedFaces);
111 }
112 
113 bool
114 ProbingModule::isProbingNeeded(const fib::Entry& fibEntry, const Interest& interest)
115 {
116  // Return the probing status flag for a namespace
117  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
118 
119  // If a first probe has not been scheduled for a namespace
120  if (!info.isFirstProbeScheduled()) {
121  // Schedule first probe between 0 and 5 seconds
122  uint64_t interval = getRandomNumber(0, 5000);
123  scheduleProbe(fibEntry, time::milliseconds(interval));
124 
126  }
127 
128  return info.isProbingDue();
129 }
130 
131 void
132 ProbingModule::afterForwardingProbe(const fib::Entry& fibEntry, const Interest& interest)
133 {
134  // After probing is done, need to set probing flag to false and
135  // schedule another future probe
136  NamespaceInfo& info = m_measurements.getOrCreateNamespaceInfo(fibEntry, interest);
137  info.setIsProbingDue(false);
138 
139  scheduleProbe(fibEntry, m_probingInterval);
140 }
141 
142 Face*
143 ProbingModule::getFaceBasedOnProbability(const FaceInfoFacePairSet& rankedFaces)
144 {
145  double randomNumber = getRandomNumber(0, 1);
146  uint64_t rankSum = ((rankedFaces.size() + 1) * rankedFaces.size()) / 2;
147 
148  uint64_t rank = 1;
149  double offset = 0.0;
150 
151  for (const auto& pair : rankedFaces) {
152  double probability = getProbingProbability(rank++, rankSum, rankedFaces.size());
153 
154  // Is the random number within the bounds of this face's probability + the previous faces'
155  // probability?
156  //
157  // e.g. (FaceId: 1, p=0.5), (FaceId: 2, p=0.33), (FaceId: 3, p=0.17)
158  // randomNumber = 0.92
159  //
160  // The face with FaceId: 3 should be picked
161  // (0.68 < 0.5 + 0.33 + 0.17) == true
162  //
163  if (randomNumber <= offset + probability) {
164  // Found face to probe
165  return pair.second;
166  }
167 
168  offset += probability;
169  }
170 
171  // Given a set of Faces, this method should always select a Face to probe
172  BOOST_ASSERT(false);
173  return nullptr;
174 }
175 
176 double
177 ProbingModule::getProbingProbability(uint64_t rank, uint64_t rankSum, uint64_t nFaces)
178 {
179  // p = n + 1 - j ; n: # faces
180  // ---------
181  // sum(ranks)
182  return static_cast<double>(nFaces + 1 - rank) / rankSum;
183 }
184 
185 double
186 ProbingModule::getRandomNumber(double start, double end)
187 {
188  std::uniform_real_distribution<double> dist(start, end);
189  return dist(getGlobalRng());
190 }
191 
192 void
193 ProbingModule::setProbingInterval(size_t probingInterval)
194 {
195  if (time::milliseconds(probingInterval) >= MIN_PROBING_INTERVAL) {
196  m_probingInterval = time::milliseconds(probingInterval);
197  }
198  else {
199  BOOST_THROW_EXCEPTION(std::invalid_argument("Probing interval should be >= "
201  + " milliseconds"));
202  }
203 }
204 
205 } // namespace asf
206 } // namespace fw
207 } // namespace nfd
Declares the global pseudorandom number generator (PRNG) for NFD.
const Name & getPrefix() const
Definition: fib-entry.hpp:58
Helper class to retrieve and create strategy measurements.
generalization of a network interface
Definition: face.hpp:67
represents a FIB entry
Definition: fib-entry.hpp:51
ProbingModule(AsfMeasurements &measurements)
Represents an Interest packet.
Definition: interest.hpp:44
stores stategy information about each face in this namespace
static constexpr time::milliseconds MIN_PROBING_INTERVAL
void setProbingInterval(size_t probingInterval)
bool isProbingNeeded(const fib::Entry &fibEntry, const Interest &interest)
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
void setHasFirstProbeBeenScheduled(bool hasBeenScheduled)
FaceId getId() const
Definition: face.hpp:233
void setIsProbingDue(bool isProbingDue)
NamespaceInfo & getOrCreateNamespaceInfo(const fib::Entry &fibEntry, const Interest &interest)
static constexpr time::microseconds MEASUREMENTS_LIFETIME
void scheduleProbe(const fib::Entry &fibEntry, const time::milliseconds &interval)
Represents an absolute name.
Definition: name.hpp:43
Face * getFaceToProbe(const Face &inFace, const Interest &interest, const fib::Entry &fibEntry, const Face &faceUsed)
Strategy information for each face in a namespace.
std::mt19937 & getGlobalRng()
Definition: random.cpp:32
NamespaceInfo * getNamespaceInfo(const Name &prefix)
This file contains common algorithms used by forwarding strategies.
static constexpr time::milliseconds DEFAULT_PROBING_INTERVAL
EventId schedule(time::nanoseconds after, const EventCallback &event)
Schedule an event.
Definition: scheduler.cpp:48
RttStats::Rtt getSrtt() const
void afterForwardingProbe(const fib::Entry &fibEntry, const Interest &interest)
FaceInfo * getFaceInfo(const fib::Entry &fibEntry, const Interest &interest, FaceId faceId)
std::string to_string(const V &v)
Definition: backports.hpp:67
const NextHopList & getNextHops() const
Definition: fib-entry.hpp:64
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
represents a nexthop record in FIB entry
Definition: fib-nexthop.hpp:38