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;