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);