rib: Perform FIB updates before modifying RIB
refs: #1941
Change-Id: I1457f71ddd1c120daae48308d5cc02a7c0ecf93d
diff --git a/rib/fib-update.cpp b/rib/fib-update.cpp
index cda4f14..25e2a62 100644
--- a/rib/fib-update.cpp
+++ b/rib/fib-update.cpp
@@ -1,12 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -28,27 +28,27 @@
namespace nfd {
namespace rib {
-shared_ptr<FibUpdate>
+FibUpdate
FibUpdate::createAddUpdate(const Name& name, const uint64_t faceId, const uint64_t cost)
{
- shared_ptr<FibUpdate> update = make_shared<FibUpdate>();
+ FibUpdate update;
- update->name = name;
- update->faceId = faceId;
- update->cost = cost;
- update->action = ADD_NEXTHOP;
+ update.name = name;
+ update.faceId = faceId;
+ update.cost = cost;
+ update.action = ADD_NEXTHOP;
return update;
}
-shared_ptr<FibUpdate>
+FibUpdate
FibUpdate::createRemoveUpdate(const Name& name, const uint64_t faceId)
{
- shared_ptr<FibUpdate> update = make_shared<FibUpdate>();
+ FibUpdate update;
- update->name = name;
- update->faceId = faceId;
- update->action = REMOVE_NEXTHOP;
+ update.name = name;
+ update.faceId = faceId;
+ update.action = REMOVE_NEXTHOP;
return update;
}
diff --git a/rib/fib-update.hpp b/rib/fib-update.hpp
index 02713ab..589871a 100644
--- a/rib/fib-update.hpp
+++ b/rib/fib-update.hpp
@@ -1,12 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -43,14 +43,22 @@
{
}
- static shared_ptr<FibUpdate>
+ bool
+ operator==(const FibUpdate& other) const
+ {
+ return (this->name == other.name &&
+ this->faceId == other.faceId &&
+ this->cost == other.cost &&
+ this->action == other.action);
+ }
+
+ static FibUpdate
createAddUpdate(const Name& name, const uint64_t faceId, const uint64_t cost);
- static shared_ptr<FibUpdate>
+ static FibUpdate
createRemoveUpdate(const Name& name, const uint64_t faceId);
- enum Action
- {
+ enum Action {
ADD_NEXTHOP = 0,
REMOVE_NEXTHOP = 1
};
@@ -69,15 +77,13 @@
<< " Name: " << update.name << ", "
<< "faceId: " << update.faceId << ", ";
- if (update.action == FibUpdate::ADD_NEXTHOP)
- {
- os << "cost: " << update.cost << ", "
- << "action: ADD_NEXTHOP";
- }
- else
- {
- os << "action: REMOVE_NEXTHOP";
- }
+ if (update.action == FibUpdate::ADD_NEXTHOP) {
+ os << "cost: " << update.cost << ", "
+ << "action: ADD_NEXTHOP";
+ }
+ else {
+ os << "action: REMOVE_NEXTHOP";
+ }
os << ")";
diff --git a/rib/fib-updater.cpp b/rib/fib-updater.cpp
new file mode 100644
index 0000000..212bccf
--- /dev/null
+++ b/rib/fib-updater.cpp
@@ -0,0 +1,720 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "fib-updater.hpp"
+
+#include "core/logger.hpp"
+
+#include <ndn-cxx/management/nfd-control-parameters.hpp>
+
+namespace nfd {
+namespace rib {
+
+using ndn::nfd::ControlParameters;
+
+NFD_LOG_INIT("FibUpdater");
+
+const unsigned int FibUpdater::MAX_NUM_TIMEOUTS = 10;
+const uint32_t FibUpdater::ERROR_FACE_NOT_FOUND = 410;
+
+FibUpdater::FibUpdater(Rib& rib, ndn::nfd::Controller& controller)
+ : m_rib(rib)
+ , m_controller(controller)
+{
+ rib.setFibUpdater(this);
+}
+
+void
+FibUpdater::computeAndSendFibUpdates(const RibUpdateBatch& batch,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure)
+{
+ m_batchFaceId = batch.getFaceId();
+
+ // Erase previously calculated inherited routes
+ m_inheritedRoutes.clear();
+
+ // Erase previously calculated FIB updates
+ m_updatesForBatchFaceId.clear();
+ m_updatesForNonBatchFaceId.clear();
+
+ computeUpdates(batch);
+
+ sendUpdatesForBatchFaceId(onSuccess, onFailure);
+}
+
+void
+FibUpdater::computeUpdates(const RibUpdateBatch& batch)
+{
+ NFD_LOG_DEBUG("Computing updates for batch with faceID: " << batch.getFaceId());
+
+ // Compute updates and add to m_fibUpdates
+ for (const RibUpdate& update : batch)
+ {
+ switch(update.getAction()) {
+ case RibUpdate::REGISTER:
+ computeUpdatesForRegistration(update);
+ break;
+ case RibUpdate::UNREGISTER:
+ computeUpdatesForUnregistration(update);
+ break;
+ case RibUpdate::REMOVE_FACE:
+ computeUpdatesForUnregistration(update);
+
+ // Do not apply updates with the same face ID as the destroyed face
+ // since they will be rejected by the FIB
+ m_updatesForBatchFaceId.clear();
+ break;
+ }
+ }
+}
+
+void
+FibUpdater::computeUpdatesForRegistration(const RibUpdate& update)
+{
+ const Name& prefix = update.getName();
+ const Route& route = update.getRoute();
+
+ Rib::const_iterator it = m_rib.find(prefix);
+
+ // Name prefix exists
+ if (it != m_rib.end()) {
+ shared_ptr<const RibEntry> entry(it->second);
+
+ RibEntry::const_iterator existingRoute = entry->findRoute(route);
+
+ // Route will be new
+ if (existingRoute == entry->end()) {
+ // Will the new route change the namespace's capture flag?
+ bool willCaptureBeTurnedOn = (entry->hasCapture() == false && route.isCapture());
+
+ createFibUpdatesForNewRoute(*entry, route, willCaptureBeTurnedOn);
+ }
+ else {
+ // Route already exists
+ RibEntry entryCopy = *entry;
+
+ Route& routeToUpdate = *(entryCopy.findRoute(route));
+
+ routeToUpdate.flags = route.flags;
+ routeToUpdate.cost = route.cost;
+ routeToUpdate.expires = route.expires;
+
+ createFibUpdatesForUpdatedRoute(entryCopy, route, *existingRoute);
+ }
+ }
+ else {
+ // New name in RIB
+ // Find prefix's parent
+ shared_ptr<RibEntry> parent = m_rib.findParent(prefix);
+
+ Rib::RibEntryList descendants = m_rib.findDescendantsForNonInsertedName(prefix);
+ Rib::RibEntryList children;
+
+ for (const auto& descendant : descendants) {
+ // If the child has the same parent as the new entry,
+ // the new entry must be the child's new parent
+ if (descendant->getParent() == parent) {
+ children.push_back(descendant);
+ }
+ }
+
+ createFibUpdatesForNewRibEntry(prefix, route, children);
+ }
+}
+
+void
+FibUpdater::computeUpdatesForUnregistration(const RibUpdate& update)
+{
+ const Name& prefix = update.getName();
+ const Route& route = update.getRoute();
+
+ Rib::const_iterator ribIt = m_rib.find(prefix);
+
+ // Name prefix exists
+ if (ribIt != m_rib.end()) {
+ shared_ptr<const RibEntry> entry(ribIt->second);
+
+ const bool hadCapture = entry->hasCapture();
+
+ RibEntry::const_iterator existing = entry->findRoute(route);
+
+ if (existing != entry->end()) {
+ RibEntry temp = *entry;
+
+ // Erase route in temp entry
+ temp.eraseRoute(route);
+
+ const bool captureWasTurnedOff = (hadCapture && !temp.hasCapture());
+
+ createFibUpdatesForErasedRoute(temp, *existing, captureWasTurnedOff);
+
+ // The RibEntry still has the face ID; need to update FIB
+ // with lowest cost for the same face instead of removing the face from the FIB
+ const Route* next = entry->getRouteWithSecondLowestCostByFaceId(route.faceId);
+
+ if (next != nullptr) {
+ createFibUpdatesForNewRoute(temp, *next, false);
+ }
+
+ // The RibEntry will be empty after this removal
+ if (entry->getNRoutes() == 1) {
+ createFibUpdatesForErasedRibEntry(*entry);
+ }
+ }
+ }
+}
+
+void
+FibUpdater::sendUpdates(const FibUpdateList& updates,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure)
+{
+ std::string updateString = (updates.size() == 1) ? " update" : " updates";
+ NFD_LOG_DEBUG("Applying " << updates.size() << updateString << " to FIB");
+
+ for (const FibUpdate& update : updates) {
+ NFD_LOG_DEBUG("Sending FIB update: " << update);
+
+ if (update.action == FibUpdate::ADD_NEXTHOP) {
+ sendAddNextHopUpdate(update, onSuccess, onFailure);
+ }
+ else if (update.action == FibUpdate::REMOVE_NEXTHOP) {
+ sendRemoveNextHopUpdate(update, onSuccess, onFailure);
+ }
+ }
+}
+
+void
+FibUpdater::sendUpdatesForBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure)
+{
+ if (m_updatesForBatchFaceId.size() > 0) {
+ sendUpdates(m_updatesForBatchFaceId, onSuccess, onFailure);
+ }
+ else {
+ sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
+ }
+}
+
+void
+FibUpdater::sendUpdatesForNonBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure)
+{
+ if (m_updatesForNonBatchFaceId.size() > 0) {
+ sendUpdates(m_updatesForNonBatchFaceId, onSuccess, onFailure);
+ }
+ else {
+ onSuccess(m_inheritedRoutes);
+ }
+}
+
+void
+FibUpdater::sendAddNextHopUpdate(const FibUpdate& update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t nTimeouts)
+{
+ m_controller.start<ndn::nfd::FibAddNextHopCommand>(
+ ControlParameters()
+ .setName(update.name)
+ .setFaceId(update.faceId)
+ .setCost(update.cost),
+ bind(&FibUpdater::onUpdateSuccess, this, update, onSuccess, onFailure),
+ bind(&FibUpdater::onUpdateError, this, update, onSuccess, onFailure, _1, _2, nTimeouts));
+}
+
+void
+FibUpdater::sendRemoveNextHopUpdate(const FibUpdate& update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t nTimeouts)
+{
+ m_controller.start<ndn::nfd::FibRemoveNextHopCommand>(
+ ControlParameters()
+ .setName(update.name)
+ .setFaceId(update.faceId),
+ bind(&FibUpdater::onUpdateSuccess, this, update, onSuccess, onFailure),
+ bind(&FibUpdater::onUpdateError, this, update, onSuccess, onFailure, _1, _2, nTimeouts));
+}
+
+void
+FibUpdater::onUpdateSuccess(const FibUpdate update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure)
+{
+ if (update.faceId == m_batchFaceId) {
+ m_updatesForBatchFaceId.remove(update);
+
+ if (m_updatesForBatchFaceId.size() == 0) {
+ sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
+ }
+ }
+ else {
+ m_updatesForNonBatchFaceId.remove(update);
+
+ if (m_updatesForNonBatchFaceId.size() == 0) {
+ onSuccess(m_inheritedRoutes);
+ }
+ }
+}
+
+void
+FibUpdater::onUpdateError(const FibUpdate update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t code, const std::string& error, uint32_t nTimeouts)
+{
+ NFD_LOG_DEBUG("Failed to apply " << update << " (code: " << code << ", error: " << error << ")");
+
+ if (code == ndn::nfd::Controller::ERROR_TIMEOUT && nTimeouts < MAX_NUM_TIMEOUTS) {
+ sendAddNextHopUpdate(update, onSuccess, onFailure, ++nTimeouts);
+ }
+ else if (code == ERROR_FACE_NOT_FOUND) {
+ if (update.faceId == m_batchFaceId) {
+ onFailure(code, error);
+ }
+ else {
+ m_updatesForNonBatchFaceId.remove(update);
+
+ if (m_updatesForNonBatchFaceId.size() == 0) {
+ onSuccess(m_inheritedRoutes);
+ }
+ }
+ }
+ else {
+ throw Error("Non-recoverable error: " + error + " code: " + std::to_string(code));
+ }
+}
+
+void
+FibUpdater::addFibUpdate(FibUpdate update)
+{
+ FibUpdateList& updates = (update.faceId == m_batchFaceId) ? m_updatesForBatchFaceId :
+ m_updatesForNonBatchFaceId;
+
+ // If an update with the same name and route already exists,
+ // replace it
+ FibUpdateList::iterator it = std::find_if(updates.begin(), updates.end(),
+ [&update] (const FibUpdate& other) {
+ return update.name == other.name && update.faceId == other.faceId;
+ });
+
+ if (it != updates.end()) {
+ FibUpdate& existingUpdate = *it;
+ existingUpdate.action = update.action;
+ existingUpdate.cost = update.cost;
+ }
+ else {
+ updates.push_back(update);
+ }
+}
+
+void
+FibUpdater::addInheritedRoutes(const RibEntry& entry, const Rib::Rib::RouteSet& routesToAdd)
+{
+ for (const Route& route : routesToAdd) {
+ // Don't add an ancestor faceId if the namespace has an entry for that faceId
+ if (!entry.hasFaceId(route.faceId)) {
+ // Create a record of the inherited route so it can be added to the RIB later
+ addInheritedRoute(entry.getName(), route);
+
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
+ }
+ }
+}
+
+void
+FibUpdater::addInheritedRoutes(const Name& name, const Rib::Rib::RouteSet& routesToAdd,
+ const Route& ignore)
+{
+ for (const Route& route : routesToAdd) {
+ if (route.faceId != ignore.faceId) {
+ // Create a record of the inherited route so it can be added to the RIB later
+ addInheritedRoute(name, route);
+
+ addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));
+ }
+ }
+}
+
+void
+FibUpdater::removeInheritedRoutes(const RibEntry& entry, const Rib::Rib::RouteSet& routesToRemove)
+{
+ for (const Route& route : routesToRemove) {
+ // Only remove if the route has been inherited
+ if (entry.hasInheritedRoute(route)) {
+ removeInheritedRoute(entry.getName(), route);
+ addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
+ }
+ }
+}
+
+void
+FibUpdater::createFibUpdatesForNewRibEntry(const Name& name, const Route& route,
+ const Rib::RibEntryList& children)
+{
+ // Create FIB update for new entry
+ addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));
+
+ // No flags are set
+ if (!route.isChildInherit() && !route.isCapture()) {
+ // Add ancestor routes to self
+ addInheritedRoutes(name, m_rib.getAncestorRoutes(name), route);
+ }
+ else if (route.isChildInherit() && route.isCapture()) {
+ // Add route to children
+ Rib::RouteSet routesToAdd;
+ routesToAdd.insert(route);
+
+ // Remove routes blocked by capture and add self to children
+ modifyChildrensInheritedRoutes(children, routesToAdd, m_rib.getAncestorRoutes(name));
+ }
+ else if (route.isChildInherit()) {
+ Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(name);
+
+ // Add ancestor routes to self
+ addInheritedRoutes(name, ancestorRoutes, route);
+
+ // If there is an ancestor route which is the same as the new route, replace it
+ // with the new route
+ Rib::RouteSet::iterator it = ancestorRoutes.find(route);
+
+ // There is a route that needs to be overwritten, erase and then replace
+ if (it != ancestorRoutes.end()) {
+ ancestorRoutes.erase(it);
+ }
+
+ // Add new route to ancestor list so it can be added to children
+ ancestorRoutes.insert(route);
+
+ // Add ancestor routes to children
+ modifyChildrensInheritedRoutes(children, ancestorRoutes, Rib::RouteSet());
+ }
+ else if (route.isCapture()) {
+ // Remove routes blocked by capture
+ modifyChildrensInheritedRoutes(children, Rib::RouteSet(), m_rib.getAncestorRoutes(name));
+ }
+}
+
+void
+FibUpdater::createFibUpdatesForNewRoute(const RibEntry& entry, const Route& route,
+ bool captureWasTurnedOn)
+{
+ // Only update if the new route has a lower cost than a previously installed route
+ shared_ptr<const Route> prevRoute =
+ entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
+
+ Rib::RouteSet routesToAdd;
+ if (route.isChildInherit()) {
+ // Add to children if this new route doesn't override a previous lower cost, or
+ // add to children if this new route is lower cost than a previous route.
+ // Less than equal, since entry may find this route
+ if (!static_cast<bool>(prevRoute) || route.cost <= prevRoute->cost) {
+ // Add self to children
+ routesToAdd.insert(route);
+ }
+ }
+
+ Rib::RouteSet routesToRemove;
+ if (captureWasTurnedOn) {
+ // Capture flag on
+ routesToRemove = m_rib.getAncestorRoutes(entry);
+
+ // Remove ancestor routes from self
+ removeInheritedRoutes(entry, routesToRemove);
+ }
+
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
+
+ // If another route with same faceId and lower cost exists, don't update.
+ // Must be done last so that add updates replace removal updates
+ // Create FIB update for new entry
+ shared_ptr<const Route> other = entry.getRouteWithLowestCostByFaceId(route.faceId);
+
+ if (!other || route.cost <= other->cost) {
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
+ }
+}
+
+void
+FibUpdater::createFibUpdatesForUpdatedRoute(const RibEntry& entry, const Route& route,
+ const Route& existingRoute)
+{
+ const bool costDidChange = (route.cost != existingRoute.cost);
+
+ // Look for an installed route with the lowest cost and child inherit set
+ shared_ptr<const Route> prevRoute =
+ entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
+
+ // No flags changed and cost didn't change, no change in FIB
+ if (route.flags == existingRoute.flags && !costDidChange) {
+ return;
+ }
+
+ // Cost changed so create update for the entry itself
+ if (costDidChange) {
+ // Create update if this route's cost is lower than other routes
+ if (route.cost <= entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
+ // Create FIB update for the updated entry
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
+ }
+ else if (existingRoute.cost < entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
+ // Create update if this route used to be the lowest route but is no longer
+ // the lowest cost route.
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevRoute->faceId, prevRoute->cost));
+ }
+
+ // If another route with same faceId and lower cost and ChildInherit exists,
+ // don't update children.
+ if (!static_cast<bool>(prevRoute) || route.cost <= prevRoute->cost) {
+ // If no flags changed but child inheritance is set, need to update children
+ // with new cost
+ if ((route.flags == existingRoute.flags) && route.isChildInherit()) {
+ // Add self to children
+ Rib::RouteSet routesToAdd;
+ routesToAdd.insert(route);
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
+
+ return;
+ }
+ }
+ }
+
+ // Child inherit was turned on
+ if (!existingRoute.isChildInherit() && route.isChildInherit()) {
+ // If another route with same faceId and lower cost and ChildInherit exists,
+ // don't update children.
+ if (!static_cast<bool>(prevRoute) || route.cost <= prevRoute->cost) {
+ // Add self to children
+ Rib::RouteSet routesToAdd;
+ routesToAdd.insert(route);
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
+ }
+ } // Child inherit was turned off
+ else if (existingRoute.isChildInherit() && !route.isChildInherit()) {
+ // Remove self from children
+ Rib::RouteSet routesToRemove;
+ routesToRemove.insert(route);
+
+ Rib::RouteSet routesToAdd;
+ // If another route with same faceId and ChildInherit exists, update children with this route.
+ if (static_cast<bool>(prevRoute)) {
+ routesToAdd.insert(*prevRoute);
+ }
+ else {
+ // Look for an ancestor that was blocked previously
+ const Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
+ Rib::RouteSet::iterator it = ancestorRoutes.find(route);
+
+ // If an ancestor is found, add it to children
+ if (it != ancestorRoutes.end()) {
+ routesToAdd.insert(*it);
+ }
+ }
+
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
+ }
+
+ // Capture was turned on
+ if (!existingRoute.isCapture() && route.isCapture()) {
+ Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
+
+ // Remove ancestor routes from self
+ removeInheritedRoutes(entry, ancestorRoutes);
+
+ // Remove ancestor routes from children
+ modifyChildrensInheritedRoutes(entry.getChildren(), Rib::RouteSet(), ancestorRoutes);
+ } // Capture was turned off
+ else if (existingRoute.isCapture() && !route.isCapture()) {
+ Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
+
+ // Add ancestor routes to self
+ addInheritedRoutes(entry, ancestorRoutes);
+
+ // Add ancestor routes to children
+ modifyChildrensInheritedRoutes(entry.getChildren(), ancestorRoutes, Rib::RouteSet());
+ }
+}
+
+void
+FibUpdater::createFibUpdatesForErasedRoute(const RibEntry& entry, const Route& route,
+ const bool captureWasTurnedOff)
+{
+ addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
+
+ if (route.isChildInherit() && route.isCapture()) {
+ // Remove self from children
+ Rib::RouteSet routesToRemove;
+ routesToRemove.insert(route);
+
+ // If capture is turned off for the route, need to add ancestors
+ // to self and children
+ Rib::RouteSet routesToAdd;
+ if (captureWasTurnedOff) {
+ // Look for an ancestors that were blocked previously
+ routesToAdd = m_rib.getAncestorRoutes(entry);
+
+ // Add ancestor routes to self
+ addInheritedRoutes(entry, routesToAdd);
+ }
+
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
+ }
+ else if (route.isChildInherit()) {
+ // If not blocked by capture, add inherited routes to children
+ Rib::RouteSet routesToAdd;
+ if (!entry.hasCapture()) {
+ routesToAdd = m_rib.getAncestorRoutes(entry);
+ }
+
+ Rib::RouteSet routesToRemove;
+ routesToRemove.insert(route);
+
+ // Add ancestor routes to children
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
+ }
+ else if (route.isCapture()) {
+ // If capture is turned off for the route, need to add ancestors
+ // to self and children
+ Rib::RouteSet routesToAdd;
+ if (captureWasTurnedOff) {
+ // Look for an ancestors that were blocked previously
+ routesToAdd = m_rib.getAncestorRoutes(entry);
+
+ // Add ancestor routes to self
+ addInheritedRoutes(entry, routesToAdd);
+ }
+
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
+ }
+
+ // Need to check if the removed route was blocking an inherited route
+ Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
+
+ if (!entry.hasCapture()) {
+ // If there is an ancestor route which is the same as the erased route, add that route
+ // to the current entry
+ Rib::RouteSet::iterator it = ancestorRoutes.find(route);
+
+ if (it != ancestorRoutes.end()) {
+ addInheritedRoute(entry.getName(), *it);
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
+ }
+ }
+}
+
+void
+FibUpdater::createFibUpdatesForErasedRibEntry(const RibEntry& entry)
+{
+ for (const Route& route : entry.getInheritedRoutes()) {
+ addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
+ }
+}
+
+void
+FibUpdater::modifyChildrensInheritedRoutes(const Rib::RibEntryList& children,
+ const Rib::RouteSet& routesToAdd,
+ const Rib::RouteSet& routesToRemove)
+{
+ for (const auto& child : children) {
+ traverseSubTree(*child, routesToAdd, routesToRemove);
+ }
+}
+
+void
+FibUpdater::traverseSubTree(const RibEntry& entry, Rib::Rib::RouteSet routesToAdd,
+ Rib::Rib::RouteSet routesToRemove)
+{
+ // If a route on the namespace has the capture flag set, ignore self and children
+ if (entry.hasCapture()) {
+ return;
+ }
+
+ // Remove inherited routes from current namespace
+ for (Rib::RouteSet::const_iterator removeIt = routesToRemove.begin();
+ removeIt != routesToRemove.end(); )
+ {
+ // If a route on the namespace has the same face ID and child inheritance set,
+ // ignore this route
+ if (entry.hasChildInheritOnFaceId(removeIt->faceId)) {
+ routesToRemove.erase(removeIt++);
+ continue;
+ }
+
+ // Only remove route if it removes an existing inherited route
+ if (entry.hasInheritedRoute(*removeIt)) {
+ removeInheritedRoute(entry.getName(), *removeIt);
+ addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
+ }
+
+ ++removeIt;
+ }
+
+ // Add inherited routes to current namespace
+ for (Rib::RouteSet::const_iterator addIt = routesToAdd.begin(); addIt != routesToAdd.end(); ) {
+
+ // If a route on the namespace has the same face ID and child inherit set, ignore this face
+ if (entry.hasChildInheritOnFaceId(addIt->faceId)) {
+ routesToAdd.erase(addIt++);
+ continue;
+ }
+
+ // Only add route if it does not override an existing route
+ if (!entry.hasFaceId(addIt->faceId)) {
+ addInheritedRoute(entry.getName(), *addIt);
+ addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
+ }
+
+ ++addIt;
+ }
+
+ modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
+}
+
+void
+FibUpdater::addInheritedRoute(const Name& name, const Route& route)
+{
+ RibUpdate update;
+ update.setAction(RibUpdate::REGISTER)
+ .setName(name)
+ .setRoute(route);
+
+ m_inheritedRoutes.push_back(update);
+}
+
+void
+FibUpdater::removeInheritedRoute(const Name& name, const Route& route)
+{
+ RibUpdate update;
+ update.setAction(RibUpdate::UNREGISTER)
+ .setName(name)
+ .setRoute(route);
+
+ m_inheritedRoutes.push_back(update);
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/fib-updater.hpp b/rib/fib-updater.hpp
new file mode 100644
index 0000000..bfa0901
--- /dev/null
+++ b/rib/fib-updater.hpp
@@ -0,0 +1,279 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_RIB_FIB_UPDATER_HPP
+#define NFD_RIB_FIB_UPDATER_HPP
+
+#include "common.hpp"
+#include "fib-update.hpp"
+#include "rib.hpp"
+#include "rib-update-batch.hpp"
+
+#include <ndn-cxx/management/nfd-controller.hpp>
+
+namespace nfd {
+namespace rib {
+
+/** \brief computes FibUpdates based on updates to the RIB and sends them to NFD
+ */
+class FibUpdater : noncopyable
+{
+public:
+ class Error : public std::runtime_error
+ {
+ public:
+ explicit
+ Error(const std::string& what)
+ : std::runtime_error(what)
+ {
+ }
+ };
+
+public:
+ typedef std::list<FibUpdate> FibUpdateList;
+
+ typedef function<void(RibUpdateList inheritedRoutes)> FibUpdateSuccessCallback;
+ typedef function<void(uint32_t code, const std::string& error)> FibUpdateFailureCallback;
+
+ FibUpdater(Rib& rib, ndn::nfd::Controller& controller);
+
+ /** \brief computes FibUpdates using the provided RibUpdateBatch and then sends the
+ * updates to NFD's FIB
+ *
+ * \note Caller must guarantee that the previous batch has either succeeded or failed
+ * before calling this method
+ */
+ void
+ computeAndSendFibUpdates(const RibUpdateBatch& batch,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure);
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /** \brief determines the type of action that will be performed on the RIB and calls the
+ * corresponding computation method
+ */
+ void
+ computeUpdates(const RibUpdateBatch& batch);
+
+ /** \brief sends the passed updates to NFD
+ *
+ * onSuccess or onFailure will be called based on the results in
+ * onUpdateSuccess or onUpdateFailure
+ *
+ * \see FibUpdater::onUpdateSuccess
+ * \see FibUpdater::onUpdateFailure
+ */
+ void
+ sendUpdates(const FibUpdateList& updates,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure);
+
+ /** \brief sends the updates in m_updatesForBatchFaceId to NFD if any exist,
+ * otherwise calls FibUpdater::sendUpdatesForNonBatchFaceId.
+ */
+ void
+ sendUpdatesForBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure);
+
+ /** \brief sends the updates in m_updatesForNonBatchFaceId to NFD if any exist,
+ * otherwise calls onSuccess.
+ */
+ void
+ sendUpdatesForNonBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure);
+
+ /** \brief sends a FibAddNextHopCommand to NFD using the parameters supplied by
+ * the passed update
+ *
+ * \param nTimeouts the number of times this FibUpdate has failed due to timeout
+ */
+ void
+ sendAddNextHopUpdate(const FibUpdate& update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t nTimeouts = 0);
+
+ /** \brief sends a FibRemoveNextHopCommand to NFD using the parameters supplied by
+ * the passed update
+ *
+ * \param nTimeouts the number of times this FibUpdate has failed due to timeout
+ */
+ void
+ sendRemoveNextHopUpdate(const FibUpdate& update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t nTimeouts = 0);
+
+private:
+ /** \brief calculates the FibUpdates generated by a RIB registration
+ */
+ void
+ computeUpdatesForRegistration(const RibUpdate& update);
+
+ /** \brief calculates the FibUpdates generated by a RIB unregistration
+ */
+ void
+ computeUpdatesForUnregistration(const RibUpdate& update);
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /** \brief callback used by NfdController when a FibAddNextHopCommand or FibRemoveNextHopCommand
+ * is successful.
+ *
+ * If the update has the same Face ID as the batch being processed, the update is
+ * removed from m_updatesForBatchFaceId. If m_updatesForBatchFaceId becomes empty,
+ * the updates with a different Face ID than the batch are sent to NFD.
+ *
+ * If the update has a different Face ID than the batch being processed, the update is
+ * removed from m_updatesForBatchNonFaceId. If m_updatesForBatchNonFaceId becomes empty,
+ * the FIB update process is considered a success.
+ */
+ void
+ onUpdateSuccess(const FibUpdate update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure);
+
+ /** \brief callback used by NfdController when a FibAddNextHopCommand or FibRemoveNextHopCommand
+ * is successful.
+ *
+ * If the update has not reached the max number of timeouts allowed, the update
+ * is retried.
+ *
+ * If the update failed due to a non-existent face and the update has the same Face ID
+ * as the update batch, the FIB update process fails.
+ *
+ * If the update failed due to a non-existent face and the update has a different
+ * face than the update batch, the update is not retried and the error is
+ * ignored.
+ *
+ * Otherwise, a non-recoverable error has occurred and an exception is thrown.
+ */
+ void
+ onUpdateError(const FibUpdate update,
+ const FibUpdateSuccessCallback& onSuccess,
+ const FibUpdateFailureCallback& onFailure,
+ uint32_t code, const std::string& error, uint32_t nTimeouts);
+
+private:
+ /** \brief adds the update to an update list based on its Face ID
+ *
+ * If the update has the same Face ID as the update batch, the update is added
+ * to m_updatesForBatchFaceId.
+ *
+ * Otherwise, the update is added to m_updatesForBatchNonFaceId.
+ */
+ void
+ addFibUpdate(const FibUpdate update);
+
+ /** \brief creates records of the passed routes added to the entry and creates FIB updates
+ */
+ void
+ addInheritedRoutes(const RibEntry& entry, const Rib::RouteSet& routesToAdd);
+
+ /** \brief creates records of the passed routes added to the name and creates FIB updates.
+ * Routes in routesToAdd with the same Face ID as ignore will be not be considered.
+ */
+ void
+ addInheritedRoutes(const Name& name, const Rib::RouteSet& routesToAdd, const Route& ignore);
+
+ /** \brief creates records of the passed routes removed from the entry and creates FIB updates
+ */
+ void
+ removeInheritedRoutes(const RibEntry& entry, const Rib::RouteSet& routesToRemove);
+
+ /** \brief calculates updates for a name that will create a new RIB entry
+ */
+ void
+ createFibUpdatesForNewRibEntry(const Name& name, const Route& route,
+ const Rib::RibEntryList& children);
+
+ /** \brief calculates updates for a new route added to a RIB entry
+ */
+ void
+ createFibUpdatesForNewRoute(const RibEntry& entry, const Route& route,
+ const bool captureWasTurnedOn);
+
+ /** \brief calculates updates for changes to an existing route for a RIB entry
+ */
+ void
+ createFibUpdatesForUpdatedRoute(const RibEntry& entry, const Route& route,
+ const Route& existingRoute);
+
+ /** \brief calculates updates for a an existing route removed from a RIB entry
+ */
+ void
+ createFibUpdatesForErasedRoute(const RibEntry& entry, const Route& route,
+ const bool captureWasTurnedOff);
+
+ /** \brief calculates updates for an entry that will be removed from the RIB
+ */
+ void
+ createFibUpdatesForErasedRibEntry(const RibEntry& entry);
+
+ /** \brief adds and removes passed routes to children's inherited routes
+ */
+ void
+ modifyChildrensInheritedRoutes(const Rib::RibEntryList& children,
+ const Rib::RouteSet& routesToAdd,
+ const Rib::RouteSet& routesToRemove);
+
+ /** \brief traverses the entry's children adding and removing the passed routes
+ */
+ void
+ traverseSubTree(const RibEntry& entry, Rib::RouteSet routesToAdd, Rib::RouteSet routesToRemove);
+
+private:
+ /** \brief creates a record of a calculated inherited route that should be added to the entry
+ */
+ void
+ addInheritedRoute(const Name& name, const Route& route);
+
+ /** \brief creates a record of an existing inherited route that should be removed from the entry
+ */
+ void
+ removeInheritedRoute(const Name& name, const Route& route);
+
+private:
+ const Rib& m_rib;
+ ndn::nfd::Controller& m_controller;
+ uint64_t m_batchFaceId;
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ FibUpdateList m_updatesForBatchFaceId;
+ FibUpdateList m_updatesForNonBatchFaceId;
+
+ /** \brief list of inherited routes generated during FIB update calculation;
+ * passed to the RIB when updates are completed successfully
+ */
+ RibUpdateList m_inheritedRoutes;
+
+private:
+ static const unsigned int MAX_NUM_TIMEOUTS;
+ static const uint32_t ERROR_FACE_NOT_FOUND;
+};
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_FIB_UPDATER_HPP
diff --git a/rib/rib-entry.cpp b/rib/rib-entry.cpp
index b841908..22b6dee 100644
--- a/rib/rib-entry.cpp
+++ b/rib/rib-entry.cpp
@@ -40,25 +40,29 @@
return std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, route));
}
+RibEntry::RouteList::const_iterator
+RibEntry::findRoute(const Route& route) const
+{
+ return std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, route));
+}
+
bool
RibEntry::insertRoute(const Route& route)
{
iterator it = findRoute(route);
- if (it == end())
- {
- if (route.flags & ndn::nfd::ROUTE_FLAG_CAPTURE)
- {
- m_nRoutesWithCaptureSet++;
- }
+ if (it == end()) {
+ if (route.flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
+ m_nRoutesWithCaptureSet++;
+ }
- m_routes.push_back(route);
- return true;
- }
- else
- {
- return false;
- }
+ m_routes.push_back(route);
+
+ return true;
+ }
+ else {
+ return false;
+ }
}
void
@@ -84,6 +88,12 @@
return it != end();
}
+size_t
+RibEntry::getNRoutes() const
+{
+ return m_routes.size();
+}
+
void
RibEntry::addChild(shared_ptr<RibEntry> child)
{
@@ -103,20 +113,18 @@
RibEntry::RouteList::iterator
RibEntry::eraseRoute(RouteList::iterator route)
{
- if (route != m_routes.end())
- {
- if (route->flags & ndn::nfd::ROUTE_FLAG_CAPTURE)
- {
- m_nRoutesWithCaptureSet--;
- }
-
- //cancel any scheduled event
- NFD_LOG_TRACE("Cancelling expiration eventId: " << route->getExpirationEvent());
- scheduler::cancel(route->getExpirationEvent());
-
- return m_routes.erase(route);
+ if (route != m_routes.end()) {
+ if (route->flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
+ m_nRoutesWithCaptureSet--;
}
+ // Cancel any scheduled event
+ NFD_LOG_TRACE("Cancelling expiration eventId: " << route->getExpirationEvent());
+ scheduler::cancel(route->getExpirationEvent());
+
+ return m_routes.erase(route);
+ }
+
return m_routes.end();
}
@@ -129,19 +137,20 @@
void
RibEntry::removeInheritedRoute(const Route& route)
{
- RouteList::iterator it = findInheritedRoute(route);
+ RouteList::iterator it = std::find_if(m_inheritedRoutes.begin(), m_inheritedRoutes.end(),
+ bind(&compareFaceId, _1, route.faceId));
m_inheritedRoutes.erase(it);
}
-RibEntry::RouteList::iterator
-RibEntry::findInheritedRoute(const Route& route)
+RibEntry::RouteList::const_iterator
+RibEntry::findInheritedRoute(const Route& route) const
{
return std::find_if(m_inheritedRoutes.begin(), m_inheritedRoutes.end(),
bind(&compareFaceId, _1, route.faceId));
}
bool
-RibEntry::hasInheritedRoute(const Route& route)
+RibEntry::hasInheritedRoute(const Route& route) const
{
RouteList::const_iterator it = findInheritedRoute(route);
@@ -157,97 +166,91 @@
bool
RibEntry::hasChildInheritOnFaceId(uint64_t faceId) const
{
- for (RibEntry::const_iterator it = m_routes.begin(); it != m_routes.end(); ++it)
- {
- if (it->faceId == faceId && (it->flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT))
- {
- return true;
- }
+ for (const Route& route : m_routes) {
+ if (route.faceId == faceId && (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)) {
+ return true;
}
+ }
return false;
}
-shared_ptr<Route>
-RibEntry::getRouteWithLowestCostByFaceId(uint64_t faceId)
+shared_ptr<const Route>
+RibEntry::getRouteWithLowestCostByFaceId(uint64_t faceId) const
{
shared_ptr<Route> candidate;
- for (const Route& route : m_routes)
- {
- // Correct face ID
- if (route.faceId == faceId)
- {
- // If this is the first route with this Face ID found
- if (candidate == nullptr)
- {
- candidate = make_shared<Route>(route);
- }
- else if (route.cost < candidate->cost) // Found a route with a lower cost
- {
- candidate = make_shared<Route>(route);
- }
- }
+ for (const Route& route : m_routes) {
+ // Matching face ID
+ if (route.faceId == faceId) {
+ // If this is the first route with this Face ID found
+ if (candidate == nullptr) {
+ candidate = make_shared<Route>(route);
+ }
+ else if (route.cost < candidate->cost) {
+ // Found a route with a lower cost
+ candidate = make_shared<Route>(route);
+ }
}
+ }
return candidate;
}
-shared_ptr<Route>
-RibEntry::getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId)
+const Route*
+RibEntry::getRouteWithSecondLowestCostByFaceId(uint64_t faceId) const
+{
+ std::vector<Route> matches;
+
+ // Copy routes which have faceId
+ std::copy_if(m_routes.begin(), m_routes.end(), std::back_inserter(matches),
+ [faceId] (const Route& route) { return route.faceId == faceId; });
+
+ // If there are not at least 2 routes, there is no second lowest
+ if (matches.size() < 2) {
+ return nullptr;
+ }
+
+ // Get second lowest cost
+ std::nth_element(matches.begin(), matches.begin() + 1, matches.end(),
+ [] (const Route& lhs, const Route& rhs) { return lhs.cost < rhs.cost; });
+
+ return &matches.at(1);
+}
+
+shared_ptr<const Route>
+RibEntry::getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId) const
{
shared_ptr<Route> candidate;
- for (const Route& route : m_routes)
+ for (const Route& route : m_routes) {
+ // Correct face ID and Child Inherit flag set
+ if (route.faceId == faceId &&
+ (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT) == ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)
{
- // Correct face ID and Child Inherit flag set
- if (route.faceId == faceId &&
- (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT) == ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)
- {
- // If this is the first route with this Face ID found
- if (candidate == nullptr)
- {
- candidate = make_shared<Route>(route);
- }
- else if (route.cost < candidate->cost) // Found a route with a lower cost
- {
- candidate = make_shared<Route>(route);
- }
- }
+ // If this is the first route with this Face ID found
+ if (candidate == nullptr) {
+ candidate = make_shared<Route>(route);
+ }
+ else if (route.cost < candidate->cost) {
+ // Found a route with a lower cost
+ candidate = make_shared<Route>(route);
+ }
}
+ }
return candidate;
}
std::ostream&
-operator<<(std::ostream& os, const Route& route)
-{
- os << "Route("
- << "faceid: " << route.faceId
- << ", origin: " << route.origin
- << ", cost: " << route.cost
- << ", flags: " << route.flags;
- if (route.expires != time::steady_clock::TimePoint::max()) {
- os << ", expires in: " << (route.expires - time::steady_clock::now());
- }
- else {
- os << ", never expires";
- }
- os << ")";
-
- return os;
-}
-
-std::ostream&
operator<<(std::ostream& os, const RibEntry& entry)
{
os << "RibEntry {\n";
os << "\tName: " << entry.getName() << "\n";
- for (const Route& route : entry)
- {
- os << "\t" << route << "\n";
- }
+ for (const Route& route : entry) {
+ os << "\t" << route << "\n";
+ }
os << "}";
diff --git a/rib/rib-entry.hpp b/rib/rib-entry.hpp
index 52adfd9..c3efbb7 100644
--- a/rib/rib-entry.hpp
+++ b/rib/rib-entry.hpp
@@ -63,8 +63,8 @@
void
removeChild(shared_ptr<RibEntry> child);
- std::list<shared_ptr<RibEntry>>&
- getChildren();
+ const std::list<shared_ptr<RibEntry>>&
+ getChildren() const;
bool
hasChildren() const;
@@ -94,9 +94,15 @@
RouteList&
getRoutes();
+ size_t
+ getNRoutes() const;
+
iterator
findRoute(const Route& route);
+ const_iterator
+ findRoute(const Route& route) const;
+
bool
hasRoute(const Route& route);
@@ -110,22 +116,22 @@
* The inherited routes returned represent inherited routes this namespace has in the FIB.
* \return{ routes inherited by this namespace }
*/
- RouteList&
- getInheritedRoutes();
+ const RouteList&
+ getInheritedRoutes() const;
/** \brief Finds an inherited route with a matching face ID.
* \return{ An iterator to the matching route if one is found;
* otherwise, an iterator to the end of the entry's
* inherited route list }
*/
- RouteList::iterator
- findInheritedRoute(const Route& route);
+ RouteList::const_iterator
+ findInheritedRoute(const Route& route) const;
/** \brief Determines if the entry has an inherited route with a matching face ID.
* \return{ True, if a matching inherited route is found; otherwise, false. }
*/
bool
- hasInheritedRoute(const Route& route);
+ hasInheritedRoute(const Route& route) const;
bool
hasCapture() const;
@@ -140,16 +146,19 @@
/** \brief Returns the route with the lowest cost that has the passed face ID.
* \return{ The route with the lowest cost that has the passed face ID}
*/
- shared_ptr<Route>
- getRouteWithLowestCostByFaceId(uint64_t faceId);
+ shared_ptr<const Route>
+ getRouteWithLowestCostByFaceId(uint64_t faceId) const;
+
+const Route*
+ getRouteWithSecondLowestCostByFaceId(uint64_t faceId) const;
/** \brief Returns the route with the lowest cost that has the passed face ID
* and its child inherit flag set.
* \return{ The route with the lowest cost that has the passed face ID
* and its child inherit flag set }
*/
- shared_ptr<Route>
- getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId);
+ shared_ptr<const Route>
+ getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId) const;
const_iterator
begin() const;
@@ -207,8 +216,8 @@
return m_parent;
}
-inline std::list<shared_ptr<RibEntry>>&
-RibEntry::getChildren()
+inline const std::list<shared_ptr<RibEntry> >&
+RibEntry::getChildren() const
{
return m_children;
}
@@ -219,8 +228,8 @@
return m_routes;
}
-inline RibEntry::RouteList&
-RibEntry::getInheritedRoutes()
+inline const RibEntry::RouteList&
+RibEntry::getInheritedRoutes() const
{
return m_inheritedRoutes;
}
diff --git a/rib/rib-manager.cpp b/rib/rib-manager.cpp
index 2b79a53..8215ade 100644
--- a/rib/rib-manager.cpp
+++ b/rib/rib-manager.cpp
@@ -82,7 +82,7 @@
, m_isLocalhopEnabled(false)
, m_remoteRegistrator(m_nfdController, m_keyChain, m_managedRib)
, m_ribStatusPublisher(m_managedRib, face, LIST_COMMAND_PREFIX, m_keyChain)
- , m_lastTransactionId(0)
+ , m_fibUpdater(m_managedRib, m_nfdController)
, m_signedVerbDispatch(SIGNED_COMMAND_VERBS,
SIGNED_COMMAND_VERBS +
(sizeof(SIGNED_COMMAND_VERBS) / sizeof(SignedVerbAndProcessor)))
@@ -146,36 +146,33 @@
{
bool isRemoteRegisterEnabled = false;
- for (ConfigSection::const_iterator i = configSection.begin();
- i != configSection.end(); ++i)
- {
- if (i->first == "localhost_security")
- m_localhostValidator.load(i->second, filename);
- else if (i->first == "localhop_security")
- {
- m_localhopValidator.load(i->second, filename);
- m_isLocalhopEnabled = true;
- }
- else if (i->first == "remote_register")
- {
- m_remoteRegistrator.loadConfig(i->second);
- isRemoteRegisterEnabled = true;
- // avoid other actions when isDryRun == true
- if (isDryRun)
- {
- continue;
- }
-
- m_remoteRegistrator.enable();
- }
- else
- throw Error("Unrecognized rib property: " + i->first);
+ for (const auto& item : configSection) {
+ if (item.first == "localhost_security") {
+ m_localhostValidator.load(item.second, filename);
}
-
- if (!isRemoteRegisterEnabled)
- {
- m_remoteRegistrator.disable();
+ else if (item.first == "localhop_security") {
+ m_localhopValidator.load(item.second, filename);
+ m_isLocalhopEnabled = true;
}
+ else if (item.first == "remote_register") {
+ m_remoteRegistrator.loadConfig(item.second);
+ isRemoteRegisterEnabled = true;
+
+ // Avoid other actions when isDryRun == true
+ if (isDryRun) {
+ continue;
+ }
+
+ m_remoteRegistrator.enable();
+ }
+ else {
+ throw Error("Unrecognized rib property: " + item.first);
+ }
+ }
+
+ if (!isRemoteRegisterEnabled) {
+ m_remoteRegistrator.disable();
+ }
}
void
@@ -208,17 +205,15 @@
UnsignedVerbDispatchTable::const_iterator unsignedVerbProcessor = m_unsignedVerbDispatch.find(verb);
- if (unsignedVerbProcessor != m_unsignedVerbDispatch.end())
- {
- NFD_LOG_DEBUG("command result: processing unsigned verb: " << verb);
- (unsignedVerbProcessor->second)(this, request);
- }
- else
- {
- m_localhostValidator.validate(request,
- bind(&RibManager::onCommandValidated, this, _1),
- bind(&RibManager::onCommandValidationFailed, this, _1, _2));
- }
+ if (unsignedVerbProcessor != m_unsignedVerbDispatch.end()) {
+ NFD_LOG_DEBUG("command result: processing unsigned verb: " << verb);
+ (unsignedVerbProcessor->second)(this, request);
+ }
+ else {
+ m_localhostValidator.validate(request,
+ bind(&RibManager::onCommandValidated, this, _1),
+ bind(&RibManager::onCommandValidationFailed, this, _1, _2));
+ }
}
void
@@ -240,26 +235,30 @@
const Name::Component& parameterComponent = command[COMMAND_PREFIX.size() + 1];
SignedVerbDispatchTable::const_iterator verbProcessor = m_signedVerbDispatch.find(verb);
- if (verbProcessor != m_signedVerbDispatch.end())
- {
- ControlParameters parameters;
- if (!extractParameters(parameterComponent, parameters))
- {
- NFD_LOG_DEBUG("command result: malformed verb: " << verb);
- if (static_cast<bool>(request))
- sendResponse(command, 400, "Malformed command");
- return;
- }
- NFD_LOG_DEBUG("command result: processing verb: " << verb);
- (verbProcessor->second)(this, request, parameters);
+ if (verbProcessor != m_signedVerbDispatch.end()) {
+
+ ControlParameters parameters;
+ if (!extractParameters(parameterComponent, parameters)) {
+ NFD_LOG_DEBUG("command result: malformed verb: " << verb);
+
+ if (static_cast<bool>(request)) {
+ sendResponse(command, 400, "Malformed command");
+ }
+
+ return;
}
- else
- {
- NFD_LOG_DEBUG("Unsupported command: " << verb);
- if (static_cast<bool>(request))
- sendResponse(request->getName(), 501, "Unsupported command");
+
+ NFD_LOG_DEBUG("command result: processing verb: " << verb);
+ (verbProcessor->second)(this, request, parameters);
+ }
+ else {
+ NFD_LOG_DEBUG("Unsupported command: " << verb);
+
+ if (static_cast<bool>(request)) {
+ sendResponse(request->getName(), 501, "Unsupported command");
}
+ }
}
void
@@ -268,23 +267,23 @@
{
ndn::nfd::RibRegisterCommand command;
- if (!validateParameters(command, parameters))
- {
- NFD_LOG_DEBUG("register result: FAIL reason: malformed");
+ if (!validateParameters(command, parameters)) {
+ NFD_LOG_DEBUG("register result: FAIL reason: malformed");
- if (static_cast<bool>(request))
- {
- sendResponse(request->getName(), 400, "Malformed command");
- }
-
- return;
+ if (static_cast<bool>(request)) {
+ sendResponse(request->getName(), 400, "Malformed command");
}
+ return;
+ }
+
bool isSelfRegistration = (!parameters.hasFaceId() || parameters.getFaceId() == 0);
- if (isSelfRegistration)
- {
- parameters.setFaceId(request->getIncomingFaceId());
- }
+ if (isSelfRegistration) {
+ parameters.setFaceId(request->getIncomingFaceId());
+ }
+
+ // Respond since command is valid and authorized
+ sendSuccessResponse(request, parameters);
Route route;
route.faceId = parameters.getFaceId();
@@ -294,44 +293,37 @@
if (parameters.hasExpirationPeriod() &&
parameters.getExpirationPeriod() != time::milliseconds::max())
- {
- route.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
+ {
+ route.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
- // Schedule a new event, the old one will be cancelled during rib insertion.
- scheduler::EventId eventId = scheduler::schedule(parameters.getExpirationPeriod(),
- bind(&RibManager::expireEntry, this, shared_ptr<Interest>(), parameters));
- NFD_LOG_TRACE("Scheduled unregistration at: " << route.expires <<
- " with EventId: " << eventId);
+ // Schedule a new event, the old one will be cancelled during rib insertion.
+ scheduler::EventId eventId = scheduler::schedule(parameters.getExpirationPeriod(),
+ bind(&Rib::onRouteExpiration, &m_managedRib, parameters.getName(), route));
- //set the NewEventId of this entry
- route.setExpirationEvent(eventId);
- }
- else
- {
- route.expires = time::steady_clock::TimePoint::max();
- }
+ NFD_LOG_TRACE("Scheduled unregistration at: " << route.expires <<
+ " with EventId: " << eventId);
+
+ // Set the NewEventId of this entry
+ route.setExpirationEvent(eventId);
+ }
+ else {
+ route.expires = time::steady_clock::TimePoint::max();
+ }
NFD_LOG_INFO("Adding route " << parameters.getName() << " nexthop=" << route.faceId
<< " origin=" << route.origin
<< " cost=" << route.cost);
- m_managedRib.insert(parameters.getName(), route);
+ RibUpdate update;
+ update.setAction(RibUpdate::REGISTER)
+ .setName(parameters.getName())
+ .setRoute(route);
+
+ m_managedRib.beginApplyUpdate(update,
+ bind(&RibManager::onRibUpdateSuccess, this, update),
+ bind(&RibManager::onRibUpdateFailure, this, update, _1, _2));
+
m_registeredFaces.insert(route.faceId);
-
- sendUpdatesToFib(request, parameters);
-}
-
-void
-RibManager::expireEntry(const shared_ptr<const Interest>& request, ControlParameters& params)
-{
- Route route;
- route.faceId = params.getFaceId();
- route.origin = params.getOrigin();
- route.cost = params.getCost();
- route.flags = params.getFlags();
-
- NFD_LOG_DEBUG(route << " for " << params.getName() << " has expired");
- unregisterEntry(request, params);
}
void
@@ -340,28 +332,36 @@
{
ndn::nfd::RibUnregisterCommand command;
- //passing all parameters gives error in validation.
- //so passing only the required arguments.
+ // Passing all parameters gives error in validation,
+ // so passing only the required arguments.
ControlParameters parameters;
parameters.setName(params.getName());
- if (params.hasFaceId())
- parameters.setFaceId(params.getFaceId());
- if (params.hasOrigin())
- parameters.setOrigin(params.getOrigin());
- if (!validateParameters(command, parameters))
- {
- NFD_LOG_DEBUG("unregister result: FAIL reason: malformed");
- if (static_cast<bool>(request))
- sendResponse(request->getName(), 400, "Malformed command");
- return;
+ if (params.hasFaceId()) {
+ parameters.setFaceId(params.getFaceId());
+ }
+
+ if (params.hasOrigin()) {
+ parameters.setOrigin(params.getOrigin());
+ }
+
+ if (!validateParameters(command, parameters)) {
+ NFD_LOG_DEBUG("unregister result: FAIL reason: malformed");
+
+ if (static_cast<bool>(request)) {
+ sendResponse(request->getName(), 400, "Malformed command");
}
+ return;
+ }
+
bool isSelfRegistration = (!parameters.hasFaceId() || parameters.getFaceId() == 0);
- if (isSelfRegistration)
- {
- parameters.setFaceId(request->getIncomingFaceId());
- }
+ if (isSelfRegistration) {
+ parameters.setFaceId(request->getIncomingFaceId());
+ }
+
+ // Respond since command is valid and authorized
+ sendSuccessResponse(request, parameters);
Route route;
route.faceId = parameters.getFaceId();
@@ -370,9 +370,14 @@
NFD_LOG_INFO("Removing route " << parameters.getName() << " nexthop=" << route.faceId
<< " origin=" << route.origin);
- m_managedRib.erase(parameters.getName(), route);
+ RibUpdate update;
+ update.setAction(RibUpdate::UNREGISTER)
+ .setName(parameters.getName())
+ .setRoute(route);
- sendUpdatesToFib(request, parameters);
+ m_managedRib.beginApplyUpdate(update,
+ bind(&RibManager::onRibUpdateSuccess, this, update),
+ bind(&RibManager::onRibUpdateFailure, this, update, _1, _2));
}
void
@@ -380,8 +385,10 @@
const std::string& failureInfo)
{
NFD_LOG_DEBUG("RibRequestValidationFailed: " << failureInfo);
- if (static_cast<bool>(request))
+
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), 403, failureInfo);
+ }
}
@@ -389,15 +396,13 @@
RibManager::extractParameters(const Name::Component& parameterComponent,
ControlParameters& extractedParameters)
{
- try
- {
- Block rawParameters = parameterComponent.blockFromValue();
- extractedParameters.wireDecode(rawParameters);
- }
- catch (const tlv::Error&)
- {
- return false;
- }
+ try {
+ Block rawParameters = parameterComponent.blockFromValue();
+ extractedParameters.wireDecode(rawParameters);
+ }
+ catch (const tlv::Error&) {
+ return false;
+ }
NFD_LOG_DEBUG("Parameters parsed OK");
return true;
@@ -407,14 +412,12 @@
RibManager::validateParameters(const ControlCommand& command,
ControlParameters& parameters)
{
- try
- {
- command.validateRequest(parameters);
- }
- catch (const ControlCommand::ArgumentError&)
- {
- return false;
- }
+ try {
+ command.validateRequest(parameters);
+ }
+ catch (const ControlCommand::ArgumentError&) {
+ return false;
+ }
command.applyDefaultsToRequest(parameters);
@@ -430,21 +433,20 @@
ControlResponse response;
- if (code == 404)
- {
- response.setCode(code);
- response.setText(error);
- }
- else
- {
- response.setCode(533);
- std::ostringstream os;
- os << "Failure to update NFD " << "(NFD Error: " << code << " " << error << ")";
- response.setText(os.str());
- }
+ if (code == 404) {
+ response.setCode(code);
+ response.setText(error);
+ }
+ else {
+ response.setCode(533);
+ std::ostringstream os;
+ os << "Failure to update NFD " << "(NFD Error: " << code << " " << error << ")";
+ response.setText(os.str());
+ }
- if (static_cast<bool>(request))
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), response);
+ }
}
void
@@ -460,8 +462,9 @@
NFD_LOG_TRACE("onRegSuccess: registered " << route);
- if (static_cast<bool>(request))
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), response);
+ }
}
@@ -478,18 +481,18 @@
NFD_LOG_TRACE("onUnRegSuccess: unregistered " << route);
- if (static_cast<bool>(request))
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), response);
+ }
}
void
RibManager::sendSuccessResponse(const shared_ptr<const Interest>& request,
const ControlParameters& parameters)
{
- if (!static_cast<bool>(request))
- {
- return;
- }
+ if (!static_cast<bool>(request)) {
+ return;
+ }
ControlResponse response;
@@ -497,8 +500,9 @@
response.setText("Success");
response.setBody(parameters.wireEncode());
- if (static_cast<bool>(request))
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), response);
+ }
}
void
@@ -507,28 +511,42 @@
{
NFD_LOG_ERROR("NFD returned an error: " << error << " (code: " << code << ")");
- if (!static_cast<bool>(request))
- {
- return;
- }
+ if (!static_cast<bool>(request)) {
+ return;
+ }
ControlResponse response;
- if (code == 404)
- {
- response.setCode(code);
- response.setText(error);
- }
- else
- {
- response.setCode(533);
- std::ostringstream os;
- os << "Failure to update NFD " << "(NFD Error: " << code << " " << error << ")";
- response.setText(os.str());
- }
+ if (code == 404) {
+ response.setCode(code);
+ response.setText(error);
+ }
+ else {
+ response.setCode(533);
+ std::ostringstream os;
+ os << "Failure to update NFD " << "(NFD Error: " << code << " " << error << ")";
+ response.setText(os.str());
+ }
- if (static_cast<bool>(request))
+ if (static_cast<bool>(request)) {
sendResponse(request->getName(), response);
+ }
+}
+
+void
+RibManager::onRibUpdateSuccess(const RibUpdate& update)
+{
+ NFD_LOG_DEBUG("RIB update succeeded for " << update);
+}
+
+void
+RibManager::onRibUpdateFailure(const RibUpdate& update, uint32_t code, const std::string& error)
+{
+ NFD_LOG_DEBUG("RIB update failed for " << update << " (code: " << code
+ << ", error: " << error << ")");
+
+ // Since the FIB rejected the update, clean up invalid routes
+ scheduleActiveFaceFetch(time::seconds(1));
}
void
@@ -547,7 +565,6 @@
m_managedRib.insert(prefix, route);
m_registeredFaces.insert(route.faceId);
- m_managedRib.clearFibUpdates();
}
void
@@ -556,92 +573,6 @@
throw Error("Error in setting interest filter (" + name.toUri() + "): " + msg);
}
-bool
-RibManager::isTransactionComplete(const TransactionId transactionId)
-{
- FibTransactionTable::iterator it = m_pendingFibTransactions.find(transactionId);
-
- if (it != m_pendingFibTransactions.end())
- {
- int& updatesLeft = it->second;
-
- updatesLeft--;
-
- // All of the updates have been applied successfully
- if (updatesLeft == 0)
- {
- m_pendingFibTransactions.erase(it);
- return true;
- }
- }
-
- return false;
-}
-
-void
-RibManager::invalidateTransaction(const TransactionId transactionId)
-{
- FibTransactionTable::iterator it = m_pendingFibTransactions.find(transactionId);
-
- if (it != m_pendingFibTransactions.end())
- {
- m_pendingFibTransactions.erase(it);
- }
-}
-
-void
-RibManager::onAddNextHopSuccess(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters,
- const TransactionId transactionId,
- const bool shouldSendResponse)
-{
- if (isTransactionComplete(transactionId) && shouldSendResponse)
- {
- sendSuccessResponse(request, parameters);
- }
-}
-
-void
-RibManager::onAddNextHopError(uint32_t code, const std::string& error,
- const shared_ptr<const Interest>& request,
- const TransactionId transactionId, const bool shouldSendResponse)
-{
- invalidateTransaction(transactionId);
-
- if (shouldSendResponse)
- {
- sendErrorResponse(code, error, request);
- }
-
- // Since the FIB rejected the update, clean up the invalid face
- scheduleActiveFaceFetch(time::seconds(1));
-}
-
-void
-RibManager::onRemoveNextHopSuccess(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters,
- const TransactionId transactionId,
- const bool shouldSendResponse)
-{
- if (isTransactionComplete(transactionId) && shouldSendResponse)
- {
- sendSuccessResponse(request, parameters);
- }
-}
-
-void
-RibManager::onRemoveNextHopError(uint32_t code, const std::string& error,
- const shared_ptr<const Interest>& request,
- const TransactionId transactionId, const bool shouldSendResponse)
-{
- invalidateTransaction(transactionId);
-
- if (shouldSendResponse)
- {
- sendErrorResponse(code, error, request);
- }
-}
-
void
RibManager::onControlHeaderSuccess()
{
@@ -672,111 +603,19 @@
{
NFD_LOG_TRACE("onNotification: " << notification);
- if (notification.getKind() == ndn::nfd::FACE_EVENT_DESTROYED)
- {
- NFD_LOG_DEBUG("Received notification for destroyed faceId: " << notification.getFaceId());
+ if (notification.getKind() == ndn::nfd::FACE_EVENT_DESTROYED) {
+ NFD_LOG_DEBUG("Received notification for destroyed faceId: " << notification.getFaceId());
- scheduler::schedule(time::seconds(0),
- bind(&RibManager::processErasureAfterNotification, this,
- notification.getFaceId()));
- }
+ scheduler::schedule(time::seconds(0),
+ bind(&RibManager::onFaceDestroyedEvent, this, notification.getFaceId()));
+ }
}
void
-RibManager::processErasureAfterNotification(uint64_t faceId)
+RibManager::onFaceDestroyedEvent(uint64_t faceId)
{
- m_managedRib.erase(faceId);
+ m_managedRib.beginRemoveFace(faceId);
m_registeredFaces.erase(faceId);
-
- sendUpdatesToFibAfterFaceDestroyEvent();
-}
-
-void
-RibManager::sendUpdatesToFib(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters)
-{
- const Rib::FibUpdateList& updates = m_managedRib.getFibUpdates();
-
- // If no updates were generated, consider the operation a success
- if (updates.empty())
- {
- sendSuccessResponse(request, parameters);
- return;
- }
-
- bool shouldWaitToRespond = false;
-
- // An application request should wait for all FIB updates to be applied
- // successfully before sending a response
- if (parameters.getOrigin() == ndn::nfd::ROUTE_ORIGIN_APP)
- {
- shouldWaitToRespond = true;
- }
- else // Respond immediately
- {
- sendSuccessResponse(request, parameters);
- }
-
- std::string updateString = (updates.size() == 1) ? " update" : " updates";
- NFD_LOG_DEBUG("Applying " << updates.size() << updateString << " to FIB");
-
- // Assign an ID to this FIB transaction
- TransactionId currentTransactionId = ++m_lastTransactionId;
-
- // Add this transaction to the transaction table
- m_pendingFibTransactions[currentTransactionId] = updates.size();
-
- for (Rib::FibUpdateList::const_iterator it = updates.begin(); it != updates.end(); ++it)
- {
- shared_ptr<const FibUpdate> update(*it);
- NFD_LOG_DEBUG("Sending FIB update: " << *update);
-
- if (update->action == FibUpdate::ADD_NEXTHOP)
- {
- Route route;
- route.faceId = update->faceId;
- route.cost = update->cost;
-
- m_nfdController.start<ndn::nfd::FibAddNextHopCommand>(
- ControlParameters()
- .setName(update->name)
- .setFaceId(route.faceId)
- .setCost(route.cost),
- bind(&RibManager::onAddNextHopSuccess, this, request,
- parameters,
- currentTransactionId,
- shouldWaitToRespond),
- bind(&RibManager::onAddNextHopError, this, _1, _2, request, currentTransactionId,
- shouldWaitToRespond));
- }
- else if (update->action == FibUpdate::REMOVE_NEXTHOP)
- {
- Route route;
- route.faceId = update->faceId;
-
- m_nfdController.start<ndn::nfd::FibRemoveNextHopCommand>(
- ControlParameters()
- .setName(update->name)
- .setFaceId(route.faceId),
- bind(&RibManager::onRemoveNextHopSuccess, this, request,
- parameters,
- currentTransactionId,
- shouldWaitToRespond),
- bind(&RibManager::onRemoveNextHopError, this, _1, _2, request, currentTransactionId,
- shouldWaitToRespond));
- }
- }
-
- m_managedRib.clearFibUpdates();
-}
-
-void
-RibManager::sendUpdatesToFibAfterFaceDestroyEvent()
-{
- ControlParameters parameters;
- parameters.setOrigin(ndn::nfd::ROUTE_ORIGIN_STATIC);
-
- sendUpdatesToFib(shared_ptr<const Interest>(), parameters);
}
void
@@ -785,13 +624,12 @@
const Name& command = request.getName();
const size_t commandNComps = command.size();
- if (commandNComps < LIST_COMMAND_NCOMPS ||
- !LIST_COMMAND_PREFIX.isPrefixOf(command))
- {
- NFD_LOG_DEBUG("command result: malformed");
- sendResponse(command, 400, "Malformed command");
- return;
- }
+ if (commandNComps < LIST_COMMAND_NCOMPS || !LIST_COMMAND_PREFIX.isPrefixOf(command)) {
+ NFD_LOG_DEBUG("command result: malformed");
+
+ sendResponse(command, 400, "Malformed command");
+ return;
+ }
m_ribStatusPublisher.publish();
}
@@ -830,16 +668,15 @@
uint64_t currentSegment = data.getName().get(-1).toSegment();
const name::Component& finalBlockId = data.getMetaInfo().getFinalBlockId();
- if (finalBlockId.empty() || finalBlockId.toSegment() > currentSegment)
- {
- m_face.expressInterest(data.getName().getPrefix(-1).appendSegment(currentSegment+1),
- bind(&RibManager::fetchSegments, this, _2, buffer),
- bind(&RibManager::onFetchFaceStatusTimeout, this));
- }
- else
- {
- removeInvalidFaces(buffer);
- }
+
+ if (finalBlockId.empty() || finalBlockId.toSegment() > currentSegment) {
+ m_face.expressInterest(data.getName().getPrefix(-1).appendSegment(currentSegment+1),
+ bind(&RibManager::fetchSegments, this, _2, buffer),
+ bind(&RibManager::onFetchFaceStatusTimeout, this));
+ }
+ else {
+ removeInvalidFaces(buffer);
+ }
}
void
@@ -869,15 +706,14 @@
// Look for face IDs that were registered but not active to find missed
// face destroyed events
- for (FaceIdSet::iterator it = m_registeredFaces.begin(); it != m_registeredFaces.end(); ++it)
- {
- if (activeFaces.find(*it) == activeFaces.end())
- {
- NFD_LOG_DEBUG("Removing invalid face ID: " << *it);
- scheduler::schedule(time::seconds(0),
- bind(&RibManager::processErasureAfterNotification, this, *it));
- }
+ for (uint64_t faceId : m_registeredFaces) {
+ if (activeFaces.find(faceId) == activeFaces.end()) {
+ NFD_LOG_DEBUG("Removing invalid face ID: " << faceId);
+
+ scheduler::schedule(time::seconds(0),
+ bind(&RibManager::onFaceDestroyedEvent, this, faceId));
}
+ }
// Reschedule the check for future clean up
scheduleActiveFaceFetch(ACTIVE_FACE_FETCH_INTERVAL);
diff --git a/rib/rib-manager.hpp b/rib/rib-manager.hpp
index 3819d5a..8d90103 100644
--- a/rib/rib-manager.hpp
+++ b/rib/rib-manager.hpp
@@ -30,6 +30,7 @@
#include "core/config-file.hpp"
#include "rib-status-publisher.hpp"
#include "remote-registrator.hpp"
+#include "fib-updater.hpp"
#include <ndn-cxx/security/validator-config.hpp>
#include <ndn-cxx/management/nfd-face-monitor.hpp>
@@ -74,10 +75,14 @@
void
setConfigFile(ConfigFile& configFile);
-private:
- typedef uint32_t TransactionId;
+ void
+ onRibUpdateSuccess(const RibUpdate& update);
void
+ onRibUpdateFailure(const RibUpdate& update, uint32_t code, const std::string& error);
+
+private:
+ void
onConfig(const ConfigSection& configSection,
bool isDryRun,
const std::string& filename);
@@ -116,9 +121,7 @@
unregisterEntry(const shared_ptr<const Interest>& request,
ControlParameters& parameters);
- void
- expireEntry(const shared_ptr<const Interest>& request, ControlParameters& params);
-
+private:
void
onCommandValidated(const shared_ptr<const Interest>& request);
@@ -152,28 +155,6 @@
onNrdCommandPrefixAddNextHopError(const Name& name, const std::string& msg);
void
- onAddNextHopSuccess(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters,
- const TransactionId transactionId,
- const bool shouldSendResponse);
-
- void
- onAddNextHopError(uint32_t code, const std::string& error,
- const shared_ptr<const Interest>& request,
- const TransactionId transactionId, const bool shouldSendResponse);
-
- void
- onRemoveNextHopSuccess(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters,
- const TransactionId transactionId,
- const bool shouldSendResponse);
-
- void
- onRemoveNextHopError(uint32_t code, const std::string& error,
- const shared_ptr<const Interest>& request,
- const TransactionId transactionId, const bool shouldSendResponse);
-
- void
onControlHeaderSuccess();
void
@@ -190,27 +171,11 @@
void
onNotification(const FaceEventNotification& notification);
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
void
- processErasureAfterNotification(uint64_t faceId);
+ onFaceDestroyedEvent(uint64_t faceId);
- void
- sendUpdatesToFib(const shared_ptr<const Interest>& request,
- const ControlParameters& parameters);
-
- void
- sendUpdatesToFibAfterFaceDestroyEvent();
-
- /** \brief Checks if the transaction has received all of the expected responses
- * from the FIB.
- * \return{ True if the transaction with the passed transactionId has applied
- * all of its FIB updates successfully; otherwise, false }
- */
- bool
- isTransactionComplete(const TransactionId transactionId);
-
- void
- invalidateTransaction(const TransactionId transactionId);
-
+private:
void
listEntries(const Interest& request);
@@ -247,22 +212,10 @@
RibStatusPublisher m_ribStatusPublisher;
- /** \brief The last transaction ID for FIB update response messages.
- * Each group of FIB updates applied to the FIB is assigned an incrementing
- * ID that is used to track the number of successfully applied updates.
- */
- TransactionId m_lastTransactionId;
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ FibUpdater m_fibUpdater;
- /// table of FIB update transactions => count of pending FIB updates
- typedef std::map<TransactionId, int> FibTransactionTable;
-
- /** \brief Table used to track the number of FIB updates that have not yet received
- * a response from the FIB.
- * The table maps a transaction ID to the number of updates remaining for that
- * specific transaction.
- */
- FibTransactionTable m_pendingFibTransactions;
-
+private:
typedef function<void(RibManager*,
const shared_ptr<const Interest>& request,
ControlParameters& parameters)> SignedVerbProcessor;
diff --git a/rib/rib-update-batch.cpp b/rib/rib-update-batch.cpp
new file mode 100644
index 0000000..e639ae3
--- /dev/null
+++ b/rib/rib-update-batch.cpp
@@ -0,0 +1,63 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib-update-batch.hpp"
+
+namespace nfd {
+namespace rib {
+
+RibUpdateBatch::RibUpdateBatch(uint64_t faceId)
+ : m_faceId(faceId)
+{
+}
+
+void
+RibUpdateBatch::add(const RibUpdate& update)
+{
+ BOOST_ASSERT(m_faceId == update.getRoute().faceId);
+
+ m_updates.push_back(update);
+}
+
+RibUpdateBatch::const_iterator
+RibUpdateBatch::begin() const
+{
+ return m_updates.begin();
+}
+
+RibUpdateBatch::const_iterator
+RibUpdateBatch::end() const
+{
+ return m_updates.end();
+}
+
+size_t
+RibUpdateBatch::size() const
+{
+ return m_updates.size();
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/rib-update-batch.hpp b/rib/rib-update-batch.hpp
new file mode 100644
index 0000000..15e9ecd
--- /dev/null
+++ b/rib/rib-update-batch.hpp
@@ -0,0 +1,76 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_RIB_RIB_UPDATE_BATCH_HPP
+#define NFD_RIB_RIB_UPDATE_BATCH_HPP
+
+#include "common.hpp"
+#include "rib-update.hpp"
+
+namespace nfd {
+namespace rib {
+
+typedef std::list<RibUpdate> RibUpdateList;
+
+/** \brief represents a collection of RibUpdates to be applied to a single FaceId
+ */
+class RibUpdateBatch
+{
+public:
+ typedef RibUpdateList::const_iterator const_iterator;
+
+ explicit
+ RibUpdateBatch(uint64_t faceId);
+
+ uint64_t
+ getFaceId() const;
+
+ void
+ add(const RibUpdate& update);
+
+ const_iterator
+ begin() const;
+
+ const_iterator
+ end() const;
+
+ size_t
+ size() const;
+
+private:
+ uint64_t m_faceId;
+ RibUpdateList m_updates;
+};
+
+inline uint64_t
+RibUpdateBatch::getFaceId() const
+{
+ return m_faceId;
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_UPDATE_BATCH_HPP
diff --git a/rib/rib-update.cpp b/rib/rib-update.cpp
new file mode 100644
index 0000000..8efe327
--- /dev/null
+++ b/rib/rib-update.cpp
@@ -0,0 +1,68 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "rib-update.hpp"
+
+namespace nfd {
+namespace rib {
+
+RibUpdate::RibUpdate()
+{
+
+}
+
+std::ostream&
+operator<<(std::ostream& os, const RibUpdate::Action action)
+{
+ switch (action) {
+ case RibUpdate::REGISTER:
+ os << "REGISTER";
+ break;
+ case RibUpdate::UNREGISTER:
+ os << "UNREGISTER";
+ break;
+ case RibUpdate::REMOVE_FACE:
+ os << "REMOVE_FACE";
+ break;
+ }
+
+ return os;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const RibUpdate& update)
+{
+ os << "RibUpdate {\n";
+ os << " Name: " << update.getName() << "\n";
+ os << " Action: " << update.getAction() << "\n";
+ os << " " << update.getRoute() << "\n";
+ os << "}";
+
+ return os;
+}
+
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/rib-update.hpp b/rib/rib-update.hpp
new file mode 100644
index 0000000..4b9d5dd
--- /dev/null
+++ b/rib/rib-update.hpp
@@ -0,0 +1,128 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_RIB_RIB_UPDATE_HPP
+#define NFD_RIB_RIB_UPDATE_HPP
+
+#include "common.hpp"
+#include "route.hpp"
+
+namespace nfd {
+namespace rib {
+
+/** RibUpdate
+ * \brief represents a route that will be added to or removed from a namespace
+ *
+ * \note This type is copyable so that it can be stored in STL containers.
+ */
+class RibUpdate
+{
+public:
+ enum Action {
+ REGISTER = 0,
+ UNREGISTER = 1,
+
+ /** \brief An update triggered by a face destruction notification
+ *
+ * \note indicates a Route needs to be removed after a face is destroyed
+ */
+ REMOVE_FACE = 2
+ };
+
+ RibUpdate();
+
+ RibUpdate&
+ setAction(Action action);
+
+ Action
+ getAction() const;
+
+ RibUpdate&
+ setName(const Name& name);
+
+ const Name&
+ getName() const;
+
+ RibUpdate&
+ setRoute(const Route& route);
+
+ const Route&
+ getRoute() const;
+
+private:
+ Action m_action;
+ Name m_name;
+ Route m_route;
+};
+
+inline RibUpdate&
+RibUpdate::setAction(Action action)
+{
+ m_action = action;
+ return *this;
+}
+
+inline RibUpdate::Action
+RibUpdate::getAction() const
+{
+ return m_action;
+}
+
+inline RibUpdate&
+RibUpdate::setName(const Name& name)
+{
+ m_name = name;
+ return *this;
+}
+
+inline const Name&
+RibUpdate::getName() const
+{
+ return m_name;
+}
+
+inline RibUpdate&
+RibUpdate::setRoute(const Route& route)
+{
+ m_route = route;
+ return *this;
+}
+
+inline const Route&
+RibUpdate::getRoute() const
+{
+ return m_route;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const RibUpdate::Action action);
+
+std::ostream&
+operator<<(std::ostream& os, const RibUpdate& update);
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_UPDATE_HPP
diff --git a/rib/rib.cpp b/rib/rib.cpp
index 5d578ab..4c4d3c5 100644
--- a/rib/rib.cpp
+++ b/rib/rib.cpp
@@ -25,6 +25,7 @@
#include "rib.hpp"
+#include "fib-updater.hpp"
#include "core/logger.hpp"
NFD_LOG_INIT("Rib");
@@ -38,35 +39,22 @@
return lhs.faceId < rhs.faceId;
}
-static inline bool
-isChildInheritFlagSet(uint64_t flags)
-{
- return flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
-}
-
-static inline bool
-isCaptureFlagSet(uint64_t flags)
-{
- return flags & ndn::nfd::ROUTE_FLAG_CAPTURE;
-}
-
-static inline bool
-isAnyFlagSet(uint64_t flags)
-{
- return isChildInheritFlagSet(flags) || isCaptureFlagSet(flags);
-}
-
-static inline bool
-areBothFlagsSet(uint64_t flags)
-{
- return isChildInheritFlagSet(flags) && isCaptureFlagSet(flags);
-}
-
Rib::Rib()
: m_nItems(0)
+ , m_isUpdateInProgress(false)
{
}
+Rib::~Rib()
+{
+}
+
+void
+Rib::setFibUpdater(FibUpdater* updater)
+{
+ m_fibUpdater = updater;
+}
+
Rib::const_iterator
Rib::find(const Name& prefix) const
{
@@ -79,17 +67,15 @@
RibTable::const_iterator ribIt = m_rib.find(prefix);
// Name prefix exists
- if (ribIt != m_rib.end())
- {
- shared_ptr<RibEntry> entry = ribIt->second;
+ if (ribIt != m_rib.end()) {
+ shared_ptr<RibEntry> entry = ribIt->second;
- RibEntry::iterator routeIt = entry->findRoute(route);
+ RibEntry::iterator routeIt = entry->findRoute(route);
- if (routeIt != entry->end())
- {
- return &((*routeIt));
- }
+ if (routeIt != entry->end()) {
+ return &((*routeIt));
}
+ }
return nullptr;
}
@@ -100,96 +86,73 @@
RibTable::iterator ribIt = m_rib.find(prefix);
// Name prefix exists
- if (ribIt != m_rib.end())
- {
- shared_ptr<RibEntry> entry(ribIt->second);
+ if (ribIt != m_rib.end()) {
+ shared_ptr<RibEntry> entry(ribIt->second);
- RibEntry::iterator routeIt = entry->findRoute(route);
+ RibEntry::iterator routeIt = entry->findRoute(route);
- if (routeIt == entry->end())
- {
- // Will the new route change the namespace's capture flag?
- bool captureWasTurnedOn = (entry->hasCapture() == false && isCaptureFlagSet(route.flags));
-
- // New route
- entry->insertRoute(route);
- m_nItems++;
-
- // Register with face lookup table
- m_faceMap[route.faceId].push_back(entry);
-
- createFibUpdatesForNewRoute(*entry, route, captureWasTurnedOn);
- }
- else // Route exists, update fields
- {
- // First cancel old scheduled event, if any, then set the EventId to new one
- if (static_cast<bool>(routeIt->getExpirationEvent()))
- {
- NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
- << *routeIt);
- scheduler::cancel(routeIt->getExpirationEvent());
- }
-
- // No checks are required here as the iterator needs to be updated in all cases.
- routeIt->setExpirationEvent(route.getExpirationEvent());
-
- // Save flags for update processing
- uint64_t previousFlags = routeIt->flags;
-
- // If the route's cost didn't change and child inherit is not set,
- // no need to traverse subtree.
- uint64_t previousCost = routeIt->cost;
-
- routeIt->flags = route.flags;
- routeIt->cost = route.cost;
- routeIt->expires = route.expires;
-
- createFibUpdatesForUpdatedRoute(*entry, route, previousFlags, previousCost);
- }
- }
- else // New name prefix
- {
- shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));
-
- m_rib[prefix] = entry;
- m_nItems++;
-
- entry->setName(prefix);
+ if (routeIt == entry->end()) {
+ // New route
entry->insertRoute(route);
-
- // Find prefix's parent
- shared_ptr<RibEntry> parent = findParent(prefix);
-
- // Add self to parent's children
- if (static_cast<bool>(parent))
- {
- parent->addChild(entry);
- }
-
- RibEntryList children = findDescendants(prefix);
-
- for (std::list<shared_ptr<RibEntry> >::iterator child = children.begin();
- child != children.end(); ++child)
- {
- if ((*child)->getParent() == parent)
- {
- // Remove child from parent and inherit parent's child
- if (static_cast<bool>(parent))
- {
- parent->removeChild((*child));
- }
- entry->addChild((*child));
- }
- }
+ m_nItems++;
// Register with face lookup table
m_faceMap[route.faceId].push_back(entry);
-
- createFibUpdatesForNewRibEntry(*entry, route);
-
- // do something after inserting an entry
- afterInsertEntry(prefix);
}
+ else {
+ // Route exists, update fields
+ // First cancel old scheduled event, if any, then set the EventId to new one
+ if (static_cast<bool>(routeIt->getExpirationEvent())) {
+ NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
+ << *routeIt);
+ scheduler::cancel(routeIt->getExpirationEvent());
+ }
+
+ // No checks are required here as the iterator needs to be updated in all cases.
+ routeIt->setExpirationEvent(route.getExpirationEvent());
+
+ routeIt->flags = route.flags;
+ routeIt->cost = route.cost;
+ routeIt->expires = route.expires;
+ }
+ }
+ else {
+ // New name prefix
+ shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));
+
+ m_rib[prefix] = entry;
+ m_nItems++;
+
+ entry->setName(prefix);
+ entry->insertRoute(route);
+
+ // Find prefix's parent
+ shared_ptr<RibEntry> parent = findParent(prefix);
+
+ // Add self to parent's children
+ if (parent != nullptr) {
+ parent->addChild(entry);
+ }
+
+ RibEntryList children = findDescendants(prefix);
+
+ for (const auto& child : children) {
+ if (child->getParent() == parent) {
+ // Remove child from parent and inherit parent's child
+ if (parent != nullptr) {
+ parent->removeChild(child);
+ }
+
+ entry->addChild(child);
+ }
+ }
+
+ // Register with face lookup table
+ m_faceMap[route.faceId].push_back(entry);
+
+ // do something after inserting an entry
+ afterInsertEntry(prefix);
+ }
}
void
@@ -198,110 +161,51 @@
RibTable::iterator ribIt = m_rib.find(prefix);
// Name prefix exists
- if (ribIt != m_rib.end())
- {
- shared_ptr<RibEntry> entry(ribIt->second);
+ if (ribIt != m_rib.end()) {
+ shared_ptr<RibEntry> entry(ribIt->second);
- const bool hadCapture = entry->hasCapture();
+ RibEntry::iterator routeIt = entry->findRoute(route);
- // Need to copy route to do FIB updates with correct cost and flags since nfdc does not
- // pass flags or cost
- RibEntry::iterator routeIt = entry->findRoute(route);
+ if (routeIt != entry->end()) {
+ entry->eraseRoute(routeIt);
+ m_nItems--;
- if (routeIt != entry->end())
- {
- Route routeToErase = *routeIt;
- routeToErase.flags = routeIt->flags;
- routeToErase.cost = routeIt->cost;
+ // If this RibEntry no longer has this faceId, unregister from face lookup table
+ if (!entry->hasFaceId(route.faceId)) {
+ m_faceMap[route.faceId].remove(entry);
+ }
- entry->eraseRoute(routeIt);
-
- m_nItems--;
-
- const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
-
- createFibUpdatesForErasedRoute(*entry, routeToErase, captureWasTurnedOff);
-
- // If this RibEntry no longer has this faceId, unregister from face lookup table
- if (!entry->hasFaceId(route.faceId))
- {
- m_faceMap[route.faceId].remove(entry);
- }
- else
- {
- // The RibEntry still has the face ID; need to update FIB
- // with lowest cost for the same route instead of removing the route from the FIB
- shared_ptr<Route> lowCostRoute = entry->getRouteWithLowestCostByFaceId(route.faceId);
-
- BOOST_ASSERT(static_cast<bool>(lowCostRoute));
-
- createFibUpdatesForNewRoute(*entry, *lowCostRoute, false);
- }
-
- // If a RibEntry's route list is empty, remove it from the tree
- if (entry->getRoutes().size() == 0)
- {
- eraseEntry(ribIt);
- }
- }
+ // If a RibEntry's route list is empty, remove it from the tree
+ if (entry->getRoutes().size() == 0) {
+ eraseEntry(ribIt);
+ }
}
+ }
}
void
-Rib::erase(const uint64_t faceId)
+Rib::onRouteExpiration(const Name& prefix, const Route& route)
{
- FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
+ NFD_LOG_DEBUG(route << " for " << prefix << " has expired");
- // No RIB entries have this face
- if (lookupIt == m_faceMap.end())
- {
- return;
- }
+ RibUpdate update;
+ update.setAction(RibUpdate::UNREGISTER)
+ .setName(prefix)
+ .setRoute(route);
- RibEntryList& ribEntries = lookupIt->second;
-
- // For each RIB entry that has faceId, remove the face from the entry
- for (shared_ptr<RibEntry>& entry : ribEntries)
- {
- const bool hadCapture = entry->hasCapture();
-
- // Find the routes in the entry
- for (RibEntry::iterator routeIt = entry->begin(); routeIt != entry->end(); ++routeIt)
- {
- if (routeIt->faceId == faceId)
- {
- Route copy = *routeIt;
-
- routeIt = entry->eraseRoute(routeIt);
- m_nItems--;
-
- const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
- createFibUpdatesForErasedRoute(*entry, copy, captureWasTurnedOff);
- }
- }
-
- // If a RibEntry's route list is empty, remove it from the tree
- if (entry->getRoutes().size() == 0)
- {
- eraseEntry(m_rib.find(entry->getName()));
- }
- }
-
- // Face no longer exists, remove from face lookup table
- m_faceMap.erase(lookupIt);
+ beginApplyUpdate(update, nullptr, nullptr);
}
shared_ptr<RibEntry>
Rib::findParent(const Name& prefix) const
{
- for (int i = prefix.size() - 1; i >= 0; i--)
- {
- RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
- if (it != m_rib.end())
- {
- return (it->second);
- }
+ for (int i = prefix.size() - 1; i >= 0; i--) {
+ RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
+
+ if (it != m_rib.end()) {
+ return (it->second);
}
+ }
return shared_ptr<RibEntry>();
}
@@ -313,21 +217,31 @@
RibTable::const_iterator it = m_rib.find(prefix);
- if (it != m_rib.end())
- {
- ++it;
- for (; it != m_rib.end(); ++it)
- {
- if (prefix.isPrefixOf(it->first))
- {
- children.push_back((it->second));
- }
- else
- {
- break;
- }
- }
+ if (it != m_rib.end()) {
+ ++it;
+ for (; it != m_rib.end(); ++it) {
+ if (prefix.isPrefixOf(it->first)) {
+ children.push_back((it->second));
+ }
+ else {
+ break;
+ }
}
+ }
+
+ return children;
+}
+
+std::list<shared_ptr<RibEntry>>
+Rib::findDescendantsForNonInsertedName(const Name& prefix) const
+{
+ std::list<shared_ptr<RibEntry>> children;
+
+ for (std::pair<Name, shared_ptr<RibEntry>> pair : m_rib) {
+ if (prefix.isPrefixOf(pair.first)) {
+ children.push_back(pair.second);
+ }
+ }
return children;
}
@@ -336,43 +250,35 @@
Rib::eraseEntry(RibTable::iterator it)
{
// Entry does not exist
- if (it == m_rib.end())
- {
- return m_rib.end();
- }
+ if (it == m_rib.end()) {
+ return m_rib.end();
+ }
shared_ptr<RibEntry> entry(it->second);
- // Remove inherited routes from namespace
- createFibUpdatesForErasedRibEntry(*entry);
-
shared_ptr<RibEntry> parent = entry->getParent();
// Remove self from parent's children
- if (static_cast<bool>(parent))
- {
- parent->removeChild(entry);
+ if (parent != nullptr) {
+ parent->removeChild(entry);
+ }
+
+ for (auto childIt = entry->getChildren().begin(); childIt != entry->getChildren().end(); ) {
+ shared_ptr<RibEntry> child = *childIt;
+
+ // Advance iterator so it is not invalidated by removal
+ ++childIt;
+
+ // Remove children from self
+ entry->removeChild(child);
+
+ // Update parent's children
+ if (parent != nullptr) {
+ parent->addChild(child);
}
+ }
- std::list<shared_ptr<RibEntry> > children = entry->getChildren();
-
- for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
- {
- // Remove children from self
- entry->removeChild(*child);
-
- // Update parent's children
- if (static_cast<bool>(parent))
- {
- parent->addChild(*child);
- }
- }
-
- // Must save and advance iterator to return a valid iterator
- RibTable::iterator nextIt = it;
- nextIt++;
-
- m_rib.erase(it);
+ RibTable::iterator nextIt = m_rib.erase(it);
// do something after erasing an entry.
afterEraseEntry(entry->getName());
@@ -380,325 +286,6 @@
return nextIt;
}
-bool
-compareFibUpdates(const shared_ptr<const FibUpdate> lhs, const shared_ptr<const FibUpdate> rhs)
-{
- return ((lhs->name == rhs->name) &&
- (lhs->faceId == rhs->faceId));
-}
-
-void
-Rib::insertFibUpdate(shared_ptr<FibUpdate> update)
-{
- // If an update with the same name and Face ID already exists, replace it
- FibUpdateList::iterator it = std::find_if(m_fibUpdateList.begin(), m_fibUpdateList.end(),
- bind(&compareFibUpdates, _1, update));
-
- if (it != m_fibUpdateList.end())
- {
- // Get rid of the const to alter the action, prevents copying or removal and
- // insertion
- FibUpdate& entry = const_cast<FibUpdate&>(*(*it));
- entry.action = update->action;
- entry.cost = update->cost;
- }
- else
- {
- m_fibUpdateList.push_back(update);
- }
-}
-
-void
-Rib::createFibUpdatesForNewRibEntry(RibEntry& entry, const Route& route)
-{
- // Create FIB update for new entry
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
-
- // No flags are set
- if (!isAnyFlagSet(route.flags))
- {
- // Add ancestor routes to self
- addInheritedRoutesToEntry(entry, getAncestorRoutes(entry));
- }
- else if (areBothFlagsSet(route.flags))
- {
- // Add route to children
- RouteSet routesToAdd;
- routesToAdd.insert(route);
-
- // Remove routes blocked by capture and add self to children
- modifyChildrensInheritedRoutes(entry, routesToAdd, getAncestorRoutes(entry));
- }
- else if (isChildInheritFlagSet(route.flags))
- {
- RouteSet ancestorRoutes = getAncestorRoutes(entry);
-
- // Add ancestor routes to self
- addInheritedRoutesToEntry(entry, ancestorRoutes);
-
- // If there is an ancestor route with the same Face ID as the new route, replace it
- // with the new route
- RouteSet::iterator it = ancestorRoutes.find(route);
-
- // There is a route that needs to be overwritten, erase and then replace
- if (it != ancestorRoutes.end())
- {
- ancestorRoutes.erase(it);
- }
-
- // Add new route to ancestor list so it can be added to children
- ancestorRoutes.insert(route);
-
- // Add ancestor routes to children
- modifyChildrensInheritedRoutes(entry, ancestorRoutes, RouteSet());
- }
- else if (isCaptureFlagSet(route.flags))
- {
- // Remove routes blocked by capture
- modifyChildrensInheritedRoutes(entry, RouteSet(), getAncestorRoutes(entry));
- }
-}
-
-void
-Rib::createFibUpdatesForNewRoute(RibEntry& entry, const Route& route, bool captureWasTurnedOn)
-{
- // Only update if the new route has a lower cost than a previously installed route
- shared_ptr<Route> prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
-
- RouteSet routesToAdd;
- if (isChildInheritFlagSet(route.flags))
- {
- // Add to children if this new route doesn't override a previous lower cost, or
- // add to children if this new route is lower cost than a previous route.
- // Less than equal, since entry may find this route
- if (prevRoute == nullptr || route.cost <= prevRoute->cost)
- {
- // Add self to children
- routesToAdd.insert(route);
- }
- }
-
- RouteSet routesToRemove;
- if (captureWasTurnedOn)
- {
- // Capture flag on
- routesToRemove = getAncestorRoutes(entry);
-
- // Remove ancestor routes from self
- removeInheritedRoutesFromEntry(entry, routesToRemove);
- }
-
- modifyChildrensInheritedRoutes(entry, routesToAdd, routesToRemove);
-
- // If another route with same faceId and lower cost, don't update.
- // Must be done last so that add updates replace removal updates
- // Create FIB update for new entry
- if (route.cost <= entry.getRouteWithLowestCostByFaceId(route.faceId)->cost)
- {
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
- }
-}
-
-void
-Rib::createFibUpdatesForUpdatedRoute(RibEntry& entry, const Route& route,
- const uint64_t previousFlags, const uint64_t previousCost)
-{
- const bool costDidChange = (route.cost != previousCost);
-
- // Look for the installed route with the lowest cost and child inherit set
- shared_ptr<Route> prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);
-
- // No flags changed and cost didn't change, no change in FIB
- if (route.flags == previousFlags && !costDidChange)
- {
- return;
- }
-
- // Cost changed so create update for the entry itself
- if (costDidChange)
- {
- // Create update if this route's cost is lower than other routes
- if (route.cost <= entry.getRouteWithLowestCostByFaceId(route.faceId)->cost)
- {
- // Create FIB update for the updated entry
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
- }
- else if (previousCost < entry.getRouteWithLowestCostByFaceId(route.faceId)->cost)
- {
- // Create update if this route used to be the lowest cost route but is no longer
- // the lowest cost route.
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevRoute->faceId,
- prevRoute->cost));
- }
-
- // If another route with same faceId and lower cost and ChildInherit exists,
- // don't update children.
- if (prevRoute == nullptr || route.cost <= prevRoute->cost)
- {
- // If no flags changed but child inheritance is set, need to update children
- // with new cost
- if ((route.flags == previousFlags) && isChildInheritFlagSet(route.flags))
- {
- // Add self to children
- RouteSet routesToAdd;
- routesToAdd.insert(route);
- modifyChildrensInheritedRoutes(entry, routesToAdd, RouteSet());
-
- return;
- }
- }
- }
-
- // Child inherit was turned on
- if (!isChildInheritFlagSet(previousFlags) && isChildInheritFlagSet(route.flags))
- {
- // If another route with same faceId and lower cost and ChildInherit exists,
- // don't update children.
- if (prevRoute == nullptr || route.cost <= prevRoute->cost)
- {
- // Add self to children
- RouteSet routesToAdd;
- routesToAdd.insert(route);
- modifyChildrensInheritedRoutes(entry, routesToAdd, RouteSet());
- }
-
- } // Child inherit was turned off
- else if (isChildInheritFlagSet(previousFlags) && !isChildInheritFlagSet(route.flags))
- {
- // Remove self from children
- RouteSet routesToRemove;
- routesToRemove.insert(route);
-
- RouteSet routesToAdd;
- // If another route with same faceId and ChildInherit exists, update children with this route.
- if (prevRoute != nullptr)
- {
- routesToAdd.insert(*prevRoute);
- }
- else
- {
- // Look for an ancestor that was blocked previously
- const RouteSet ancestorRoutes = getAncestorRoutes(entry);
- RouteSet::iterator it = ancestorRoutes.find(route);
-
- // If an ancestor is found, add it to children
- if (it != ancestorRoutes.end())
- {
- routesToAdd.insert(*it);
- }
- }
-
- modifyChildrensInheritedRoutes(entry, routesToAdd, routesToRemove);
- }
-
- // Capture was turned on
- if (!isCaptureFlagSet(previousFlags) && isCaptureFlagSet(route.flags))
- {
- RouteSet ancestorRoutes = getAncestorRoutes(entry);
-
- // Remove ancestor routes from self
- removeInheritedRoutesFromEntry(entry, ancestorRoutes);
-
- // Remove ancestor routes from children
- modifyChildrensInheritedRoutes(entry, RouteSet(), ancestorRoutes);
- } // Capture was turned off
- else if (isCaptureFlagSet(previousFlags) && !isCaptureFlagSet(route.flags))
- {
- RouteSet ancestorRoutes = getAncestorRoutes(entry);
-
- // Add ancestor routes to self
- addInheritedRoutesToEntry(entry, ancestorRoutes);
-
- // Add ancestor routes to children
- modifyChildrensInheritedRoutes(entry, ancestorRoutes, RouteSet());
- }
-}
-
-void
-Rib::createFibUpdatesForErasedRoute(RibEntry& entry, const Route& route,
- const bool captureWasTurnedOff)
-{
- insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
-
- if (areBothFlagsSet(route.flags))
- {
- // Remove self from children
- RouteSet routesToRemove;
- routesToRemove.insert(route);
-
- // If capture is turned off for the route, need to add ancestors
- // to self and children
- RouteSet routesToAdd;
- if (captureWasTurnedOff)
- {
- // Look for ancestors that were blocked previously
- routesToAdd = getAncestorRoutes(entry);
-
- // Add ancestor routes to self
- addInheritedRoutesToEntry(entry, routesToAdd);
- }
-
- modifyChildrensInheritedRoutes(entry, routesToAdd, routesToRemove);
- }
- else if (isChildInheritFlagSet(route.flags))
- {
- // If not blocked by capture, add inherited routes to children
- RouteSet routesToAdd;
- if (!entry.hasCapture())
- {
- routesToAdd = getAncestorRoutes(entry);
- }
-
- RouteSet routesToRemove;
- routesToRemove.insert(route);
-
- // Add ancestor routes to children
- modifyChildrensInheritedRoutes(entry, routesToAdd, routesToRemove);
- }
- else if (isCaptureFlagSet(route.flags))
- {
- // If capture is turned off for the route, need to add ancestors
- // to self and children
- RouteSet routesToAdd;
- if (captureWasTurnedOff)
- {
- // Look for an ancestors that were blocked previously
- routesToAdd = getAncestorRoutes(entry);
-
- // Add ancestor routes to self
- addInheritedRoutesToEntry(entry, routesToAdd);
- }
-
- modifyChildrensInheritedRoutes(entry, routesToAdd, RouteSet());
- }
-
- // Need to check if the removed route was blocking an inherited route
- RouteSet ancestorRoutes = getAncestorRoutes(entry);
-
- if (!entry.hasCapture())
- {
- // If there is an ancestor route with the same Face ID as the erased route, add that route
- // to the current entry
- RouteSet::iterator it = ancestorRoutes.find(route);
-
- if (it != ancestorRoutes.end())
- {
- entry.addInheritedRoute(*it);
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
- }
- }
-}
-
-void
-Rib::createFibUpdatesForErasedRibEntry(RibEntry& entry)
-{
- for (RibEntry::RouteList::iterator it = entry.getInheritedRoutes().begin();
- it != entry.getInheritedRoutes().end(); ++it)
- {
- insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
- }
-}
-
Rib::RouteSet
Rib::getAncestorRoutes(const RibEntry& entry) const
{
@@ -706,145 +293,216 @@
shared_ptr<RibEntry> parent = entry.getParent();
- while (static_cast<bool>(parent))
- {
- for (RibEntry::iterator it = parent->getRoutes().begin();
- it != parent->getRoutes().end(); ++it)
- {
- if (isChildInheritFlagSet(it->flags))
- {
- ancestorRoutes.insert(*it);
- }
- }
-
- if (parent->hasCapture())
- {
- break;
- }
-
- parent = parent->getParent();
- }
-
- return ancestorRoutes;
-}
-
-void
-Rib::addInheritedRoutesToEntry(RibEntry& entry, const Rib::RouteSet& routesToAdd)
-{
- for (RouteSet::const_iterator it = routesToAdd.begin(); it != routesToAdd.end(); ++it)
- {
- // Don't add an ancestor route if the namespace has a route with that Face ID
- if (!entry.hasFaceId(it->faceId))
- {
- entry.addInheritedRoute(*it);
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
- }
- }
-}
-
-void
-Rib::removeInheritedRoutesFromEntry(RibEntry& entry, const Rib::RouteSet& routesToRemove)
-{
- for (RouteSet::const_iterator it = routesToRemove.begin(); it != routesToRemove.end(); ++it)
- {
- // Only remove if the route has been inherited
- if (entry.hasInheritedRoute(*it))
- {
- entry.removeInheritedRoute(*it);
- insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
- }
- }
-}
-
-void
-Rib::modifyChildrensInheritedRoutes(RibEntry& entry, const Rib::RouteSet& routesToAdd,
- const Rib::RouteSet& routesToRemove)
-{
- RibEntryList children = entry.getChildren();
-
- for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
- {
- traverseSubTree(*(*child), routesToAdd, routesToRemove);
- }
-}
-
-void
-Rib::traverseSubTree(RibEntry& entry, Rib::RouteSet routesToAdd, Rib::RouteSet routesToRemove)
-{
- // If a route on the namespace has the capture flag set, ignore self and children
- if (entry.hasCapture())
- {
- return;
- }
-
- // Remove inherited routes from current namespace
- for (Rib::RouteSet::const_iterator removeIt = routesToRemove.begin();
- removeIt != routesToRemove.end(); )
- {
- // If a route on the namespace has the same face and child inheritance set, ignore this route
- if (entry.hasChildInheritOnFaceId(removeIt->faceId))
- {
- routesToRemove.erase(removeIt++);
- continue;
- }
-
- // Only remove route if it removes an existing inherited route
- if (entry.hasInheritedRoute(*removeIt))
- {
- entry.removeInheritedRoute(*removeIt);
- insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
- }
-
- ++removeIt;
- }
-
- // Add inherited routes to current namespace
- for (Rib::RouteSet::const_iterator addIt = routesToAdd.begin(); addIt != routesToAdd.end(); )
- {
- // If a route on the namespace has the same face and child inherit set, ignore this route
- if (entry.hasChildInheritOnFaceId(addIt->faceId))
- {
- routesToAdd.erase(addIt++);
- continue;
+ while (parent != nullptr) {
+ for (const Route& route : parent->getRoutes()) {
+ if (route.isChildInherit()) {
+ ancestorRoutes.insert(route);
}
-
- // Only add route if it does not override an existing route
- if (!entry.hasFaceId(addIt->faceId))
- {
- RibEntry::RouteList::iterator routeIt = entry.findInheritedRoute(*addIt);
-
- // If the entry already has the inherited route, just update the route
- if (routeIt != entry.getInheritedRoutes().end())
- {
- routeIt->cost = addIt->cost;
- }
- else // Otherwise, this is a newly inherited route
- {
- entry.addInheritedRoute(*addIt);
- }
-
- insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
- }
-
- ++addIt;
}
- Rib::RibEntryList children = entry.getChildren();
-
- // Apply route operations to current namespace's children
- for (Rib::RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
- {
- traverseSubTree(*(*child), routesToAdd, routesToRemove);
+ if (parent->hasCapture()) {
+ break;
}
+
+ parent = parent->getParent();
+ }
+
+ return ancestorRoutes;
+}
+
+Rib::RouteSet
+Rib::getAncestorRoutes(const Name& name) const
+{
+ RouteSet ancestorRoutes(&sortRoutes);
+
+ shared_ptr<RibEntry> parent = findParent(name);
+
+ while (parent != nullptr) {
+ for (const Route& route : parent->getRoutes()) {
+ if (route.isChildInherit()) {
+ ancestorRoutes.insert(route);
+ }
+ }
+
+ if (parent->hasCapture()) {
+ break;
+ }
+
+ parent = parent->getParent();
+ }
+
+ return ancestorRoutes;
+}
+
+void
+Rib::beginApplyUpdate(const RibUpdate& update,
+ const Rib::UpdateSuccessCallback& onSuccess,
+ const Rib::UpdateFailureCallback& onFailure)
+{
+ BOOST_ASSERT(m_fibUpdater != nullptr);
+
+ addUpdateToQueue(update, onSuccess, onFailure);
+
+ sendBatchFromQueue();
+}
+
+void
+Rib::beginRemoveFace(uint64_t faceId)
+{
+ for (const auto& nameAndRoute : findRoutesWithFaceId(faceId)) {
+ RibUpdate update;
+ update.setAction(RibUpdate::REMOVE_FACE)
+ .setName(nameAndRoute.first)
+ .setRoute(nameAndRoute.second);
+
+ addUpdateToQueue(update, nullptr, nullptr);
+ }
+
+ sendBatchFromQueue();
+}
+
+void
+Rib::addUpdateToQueue(const RibUpdate& update,
+ const Rib::UpdateSuccessCallback& onSuccess,
+ const Rib::UpdateFailureCallback& onFailure)
+{
+ RibUpdateBatch batch(update.getRoute().faceId);
+ batch.add(update);
+
+ UpdateQueueItem item{batch, onSuccess, onFailure};
+ m_updateBatches.push_back(std::move(item));
+}
+
+void
+Rib::sendBatchFromQueue()
+{
+ if (m_updateBatches.empty() || m_isUpdateInProgress) {
+ return;
+ }
+
+ m_isUpdateInProgress = true;
+
+ UpdateQueueItem item = std::move(m_updateBatches.front());
+ m_updateBatches.pop_front();
+
+ RibUpdateBatch& batch = item.batch;
+
+ // Until task #1698, each RibUpdateBatch contains exactly one RIB update
+ BOOST_ASSERT(batch.size() == 1);
+
+ const Rib::UpdateSuccessCallback& managerSuccessCallback = item.managerSuccessCallback;
+ const Rib::UpdateFailureCallback& managerFailureCallback = item.managerFailureCallback;
+
+ m_fibUpdater->computeAndSendFibUpdates(batch,
+ bind(&Rib::onFibUpdateSuccess, this,
+ batch, _1, managerSuccessCallback),
+ bind(&Rib::onFibUpdateFailure, this,
+ managerFailureCallback, _1, _2));
+
+ if (m_onSendBatchFromQueue != nullptr) {
+ m_onSendBatchFromQueue(batch);
+ }
+}
+
+void
+Rib::onFibUpdateSuccess(const RibUpdateBatch& batch,
+ const RibUpdateList& inheritedRoutes,
+ const Rib::UpdateSuccessCallback& onSuccess)
+{
+ for (const RibUpdate& update : batch) {
+ switch (update.getAction()) {
+ case RibUpdate::REGISTER:
+ insert(update.getName(), update.getRoute());
+ break;
+ case RibUpdate::UNREGISTER:
+ case RibUpdate::REMOVE_FACE:
+ erase(update.getName(), update.getRoute());
+ break;
+ }
+ }
+
+ // Add and remove precalculated inherited routes to RibEntries
+ modifyInheritedRoutes(inheritedRoutes);
+
+ m_isUpdateInProgress = false;
+
+ if (onSuccess != nullptr) {
+ onSuccess();
+ }
+
+ // Try to advance the batch queue
+ sendBatchFromQueue();
+}
+
+void
+Rib::onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
+ uint32_t code, const std::string& error)
+{
+ m_isUpdateInProgress = false;
+
+ if (onFailure != nullptr) {
+ onFailure(code, error);
+ }
+
+ // Try to advance the batch queue
+ sendBatchFromQueue();
+}
+
+void
+Rib::modifyInheritedRoutes(const RibUpdateList& inheritedRoutes)
+{
+ for (const RibUpdate& update : inheritedRoutes) {
+ RibTable::iterator ribIt = m_rib.find(update.getName());
+
+ BOOST_ASSERT(ribIt != m_rib.end());
+ shared_ptr<RibEntry> entry(ribIt->second);
+
+ switch (update.getAction()) {
+ case RibUpdate::REGISTER:
+ entry->addInheritedRoute(update.getRoute());
+ break;
+ case RibUpdate::UNREGISTER:
+ entry->removeInheritedRoute(update.getRoute());
+ break;
+ case RibUpdate::REMOVE_FACE:
+ break;
+ }
+ }
+}
+
+std::list<Rib::NameAndRoute>
+Rib::findRoutesWithFaceId(uint64_t faceId)
+{
+ std::list<NameAndRoute> routes;
+
+ FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
+
+ // No RIB entries have this face
+ if (lookupIt == m_faceMap.end()) {
+ return routes;
+ }
+
+ RibEntryList& ribEntries = lookupIt->second;
+
+ // For each RIB entry that has faceId
+ for (const shared_ptr<RibEntry>& entry : ribEntries) {
+ // Find the routes in the entry
+ for (const Route& route : *entry) {
+ if (route.faceId == faceId) {
+ routes.push_back(NameAndRoute(entry->getName(), route));
+ }
+ }
+ }
+
+ return routes;
}
std::ostream&
operator<<(std::ostream& os, const Rib& rib)
{
- for (Rib::RibTable::const_iterator it = rib.begin(); it != rib.end(); ++it)
- {
- os << *(it->second) << "\n";
- }
+ for (const auto& item : rib) {
+ os << item.second << "\n";
+ }
return os;
}
diff --git a/rib/rib.hpp b/rib/rib.hpp
index dabf69f..2e13692 100644
--- a/rib/rib.hpp
+++ b/rib/rib.hpp
@@ -26,15 +26,20 @@
#ifndef NFD_RIB_RIB_HPP
#define NFD_RIB_RIB_HPP
-#include "rib-entry.hpp"
-#include "fib-update.hpp"
#include "common.hpp"
-#include <ndn-cxx/management/nfd-control-command.hpp>
-#include <ndn-cxx/util/signal.hpp>
+
+#include "rib-entry.hpp"
+#include "rib-update-batch.hpp"
+
+#include <ndn-cxx/management/nfd-control-parameters.hpp>
namespace nfd {
namespace rib {
+using ndn::nfd::ControlParameters;
+
+class FibUpdater;
+
/** \brief represents the RIB
*/
class Rib : noncopyable
@@ -46,25 +51,20 @@
typedef std::map<uint64_t, std::list<shared_ptr<RibEntry>>> FaceLookupTable;
typedef bool (*RouteComparePredicate)(const Route&, const Route&);
typedef std::set<Route, RouteComparePredicate> RouteSet;
- typedef std::list<shared_ptr<const FibUpdate>> FibUpdateList;
Rib();
+ ~Rib();
+
+ void
+ setFibUpdater(FibUpdater* updater);
+
const_iterator
find(const Name& prefix) const;
Route*
find(const Name& prefix, const Route& route) const;
- void
- insert(const Name& prefix, const Route& route);
-
- void
- erase(const Name& prefix, const Route& route);
-
- void
- erase(const uint64_t faceId);
-
const_iterator
begin() const;
@@ -86,56 +86,123 @@
std::list<shared_ptr<RibEntry>>
findDescendants(const Name& prefix) const;
- const std::list<shared_ptr<const FibUpdate>>&
- getFibUpdates() const;
+ /** \brief finds namespaces under the passed prefix
+ *
+ * \note Unlike findDescendants, needs to find where prefix would fit in tree
+ * before collecting list of descendant prefixes
+ *
+ * \return{ a list of entries which would be under the passed prefix if the prefix
+ * existed in the RIB }
+ */
+ std::list<shared_ptr<RibEntry>>
+ findDescendantsForNonInsertedName(const Name& prefix) const;
+
+public:
+ typedef function<void()> UpdateSuccessCallback;
+ typedef function<void(uint32_t code, const std::string& error)> UpdateFailureCallback;
+
+ /** \brief passes the provided RibUpdateBatch to FibUpdater to calculate and send FibUpdates.
+ *
+ * If the FIB is updated successfully, onFibUpdateSuccess() will be called, and the
+ * RIB will be updated
+ *
+ * If the FIB update fails, onFibUpdateFailure() will be called, and the RIB will not
+ * be updated.
+ */
+ void
+ beginApplyUpdate(const RibUpdate& update,
+ const UpdateSuccessCallback& onSuccess,
+ const UpdateFailureCallback& onFailure);
+
+ /** \brief starts the FIB update process when a face has been destroyed
+ */
+ void
+ beginRemoveFace(uint64_t faceId);
void
- clearFibUpdates();
+ onFibUpdateSuccess(const RibUpdateBatch& batch,
+ const RibUpdateList& inheritedRoutes,
+ const Rib::UpdateSuccessCallback& onSuccess);
+
+ void
+ onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
+ uint32_t code, const std::string& error);
+
+ void
+ onRouteExpiration(const Name& prefix, const Route& route);
+
+private:
+ /** \brief adds the passed update to a RibUpdateBatch and adds the batch to
+ * the end of the update queue.
+ *
+ * If an update is not in progress, the front update batch in the queue will be
+ * processed by the RIB.
+ *
+ * If an update is in progress, the added update will eventually be processed
+ * when it reaches the front of the queue; after other update batches are
+ * processed, the queue is advanced.
+ */
+ void
+ addUpdateToQueue(const RibUpdate& update,
+ const Rib::UpdateSuccessCallback& onSuccess,
+ const Rib::UpdateFailureCallback& onFailure);
+
+ /** \brief Attempts to send the front update batch in the queue.
+ *
+ * If an update is not in progress, the front update batch in the queue will be
+ * sent to the RIB for processing.
+ *
+ * If an update is in progress, nothing will be done.
+ */
+ void
+ sendBatchFromQueue();
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ // Used by RibManager unit-tests to get sent batch to simulate successful FIB update
+ function<void(RibUpdateBatch)> m_onSendBatchFromQueue;
+
+public:
+ void
+ insert(const Name& prefix, const Route& route);
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ void
+ erase(const Name& prefix, const Route& route);
private:
RibTable::iterator
eraseEntry(RibTable::iterator it);
void
- insertFibUpdate(shared_ptr<FibUpdate> update);
+ updateRib(const RibUpdateBatch& batch);
- void
- createFibUpdatesForNewRibEntry(RibEntry& entry, const Route& route);
-
- void
- createFibUpdatesForNewRoute(RibEntry& entry, const Route& route,
- const bool captureWasTurnedOn);
-
- void
- createFibUpdatesForUpdatedRoute(RibEntry& entry, const Route& route,
- const uint64_t previousFlags, const uint64_t previousCost);
- void
- createFibUpdatesForErasedRoute(RibEntry& entry, const Route& route,
- const bool captureWasTurnedOff);
-
- void
- createFibUpdatesForErasedRibEntry(RibEntry& entry);
-
+ /** \brief returns routes inherited from the entry's ancestors
+ *
+ * \return{ a list of inherited routes }
+ */
RouteSet
getAncestorRoutes(const RibEntry& entry) const;
- void
- modifyChildrensInheritedRoutes(RibEntry& entry, const Rib::RouteSet& routesToAdd,
- const Rib::RouteSet& routesToRemove);
+ /** \brief returns routes inherited from the parent of the name and the parent's ancestors
+ *
+ * \note A parent is first found for the passed name before inherited routes are collected
+ *
+ * \return{ a list of inherited routes }
+ */
+ RouteSet
+ getAncestorRoutes(const Name& name) const;
- void
- traverseSubTree(RibEntry& entry, Rib::RouteSet routesToAdd,
- Rib::RouteSet routesToRemove);
-
- /** \brief Adds passed routes to the entry's inherited routes list
+ /** \brief applies the passed inheritedRoutes and their actions to the corresponding RibEntries'
+ * inheritedRoutes lists
*/
void
- addInheritedRoutesToEntry(RibEntry& entry, const Rib::RouteSet& routesToAdd);
+ modifyInheritedRoutes(const RibUpdateList& inheritedRoutes);
- /** \brief Removes passed routes from the entry's inherited routes list
- */
- void
- removeInheritedRoutesFromEntry(RibEntry& entry, const Rib::RouteSet& routesToRemove);
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ typedef std::pair<const Name&,const Route&> NameAndRoute;
+
+ std::list<NameAndRoute>
+ findRoutesWithFaceId(uint64_t faceId);
public:
ndn::util::signal::Signal<Rib, Name> afterInsertEntry;
@@ -144,9 +211,26 @@
private:
RibTable m_rib;
FaceLookupTable m_faceMap;
- FibUpdateList m_fibUpdateList;
+ FibUpdater* m_fibUpdater;
size_t m_nItems;
+
+ friend class FibUpdater;
+
+private:
+ struct UpdateQueueItem
+ {
+ RibUpdateBatch batch;
+ const Rib::UpdateSuccessCallback managerSuccessCallback;
+ const Rib::UpdateFailureCallback managerFailureCallback;
+ };
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ typedef std::list<UpdateQueueItem> UpdateQueue;
+ UpdateQueue m_updateBatches;
+
+private:
+ bool m_isUpdateInProgress;
};
inline Rib::const_iterator
@@ -173,18 +257,6 @@
return m_rib.empty();
}
-inline const Rib::FibUpdateList&
-Rib::getFibUpdates() const
-{
- return m_fibUpdateList;
-}
-
-inline void
-Rib::clearFibUpdates()
-{
- m_fibUpdateList.clear();
-}
-
std::ostream&
operator<<(std::ostream& os, const Rib& rib);
diff --git a/rib/route.cpp b/rib/route.cpp
new file mode 100644
index 0000000..7ee9353
--- /dev/null
+++ b/rib/route.cpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "route.hpp"
+
+namespace nfd {
+namespace rib {
+
+bool
+Route::operator==(const Route& other) const
+{
+ return (this->faceId == other.faceId &&
+ this->origin == other.origin &&
+ this->flags == other.flags &&
+ this->cost == other.cost &&
+ this->expires == other.expires);
+}
+
+std::ostream&
+operator<<(std::ostream& os, const Route& route)
+{
+ os << "Route("
+ << "faceid: " << route.faceId
+ << ", origin: " << route.origin
+ << ", cost: " << route.cost
+ << ", flags: " << route.flags;
+ if (route.expires != time::steady_clock::TimePoint::max()) {
+ os << ", expires in: " << (route.expires - time::steady_clock::now());
+ }
+ else {
+ os << ", never expires";
+ }
+ os << ")";
+
+ return os;
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/route.hpp b/rib/route.hpp
index 68769ef..d6a8b6e 100644
--- a/rib/route.hpp
+++ b/rib/route.hpp
@@ -47,6 +47,9 @@
{
}
+ bool
+ operator==(const Route& other) const;
+
public:
void
setExpirationEvent(const scheduler::EventId eid)
@@ -60,6 +63,18 @@
return m_expirationEvent;
}
+ bool
+ isChildInherit() const
+ {
+ return flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
+ }
+
+ bool
+ isCapture() const
+ {
+ return flags & ndn::nfd::ROUTE_FLAG_CAPTURE;
+ }
+
public:
uint64_t faceId;
uint64_t origin;
@@ -83,7 +98,6 @@
return (route.faceId == faceId);
}
-// Method definition in rib-entry.cpp
std::ostream&
operator<<(std::ostream& os, const Route& route);