diff --git a/src/route/fib.cpp b/src/route/fib.cpp
index 1004889..2d34a36 100644
--- a/src/route/fib.cpp
+++ b/src/route/fib.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2020,  The University of Memphis,
+ * Copyright (c) 2014-2021,  The University of Memphis,
  *                           Regents of the University of California
  *
  * This file is part of NLSR (Named-data Link State Routing).
@@ -54,7 +54,7 @@
 
   // Only unregister the prefix if it ISN'T a neighbor.
   if (it != m_table.end() && isNotNeighbor((it->second).name)) {
-    for (const auto& nexthop : (it->second).nexthopList.getNextHops()) {
+    for (const auto& nexthop : (it->second).nexthopSet) {
       unregisterPrefix((it->second).name, nexthop.getConnectingFaceUri());
     }
     m_table.erase(it);
@@ -62,16 +62,17 @@
 }
 
 void
-Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, const NexthopList& hopsToAdd)
+Fib::addNextHopsToFibEntryAndNfd(FibEntry& entry, const NextHopsUriSortedSet& hopsToAdd)
 {
   const ndn::Name& name = entry.name;
 
   bool shouldRegister = isNotNeighbor(name);
 
-  for (const auto& hop : hopsToAdd.getNextHops())
+  for (const auto& hop : hopsToAdd)
   {
     // Add nexthop to FIB entry
-    entry.nexthopList.addNextHop(hop);
+    NLSR_LOG_DEBUG("Adding " << hop.getConnectingFaceUri() << " to " << entry.name);
+    entry.nexthopSet.addNextHop(hop);
 
     if (shouldRegister) {
       // Add nexthop to NDN-FIB
@@ -92,7 +93,7 @@
   // the length of the list of all next hops.
   unsigned int maxFaces = getNumberOfFacesForName(allHops);
 
-  NexthopList hopsToAdd;
+  NextHopsUriSortedSet hopsToAdd;
   unsigned int nFaces = 0;
 
   // Create a list of next hops to be installed with length == maxFaces
@@ -129,10 +130,11 @@
     FibEntry& entry = (entryIt->second);
     addNextHopsToFibEntryAndNfd(entry, hopsToAdd);
 
-    std::set<NextHop, NextHopComparator> hopsToRemove;
-    std::set_difference(entry.nexthopList.begin(), entry.nexthopList.end(),
+    std::set<NextHop, NextHopUriSortedComparator> hopsToRemove;
+    std::set_difference(entry.nexthopSet.begin(), entry.nexthopSet.end(),
                         hopsToAdd.begin(), hopsToAdd.end(),
-                        std::inserter(hopsToRemove, hopsToRemove.end()), NextHopComparator());
+                        std::inserter(hopsToRemove, hopsToRemove.begin()),
+                        NextHopUriSortedComparator());
 
     bool isUpdatable = isNotNeighbor(entry.name);
     // Remove the uninstalled next hops from NFD and FIB entry
@@ -141,7 +143,7 @@
         unregisterPrefix(entry.name, hop.getConnectingFaceUri());
       }
       NLSR_LOG_DEBUG("Removing " << hop.getConnectingFaceUri() << " from " << entry.name);
-      entry.nexthopList.removeNextHop(hop);
+      entry.nexthopSet.removeNextHop(hop);
     }
 
     // Increment sequence number
@@ -161,7 +163,7 @@
 {
   NLSR_LOG_DEBUG("Clean called");
   for (const auto& it : m_table) {
-    for (const auto& hop : it.second.nexthopList.getNextHops()) {
+    for (const auto& hop : it.second.nexthopSet) {
       unregisterPrefix(it.second.name, hop.getConnectingFaceUri());
     }
   }
@@ -339,7 +341,7 @@
 
   entry.seqNo += 1;
 
-  for (const NextHop& hop : entry.nexthopList) {
+  for (const NextHop& hop : entry.nexthopSet) {
     registerPrefix(entry.name,
                    ndn::FaceUri(hop.getConnectingFaceUri()),
                    hop.getRouteCostAsAdjustedInteger(),
@@ -355,9 +357,9 @@
 {
   NLSR_LOG_DEBUG("-------------------FIB-----------------------------");
   for (const auto& entry : m_table) {
-    NLSR_LOG_DEBUG("Name Prefix: " << entry.second.name);
+    NLSR_LOG_DEBUG("Name prefix: "  << entry.first);
     NLSR_LOG_DEBUG("Seq No: " <<  entry.second.seqNo);
-    NLSR_LOG_DEBUG(entry.second.nexthopList);
+    NLSR_LOG_DEBUG("Nexthop List: \n" << entry.second.nexthopSet);
   }
 }
 
diff --git a/src/route/fib.hpp b/src/route/fib.hpp
index e8f8a40..25b5956 100644
--- a/src/route/fib.hpp
+++ b/src/route/fib.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2020,  The University of Memphis,
+ * Copyright (c) 2014-2021,  The University of Memphis,
  *                           Regents of the University of California,
  *                           Arizona Board of Regents.
  *
@@ -31,11 +31,13 @@
 
 namespace nlsr {
 
+typedef NexthopListT<NextHopUriSortedComparator> NextHopsUriSortedSet;
+
 struct FibEntry {
   ndn::Name name;
   ndn::scheduler::ScopedEventId refreshEventId;
   int32_t seqNo = 1;
-  NexthopList nexthopList;
+  NextHopsUriSortedSet nexthopSet;
 };
 
 typedef std::function<void(FibEntry&)> afterRefreshCallback;
@@ -153,7 +155,7 @@
    * \sa Fib::removeOldNextHopsFromFibEntryAndNfd
    */
   void
-  addNextHopsToFibEntryAndNfd(FibEntry& entry, const NexthopList& hopsToAdd);
+  addNextHopsToFibEntryAndNfd(FibEntry& entry, const NextHopsUriSortedSet& hopsToAdd);
 
   unsigned int
   getNumberOfFacesForName(const NexthopList& nextHopList);
diff --git a/src/route/nexthop-list.cpp b/src/route/nexthop-list.cpp
deleted file mode 100644
index 7ab1352..0000000
--- a/src/route/nexthop-list.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2020,  The University of Memphis,
- *                           Regents of the University of California,
- *                           Arizona Board of Regents.
- *
- * This file is part of NLSR (Named-data Link State Routing).
- * See AUTHORS.md for complete list of NLSR authors and contributors.
- *
- * NLSR 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.
- *
- * NLSR 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
- * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include "nexthop-list.hpp"
-#include "common.hpp"
-#include "nexthop.hpp"
-
-#include <ndn-cxx/util/ostream-joiner.hpp>
-
-namespace nlsr {
-
-static bool
-nexthopAddCompare(const NextHop& nh1, const NextHop& nh2)
-{
-  return nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri();
-}
-
-static bool
-nexthopRemoveCompare(const NextHop& nh1, const NextHop& nh2)
-{
-  return (nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri() &&
-          nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) ;
-}
-
-bool
-operator==(const NexthopList& lhs, const NexthopList& rhs)
-{
-  if (lhs.size() != rhs.size()) {
-    return false;
-  }
-
-  NexthopList slhs = lhs;
-  NexthopList srhs = rhs;
-
-  for (struct {std::set<NextHop>::iterator lItr;
-    std::set<NextHop>::iterator rItr;} pair = {slhs.begin(), srhs.begin()};
-       (pair.lItr != slhs.end() || pair.rItr != srhs.end());
-       pair.rItr++, pair.lItr++) {
-    if (!((*pair.lItr) == (*pair.rItr))) {
-      return false;
-    }
-  }
-  return true;
-}
-
-bool
-operator!=(const NexthopList& lhs, const NexthopList& rhs)
-{
-  return !(lhs == rhs);
-}
-
-std::ostream&
-operator<<(std::ostream& os, const NexthopList& nhl)
-{
-  os << "    ";
-  std::copy(nhl.cbegin(), nhl.cend(), ndn::make_ostream_joiner(os, "\n    "));
-  return os;
-}
-
-void
-NexthopList::addNextHop(const NextHop& nh)
-{
-  auto it = std::find_if(m_nexthopList.begin(), m_nexthopList.end(),
-                         std::bind(&nexthopAddCompare, _1, nh));
-  if (it == m_nexthopList.end()) {
-    m_nexthopList.insert(nh);
-  }
-  else if (it->getRouteCost() > nh.getRouteCost()) {
-    removeNextHop(*it);
-    m_nexthopList.insert(nh);
-  }
-}
-
-void
-NexthopList::removeNextHop(const NextHop& nh)
-{
-  auto it = std::find_if(m_nexthopList.begin(), m_nexthopList.end(),
-                         std::bind(&nexthopRemoveCompare, _1, nh));
-  if (it != m_nexthopList.end()) {
-    m_nexthopList.erase(it);
-  }
-}
-
-} // namespace nlsr
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index 537448e..98e5760 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2020,  The University of Memphis,
+ * Copyright (c) 2014-2021,  The University of Memphis,
  *                           Regents of the University of California
  *
  * This file is part of NLSR (Named-data Link State Routing).
@@ -25,6 +25,8 @@
 #include "adjacent.hpp"
 
 #include <ndn-cxx/face.hpp>
+#include <ndn-cxx/util/ostream-joiner.hpp>
+
 #include <set>
 
 namespace nlsr {
@@ -44,10 +46,31 @@
   }
 };
 
-class NexthopList
+struct NextHopUriSortedComparator {
+  bool
+  operator() (const NextHop& nh1, const NextHop& nh2) const {
+    return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
+  }
+};
+
+static inline bool
+nexthopAddCompare(const NextHop& nh1, const NextHop& nh2)
+{
+  return nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri();
+}
+
+static inline bool
+nexthopRemoveCompare(const NextHop& nh1, const NextHop& nh2)
+{
+  return (nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri() &&
+          nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) ;
+}
+
+template<typename T = NextHopComparator>
+class NexthopListT
 {
 public:
-  NexthopList() = default;
+  NexthopListT() = default;
 
   /*! \brief Adds a next hop to the list.
     \param nh The next hop.
@@ -57,7 +80,18 @@
     hop's route cost is updated.
   */
   void
-  addNextHop(const NextHop& nh);
+  addNextHop(const NextHop& nh)
+  {
+    auto it = std::find_if(m_nexthopList.begin(), m_nexthopList.end(),
+                           std::bind(&nexthopAddCompare, _1, nh));
+    if (it == m_nexthopList.end()) {
+      m_nexthopList.insert(nh);
+    }
+    else if (it->getRouteCost() > nh.getRouteCost()) {
+      removeNextHop(*it);
+      m_nexthopList.insert(nh);
+    }
+  }
 
   /*! \brief Remove a next hop from the Next Hop list
       \param nh The NextHop we want to remove.
@@ -65,7 +99,14 @@
     The next hop gets removed only if both next hop face and route cost are same.
   */
   void
-  removeNextHop(const NextHop& nh);
+  removeNextHop(const NextHop& nh)
+  {
+    auto it = std::find_if(m_nexthopList.begin(), m_nexthopList.end(),
+                           std::bind(&nexthopRemoveCompare, _1, nh));
+    if (it != m_nexthopList.end()) {
+      m_nexthopList.erase(it);
+    }
+  }
 
   size_t
   size() const
@@ -79,24 +120,25 @@
     m_nexthopList.clear();
   }
 
-  const std::set<NextHop, NextHopComparator>&
+  const std::set<NextHop, T>&
   getNextHops() const
   {
     return m_nexthopList;
   }
 
-  typedef std::set<NextHop, NextHopComparator>::iterator iterator;
-  typedef std::set<NextHop, NextHopComparator>::const_iterator const_iterator;
-  typedef std::set<NextHop, NextHopComparator>::reverse_iterator reverse_iterator;
+  typedef T value_type;
+  typedef typename std::set<NextHop, T>::iterator iterator;
+  typedef typename std::set<NextHop, T>::const_iterator const_iterator;
+  typedef typename std::set<NextHop, T>::reverse_iterator reverse_iterator;
 
   iterator
-  begin()
+  begin() const
   {
     return m_nexthopList.begin();
   }
 
   iterator
-  end()
+  end() const
   {
     return m_nexthopList.end();
   }
@@ -126,20 +168,33 @@
   }
 
 private:
-  std::set<NextHop, NextHopComparator> m_nexthopList;
+  std::set<NextHop, T> m_nexthopList;
 };
 
-bool
-operator==(NexthopList& lhs, NexthopList& rhs);
+typedef NexthopListT<> NexthopList;
 
+template<typename T>
 bool
-operator==(const NexthopList& lhs, const NexthopList& rhs);
+operator==(const NexthopListT<T>& lhs, const NexthopListT<T>& rhs)
+{
+  return lhs.getNextHops() == rhs.getNextHops();
+}
 
+template<typename T>
 bool
-operator!=(const NexthopList& lhs, const NexthopList& rhs);
+operator!=(const NexthopListT<T>& lhs, const NexthopListT<T>& rhs)
+{
+  return !(lhs == rhs);
+}
 
+template<typename T>
 std::ostream&
-operator<<(std::ostream& os, const NexthopList& nhl);
+operator<<(std::ostream& os, const NexthopListT<T>& nhl)
+{
+  os << "    ";
+  std::copy(nhl.cbegin(), nhl.cend(), ndn::make_ostream_joiner(os, "\n    "));
+  return os;
+}
 
 } // namespace nlsr
 
diff --git a/tests/route/test-fib.cpp b/tests/route/test-fib.cpp
index fd68e80..3961b05 100644
--- a/tests/route/test-fib.cpp
+++ b/tests/route/test-fib.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2020,  The University of Memphis,
+ * Copyright (c) 2014-2021,  The University of Memphis,
  *                           Regents of the University of California
  *
  * This file is part of NLSR (Named-data Link State Routing).
@@ -29,16 +29,19 @@
 namespace nlsr {
 namespace test {
 
-using std::shared_ptr;
-
 class FibFixture : public UnitTestTimeFixture
 {
 public:
   FibFixture()
-    : face(std::make_shared<ndn::util::DummyClientFace>(m_ioService, m_keyChain))
-    , conf(*face, m_keyChain)
-    , interests(face->sentInterests)
+    : face(m_ioService, m_keyChain)
+    , conf(face, m_keyChain)
+    , adjacencies(conf.getAdjacencyList())
+    , fib(face, m_scheduler, adjacencies, conf, m_keyChain)
+    , interests(face.sentInterests)
   {
+    enableRegistrationReplyWithFaceId();
+    advanceClocks(1_s);
+
     Adjacent neighbor1(router1Name, ndn::FaceUri(router1FaceUri), 0, Adjacent::STATUS_ACTIVE, 0, router1FaceId);
     adjacencies.insert(neighbor1);
 
@@ -50,16 +53,44 @@
 
     conf.setMaxFacesPerPrefix(2);
 
-    fib = std::make_shared<Fib>(*face, m_scheduler, adjacencies, conf, m_keyChain);
-    fib->setEntryRefreshTime(1);
+    fib.setEntryRefreshTime(1);
+  }
+
+  void
+  enableRegistrationReplyWithFaceId() {
+    face.onSendInterest.connect([this] (const ndn::Interest& interest) {
+      static const ndn::Name localhostRegistration("/localhost/nfd/rib");
+      if (!localhostRegistration.isPrefixOf(interest.getName()))
+        return;
+
+      ndn::nfd::ControlParameters params(interest.getName().get(-5).blockFromValue());
+      if (!params.hasFaceId()) {
+        params.setFaceId(1);
+      }
+      params.setOrigin(ndn::nfd::ROUTE_ORIGIN_APP);
+      if (interest.getName().get(3) == ndn::name::Component("register")) {
+        params.setCost(0);
+      }
+
+      ndn::nfd::ControlResponse resp;
+      resp.setCode(200);
+      resp.setBody(params.wireEncode());
+
+      ndn::Data data(interest.getName());
+      data.setContent(resp.wireEncode());
+
+      m_keyChain.sign(data, ndn::security::SigningInfo(ndn::security::SigningInfo::SIGNER_TYPE_SHA256));
+
+      face.getIoService().post([this, data] { face.receive(data); });
+    });
   }
 
 public:
-  std::shared_ptr<ndn::util::DummyClientFace> face;
-  std::shared_ptr<Fib> fib;
+  ndn::util::DummyClientFace face;
 
-  AdjacencyList adjacencies;
   ConfParameter conf;
+  AdjacencyList& adjacencies;
+  Fib fib;
   std::vector<ndn::Interest>& interests;
 
   static const ndn::Name router1Name;
@@ -98,8 +129,8 @@
   hops.addNextHop(hop1);
   hops.addNextHop(hop2);
 
-  fib->update("/ndn/name", hops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", hops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // Should register faces 1 and 2 for /ndn/name
   BOOST_REQUIRE_EQUAL(interests.size(), 2);
@@ -122,7 +153,6 @@
               verb == ndn::Name::Component("register"));
 }
 
-
 BOOST_AUTO_TEST_CASE(NextHopsNoChange)
 {
   NextHop hop1(router1FaceUri, 10);
@@ -132,14 +162,14 @@
   oldHops.addNextHop(hop1);
   oldHops.addNextHop(hop2);
 
-  fib->update("/ndn/name", oldHops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", oldHops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   BOOST_REQUIRE_EQUAL(interests.size(), 2);
   interests.clear();
 
-  fib->update("/ndn/name", oldHops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", oldHops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // Should register face 1 and 2 for /ndn/name
   BOOST_REQUIRE_EQUAL(interests.size(), 2);
@@ -171,16 +201,16 @@
   oldHops.addNextHop(hop1);
   oldHops.addNextHop(hop2);
 
-  fib->update("/ndn/name", oldHops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", oldHops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   BOOST_REQUIRE_EQUAL(interests.size(), 2);
   interests.clear();
 
   NexthopList empty;
 
-  fib->update("/ndn/name", empty);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", empty);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // Should unregister faces 1 and 2 for /ndn/name
   BOOST_CHECK_EQUAL(interests.size(), 2);
@@ -214,8 +244,8 @@
   hops.addNextHop(hop2);
   hops.addNextHop(hop3);
 
-  fib->update("/ndn/name", hops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", hops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // Should only register faces 1 and 2 for /ndn/name
   BOOST_CHECK_EQUAL(interests.size(), 2);
@@ -247,8 +277,8 @@
   hops.addNextHop(hop1);
   hops.addNextHop(hop2);
 
-  fib->update("/ndn/name", hops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", hops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // FIB
   // Name        NextHops
@@ -260,8 +290,8 @@
   NextHop hop3(router3FaceUri, 5);
   hops.addNextHop(hop3);
 
-  fib->update("/ndn/name", hops);
-  face->processEvents(ndn::time::milliseconds(-1));
+  fib.update("/ndn/name", hops);
+  face.processEvents(ndn::time::milliseconds(-1));
 
   // To maintain a max 2 face requirement, face 3 should be registered and face 2 should be
   // unregistered. Face 1 will also be re-registered.
@@ -279,14 +309,14 @@
   extractRibCommandParameters(*it, verb, extractedParameters);
 
   BOOST_CHECK(extractedParameters.getName() == "/ndn/name" &&
-              extractedParameters.getFaceId() == router3FaceId &&
+              extractedParameters.getFaceId() == router1FaceId &&
               verb == ndn::Name::Component("register"));
 
   ++it;
   extractRibCommandParameters(*it, verb, extractedParameters);
 
   BOOST_CHECK(extractedParameters.getName() == "/ndn/name" &&
-              extractedParameters.getFaceId() == router1FaceId &&
+              extractedParameters.getFaceId() == router3FaceId &&
               verb == ndn::Name::Component("register"));
 
   ++it;
@@ -303,9 +333,9 @@
   FibEntry fe;
   fe.name = name1;
   int origSeqNo = fe.seqNo;
-  fib->m_table.emplace(name1, std::move(fe));
+  fib.m_table.emplace(name1, std::move(fe));
 
-  fib->scheduleEntryRefresh(fe,
+  fib.scheduleEntryRefresh(fe,
                             [&] (FibEntry& entry) {
                               BOOST_CHECK_EQUAL(origSeqNo + 1, entry.seqNo);
                             });
@@ -321,11 +351,64 @@
   hops.addNextHop(hop1);
 
   // Simulate update for this neighbor from name prefix table
-  fib->update(router1Name, hops);
+  fib.update(router1Name, hops);
   this->advanceClocks(ndn::time::seconds(1));
 
   // Should not send the register interest
-  BOOST_CHECK_EQUAL(face->sentInterests.size(), 0);
+  BOOST_CHECK_EQUAL(face.sentInterests.size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(PrefixWithdrawalFibUpdateBug) // #5179
+{
+  fib.setEntryRefreshTime(3600);
+  conf.setMaxFacesPerPrefix(3);
+
+  // Three adjacencies of Neu
+  Adjacent neighbor1("/ndn/memphis/router-memphis",
+                     ndn::FaceUri("udp4://10.0.0.9:6363"), 21, Adjacent::STATUS_ACTIVE, 0, router1FaceId);
+  adjacencies.insert(neighbor1);
+
+  Adjacent neighbor2("/ndn/michigan/router-michigan",
+                     ndn::FaceUri("udp4://10.0.0.13:6363"), 14, Adjacent::STATUS_ACTIVE, 0, router2FaceId);
+  adjacencies.insert(neighbor2);
+
+  Adjacent neighbor3("/ndn/savi/router-savi",
+                     ndn::FaceUri("udp4://10.0.0.26:6363"), 15, Adjacent::STATUS_ACTIVE, 0, router3FaceId);
+  adjacencies.insert(neighbor3);
+
+  // Wustl advertises /test
+  NexthopList nhl1;
+  nhl1.addNextHop(NextHop("udp4://10.0.0.13:6363", 28));
+  nhl1.addNextHop(NextHop("udp4://10.0.0.9:6363", 38));
+  nhl1.addNextHop(NextHop("udp4://10.0.0.26:6363", 44));
+  fib.update("/test", nhl1);
+
+  // Memphis advertises /test
+  NexthopList nhl2;
+  nhl2.addNextHop(NextHop("udp4://10.0.0.9:6363", 21));
+  nhl2.addNextHop(NextHop("udp4://10.0.0.13:6363", 26));
+  nhl2.addNextHop(NextHop("udp4://10.0.0.26:6363", 42));
+  fib.update("/test", nhl2);
+
+  advanceClocks(10_ms);
+  face.sentInterests.clear();
+  // Memphis withdraws /test
+  // NamePrefixTable calls this saying we need to install the Wu routes
+  // instead of the existing Memphis' cheaper routes
+  fib.update("/test", nhl1);
+
+  advanceClocks(10_ms);
+  int numRegister = 0;
+  // Do not expect any unregisters, just registers which will update the cost in NFD
+  for (const auto& i : face.sentInterests) {
+    if (i.getName().getPrefix(4) == "/localhost/nfd/rib/unregister/") {
+      BOOST_CHECK(false);
+    }
+    else {
+      ++numRegister;
+    }
+  }
+  BOOST_CHECK_EQUAL(numRegister, 3);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/tests/route/test-nexthop-list.cpp b/tests/route/test-nexthop-list.cpp
index 9ab8572..73108dc 100644
--- a/tests/route/test-nexthop-list.cpp
+++ b/tests/route/test-nexthop-list.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2020,  The University of Memphis,
+ * Copyright (c) 2014-2021,  The University of Memphis,
  *                           Regents of the University of California,
  *                           Arizona Board of Regents.
  *
@@ -21,6 +21,7 @@
 
 #include "route/nexthop-list.hpp"
 #include "route/nexthop.hpp"
+#include "route/fib.hpp"
 #include "tests/boost-test.hpp"
 
 namespace nlsr {
@@ -180,6 +181,53 @@
   }
 }
 
+/* Fib needs a NexthopList to be sorted by FaceUri when updating
+   to avoid removing prefixes that were just installed. The above
+   test does not apply to this scenario as the NexthopList
+   sorted by cost is given to the Fib::update.
+ */
+BOOST_AUTO_TEST_CASE(NextHopListDiffForFibUpdate) // #5179
+{
+  // If default sorter is used then difference results in
+  // the same hops to remove as those that were added
+  NexthopList nhl1;
+  nhl1.addNextHop(NextHop("udp4://10.0.0.13:6363", 28));
+  nhl1.addNextHop(NextHop("udp4://10.0.0.9:6363", 38));
+  nhl1.addNextHop(NextHop("udp4://10.0.0.26:6363", 44));
+
+  NexthopList nhl2;
+  nhl2.addNextHop(NextHop("udp4://10.0.0.9:6363", 21));
+  nhl2.addNextHop(NextHop("udp4://10.0.0.13:6363", 26));
+  nhl2.addNextHop(NextHop("udp4://10.0.0.26:6363", 42));
+
+  std::set<NextHop, NextHopComparator> hopsToRemove;
+  std::set_difference(nhl2.begin(), nhl2.end(),
+                      nhl1.begin(), nhl1.end(),
+                      std::inserter(hopsToRemove, hopsToRemove.begin()),
+                      NextHopComparator());
+
+  BOOST_CHECK_EQUAL(hopsToRemove.size(), 3);
+
+  // Sorted by FaceUri
+  NextHopsUriSortedSet nhs1;
+  nhs1.addNextHop(NextHop("udp4://10.0.0.13:6363", 28));
+  nhs1.addNextHop(NextHop("udp4://10.0.0.9:6363", 38));
+  nhs1.addNextHop(NextHop("udp4://10.0.0.26:6363", 44));
+
+  NextHopsUriSortedSet nhs2;
+  nhs2.addNextHop(NextHop("udp4://10.0.0.9:6363", 21));
+  nhs2.addNextHop(NextHop("udp4://10.0.0.13:6363", 26));
+  nhs2.addNextHop(NextHop("udp4://10.0.0.26:6363", 42));
+
+  std::set<NextHop, NextHopUriSortedComparator> hopsToRemove2;
+  std::set_difference(nhs2.begin(), nhs2.end(),
+                      nhs1.begin(), nhs1.end(),
+                      std::inserter(hopsToRemove2, hopsToRemove2.begin()),
+                      NextHopUriSortedComparator());
+
+  BOOST_CHECK_EQUAL(hopsToRemove2.size(), 0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace test