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