fib-updater.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "fib-updater.hpp"
27 
28 #include "core/logger.hpp"
29 
30 #include <ndn-cxx/mgmt/nfd/control-parameters.hpp>
31 
32 namespace nfd {
33 namespace rib {
34 
35 using ndn::nfd::ControlParameters;
36 
37 NFD_LOG_INIT("FibUpdater");
38 
39 const unsigned int FibUpdater::MAX_NUM_TIMEOUTS = 10;
40 const uint32_t FibUpdater::ERROR_FACE_NOT_FOUND = 410;
41 
42 FibUpdater::FibUpdater(Rib& rib, ndn::nfd::Controller& controller)
43  : m_rib(rib)
44  , m_controller(controller)
45 {
46  rib.setFibUpdater(this);
47 }
48 
49 void
51  const FibUpdateSuccessCallback& onSuccess,
52  const FibUpdateFailureCallback& onFailure)
53 {
54  m_batchFaceId = batch.getFaceId();
55 
56  // Erase previously calculated inherited routes
57  m_inheritedRoutes.clear();
58 
59  // Erase previously calculated FIB updates
60  m_updatesForBatchFaceId.clear();
61  m_updatesForNonBatchFaceId.clear();
62 
63  computeUpdates(batch);
64 
65  sendUpdatesForBatchFaceId(onSuccess, onFailure);
66 }
67 
68 void
69 FibUpdater::computeUpdates(const RibUpdateBatch& batch)
70 {
71  NFD_LOG_DEBUG("Computing updates for batch with faceID: " << batch.getFaceId());
72 
73  // Compute updates and add to m_fibUpdates
74  for (const RibUpdate& update : batch) {
75  switch (update.getAction()) {
77  computeUpdatesForRegistration(update);
78  break;
80  computeUpdatesForUnregistration(update);
81  break;
83  computeUpdatesForUnregistration(update);
84 
85  // Do not apply updates with the same face ID as the destroyed face
86  // since they will be rejected by the FIB
87  m_updatesForBatchFaceId.clear();
88  break;
89  }
90  }
91 }
92 
93 void
94 FibUpdater::computeUpdatesForRegistration(const RibUpdate& update)
95 {
96  const Name& prefix = update.getName();
97  const Route& route = update.getRoute();
98 
99  Rib::const_iterator it = m_rib.find(prefix);
100 
101  // Name prefix exists
102  if (it != m_rib.end()) {
103  shared_ptr<const RibEntry> entry(it->second);
104 
105  RibEntry::const_iterator existingRoute = entry->findRoute(route);
106 
107  // Route will be new
108  if (existingRoute == entry->end()) {
109  // Will the new route change the namespace's capture flag?
110  bool willCaptureBeTurnedOn = (entry->hasCapture() == false && route.isRibCapture());
111 
112  createFibUpdatesForNewRoute(*entry, route, willCaptureBeTurnedOn);
113  }
114  else {
115  // Route already exists
116  RibEntry entryCopy = *entry;
117 
118  Route& routeToUpdate = *(entryCopy.findRoute(route));
119 
120  routeToUpdate.flags = route.flags;
121  routeToUpdate.cost = route.cost;
122  routeToUpdate.expires = route.expires;
123 
124  createFibUpdatesForUpdatedRoute(entryCopy, route, *existingRoute);
125  }
126  }
127  else {
128  // New name in RIB
129  // Find prefix's parent
130  shared_ptr<RibEntry> parent = m_rib.findParent(prefix);
131 
132  Rib::RibEntryList descendants = m_rib.findDescendantsForNonInsertedName(prefix);
133  Rib::RibEntryList children;
134 
135  for (const auto& descendant : descendants) {
136  // If the child has the same parent as the new entry,
137  // the new entry must be the child's new parent
138  if (descendant->getParent() == parent) {
139  children.push_back(descendant);
140  }
141  }
142 
143  createFibUpdatesForNewRibEntry(prefix, route, children);
144  }
145 }
146 
147 void
148 FibUpdater::computeUpdatesForUnregistration(const RibUpdate& update)
149 {
150  const Name& prefix = update.getName();
151  const Route& route = update.getRoute();
152 
153  Rib::const_iterator ribIt = m_rib.find(prefix);
154 
155  // Name prefix exists
156  if (ribIt != m_rib.end()) {
157  shared_ptr<const RibEntry> entry(ribIt->second);
158 
159  const bool hadCapture = entry->hasCapture();
160 
161  RibEntry::const_iterator existing = entry->findRoute(route);
162 
163  if (existing != entry->end()) {
164  RibEntry temp = *entry;
165 
166  // Erase route in temp entry
167  temp.eraseRoute(route);
168 
169  const bool captureWasTurnedOff = (hadCapture && !temp.hasCapture());
170 
171  createFibUpdatesForErasedRoute(temp, *existing, captureWasTurnedOff);
172 
173  // The RibEntry still has the face ID; need to update FIB
174  // with lowest cost for the same face instead of removing the face from the FIB
175  const Route* next = entry->getRouteWithSecondLowestCostByFaceId(route.faceId);
176 
177  if (next != nullptr) {
178  createFibUpdatesForNewRoute(temp, *next, false);
179  }
180 
181  // The RibEntry will be empty after this removal
182  if (entry->getNRoutes() == 1) {
183  createFibUpdatesForErasedRibEntry(*entry);
184  }
185  }
186  }
187 }
188 
189 void
190 FibUpdater::sendUpdates(const FibUpdateList& updates,
191  const FibUpdateSuccessCallback& onSuccess,
192  const FibUpdateFailureCallback& onFailure)
193 {
194  std::string updateString = (updates.size() == 1) ? " update" : " updates";
195  NFD_LOG_DEBUG("Applying " << updates.size() << updateString << " to FIB");
196 
197  for (const FibUpdate& update : updates) {
198  NFD_LOG_DEBUG("Sending FIB update: " << update);
199 
200  if (update.action == FibUpdate::ADD_NEXTHOP) {
201  sendAddNextHopUpdate(update, onSuccess, onFailure);
202  }
203  else if (update.action == FibUpdate::REMOVE_NEXTHOP) {
204  sendRemoveNextHopUpdate(update, onSuccess, onFailure);
205  }
206  }
207 }
208 
209 void
210 FibUpdater::sendUpdatesForBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
211  const FibUpdateFailureCallback& onFailure)
212 {
213  if (m_updatesForBatchFaceId.size() > 0) {
214  sendUpdates(m_updatesForBatchFaceId, onSuccess, onFailure);
215  }
216  else {
217  sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
218  }
219 }
220 
221 void
222 FibUpdater::sendUpdatesForNonBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
223  const FibUpdateFailureCallback& onFailure)
224 {
225  if (m_updatesForNonBatchFaceId.size() > 0) {
226  sendUpdates(m_updatesForNonBatchFaceId, onSuccess, onFailure);
227  }
228  else {
229  onSuccess(m_inheritedRoutes);
230  }
231 }
232 
233 void
234 FibUpdater::sendAddNextHopUpdate(const FibUpdate& update,
235  const FibUpdateSuccessCallback& onSuccess,
236  const FibUpdateFailureCallback& onFailure,
237  uint32_t nTimeouts)
238 {
239  m_controller.start<ndn::nfd::FibAddNextHopCommand>(
240  ControlParameters()
241  .setName(update.name)
242  .setFaceId(update.faceId)
243  .setCost(update.cost),
244  bind(&FibUpdater::onUpdateSuccess, this, update, onSuccess, onFailure),
245  bind(&FibUpdater::onUpdateError, this, update, onSuccess, onFailure, _1, nTimeouts));
246 }
247 
248 void
249 FibUpdater::sendRemoveNextHopUpdate(const FibUpdate& update,
250  const FibUpdateSuccessCallback& onSuccess,
251  const FibUpdateFailureCallback& onFailure,
252  uint32_t nTimeouts)
253 {
254  m_controller.start<ndn::nfd::FibRemoveNextHopCommand>(
255  ControlParameters()
256  .setName(update.name)
257  .setFaceId(update.faceId),
258  bind(&FibUpdater::onUpdateSuccess, this, update, onSuccess, onFailure),
259  bind(&FibUpdater::onUpdateError, this, update, onSuccess, onFailure, _1, nTimeouts));
260 }
261 
262 void
263 FibUpdater::onUpdateSuccess(const FibUpdate update,
264  const FibUpdateSuccessCallback& onSuccess,
265  const FibUpdateFailureCallback& onFailure)
266 {
267  if (update.faceId == m_batchFaceId) {
268  m_updatesForBatchFaceId.remove(update);
269 
270  if (m_updatesForBatchFaceId.size() == 0) {
271  sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
272  }
273  }
274  else {
275  m_updatesForNonBatchFaceId.remove(update);
276 
277  if (m_updatesForNonBatchFaceId.size() == 0) {
278  onSuccess(m_inheritedRoutes);
279  }
280  }
281 }
282 
283 void
284 FibUpdater::onUpdateError(const FibUpdate update,
285  const FibUpdateSuccessCallback& onSuccess,
286  const FibUpdateFailureCallback& onFailure,
287  const ndn::nfd::ControlResponse& response, uint32_t nTimeouts)
288 {
289  uint32_t code = response.getCode();
290  NFD_LOG_DEBUG("Failed to apply " << update <<
291  " (code: " << code << ", error: " << response.getText() << ")");
292 
293  if (code == ndn::nfd::Controller::ERROR_TIMEOUT && nTimeouts < MAX_NUM_TIMEOUTS) {
294  sendAddNextHopUpdate(update, onSuccess, onFailure, ++nTimeouts);
295  }
296  else if (code == ERROR_FACE_NOT_FOUND) {
297  if (update.faceId == m_batchFaceId) {
298  onFailure(code, response.getText());
299  }
300  else {
301  m_updatesForNonBatchFaceId.remove(update);
302 
303  if (m_updatesForNonBatchFaceId.size() == 0) {
304  onSuccess(m_inheritedRoutes);
305  }
306  }
307  }
308  else {
309  BOOST_THROW_EXCEPTION(Error("Non-recoverable error: " + response.getText() +
310  " code: " + to_string(code)));
311  }
312 }
313 
314 void
315 FibUpdater::addFibUpdate(FibUpdate update)
316 {
317  FibUpdateList& updates = (update.faceId == m_batchFaceId) ? m_updatesForBatchFaceId :
318  m_updatesForNonBatchFaceId;
319 
320  // If an update with the same name and route already exists,
321  // replace it
322  FibUpdateList::iterator it = std::find_if(updates.begin(), updates.end(),
323  [&update] (const FibUpdate& other) {
324  return update.name == other.name && update.faceId == other.faceId;
325  });
326 
327  if (it != updates.end()) {
328  FibUpdate& existingUpdate = *it;
329  existingUpdate.action = update.action;
330  existingUpdate.cost = update.cost;
331  }
332  else {
333  updates.push_back(update);
334  }
335 }
336 
337 void
338 FibUpdater::addInheritedRoutes(const RibEntry& entry, const Rib::RouteSet& routesToAdd)
339 {
340  for (const Route& route : routesToAdd) {
341  // Don't add an ancestor faceId if the namespace has an entry for that faceId
342  if (!entry.hasFaceId(route.faceId)) {
343  // Create a record of the inherited route so it can be added to the RIB later
344  addInheritedRoute(entry.getName(), route);
345 
346  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
347  }
348  }
349 }
350 
351 void
352 FibUpdater::addInheritedRoutes(const Name& name, const Rib::RouteSet& routesToAdd,
353  const Route& ignore)
354 {
355  for (const Route& route : routesToAdd) {
356  if (route.faceId != ignore.faceId) {
357  // Create a record of the inherited route so it can be added to the RIB later
358  addInheritedRoute(name, route);
359 
360  addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));
361  }
362  }
363 }
364 
365 void
366 FibUpdater::removeInheritedRoutes(const RibEntry& entry, const Rib::Rib::RouteSet& routesToRemove)
367 {
368  for (const Route& route : routesToRemove) {
369  // Only remove if the route has been inherited
370  if (entry.hasInheritedRoute(route)) {
371  removeInheritedRoute(entry.getName(), route);
372  addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
373  }
374  }
375 }
376 
377 void
378 FibUpdater::createFibUpdatesForNewRibEntry(const Name& name, const Route& route,
379  const Rib::RibEntryList& children)
380 {
381  // Create FIB update for new entry
382  addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));
383 
384  // No flags are set
385  if (!route.isChildInherit() && !route.isRibCapture()) {
386  // Add ancestor routes to self
387  addInheritedRoutes(name, m_rib.getAncestorRoutes(name), route);
388  }
389  else if (route.isChildInherit() && route.isRibCapture()) {
390  // Add route to children
391  Rib::RouteSet routesToAdd;
392  routesToAdd.insert(route);
393 
394  // Remove routes blocked by capture and add self to children
395  modifyChildrensInheritedRoutes(children, routesToAdd, m_rib.getAncestorRoutes(name));
396  }
397  else if (route.isChildInherit()) {
398  Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(name);
399 
400  // Add ancestor routes to self
401  addInheritedRoutes(name, ancestorRoutes, route);
402 
403  // If there is an ancestor route which is the same as the new route, replace it
404  // with the new route
405  Rib::RouteSet::iterator it = ancestorRoutes.find(route);
406 
407  // There is a route that needs to be overwritten, erase and then replace
408  if (it != ancestorRoutes.end()) {
409  ancestorRoutes.erase(it);
410  }
411 
412  // Add new route to ancestor list so it can be added to children
413  ancestorRoutes.insert(route);
414 
415  // Add ancestor routes to children
416  modifyChildrensInheritedRoutes(children, ancestorRoutes, Rib::RouteSet());
417  }
418  else if (route.isRibCapture()) {
419  // Remove routes blocked by capture
420  modifyChildrensInheritedRoutes(children, Rib::RouteSet(), m_rib.getAncestorRoutes(name));
421  }
422 }
423 
424 void
425 FibUpdater::createFibUpdatesForNewRoute(const RibEntry& entry, const Route& route,
426  bool captureWasTurnedOn)
427 {
428  // Only update if the new route has a lower cost than a previously installed route
429  const Route* prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
430 
431  Rib::RouteSet routesToAdd;
432  if (route.isChildInherit()) {
433  // Add to children if this new route doesn't override a previous lower cost, or
434  // add to children if this new route is lower cost than a previous route.
435  // Less than equal, since entry may find this route
436  if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
437  // Add self to children
438  routesToAdd.insert(route);
439  }
440  }
441 
442  Rib::RouteSet routesToRemove;
443  if (captureWasTurnedOn) {
444  // Capture flag on
445  routesToRemove = m_rib.getAncestorRoutes(entry);
446 
447  // Remove ancestor routes from self
448  removeInheritedRoutes(entry, routesToRemove);
449  }
450 
451  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
452 
453  // If another route with same faceId and lower cost exists, don't update.
454  // Must be done last so that add updates replace removal updates
455  // Create FIB update for new entry
456  const Route* other = entry.getRouteWithLowestCostByFaceId(route.faceId);
457 
458  if (other == nullptr || route.cost <= other->cost) {
459  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
460  }
461 }
462 
463 void
464 FibUpdater::createFibUpdatesForUpdatedRoute(const RibEntry& entry, const Route& route,
465  const Route& existingRoute)
466 {
467  const bool costDidChange = (route.cost != existingRoute.cost);
468 
469  // Look for an installed route with the lowest cost and child inherit set
470  const Route* prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
471 
472  // No flags changed and cost didn't change, no change in FIB
473  if (route.flags == existingRoute.flags && !costDidChange) {
474  return;
475  }
476 
477  // Cost changed so create update for the entry itself
478  if (costDidChange) {
479  // Create update if this route's cost is lower than other routes
480  if (route.cost <= entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
481  // Create FIB update for the updated entry
482  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
483  }
484  else if (existingRoute.cost < entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
485  // Create update if this route used to be the lowest route but is no longer
486  // the lowest cost route.
487  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevRoute->faceId, prevRoute->cost));
488  }
489 
490  // If another route with same faceId and lower cost and ChildInherit exists,
491  // don't update children.
492  if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
493  // If no flags changed but child inheritance is set, need to update children
494  // with new cost
495  if ((route.flags == existingRoute.flags) && route.isChildInherit()) {
496  // Add self to children
497  Rib::RouteSet routesToAdd;
498  routesToAdd.insert(route);
499  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
500 
501  return;
502  }
503  }
504  }
505 
506  // Child inherit was turned on
507  if (!existingRoute.isChildInherit() && route.isChildInherit()) {
508  // If another route with same faceId and lower cost and ChildInherit exists,
509  // don't update children.
510  if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
511  // Add self to children
512  Rib::RouteSet routesToAdd;
513  routesToAdd.insert(route);
514  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
515  }
516  } // Child inherit was turned off
517  else if (existingRoute.isChildInherit() && !route.isChildInherit()) {
518  // Remove self from children
519  Rib::RouteSet routesToRemove;
520  routesToRemove.insert(route);
521 
522  Rib::RouteSet routesToAdd;
523  // If another route with same faceId and ChildInherit exists, update children with this route.
524  if (prevRoute != nullptr) {
525  routesToAdd.insert(*prevRoute);
526  }
527  else {
528  // Look for an ancestor that was blocked previously
529  const Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
530  Rib::RouteSet::iterator it = ancestorRoutes.find(route);
531 
532  // If an ancestor is found, add it to children
533  if (it != ancestorRoutes.end()) {
534  routesToAdd.insert(*it);
535  }
536  }
537 
538  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
539  }
540 
541  // Capture was turned on
542  if (!existingRoute.isRibCapture() && route.isRibCapture()) {
543  Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
544 
545  // Remove ancestor routes from self
546  removeInheritedRoutes(entry, ancestorRoutes);
547 
548  // Remove ancestor routes from children
549  modifyChildrensInheritedRoutes(entry.getChildren(), Rib::RouteSet(), ancestorRoutes);
550  } // Capture was turned off
551  else if (existingRoute.isRibCapture() && !route.isRibCapture()) {
552  Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
553 
554  // Add ancestor routes to self
555  addInheritedRoutes(entry, ancestorRoutes);
556 
557  // Add ancestor routes to children
558  modifyChildrensInheritedRoutes(entry.getChildren(), ancestorRoutes, Rib::RouteSet());
559  }
560 }
561 
562 void
563 FibUpdater::createFibUpdatesForErasedRoute(const RibEntry& entry, const Route& route,
564  const bool captureWasTurnedOff)
565 {
566  addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
567 
568  if (route.isChildInherit() && route.isRibCapture()) {
569  // Remove self from children
570  Rib::RouteSet routesToRemove;
571  routesToRemove.insert(route);
572 
573  // If capture is turned off for the route and another route is installed in the RibEntry,
574  // add ancestors to self
575  Rib::RouteSet routesToAdd;
576  if (captureWasTurnedOff && entry.getNRoutes() != 0) {
577  // Look for an ancestors that were blocked previously
578  routesToAdd = m_rib.getAncestorRoutes(entry);
579 
580  // Add ancestor routes to self
581  addInheritedRoutes(entry, routesToAdd);
582  }
583 
584  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
585  }
586  else if (route.isChildInherit()) {
587  // If not blocked by capture, add inherited routes to children
588  Rib::RouteSet routesToAdd;
589  if (!entry.hasCapture()) {
590  routesToAdd = m_rib.getAncestorRoutes(entry);
591  }
592 
593  Rib::RouteSet routesToRemove;
594  routesToRemove.insert(route);
595 
596  // Add ancestor routes to children
597  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
598  }
599  else if (route.isRibCapture()) {
600  // If capture is turned off for the route and another route is installed in the RibEntry,
601  // add ancestors to self
602  Rib::RouteSet routesToAdd;
603  if (captureWasTurnedOff && entry.getNRoutes() != 0) {
604  // Look for an ancestors that were blocked previously
605  routesToAdd = m_rib.getAncestorRoutes(entry);
606 
607  // Add ancestor routes to self
608  addInheritedRoutes(entry, routesToAdd);
609  }
610 
611  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
612  }
613 
614  // Need to check if the removed route was blocking an inherited route
615  Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
616 
617  // If the current entry has capture set or is pending removal, don't add inherited route
618  if (!entry.hasCapture() && entry.getNRoutes() != 0) {
619  // If there is an ancestor route which is the same as the erased route, add that route
620  // to the current entry
621  Rib::RouteSet::iterator it = ancestorRoutes.find(route);
622 
623  if (it != ancestorRoutes.end()) {
624  addInheritedRoute(entry.getName(), *it);
625  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
626  }
627  }
628 }
629 
630 void
631 FibUpdater::createFibUpdatesForErasedRibEntry(const RibEntry& entry)
632 {
633  for (const Route& route : entry.getInheritedRoutes()) {
634  addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
635  }
636 }
637 
638 void
639 FibUpdater::modifyChildrensInheritedRoutes(const Rib::RibEntryList& children,
640  const Rib::RouteSet& routesToAdd,
641  const Rib::RouteSet& routesToRemove)
642 {
643  for (const auto& child : children) {
644  traverseSubTree(*child, routesToAdd, routesToRemove);
645  }
646 }
647 
648 void
649 FibUpdater::traverseSubTree(const RibEntry& entry, Rib::Rib::RouteSet routesToAdd,
650  Rib::Rib::RouteSet routesToRemove)
651 {
652  // If a route on the namespace has the capture flag set, ignore self and children
653  if (entry.hasCapture()) {
654  return;
655  }
656 
657  // Remove inherited routes from current namespace
658  for (Rib::RouteSet::const_iterator removeIt = routesToRemove.begin();
659  removeIt != routesToRemove.end(); )
660  {
661  // If a route on the namespace has the same face ID and child inheritance set,
662  // ignore this route
663  if (entry.hasChildInheritOnFaceId(removeIt->faceId)) {
664  routesToRemove.erase(removeIt++);
665  continue;
666  }
667 
668  // Only remove route if it removes an existing inherited route
669  if (entry.hasInheritedRoute(*removeIt)) {
670  removeInheritedRoute(entry.getName(), *removeIt);
671  addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
672  }
673 
674  ++removeIt;
675  }
676 
677  // Add inherited routes to current namespace
678  for (Rib::RouteSet::const_iterator addIt = routesToAdd.begin(); addIt != routesToAdd.end(); ) {
679 
680  // If a route on the namespace has the same face ID and child inherit set, ignore this face
681  if (entry.hasChildInheritOnFaceId(addIt->faceId)) {
682  routesToAdd.erase(addIt++);
683  continue;
684  }
685 
686  // Only add route if it does not override an existing route
687  if (!entry.hasFaceId(addIt->faceId)) {
688  addInheritedRoute(entry.getName(), *addIt);
689  addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
690  }
691 
692  ++addIt;
693  }
694 
695  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
696 }
697 
698 void
699 FibUpdater::addInheritedRoute(const Name& name, const Route& route)
700 {
701  RibUpdate update;
703  .setName(name)
704  .setRoute(route);
705 
706  m_inheritedRoutes.push_back(update);
707 }
708 
709 void
710 FibUpdater::removeInheritedRoute(const Name& name, const Route& route)
711 {
712  RibUpdate update;
714  .setName(name)
715  .setRoute(route);
716 
717  m_inheritedRoutes.push_back(update);
718 }
719 
720 } // namespace rib
721 } // namespace nfd
std::list< FibUpdate > FibUpdateList
Definition: fib-updater.hpp:55
void eraseRoute(const Route &route)
erases a Route with the same faceId and origin
Definition: rib-entry.cpp:69
uint64_t faceId
Definition: route.hpp:63
RibUpdate & setRoute(const Route &route)
Definition: rib-update.hpp:107
uint64_t cost
Definition: route.hpp:65
represents the Routing Information Base
Definition: rib.hpp:59
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:161
std::set< Route, RouteComparePredicate > RouteSet
Definition: rib.hpp:67
RibUpdate & setAction(Action action)
Definition: rib-update.hpp:81
An update triggered by a face destruction notification.
Definition: rib-update.hpp:51
const_iterator find(const Name &prefix) const
Definition: rib.cpp:66
function< void(RibUpdateList inheritedRoutes)> FibUpdateSuccessCallback
Definition: fib-updater.hpp:57
const Name & getName() const
Definition: rib-update.hpp:101
std::list< shared_ptr< RibEntry > > findDescendantsForNonInsertedName(const Name &prefix) const
finds namespaces under the passed prefix
Definition: rib.cpp:249
represents a collection of RibUpdates to be applied to a single FaceId
void setFibUpdater(FibUpdater *updater)
Definition: rib.cpp:60
const_iterator end() const
Definition: rib.hpp:275
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
Table::const_iterator iterator
Definition: cs-internal.hpp:41
RibUpdate & setName(const Name &name)
Definition: rib-update.hpp:94
static FibUpdate createAddUpdate(const Name &name, const uint64_t faceId, const uint64_t cost)
Definition: fib-update.cpp:32
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
const Name & getName() const
Definition: rib-entry.hpp:205
const std::list< shared_ptr< RibEntry > > & getChildren() const
Definition: rib-entry.hpp:223
std::list< shared_ptr< RibEntry > > RibEntryList
Definition: rib.hpp:62
represents a route for a name prefix
Definition: route.hpp:39
RouteList::const_iterator const_iterator
Definition: rib-entry.hpp:41
bool hasInheritedRoute(const Route &route) const
Determines if the entry has an inherited route with a matching face ID.
Definition: rib-entry.cpp:153
FibUpdater(Rib &rib, ndn::nfd::Controller &controller)
Definition: fib-updater.cpp:42
uint64_t getFaceId() const
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
ndn::optional< time::steady_clock::TimePoint > expires
Definition: route.hpp:67
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:167
const Route & getRoute() const
Definition: rib-update.hpp:114
represents a FIB update
Definition: fib-update.hpp:37
RibTable::const_iterator const_iterator
Definition: rib.hpp:64
represents a RIB entry, which contains one or more Routes with the same prefix
Definition: rib-entry.hpp:36
bool hasCapture() const
Definition: rib-entry.cpp:161
function< void(uint32_t code, const std::string &error)> FibUpdateFailureCallback
Definition: fib-updater.hpp:58
size_t getNRoutes() const
Definition: rib-entry.cpp:92
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:225
iterator findRoute(const Route &route)
Definition: rib-entry.cpp:38
bool hasFaceId(const uint64_t faceId) const
Definition: rib-entry.cpp:84
static FibUpdate createRemoveUpdate(const Name &name, const uint64_t faceId)
Definition: fib-update.cpp:45
const Route * getRouteWithLowestCostByFaceId(uint64_t faceId) const
Returns the route with the lowest cost that has the passed face ID.
Definition: rib-entry.cpp:179
const RouteList & getInheritedRoutes() const
Returns the routes this namespace has inherited.
Definition: rib-entry.hpp:235
shared_ptr< RibEntry > findParent(const Name &prefix) const
Definition: rib.cpp:213
std::underlying_type< ndn::nfd::RouteFlags >::type flags
Definition: route.hpp:66