NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
rib.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "rib.hpp"
27 
28 #include "fib-updater.hpp"
29 #include "core/logger.hpp"
30 
31 NFD_LOG_INIT("Rib");
32 
33 namespace nfd {
34 namespace rib {
35 
36 bool
37 operator<(const RibRouteRef& lhs, const RibRouteRef& rhs)
38 {
39  return std::tie(lhs.entry->getName(), lhs.route->faceId, lhs.route->origin) <
40  std::tie(rhs.entry->getName(), rhs.route->faceId, rhs.route->origin);
41 }
42 
43 static inline bool
44 sortRoutes(const Route& lhs, const Route& rhs)
45 {
46  return lhs.faceId < rhs.faceId;
47 }
48 
50  : m_nItems(0)
51  , m_isUpdateInProgress(false)
52 {
53 }
54 
56 {
57 }
58 
59 void
61 {
62  m_fibUpdater = updater;
63 }
64 
66 Rib::find(const Name& prefix) const
67 {
68  return m_rib.find(prefix);
69 }
70 
71 Route*
72 Rib::find(const Name& prefix, const Route& route) const
73 {
74  RibTable::const_iterator ribIt = m_rib.find(prefix);
75 
76  // Name prefix exists
77  if (ribIt != m_rib.end()) {
78  shared_ptr<RibEntry> entry = ribIt->second;
79 
80  RibEntry::iterator routeIt = entry->findRoute(route);
81 
82  if (routeIt != entry->end()) {
83  return &((*routeIt));
84  }
85  }
86 
87  return nullptr;
88 }
89 
90 void
91 Rib::insert(const Name& prefix, const Route& route)
92 {
93  RibTable::iterator ribIt = m_rib.find(prefix);
94 
95  // Name prefix exists
96  if (ribIt != m_rib.end()) {
97  shared_ptr<RibEntry> entry(ribIt->second);
98 
99  RibEntry::iterator entryIt;
100  bool didInsert = false;
101  std::tie(entryIt, didInsert) = entry->insertRoute(route);
102 
103  if (didInsert) {
104  // The route was new and we successfully inserted it.
105  m_nItems++;
106 
107  afterAddRoute(RibRouteRef{entry, entryIt});
108 
109  // Register with face lookup table
110  m_faceMap[route.faceId].push_back(entry);
111  }
112  else {
113  // Route exists, update fields
114  // First cancel old scheduled event, if any, then set the EventId to new one
115  if (static_cast<bool>(entryIt->getExpirationEvent())) {
116  NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
117  << (*entryIt));
118  scheduler::cancel(entryIt->getExpirationEvent());
119  }
120 
121  // No checks are required here as the iterator needs to be updated in all cases.
122  entryIt->setExpirationEvent(route.getExpirationEvent());
123 
124  entryIt->flags = route.flags;
125  entryIt->cost = route.cost;
126  entryIt->expires = route.expires;
127  }
128  }
129  else {
130  // New name prefix
131  shared_ptr<RibEntry> entry = make_shared<RibEntry>();
132 
133  m_rib[prefix] = entry;
134  m_nItems++;
135 
136  entry->setName(prefix);
137  RibEntry::iterator routeIt = entry->insertRoute(route).first;
138 
139  // Find prefix's parent
140  shared_ptr<RibEntry> parent = findParent(prefix);
141 
142  // Add self to parent's children
143  if (parent != nullptr) {
144  parent->addChild(entry);
145  }
146 
147  RibEntryList children = findDescendants(prefix);
148 
149  for (const auto& child : children) {
150  if (child->getParent() == parent) {
151  // Remove child from parent and inherit parent's child
152  if (parent != nullptr) {
153  parent->removeChild(child);
154  }
155 
156  entry->addChild(child);
157  }
158  }
159 
160  // Register with face lookup table
161  m_faceMap[route.faceId].push_back(entry);
162 
163  // do something after inserting an entry
164  afterInsertEntry(prefix);
165  afterAddRoute(RibRouteRef{entry, routeIt});
166  }
167 }
168 
169 void
170 Rib::erase(const Name& prefix, const Route& route)
171 {
172  RibTable::iterator ribIt = m_rib.find(prefix);
173 
174  // Name prefix exists
175  if (ribIt != m_rib.end()) {
176  shared_ptr<RibEntry> entry = ribIt->second;
177  RibEntry::iterator routeIt = entry->findRoute(route);
178 
179  if (routeIt != entry->end()) {
180  beforeRemoveRoute(RibRouteRef{entry, routeIt});
181 
182  auto faceId = route.faceId;
183  entry->eraseRoute(routeIt);
184  m_nItems--;
185 
186  // If this RibEntry no longer has this faceId, unregister from face lookup table
187  if (!entry->hasFaceId(faceId)) {
188  m_faceMap[faceId].remove(entry);
189  }
190 
191  // If a RibEntry's route list is empty, remove it from the tree
192  if (entry->getRoutes().empty()) {
193  eraseEntry(ribIt);
194  }
195  }
196  }
197 }
198 
199 void
200 Rib::onRouteExpiration(const Name& prefix, const Route& route)
201 {
202  NFD_LOG_DEBUG(route << " for " << prefix << " has expired");
203 
204  RibUpdate update;
206  .setName(prefix)
207  .setRoute(route);
208 
209  beginApplyUpdate(update, nullptr, nullptr);
210 }
211 
212 shared_ptr<RibEntry>
213 Rib::findParent(const Name& prefix) const
214 {
215  for (int i = prefix.size() - 1; i >= 0; i--) {
216  RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
217 
218  if (it != m_rib.end()) {
219  return (it->second);
220  }
221  }
222 
223  return shared_ptr<RibEntry>();
224 }
225 
226 std::list<shared_ptr<RibEntry> >
227 Rib::findDescendants(const Name& prefix) const
228 {
229  std::list<shared_ptr<RibEntry> > children;
230 
231  RibTable::const_iterator it = m_rib.find(prefix);
232 
233  if (it != m_rib.end()) {
234  ++it;
235  for (; it != m_rib.end(); ++it) {
236  if (prefix.isPrefixOf(it->first)) {
237  children.push_back((it->second));
238  }
239  else {
240  break;
241  }
242  }
243  }
244 
245  return children;
246 }
247 
248 std::list<shared_ptr<RibEntry>>
250 {
251  std::list<shared_ptr<RibEntry>> children;
252 
253  for (std::pair<Name, shared_ptr<RibEntry>> pair : m_rib) {
254  if (prefix.isPrefixOf(pair.first)) {
255  children.push_back(pair.second);
256  }
257  }
258 
259  return children;
260 }
261 
263 Rib::eraseEntry(RibTable::iterator it)
264 {
265  // Entry does not exist
266  if (it == m_rib.end()) {
267  return m_rib.end();
268  }
269 
270  shared_ptr<RibEntry> entry(it->second);
271 
272  shared_ptr<RibEntry> parent = entry->getParent();
273 
274  // Remove self from parent's children
275  if (parent != nullptr) {
276  parent->removeChild(entry);
277  }
278 
279  for (auto childIt = entry->getChildren().begin(); childIt != entry->getChildren().end(); ) {
280  shared_ptr<RibEntry> child = *childIt;
281 
282  // Advance iterator so it is not invalidated by removal
283  ++childIt;
284 
285  // Remove children from self
286  entry->removeChild(child);
287 
288  // Update parent's children
289  if (parent != nullptr) {
290  parent->addChild(child);
291  }
292  }
293 
294  RibTable::iterator nextIt = m_rib.erase(it);
295 
296  // do something after erasing an entry.
297  afterEraseEntry(entry->getName());
298 
299  return nextIt;
300 }
301 
303 Rib::getAncestorRoutes(const RibEntry& entry) const
304 {
305  RouteSet ancestorRoutes(&sortRoutes);
306 
307  shared_ptr<RibEntry> parent = entry.getParent();
308 
309  while (parent != nullptr) {
310  for (const Route& route : parent->getRoutes()) {
311  if (route.isChildInherit()) {
312  ancestorRoutes.insert(route);
313  }
314  }
315 
316  if (parent->hasCapture()) {
317  break;
318  }
319 
320  parent = parent->getParent();
321  }
322 
323  return ancestorRoutes;
324 }
325 
327 Rib::getAncestorRoutes(const Name& name) const
328 {
329  RouteSet ancestorRoutes(&sortRoutes);
330 
331  shared_ptr<RibEntry> parent = findParent(name);
332 
333  while (parent != nullptr) {
334  for (const Route& route : parent->getRoutes()) {
335  if (route.isChildInherit()) {
336  ancestorRoutes.insert(route);
337  }
338  }
339 
340  if (parent->hasCapture()) {
341  break;
342  }
343 
344  parent = parent->getParent();
345  }
346 
347  return ancestorRoutes;
348 }
349 
350 void
352  const Rib::UpdateSuccessCallback& onSuccess,
353  const Rib::UpdateFailureCallback& onFailure)
354 {
355  BOOST_ASSERT(m_fibUpdater != nullptr);
356 
357  addUpdateToQueue(update, onSuccess, onFailure);
358 
359  sendBatchFromQueue();
360 }
361 
362 void
363 Rib::beginRemoveFace(uint64_t faceId)
364 {
365  for (const auto& nameAndRoute : findRoutesWithFaceId(faceId)) {
366  RibUpdate update;
368  .setName(nameAndRoute.first)
369  .setRoute(nameAndRoute.second);
370 
371  addUpdateToQueue(update, nullptr, nullptr);
372  }
373 
374  sendBatchFromQueue();
375 }
376 
377 void
378 Rib::addUpdateToQueue(const RibUpdate& update,
379  const Rib::UpdateSuccessCallback& onSuccess,
380  const Rib::UpdateFailureCallback& onFailure)
381 {
382  RibUpdateBatch batch(update.getRoute().faceId);
383  batch.add(update);
384 
385  UpdateQueueItem item{batch, onSuccess, onFailure};
386  m_updateBatches.push_back(std::move(item));
387 }
388 
389 void
390 Rib::sendBatchFromQueue()
391 {
392  if (m_updateBatches.empty() || m_isUpdateInProgress) {
393  return;
394  }
395 
396  m_isUpdateInProgress = true;
397 
398  UpdateQueueItem item = std::move(m_updateBatches.front());
399  m_updateBatches.pop_front();
400 
401  RibUpdateBatch& batch = item.batch;
402 
403  // Until task #1698, each RibUpdateBatch contains exactly one RIB update
404  BOOST_ASSERT(batch.size() == 1);
405 
406  const Rib::UpdateSuccessCallback& managerSuccessCallback = item.managerSuccessCallback;
407  const Rib::UpdateFailureCallback& managerFailureCallback = item.managerFailureCallback;
408 
409  m_fibUpdater->computeAndSendFibUpdates(batch,
410  bind(&Rib::onFibUpdateSuccess, this,
411  batch, _1, managerSuccessCallback),
412  bind(&Rib::onFibUpdateFailure, this,
413  managerFailureCallback, _1, _2));
414 
415  if (m_onSendBatchFromQueue != nullptr) {
416  m_onSendBatchFromQueue(batch);
417  }
418 }
419 
420 void
422  const RibUpdateList& inheritedRoutes,
423  const Rib::UpdateSuccessCallback& onSuccess)
424 {
425  for (const RibUpdate& update : batch) {
426  switch (update.getAction()) {
427  case RibUpdate::REGISTER:
428  insert(update.getName(), update.getRoute());
429  break;
432  erase(update.getName(), update.getRoute());
433  break;
434  }
435  }
436 
437  // Add and remove precalculated inherited routes to RibEntries
438  modifyInheritedRoutes(inheritedRoutes);
439 
440  m_isUpdateInProgress = false;
441 
442  if (onSuccess != nullptr) {
443  onSuccess();
444  }
445 
446  // Try to advance the batch queue
447  sendBatchFromQueue();
448 }
449 
450 void
452  uint32_t code, const std::string& error)
453 {
454  m_isUpdateInProgress = false;
455 
456  if (onFailure != nullptr) {
457  onFailure(code, error);
458  }
459 
460  // Try to advance the batch queue
461  sendBatchFromQueue();
462 }
463 
464 void
465 Rib::modifyInheritedRoutes(const RibUpdateList& inheritedRoutes)
466 {
467  for (const RibUpdate& update : inheritedRoutes) {
468  RibTable::iterator ribIt = m_rib.find(update.getName());
469 
470  BOOST_ASSERT(ribIt != m_rib.end());
471  shared_ptr<RibEntry> entry(ribIt->second);
472 
473  switch (update.getAction()) {
474  case RibUpdate::REGISTER:
475  entry->addInheritedRoute(update.getRoute());
476  break;
478  entry->removeInheritedRoute(update.getRoute());
479  break;
481  break;
482  }
483  }
484 }
485 
486 std::list<Rib::NameAndRoute>
487 Rib::findRoutesWithFaceId(uint64_t faceId)
488 {
489  std::list<NameAndRoute> routes;
490 
491  FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
492 
493  // No RIB entries have this face
494  if (lookupIt == m_faceMap.end()) {
495  return routes;
496  }
497 
498  RibEntryList& ribEntries = lookupIt->second;
499 
500  // For each RIB entry that has faceId
501  for (const shared_ptr<RibEntry>& entry : ribEntries) {
502  // Find the routes in the entry
503  for (const Route& route : *entry) {
504  if (route.faceId == faceId) {
505  routes.push_back(NameAndRoute(entry->getName(), route));
506  }
507  }
508  }
509 
510  return routes;
511 }
512 
513 std::ostream&
514 operator<<(std::ostream& os, const Rib& rib)
515 {
516  for (const auto& item : rib) {
517  os << *item.second << "\n";
518  }
519 
520  return os;
521 }
522 
523 } // namespace rib
524 } // namespace nfd
RibUpdate & setRoute(const Route &route)
Definition: rib-update.hpp:107
std::list< shared_ptr< RibEntry > > findDescendants(const Name &prefix) const
finds namespaces under the passed prefix
Definition: rib.cpp:227
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix of the name.
Definition: name.hpp:210
represents the Routing Information Base
Definition: rib.hpp:59
RibEntry
Copyright (c) 2014-2017, Regents of the University of California, Arizona Board of Regents...
Definition: rib-entry.cpp:32
const scheduler::EventId & getExpirationEvent() const
Definition: route.hpp:51
const Route & getRoute() const
Definition: rib-update.hpp:114
void beginApplyUpdate(const RibUpdate &update, const UpdateSuccessCallback &onSuccess, const UpdateFailureCallback &onFailure)
passes the provided RibUpdateBatch to FibUpdater to calculate and send FibUpdates.
Definition: rib.cpp:351
void cancel(const EventId &eventId)
cancel a scheduled event
Definition: scheduler.cpp:53
void add(const RibUpdate &update)
static bool sortRoutes(const Route &lhs, const Route &rhs)
Definition: rib.cpp:44
represents a collection of RibUpdates to be applied to a single FaceId
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.hpp:74
bool isPrefixOf(const Name &other) const
Check if this name is a prefix of another name.
Definition: name.cpp:260
const_iterator find(const Name &prefix) const
Definition: rib.cpp:66
std::underlying_type< ndn::nfd::RouteFlags >::type flags
Definition: route.hpp:66
ndn::util::signal::Signal< Rib, RibRouteRef > afterAddRoute
signals after a Route is added
Definition: rib.hpp:237
computes FibUpdates based on updates to the RIB and sends them to NFD
Definition: fib-updater.hpp:41
uint64_t cost
Definition: route.hpp:65
uint64_t faceId
Definition: route.hpp:63
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:55
void onFibUpdateSuccess(const RibUpdateBatch &batch, const RibUpdateList &inheritedRoutes, const Rib::UpdateSuccessCallback &onSuccess)
Definition: rib.cpp:421
RibEntry::const_iterator route
Definition: rib.hpp:46
references a route
Definition: rib.hpp:43
ndn::optional< time::steady_clock::TimePoint > expires
Definition: route.hpp:67
RouteList::iterator iterator
Definition: rib-entry.hpp:40
function< void(uint32_t code, const std::string &error)> UpdateFailureCallback
Definition: rib.hpp:116
std::set< Route, RouteComparePredicate > RouteSet
Definition: rib.hpp:67
Table::const_iterator iterator
Definition: cs-internal.hpp:41
function< void()> UpdateSuccessCallback
Definition: rib.hpp:115
std::list< shared_ptr< RibEntry > > RibEntryList
Definition: rib.hpp:62
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:54
const Name & getName() const
Definition: rib-update.hpp:101
std::list< RibUpdate > RibUpdateList
void insert(const Name &prefix, const Route &route)
Definition: rib.cpp:91
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
shared_ptr< RibEntry > entry
Definition: rib.hpp:45
RibUpdate & setAction(Action action)
Definition: rib-update.hpp:81
represents a route for a name prefix
Definition: route.hpp:39
shared_ptr< RibEntry > findParent(const Name &prefix) const
Definition: rib.cpp:213
Represents an absolute name.
Definition: name.hpp:42
RibTable::const_iterator const_iterator
Definition: rib.hpp:64
void beginRemoveFace(uint64_t faceId)
starts the FIB update process when a face has been destroyed
Definition: rib.cpp:363
ndn::util::signal::Signal< Rib, Name > afterInsertEntry
signals after a RIB entry is inserted
Definition: rib.hpp:225
size_t size() const
Get number of components.
Definition: name.hpp:154
void onFibUpdateFailure(const Rib::UpdateFailureCallback &onFailure, uint32_t code, const std::string &error)
Definition: rib.cpp:451
ndn::util::signal::Signal< Rib, Name > afterEraseEntry
signals after a RIB entry is erased
Definition: rib.hpp:233
RibUpdate & setName(const Name &name)
Definition: rib-update.hpp:94
void onRouteExpiration(const Name &prefix, const Route &route)
Definition: rib.cpp:200
std::list< shared_ptr< RibEntry > > findDescendantsForNonInsertedName(const Name &prefix) const
finds namespaces under the passed prefix
Definition: rib.cpp:249
An update triggered by a face destruction notification.
Definition: rib-update.hpp:51
void computeAndSendFibUpdates(const RibUpdateBatch &batch, const FibUpdateSuccessCallback &onSuccess, const FibUpdateFailureCallback &onFailure)
computes FibUpdates using the provided RibUpdateBatch and then sends the updates to NFD&#39;s FIB ...
Definition: fib-updater.cpp:50
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
bool operator<(const ReadvertisedRoute &lhs, const ReadvertisedRoute &rhs)
ndn::util::signal::Signal< Rib, RibRouteRef > beforeRemoveRoute
signals before a route is removed
Definition: rib.hpp:241
void setFibUpdater(FibUpdater *updater)
Definition: rib.cpp:60
Action getAction() const
Definition: rib-update.hpp:88