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-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 
30 
31 namespace nfd {
32 namespace rib {
33 
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 &&
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 
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 
267  ann.setAnnouncedName(m_name);
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
NFD_LOG_TRACE
#define NFD_LOG_TRACE
Definition: logger.hpp:37
nfd::rib::RibEntry::findRoute
iterator findRoute(const Route &route)
Definition: rib-entry.cpp:37
nfd::rib::RibEntry::hasRoute
bool hasRoute(const Route &route)
Definition: rib-entry.cpp:73
rib-entry.hpp
nfd::rib::RibEntry::getName
const Name & getName() const
Definition: rib-entry.hpp:223
nfd::rib::RibEntry::getNRoutes
size_t getNRoutes() const
Definition: rib-entry.cpp:89
nfd::rib::RibEntry
Represents a RIB entry, which contains one or more Routes with the same prefix.
Definition: rib-entry.hpp:39
nfd::rib::Route::cost
uint64_t cost
Definition: route.hpp:83
nonstd::optional_lite::std11::move
T & move(T &t)
Definition: optional.hpp:421
ndn::time::steady_clock::now
static time_point now() noexcept
Definition: time.cpp:80
control-command.hpp
ndn::PrefixAnnouncement::setExpiration
PrefixAnnouncement & setExpiration(time::milliseconds expiration)
Set relative expiration period.
Definition: prefix-announcement.cpp:99
nfd::rib::RibEntry::getRouteWithSecondLowestCostByFaceId
const Route * getRouteWithSecondLowestCostByFaceId(uint64_t faceId) const
Definition: rib-entry.cpp:194
nfd::rib::RibEntry::eraseRoute
void eraseRoute(const Route &route)
erases a Route with the same faceId and origin
Definition: rib-entry.cpp:66
ndn::PrefixAnnouncement
A prefix announcement object that represents an application's intent of registering a prefix toward i...
Definition: prefix-announcement.hpp:34
nfd::rib::RibEntry::getRouteWithLowestCostAndChildInheritByFaceId
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
nfd::rib::RibEntry::getRouteWithLowestCostByFaceId
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
nfd::rib::RibEntry::hasChildInheritOnFaceId
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
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
nfd::rib::compareFaceId
bool compareFaceId(const Route &route, const uint64_t faceId)
Definition: route.hpp:123
nfd::rib::Route::faceId
uint64_t faceId
Definition: route.hpp:81
ndn::nfd::ROUTE_FLAG_CAPTURE
@ ROUTE_FLAG_CAPTURE
Definition: nfd-constants.hpp:126
nfd::rib::RibEntry::const_iterator
RouteList::const_iterator const_iterator
Definition: rib-entry.hpp:43
nfd::rib::RibEntry::iterator
RouteList::iterator iterator
Definition: rib-entry.hpp:42
nfd::rib::operator<<
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.hpp:74
nfd::rib::compareFaceIdAndOrigin
bool compareFaceIdAndOrigin(const Route &lhs, const Route &rhs)
Definition: route.hpp:117
nfd::rib::RibEntry::addInheritedRoute
void addInheritedRoute(const Route &route)
Definition: rib-entry.cpp:129
nfd::rib::RibEntry::getPrefixAnnouncement
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
nfd::rib::RibEntry::hasFaceId
bool hasFaceId(const uint64_t faceId) const
Definition: rib-entry.cpp:81
nfd::rib::RibEntry::hasInheritedRoute
bool hasInheritedRoute(const Route &route) const
Determines if the entry has an inherited route with a matching face ID.
Definition: rib-entry.cpp:148
nfd::rib::RibEntry::addChild
void addChild(shared_ptr< RibEntry > child)
Definition: rib-entry.cpp:95
ndn::clamp
constexpr const T & clamp(const T &v, const T &lo, const T &hi, Compare comp)
Definition: backports.hpp:117
nfd::rib::RibEntry::hasCapture
bool hasCapture() const
Definition: rib-entry.cpp:154
nfd::rib::RibEntry::findInheritedRoute
RouteList::const_iterator findInheritedRoute(const Route &route) const
Finds an inherited route with a matching face ID.
Definition: rib-entry.cpp:141
nfd::rib::Route::announcement
optional< ndn::PrefixAnnouncement > announcement
The prefix announcement that caused the creation of this route.
Definition: route.hpp:91
nfd::rib::RibEntry::end
const_iterator end() const
Definition: rib-entry.hpp:265
nfd::rib::RibEntry::removeChild
void removeChild(shared_ptr< RibEntry > child)
Definition: rib-entry.cpp:103
nfd::rib::Route::flags
std::underlying_type_t< ndn::nfd::RouteFlags > flags
Definition: route.hpp:84
nfd::rib::Route
represents a route for a name prefix
Definition: route.hpp:44
nfd::rib::Route::expires
optional< time::steady_clock::TimePoint > expires
Definition: route.hpp:85
nfd::rib::RibEntry::begin
const_iterator begin() const
Definition: rib-entry.hpp:259
nfd::rib::RibEntry::insertRoute
std::pair< RibEntry::iterator, bool > insertRoute(const Route &route)
inserts a new route into the entry's route list If another route already exists with the same faceId ...
Definition: rib-entry.cpp:49
nfd::rib::RibEntry::removeInheritedRoute
void removeInheritedRoute(const Route &route)
Definition: rib-entry.cpp:135
ndn::PrefixAnnouncement::setAnnouncedName
PrefixAnnouncement & setAnnouncedName(Name name)
Set announced name.
Definition: prefix-announcement.cpp:91
NFD_LOG_INIT
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
logger.hpp
ndn::nfd::ROUTE_FLAG_CHILD_INHERIT
@ ROUTE_FLAG_CHILD_INHERIT
Definition: nfd-constants.hpp:125