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