diff --git a/src/route/fib.cpp b/src/route/fib.cpp
index c4ddad8..73cde75 100644
--- a/src/route/fib.cpp
+++ b/src/route/fib.cpp
@@ -26,6 +26,8 @@
 
 #include <map>
 #include <cmath>
+#include <algorithm>
+#include <iterator>
 
 namespace nlsr {
 
@@ -82,43 +84,6 @@
 }
 
 void
-Fib::removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, const NexthopList& installedHops)
-{
-  _LOG_DEBUG("Fib::removeOldNextHopsFromFibEntryAndNfd Called");
-
-  const ndn::Name& name = entry.getName();
-  NexthopList& entryHopList = entry.getNexthopList();
-
-  for (NexthopList::iterator it = entryHopList.begin(); it != entryHopList.end();) {
-
-    const std::string& faceUri = it->getConnectingFaceUri();
-
-    // See if the nexthop is installed in NFD's FIB
-    NexthopList::const_iterator foundIt = std::find_if(installedHops.cbegin(),
-                                                       installedHops.cend(),
-                                                       std::bind(&compareFaceUri, _1, faceUri));
-
-    // The next hop is not installed
-    if (foundIt == installedHops.cend()) {
-
-      if (isPrefixUpdatable(name)) {
-        // Remove the nexthop from NDN's FIB
-        unregisterPrefix(name, it->getConnectingFaceUri());
-      }
-
-      // Remove the next hop from the FIB entry
-      _LOG_DEBUG("Removing " << it->getConnectingFaceUri() << " from " << name);
-      // Since the iterator will be invalidated on removal, dereference the original
-      // and increment the copy
-      entryHopList.removeNextHop(*(it++));
-    }
-    else {
-      ++it;
-    }
-  }
-}
-
-void
 Fib::update(const ndn::Name& name, NexthopList& allHops)
 {
   FibEntry* entry = processUpdate(name, allHops);
@@ -176,7 +141,20 @@
     FibEntry& entry = (entryIt->second);
     addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
 
-    removeOldNextHopsFromFibEntryAndNfd(entry, hopsToAdd);
+    std::set<NextHop, NextHopComparator> hopsToRemove;
+    std::set_difference(entry.getNexthopList().begin(), entry.getNexthopList().end(),
+                        hopsToAdd.begin(), hopsToAdd.end(),
+                        std::inserter(hopsToRemove, hopsToRemove.end()), NextHopComparator());
+
+    bool isUpdatable = isPrefixUpdatable(entry.getName());
+    // Remove the uninstalled next hops from NFD and FIB entry
+    for (const auto& hop: hopsToRemove){
+      if (isUpdatable) {
+        unregisterPrefix(entry.getName(), hop.getConnectingFaceUri());
+      }
+      _LOG_DEBUG("Removing " << hop.getConnectingFaceUri() << " from " << entry.getName());
+      entry.getNexthopList().removeNextHop(hop);
+    }
 
     // Increment sequence number
     entry.setSeqNo(entry.getSeqNo() + 1);
diff --git a/src/route/fib.hpp b/src/route/fib.hpp
index 5e15fea..10aa4fa 100644
--- a/src/route/fib.hpp
+++ b/src/route/fib.hpp
@@ -109,9 +109,6 @@
   void
   addNextHopsToFibEntryAndNfd(FibEntry& entry, NexthopList& hopsToAdd);
 
-  void
-  removeOldNextHopsFromFibEntryAndNfd(FibEntry& entry, const NexthopList& installedHops);
-
   unsigned int
   getNumberOfFacesForName(NexthopList& nextHopList);