diff --git a/daemon/mgmt/rib-manager.cpp b/daemon/mgmt/rib-manager.cpp
index 383c47f..1e881fa 100644
--- a/daemon/mgmt/rib-manager.cpp
+++ b/daemon/mgmt/rib-manager.cpp
@@ -141,8 +141,6 @@
     NFD_LOG_TRACE("Scheduled unregistration at: " << *route.expires);
   }
 
-  m_registeredFaces.insert(route.faceId);
-
   RibUpdate update;
   update.setAction(RibUpdate::REGISTER)
         .setName(name)
@@ -200,8 +198,6 @@
       route.flags = ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
 
       m_rib.insert(topPrefix, route);
-
-      m_registeredFaces.insert(route.faceId);
     },
     [=] (const ControlResponse& res) {
       NDN_THROW(Error("Cannot add FIB entry " + topPrefix.toUri() + " (" +
@@ -449,13 +445,6 @@
 }
 
 void
-RibManager::onFaceDestroyedEvent(uint64_t faceId)
-{
-  m_rib.beginRemoveFace(faceId);
-  m_registeredFaces.erase(faceId);
-}
-
-void
 RibManager::scheduleActiveFaceFetch(const time::seconds& timeToWait)
 {
   m_activeFaceFetchEvent = getScheduler().schedule(timeToWait, [this] { fetchActiveFaces(); });
@@ -466,19 +455,11 @@
 {
   NFD_LOG_DEBUG("Checking for invalid face registrations");
 
-  FaceIdSet activeFaceIds;
+  std::set<uint64_t> activeFaceIds;
   for (const auto& faceStatus : activeFaces) {
     activeFaceIds.insert(faceStatus.getFaceId());
   }
-
-  // Look for face IDs that were registered but not active to find missed
-  // face destroyed events
-  for (auto faceId : m_registeredFaces) {
-    if (activeFaceIds.count(faceId) == 0) {
-      NFD_LOG_DEBUG("Removing invalid FaceId " << faceId);
-      getGlobalIoService().post([this, faceId] { onFaceDestroyedEvent(faceId); });
-    }
-  }
+  getGlobalIoService().post([=] { m_rib.beginRemoveFailedFaces(activeFaceIds); });
 
   // Reschedule the check for future clean up
   scheduleActiveFaceFetch(ACTIVE_FACE_FETCH_INTERVAL);
@@ -491,7 +472,7 @@
 
   if (notification.getKind() == ndn::nfd::FACE_EVENT_DESTROYED) {
     NFD_LOG_DEBUG("Received notification for destroyed FaceId " << notification.getFaceId());
-    getGlobalIoService().post([this, id = notification.getFaceId()] { onFaceDestroyedEvent(id); });
+    getGlobalIoService().post([this, id = notification.getFaceId()] { m_rib.beginRemoveFace(id); });
   }
 }
 
diff --git a/daemon/mgmt/rib-manager.hpp b/daemon/mgmt/rib-manager.hpp
index a5e663f..1be0b81 100644
--- a/daemon/mgmt/rib-manager.hpp
+++ b/daemon/mgmt/rib-manager.hpp
@@ -223,9 +223,6 @@
   void
   onFetchActiveFacesFailure(uint32_t code, const std::string& reason);
 
-  void
-  onFaceDestroyedEvent(uint64_t faceId);
-
 PUBLIC_WITH_TESTS_ELSE_PRIVATE:
   void
   scheduleActiveFaceFetch(const time::seconds& timeToWait);
@@ -251,8 +248,6 @@
   bool m_isLocalhopEnabled;
 
   scheduler::ScopedEventId m_activeFaceFetchEvent;
-  using FaceIdSet = std::set<uint64_t>;
-  FaceIdSet m_registeredFaces; ///< contains FaceIds with one or more Routes in the RIB
 };
 
 std::ostream&
diff --git a/daemon/rib/rib.cpp b/daemon/rib/rib.cpp
index 1491c87..0f099d6 100644
--- a/daemon/rib/rib.cpp
+++ b/daemon/rib/rib.cpp
@@ -114,7 +114,7 @@
       afterAddRoute(RibRouteRef{entry, entryIt});
 
       // Register with face lookup table
-      m_faceMap[route.faceId].push_back(entry);
+      m_faceEntries.emplace(route.faceId, entry);
     }
     else {
       // Route exists, update fields
@@ -159,7 +159,7 @@
     }
 
     // Register with face lookup table
-    m_faceMap[route.faceId].push_back(entry);
+    m_faceEntries.emplace(route.faceId, entry);
 
     // do something after inserting an entry
     afterInsertEntry(prefix);
@@ -171,28 +171,35 @@
 Rib::erase(const Name& prefix, const Route& route)
 {
   auto ribIt = m_rib.find(prefix);
+  if (ribIt == m_rib.end()) {
+    // Name prefix does not exist
+    return;
+  }
 
-  // Name prefix exists
-  if (ribIt != m_rib.end()) {
-    shared_ptr<RibEntry> entry = ribIt->second;
-    auto routeIt = entry->findRoute(route);
+  shared_ptr<RibEntry> entry = ribIt->second;
+  auto routeIt = entry->findRoute(route);
 
-    if (routeIt != entry->end()) {
-      beforeRemoveRoute(RibRouteRef{entry, routeIt});
+  if (routeIt != entry->end()) {
+    beforeRemoveRoute(RibRouteRef{entry, routeIt});
 
-      auto faceId = route.faceId;
-      entry->eraseRoute(routeIt);
-      m_nItems--;
+    auto faceId = route.faceId;
+    entry->eraseRoute(routeIt);
+    m_nItems--;
 
-      // If this RibEntry no longer has this faceId, unregister from face lookup table
-      if (!entry->hasFaceId(faceId)) {
-        m_faceMap[faceId].remove(entry);
+    // If this RibEntry no longer has this faceId, unregister from face lookup table
+    if (!entry->hasFaceId(faceId)) {
+      auto range = m_faceEntries.equal_range(faceId);
+      for (auto it = range.first; it != range.second; ++it) {
+        if (it->second == entry) {
+          m_faceEntries.erase(it);
+          break;
+        }
       }
+    }
 
-      // If a RibEntry's route list is empty, remove it from the tree
-      if (entry->getRoutes().empty()) {
-        eraseEntry(ribIt);
-      }
+    // If a RibEntry's route list is empty, remove it from the tree
+    if (entry->getRoutes().empty()) {
+      eraseEntry(ribIt);
     }
   }
 }
@@ -361,16 +368,39 @@
 void
 Rib::beginRemoveFace(uint64_t faceId)
 {
-  for (const auto& nameAndRoute : findRoutesWithFaceId(faceId)) {
+  auto range = m_faceEntries.equal_range(faceId);
+  for (auto it = range.first; it != range.second; ++it) {
+    enqueueRemoveFace(*it->second, faceId);
+  }
+  sendBatchFromQueue();
+}
+
+void
+Rib::beginRemoveFailedFaces(const std::set<uint64_t>& activeFaceIds)
+{
+  for (auto it = m_faceEntries.begin(); it != m_faceEntries.end(); ++it) {
+    if (activeFaceIds.count(it->first) > 0) {
+      continue;
+    }
+    enqueueRemoveFace(*it->second, it->first);
+  }
+  sendBatchFromQueue();
+}
+
+void
+Rib::enqueueRemoveFace(const RibEntry& entry, uint64_t faceId)
+{
+  for (const Route& route : entry) {
+    if (route.faceId != faceId) {
+      continue;
+    }
+
     RibUpdate update;
     update.setAction(RibUpdate::REMOVE_FACE)
-          .setName(nameAndRoute.first)
-          .setRoute(nameAndRoute.second);
-
+          .setName(entry.getName())
+          .setRoute(route);
     addUpdateToQueue(update, nullptr, nullptr);
   }
-
-  sendBatchFromQueue();
 }
 
 void
@@ -490,30 +520,6 @@
   }
 }
 
-std::list<Rib::NameAndRoute>
-Rib::findRoutesWithFaceId(uint64_t faceId)
-{
-  std::list<NameAndRoute> routes;
-
-  auto lookupIt = m_faceMap.find(faceId);
-  if (lookupIt == m_faceMap.end()) {
-    // No RIB entries have this face
-    return routes;
-  }
-
-  // For each RIB entry that has faceId
-  for (const auto& entry : lookupIt->second) {
-    // Find the routes in the entry
-    for (const Route& route : *entry) {
-      if (route.faceId == faceId) {
-        routes.emplace_back(entry->getName(), route);
-      }
-    }
-  }
-
-  return routes;
-}
-
 std::ostream&
 operator<<(std::ostream& os, const Rib& rib)
 {
diff --git a/daemon/rib/rib.hpp b/daemon/rib/rib.hpp
index ea848f8..f842edc 100644
--- a/daemon/rib/rib.hpp
+++ b/daemon/rib/rib.hpp
@@ -62,7 +62,6 @@
   typedef std::list<shared_ptr<RibEntry>> RibEntryList;
   typedef std::map<Name, shared_ptr<RibEntry>> RibTable;
   typedef RibTable::const_iterator const_iterator;
-  typedef std::map<uint64_t, std::list<shared_ptr<RibEntry>>> FaceLookupTable;
   typedef bool (*RouteComparePredicate)(const Route&, const Route&);
   typedef std::set<Route, RouteComparePredicate> RouteSet;
 
@@ -135,6 +134,9 @@
   beginRemoveFace(uint64_t faceId);
 
   void
+  beginRemoveFailedFaces(const std::set<uint64_t>& activeFaceIds);
+
+  void
   onFibUpdateSuccess(const RibUpdateBatch& batch,
                      const RibUpdateList& inheritedRoutes,
                      const Rib::UpdateSuccessCallback& onSuccess);
@@ -150,6 +152,9 @@
   insert(const Name& prefix, const Route& route);
 
 private:
+  void
+  enqueueRemoveFace(const RibEntry& entry, uint64_t faceId);
+
   /** \brief adds the passed update to a RibUpdateBatch and adds the batch to
   *          the end of the update queue.
   *
@@ -219,12 +224,6 @@
   void
   modifyInheritedRoutes(const RibUpdateList& inheritedRoutes);
 
-PUBLIC_WITH_TESTS_ELSE_PRIVATE:
-  using NameAndRoute = std::pair<const Name&, const Route&>;
-
-  std::list<NameAndRoute>
-  findRoutesWithFaceId(uint64_t faceId);
-
 public:
   /** \brief signals after a RIB entry is inserted
    *
@@ -251,7 +250,7 @@
 
 private:
   RibTable m_rib;
-  FaceLookupTable m_faceMap;
+  std::multimap<uint64_t, shared_ptr<RibEntry>> m_faceEntries; ///< FaceId => Entry with Route on this face
   FibUpdater* m_fibUpdater;
 
   size_t m_nItems;