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