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