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