NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
rib-entry.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2021, 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 "rib-entry.hpp"
27 #include "common/logger.hpp"
28 
30 
31 namespace nfd {
32 namespace rib {
33 
35 
36 static bool
37 compareFaceIdAndOrigin(const Route& lhs, const Route& rhs)
38 {
39  return lhs.faceId == rhs.faceId && lhs.origin == rhs.origin;
40 }
41 
42 RibEntry::RouteList::iterator
44 {
45  return std::find_if(begin(), end(),
46  [&] (const auto& r) { return compareFaceIdAndOrigin(r, route); });
47 }
48 
49 RibEntry::RouteList::const_iterator
50 RibEntry::findRoute(const Route& route) const
51 {
52  return std::find_if(begin(), end(),
53  [&] (const auto& r) { return compareFaceIdAndOrigin(r, route); });
54 }
55 
56 std::pair<RibEntry::iterator, bool>
58 {
59  auto it = findRoute(route);
60 
61  if (it == end()) {
62  if (route.flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
63  m_nRoutesWithCaptureSet++;
64  }
65 
66  m_routes.push_back(route);
67  return {std::prev(m_routes.end()), true};
68  }
69 
70  return {it, false};
71 }
72 
73 void
75 {
76  auto it = findRoute(route);
77  eraseRoute(it);
78 }
79 
80 bool
82 {
83  auto it = findRoute(route);
84  return it != end();
85 }
86 
87 bool
88 RibEntry::hasFaceId(uint64_t faceId) const
89 {
90  auto it = std::find_if(begin(), end(), [faceId] (const auto& r) { return r.faceId == faceId; });
91  return it != end();
92 }
93 
94 size_t
96 {
97  return m_routes.size();
98 }
99 
100 void
101 RibEntry::addChild(shared_ptr<RibEntry> child)
102 {
103  BOOST_ASSERT(!child->getParent());
104  child->setParent(this->shared_from_this());
105  m_children.push_back(std::move(child));
106 }
107 
108 void
109 RibEntry::removeChild(shared_ptr<RibEntry> child)
110 {
111  BOOST_ASSERT(child->getParent().get() == this);
112  child->setParent(nullptr);
113  m_children.remove(child);
114 }
115 
116 RibEntry::RouteList::iterator
117 RibEntry::eraseRoute(RouteList::iterator route)
118 {
119  if (route != m_routes.end()) {
120  if (route->flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
121  m_nRoutesWithCaptureSet--;
122  }
123 
124  // Cancel any scheduled event
125  NFD_LOG_TRACE("Cancelling expiration event: " << route->getExpirationEvent());
126  route->cancelExpirationEvent();
127 
128  return m_routes.erase(route);
129  }
130 
131  return m_routes.end();
132 }
133 
134 void
136 {
137  m_inheritedRoutes.push_back(route);
138 }
139 
140 void
142 {
143  m_inheritedRoutes.remove_if([id = route.faceId] (const auto& r) { return r.faceId == id; });
144 }
145 
146 RibEntry::RouteList::const_iterator
148 {
149  return std::find_if(m_inheritedRoutes.begin(), m_inheritedRoutes.end(),
150  [id = route.faceId] (const auto& r) { return r.faceId == id; });
151 }
152 
153 bool
155 {
156  return findInheritedRoute(route) != m_inheritedRoutes.end();
157 }
158 
159 bool
161 {
162  return m_nRoutesWithCaptureSet > 0;
163 }
164 
165 bool
166 RibEntry::hasChildInheritOnFaceId(uint64_t faceId) const
167 {
168  for (const Route& route : m_routes) {
169  if (route.faceId == faceId && (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)) {
170  return true;
171  }
172  }
173 
174  return false;
175 }
176 
177 const Route*
179 {
180  const Route* candidate = nullptr;
181 
182  for (const Route& route : m_routes) {
183  // Matching face ID
184  if (route.faceId == faceId) {
185  // If this is the first route with this Face ID found
186  if (candidate == nullptr) {
187  candidate = &route;
188  }
189  else if (route.cost < candidate->cost) {
190  // Found a route with a lower cost
191  candidate = &route;
192  }
193  }
194  }
195 
196  return candidate;
197 }
198 
199 const Route*
201 {
202  std::vector<const Route*> matches;
203 
204  // Copy routes which have faceId
205  for (const Route& route : m_routes) {
206  if (route.faceId == faceId) {
207  matches.push_back(&route);
208  }
209  }
210 
211  // If there are less than 2 routes, there is no second lowest
212  if (matches.size() < 2) {
213  return nullptr;
214  }
215 
216  // Get second lowest cost
217  std::nth_element(matches.begin(), matches.begin() + 1, matches.end(),
218  [] (const Route* lhs, const Route* rhs) { return lhs->cost < rhs->cost; });
219 
220  return matches.at(1);
221 }
222 
223 const Route*
225 {
226  const Route* candidate = nullptr;
227 
228  for (const Route& route : m_routes) {
229  // Correct face ID and Child Inherit flag set
230  if (route.faceId == faceId &&
232  {
233  // If this is the first route with this Face ID found
234  if (candidate == nullptr) {
235  candidate = &route;
236  }
237  else if (route.cost < candidate->cost) {
238  // Found a route with a lower cost
239  candidate = &route;
240  }
241  }
242  }
243 
244  return candidate;
245 }
246 
249  time::milliseconds maxExpiration) const
250 {
251  const Route* bestAnnRoute = nullptr;
252  auto entryExpiry = time::steady_clock::time_point::min();
253 
254  for (const Route& route : *this) {
255  if (route.expires) {
256  entryExpiry = std::max(entryExpiry, *route.expires);
257  if (route.announcement) {
258  if (bestAnnRoute == nullptr || *route.expires > *bestAnnRoute->expires) {
259  bestAnnRoute = &route;
260  }
261  }
262  }
263  else {
264  entryExpiry = time::steady_clock::time_point::max();
265  }
266  }
267 
268  if (bestAnnRoute != nullptr) {
269  return *bestAnnRoute->announcement;
270  }
271 
273  ann.setAnnouncedName(m_name);
275  time::duration_cast<time::milliseconds>(entryExpiry - time::steady_clock::now()),
276  minExpiration, maxExpiration));
277  return ann;
278 }
279 
280 std::ostream&
281 operator<<(std::ostream& os, const RibEntry& entry)
282 {
283  os << "RibEntry {\n";
284  os << " Name: " << entry.getName() << "\n";
285 
286  for (const Route& route : entry) {
287  os << " " << route << "\n";
288  }
289 
290  os << "}";
291 
292  return os;
293 }
294 
295 } // namespace rib
296 } // namespace nfd
bool hasFaceId(uint64_t faceId) const
Definition: rib-entry.cpp:88
std::underlying_type_t< ndn::nfd::RouteFlags > flags
Definition: route.hpp:84
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
static bool compareFaceIdAndOrigin(const Route &lhs, const Route &rhs)
Definition: rib-entry.cpp:37
void removeChild(shared_ptr< RibEntry > child)
Definition: rib-entry.cpp:109
iterator findRoute(const Route &route)
Definition: rib-entry.cpp:43
void addChild(shared_ptr< RibEntry > child)
Definition: rib-entry.cpp:101
bool hasRoute(const Route &route)
Definition: rib-entry.cpp:81
static time_point now() noexcept
Definition: time.cpp:80
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.hpp:74
size_t getNRoutes() const
Definition: rib-entry.cpp:95
constexpr const T & clamp(const T &v, const T &lo, const T &hi, Compare comp)
Definition: backports.hpp:101
const Route * getRouteWithSecondLowestCostByFaceId(uint64_t faceId) const
Definition: rib-entry.cpp:200
uint64_t cost
Definition: route.hpp:83
uint64_t faceId
Definition: route.hpp:81
const Name & getName() const
Definition: rib-entry.hpp:223
void removeInheritedRoute(const Route &route)
Definition: rib-entry.cpp:141
A prefix announcement object that represents an application&#39;s intent of registering a prefix toward i...
ndn::PrefixAnnouncement getPrefixAnnouncement(time::milliseconds minExpiration=15_s, time::milliseconds maxExpiration=1_h) const
Retrieve a prefix announcement suitable for readvertising this route.
Definition: rib-entry.cpp:248
optional< ndn::PrefixAnnouncement > announcement
The prefix announcement that caused the creation of this route.
Definition: route.hpp:91
optional< time::steady_clock::time_point > expires
Definition: route.hpp:85
ndn::nfd::RouteOrigin origin
Definition: route.hpp:82
void addInheritedRoute(const Route &route)
Definition: rib-entry.cpp:135
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:39
PrefixAnnouncement & setExpiration(time::milliseconds expiration)
Set relative expiration period.
const Route * getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId) const
Returns the route with the lowest cost that has the passed face ID and its child inherit flag set...
Definition: rib-entry.cpp:224
Represents a RIB entry, which contains one or more Routes with the same prefix.
Definition: rib-entry.hpp:38
represents a route for a name prefix
Definition: route.hpp:43
#define NFD_LOG_TRACE
Definition: logger.hpp:37
bool hasInheritedRoute(const Route &route) const
Determines if the entry has an inherited route with a matching face ID.
Definition: rib-entry.cpp:154
RouteList::const_iterator findInheritedRoute(const Route &route) const
Finds an inherited route with a matching face ID.
Definition: rib-entry.cpp:147
const_iterator begin() const
Definition: rib-entry.hpp:259
PrefixAnnouncement & setAnnouncedName(Name name)
Set announced name.
bool hasChildInheritOnFaceId(uint64_t faceId) const
Determines if the entry has an inherited route with the passed face ID and its child inherit flag set...
Definition: rib-entry.cpp:166
std::pair< RibEntry::iterator, bool > insertRoute(const Route &route)
inserts a new route into the entry&#39;s route list If another route already exists with the same faceId ...
Definition: rib-entry.cpp:57
void eraseRoute(const Route &route)
erases a Route with the same faceId and origin
Definition: rib-entry.cpp:74
bool hasCapture() const
Definition: rib-entry.cpp:160
const Route * getRouteWithLowestCostByFaceId(uint64_t faceId) const
Returns the route with the lowest cost that has the passed face ID.
Definition: rib-entry.cpp:178
const_iterator end() const
Definition: rib-entry.hpp:265
boost::chrono::milliseconds milliseconds
Definition: time.hpp:48