diff --git a/daemon/mgmt/fib-manager.cpp b/daemon/mgmt/fib-manager.cpp
index c736869..c048da5 100644
--- a/daemon/mgmt/fib-manager.cpp
+++ b/daemon/mgmt/fib-manager.cpp
@@ -77,7 +77,7 @@
   }
 
   fib::Entry* entry = m_fib.insert(prefix).first;
-  entry->addOrUpdateNextHop(*face, cost);
+  m_fib.addOrUpdateNextHop(*entry, *face, cost);
 
   NFD_LOG_TRACE("fib/add-nexthop(" << prefix << ',' << faceId << ',' << cost << "): OK");
   return done(ControlResponse(200, "Success").setBody(parameters.wireEncode()));
@@ -106,13 +106,17 @@
     return;
   }
 
-  entry->removeNextHop(*face);
-  if (!entry->hasNextHops()) {
-    m_fib.erase(*entry);
-    NFD_LOG_TRACE("fib/remove-nexthop(" << prefix << ',' << faceId << "): OK entry-erased");
-  }
-  else {
-    NFD_LOG_TRACE("fib/remove-nexthop(" << prefix << ',' << faceId << "): OK nexthop-removed");
+  auto status = m_fib.removeNextHop(*entry, *face);
+  switch (status) {
+    case Fib::RemoveNextHopResult::NO_SUCH_NEXTHOP:
+      NFD_LOG_TRACE("fib/remove-nexthop(" << prefix << ',' << faceId << "): OK no-nexthop");
+      break;
+    case Fib::RemoveNextHopResult::FIB_ENTRY_REMOVED:
+      NFD_LOG_TRACE("fib/remove-nexthop(" << prefix << ',' << faceId << "): OK entry-erased");
+      break;
+    case Fib::RemoveNextHopResult::NEXTHOP_REMOVED:
+      NFD_LOG_TRACE("fib/remove-nexthop(" << prefix << ',' << faceId << "): OK nexthop-removed");
+      break;
   }
 }
 
diff --git a/daemon/nfd.cpp b/daemon/nfd.cpp
index 7877dea..63af6c7 100644
--- a/daemon/nfd.cpp
+++ b/daemon/nfd.cpp
@@ -170,7 +170,8 @@
 
   // add FIB entry for NFD Management Protocol
   Name topPrefix("/localhost/nfd");
-  m_forwarder->getFib().insert(topPrefix).first->addOrUpdateNextHop(*m_internalFace, 0);
+  fib::Entry* entry = m_forwarder->getFib().insert(topPrefix).first;
+  m_forwarder->getFib().addOrUpdateNextHop(*entry, *m_internalFace, 0);
   m_dispatcher->addTopPrefix(topPrefix, false);
 }
 
diff --git a/daemon/table/fib-entry.cpp b/daemon/table/fib-entry.cpp
index ff5c125..ade4c9f 100644
--- a/daemon/table/fib-entry.cpp
+++ b/daemon/table/fib-entry.cpp
@@ -48,26 +48,32 @@
   return const_cast<Entry*>(this)->findNextHop(face) != m_nextHops.end();
 }
 
-void
+std::pair<NextHopList::iterator, bool>
 Entry::addOrUpdateNextHop(Face& face, uint64_t cost)
 {
   auto it = this->findNextHop(face);
+  bool isNew = false;
   if (it == m_nextHops.end()) {
     m_nextHops.emplace_back(face);
     it = std::prev(m_nextHops.end());
+    isNew = true;
   }
 
   it->setCost(cost);
   this->sortNextHops();
+
+  return std::make_pair(it, isNew);
 }
 
-void
+bool
 Entry::removeNextHop(const Face& face)
 {
   auto it = this->findNextHop(face);
   if (it != m_nextHops.end()) {
     m_nextHops.erase(it);
+    return true;
   }
+  return false;
 }
 
 void
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index 52dfbd8..7460eda 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -36,6 +36,8 @@
 
 namespace fib {
 
+class Fib;
+
 /** \class nfd::fib::NextHopList
  *  \brief Represents a collection of nexthops.
  *
@@ -79,21 +81,24 @@
   bool
   hasNextHop(const Face& face) const;
 
-  /** \brief adds a NextHop record
+private:
+  /** \brief adds a NextHop record to the entry
    *
-   *  If a NextHop record for \p face already exists, its cost is updated.
+   *  If a NextHop record for \p face already exists in the entry, its cost is set to \p cost.
+   *
+   *  \return the iterator to the new or updated NextHop and a bool indicating whether a new
+   *  NextHop was inserted
    */
-  void
+  std::pair<NextHopList::iterator, bool>
   addOrUpdateNextHop(Face& face, uint64_t cost);
 
   /** \brief removes a NextHop record
    *
    *  If no NextHop record for face exists, do nothing.
    */
-  void
+  bool
   removeNextHop(const Face& face);
 
-private:
   /** \note This method is non-const because mutable iterators are needed by callers.
    */
   NextHopList::iterator
@@ -111,6 +116,7 @@
   name_tree::Entry* m_nameTreeEntry = nullptr;
 
   friend class name_tree::Entry;
+  friend class Fib;
 };
 
 } // namespace fib
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 62938e0..99892e6 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -133,13 +133,31 @@
 }
 
 void
+Fib::addOrUpdateNextHop(Entry& entry, Face& face, uint64_t cost)
+{
+  NextHopList::iterator it;
+  bool isNew;
+  std::tie(it, isNew) = entry.addOrUpdateNextHop(face, cost);
+
+  if (isNew)
+    this->afterNewNextHop(entry.getPrefix(), *it);
+}
+
+Fib::RemoveNextHopResult
 Fib::removeNextHop(Entry& entry, const Face& face)
 {
-  entry.removeNextHop(face);
+  bool isRemoved = entry.removeNextHop(face);
 
-  if (!entry.hasNextHops()) {
+  if (!isRemoved) {
+    return RemoveNextHopResult::NO_SUCH_NEXTHOP;
+  }
+  else if (!entry.hasNextHops()) {
     name_tree::Entry* nte = m_nameTree.getEntry(entry);
     this->erase(nte, false);
+    return RemoveNextHopResult::FIB_ENTRY_REMOVED;
+  }
+  else {
+    return RemoveNextHopResult::NEXTHOP_REMOVED;
   }
 }
 
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 8543440..f5984aa 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -103,9 +103,22 @@
   void
   erase(const Entry& entry);
 
-  /** \brief Remove the NextHop record for \p face
+  /** \brief Add a NextHop record
+   *
+   *  If a NextHop record for \p face already exists in \p entry, its cost is set to \p cost.
    */
   void
+  addOrUpdateNextHop(Entry& entry, Face& face, uint64_t cost);
+
+  enum class RemoveNextHopResult {
+    NO_SUCH_NEXTHOP, ///< the nexthop is not found
+    NEXTHOP_REMOVED, ///< the nexthop is removed and the fib entry stays
+    FIB_ENTRY_REMOVED ///< the nexthop is removed and the fib entry is removed
+  };
+
+  /** \brief Remove the NextHop record for \p face from \p entry
+   */
+  RemoveNextHopResult
   removeNextHop(Entry& entry, const Face& face);
 
 public: // enumeration
@@ -132,6 +145,11 @@
     return this->getRange().end();
   }
 
+public: // signal
+  /** \brief signals on Fib entry nexthop creation
+   */
+  signal::Signal<Fib, Name, NextHop> afterNewNextHop;
+
 private:
   /** \tparam K a parameter acceptable to NameTree::findLongestPrefixMatch
    */
diff --git a/tests/daemon/fw/best-route-strategy2.t.cpp b/tests/daemon/fw/best-route-strategy2.t.cpp
index d8008f7..9614a26 100644
--- a/tests/daemon/fw/best-route-strategy2.t.cpp
+++ b/tests/daemon/fw/best-route-strategy2.t.cpp
@@ -77,9 +77,9 @@
 BOOST_AUTO_TEST_CASE(Forward)
 {
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 10);
-  fibEntry.addOrUpdateNextHop(*face2, 20);
-  fibEntry.addOrUpdateNextHop(*face3, 30);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face3, 30);
 
   shared_ptr<Interest> interest = makeInterest("ndn:/BzgFBchqA");
   shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
@@ -128,7 +128,7 @@
   BOOST_CHECK_EQUAL(strategy.sendInterestHistory[4].outFaceId, face1->getId());
   BOOST_CHECK_EQUAL(strategy.sendInterestHistory[5].outFaceId, face3->getId());
 
-  fibEntry.removeNextHop(*face1);
+  fib.removeNextHop(fibEntry, *face1);
 
   strategy.sendInterestHistory.clear();
   for (int i = 0; i < 3; ++i) {
diff --git a/tests/daemon/fw/forwarder.t.cpp b/tests/daemon/fw/forwarder.t.cpp
index 247821a..9f7d1ce 100644
--- a/tests/daemon/fw/forwarder.t.cpp
+++ b/tests/daemon/fw/forwarder.t.cpp
@@ -50,7 +50,8 @@
   forwarder.addFace(face2);
 
   Fib& fib = forwarder.getFib();
-  fib.insert("/A").first->addOrUpdateNextHop(*face2, 0);
+  fib::Entry* entry = fib.insert("/A").first;
+  fib.addOrUpdateNextHop(*entry, *face2, 0);
 
   BOOST_CHECK_EQUAL(forwarder.getCounters().nInInterests, 0);
   BOOST_CHECK_EQUAL(forwarder.getCounters().nOutInterests, 0);
@@ -91,7 +92,8 @@
   forwarder.addFace(face3);
 
   Fib& fib = forwarder.getFib();
-  fib.insert("/A").first->addOrUpdateNextHop(*face2, 0);
+  fib::Entry* entry = fib.insert("/A").first;
+  fib.addOrUpdateNextHop(*entry, *face2, 0);
 
   Pit& pit = forwarder.getPit();
   BOOST_CHECK_EQUAL(pit.size(), 0);
@@ -156,7 +158,8 @@
   forwarder.addFace(face3);
 
   Fib& fib = forwarder.getFib();
-  fib.insert("/A").first->addOrUpdateNextHop(*face3, 0);
+  fib::Entry* entry = fib.insert("/A").first;
+  fib.addOrUpdateNextHop(*entry, *face3, 0);
 
   auto interest = makeInterest("/A/B");
   interest->setTag(make_shared<lp::NextHopFaceIdTag>(face2->getId()));
@@ -485,7 +488,8 @@
   forwarder.addFace(face4);
 
   Fib& fib = forwarder.getFib();
-  fib.insert("/zT4XwK0Hnx").first->addOrUpdateNextHop(*face4, 0);
+  fib::Entry* entry = fib.insert("/zT4XwK0Hnx").first;
+  fib.addOrUpdateNextHop(*entry, *face4, 0);
 
   // receive Interest on face1
   face1->sentNacks.clear();
@@ -537,7 +541,8 @@
   });
 
   Fib& fib = forwarder.getFib();
-  fib.insert("/A").first->addOrUpdateNextHop(*face2, 0);
+  fib::Entry* entry = fib.insert("/A").first;
+  fib.addOrUpdateNextHop(*entry, *face2, 0);
 
   // receive an Interest
   auto interest = makeInterest("/A/1", false, 50_ms, 82101183);
diff --git a/tests/daemon/fw/multicast-strategy.t.cpp b/tests/daemon/fw/multicast-strategy.t.cpp
index 24027f0..b162926 100644
--- a/tests/daemon/fw/multicast-strategy.t.cpp
+++ b/tests/daemon/fw/multicast-strategy.t.cpp
@@ -69,9 +69,9 @@
 BOOST_AUTO_TEST_CASE(Forward2)
 {
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 0);
-  fibEntry.addOrUpdateNextHop(*face2, 0);
-  fibEntry.addOrUpdateNextHop(*face3, 0);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 0);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 0);
+  fib.addOrUpdateNextHop(fibEntry, *face3, 0);
 
   shared_ptr<Interest> interest = makeInterest("ndn:/H0D6i5fc");
   shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
@@ -123,7 +123,7 @@
 BOOST_AUTO_TEST_CASE(RejectLoopback)
 {
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 0);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 0);
 
   shared_ptr<Interest> interest = makeInterest("ndn:/H0D6i5fc");
   shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
diff --git a/tests/daemon/fw/ncc-strategy.t.cpp b/tests/daemon/fw/ncc-strategy.t.cpp
index c9a604b..b2f919a 100644
--- a/tests/daemon/fw/ncc-strategy.t.cpp
+++ b/tests/daemon/fw/ncc-strategy.t.cpp
@@ -59,8 +59,8 @@
 
   Fib& fib = forwarder.getFib();
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 10);
-  fibEntry.addOrUpdateNextHop(*face2, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 20);
 
   Pit& pit = forwarder.getPit();
 
@@ -118,7 +118,7 @@
 
   Fib& fib = forwarder.getFib();
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 10);
 
   Pit& pit = forwarder.getPit();
 
@@ -149,7 +149,7 @@
   strategy.afterReceiveInterest(FaceEndpoint(*face3, 0), *interest2, pitEntry2);
 
   // FIB entry is changed before doPropagate executes
-  fibEntry.addOrUpdateNextHop(*face2, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 20);
   this->advanceClocks(10_ms, 1_s);// should not crash
 }
 
@@ -169,8 +169,8 @@
 
   Fib& fib = forwarder.getFib();
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 10);
-  fibEntry.addOrUpdateNextHop(*face2, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 20);
 
   Pit& pit = forwarder.getPit();
 
@@ -222,7 +222,7 @@
 
   Fib& fib = forwarder.getFib();
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face2, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face2, 10);
 
   Pit& pit = forwarder.getPit();
 
@@ -265,8 +265,8 @@
 
   Fib& fib = forwarder.getFib();
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face1, 10); // face1 is top-ranked nexthop
-  fibEntry.addOrUpdateNextHop(*face2, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face1, 10); // face1 is top-ranked nexthop
+  fib.addOrUpdateNextHop(fibEntry, *face2, 20);
 
   Pit& pit = forwarder.getPit();
 
diff --git a/tests/daemon/fw/strategy-nack-return.t.cpp b/tests/daemon/fw/strategy-nack-return.t.cpp
index df2c1bb..ea2d417 100644
--- a/tests/daemon/fw/strategy-nack-return.t.cpp
+++ b/tests/daemon/fw/strategy-nack-return.t.cpp
@@ -93,9 +93,9 @@
                                  S, Strategies, StrategyNackReturnFixture<S>)
 {
   fib::Entry& fibEntry = *this->fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*this->face3, 10);
-  fibEntry.addOrUpdateNextHop(*this->face4, 20);
-  fibEntry.addOrUpdateNextHop(*this->face5, 30);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face3, 10);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face4, 20);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face5, 30);
 
   auto interest1 = makeInterest("/McQYjMbm", false, nullopt, 992);
   auto interest2 = makeInterest("/McQYjMbm", false, nullopt, 114);
@@ -132,9 +132,9 @@
                                  S, Strategies, StrategyNackReturnFixture<S>)
 {
   fib::Entry& fibEntry = *this->fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*this->face3, 10);
-  fibEntry.addOrUpdateNextHop(*this->face4, 20);
-  fibEntry.addOrUpdateNextHop(*this->face5, 30);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face3, 10);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face4, 20);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face5, 30);
 
   auto interest1 = makeInterest("/aS9FAyUV19", 286);
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest1).first;
@@ -168,9 +168,9 @@
                                  S, Strategies, StrategyNackReturnFixture<S>)
 {
   fib::Entry& fibEntry = *this->fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*this->face3, 10);
-  fibEntry.addOrUpdateNextHop(*this->face4, 20);
-  fibEntry.addOrUpdateNextHop(*this->face5, 30);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face3, 10);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face4, 20);
+  this->fib.addOrUpdateNextHop(fibEntry, *this->face5, 30);
 
   auto interest1 = makeInterest("/sIYw0TXWDj", false, 400_ms, 115);
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest1).first;
@@ -320,9 +320,9 @@
                                  StrategyNackReturnFixture<BestRouteStrategy2>)
 {
   fib::Entry& fibEntry = *fib.insert(Name()).first;
-  fibEntry.addOrUpdateNextHop(*face3, 10);
-  fibEntry.addOrUpdateNextHop(*face4, 20);
-  fibEntry.addOrUpdateNextHop(*face5, 30);
+  fib.addOrUpdateNextHop(fibEntry, *face3, 10);
+  fib.addOrUpdateNextHop(fibEntry, *face4, 20);
+  fib.addOrUpdateNextHop(fibEntry, *face5, 30);
 
   auto interest1 = makeInterest("/F6sEwB24I", false, nullopt, 282);
   shared_ptr<pit::Entry> pitEntry = pit.insert(*interest1).first;
diff --git a/tests/daemon/fw/strategy-no-route.t.cpp b/tests/daemon/fw/strategy-no-route.t.cpp
index cea980f..a8fed80 100644
--- a/tests/daemon/fw/strategy-no-route.t.cpp
+++ b/tests/daemon/fw/strategy-no-route.t.cpp
@@ -115,7 +115,8 @@
   void
   insertFibEntry(StrategyNoRouteFixture<S>* fixture)
   {
-    fixture->fib.insert(Name()).first->addOrUpdateNextHop(*fixture->face1, 10);
+    fib::Entry* entry = fixture->fib.insert(Name()).first;
+    fixture->fib.addOrUpdateNextHop(*entry, *fixture->face1, 10);
   }
 };
 
@@ -132,7 +133,8 @@
   void
   insertFibEntry(StrategyNoRouteFixture<S>* fixture)
   {
-    fixture->fib.insert("/localhop").first->addOrUpdateNextHop(*fixture->face2, 10);
+    fib::Entry* entry = fixture->fib.insert("/localhop").first;
+    fixture->fib.addOrUpdateNextHop(*entry, *fixture->face2, 10);
     // face1 and face2 are both non-local; Interest from face1 cannot be forwarded to face2
   }
 };
diff --git a/tests/daemon/fw/strategy-scope-control.t.cpp b/tests/daemon/fw/strategy-scope-control.t.cpp
index ec88374..a2fa21d 100644
--- a/tests/daemon/fw/strategy-scope-control.t.cpp
+++ b/tests/daemon/fw/strategy-scope-control.t.cpp
@@ -116,7 +116,7 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhost/A").first;
-  fibEntry->addOrUpdateNextHop(*this->localFace4, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->localFace4, 10);
 
   auto interest = makeInterest("/localhost/A/1");
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -135,7 +135,7 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhost/A").first;
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 10);
 
   auto interest = makeInterest("/localhost/A/1");
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -157,8 +157,8 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhost/A").first;
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 10);
-  fibEntry->addOrUpdateNextHop(*this->localFace4, 20);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->localFace4, 20);
 
   auto interest = makeInterest("/localhost/A/1");
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -178,7 +178,7 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhop/A").first;
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 10);
 
   auto interest = makeInterest("/localhop/A/1");
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -200,8 +200,8 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhop/A").first;
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 10);
-  fibEntry->addOrUpdateNextHop(*this->localFace4, 20);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->localFace4, 20);
 
   auto interest = makeInterest("/localhop/A/1");
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -221,8 +221,8 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhost/A").first;
-  fibEntry->addOrUpdateNextHop(*this->localFace4, 10);
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 20);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->localFace4, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 20);
 
   auto interest = makeInterest("/localhost/A/1", false, nullopt, 1460);
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
@@ -246,8 +246,8 @@
                                  T, Tests, StrategyScopeControlFixture<typename T::Strategy>)
 {
   fib::Entry* fibEntry = this->fib.insert("/localhop/A").first;
-  fibEntry->addOrUpdateNextHop(*this->localFace4, 10);
-  fibEntry->addOrUpdateNextHop(*this->nonLocalFace2, 20);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->localFace4, 10);
+  this->fib.addOrUpdateNextHop(*fibEntry, *this->nonLocalFace2, 20);
 
   auto interest = makeInterest("/localhop/A/1", 1377);
   shared_ptr<pit::Entry> pitEntry = this->pit.insert(*interest).first;
diff --git a/tests/daemon/fw/topology-tester.cpp b/tests/daemon/fw/topology-tester.cpp
index ce7bc26..3007f38 100644
--- a/tests/daemon/fw/topology-tester.cpp
+++ b/tests/daemon/fw/topology-tester.cpp
@@ -242,7 +242,8 @@
 {
   Forwarder& forwarder = this->getForwarder(i);
   Fib& fib = forwarder.getFib();
-  fib.insert(prefix).first->addOrUpdateNextHop(const_cast<Face&>(face), cost);
+  fib::Entry* entry = fib.insert(prefix).first;
+  fib.addOrUpdateNextHop(*entry, const_cast<Face&>(face), cost);
 }
 
 void
diff --git a/tests/daemon/mgmt/fib-manager.t.cpp b/tests/daemon/mgmt/fib-manager.t.cpp
index 6a0ab6c..4907a61 100644
--- a/tests/daemon/mgmt/fib-manager.t.cpp
+++ b/tests/daemon/mgmt/fib-manager.t.cpp
@@ -301,9 +301,9 @@
   BOOST_REQUIRE_NE(face3, face::INVALID_FACEID);
 
   fib::Entry* entry = m_fib.insert("/hello").first;
-  entry->addOrUpdateNextHop(*m_faceTable.get(face1), 101);
-  entry->addOrUpdateNextHop(*m_faceTable.get(face2), 202);
-  entry->addOrUpdateNextHop(*m_faceTable.get(face3), 303);
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face1), 101);
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face2), 202);
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face3), 303);
 
   testRemoveNextHop(makeParameters("/hello", face1));
   BOOST_REQUIRE_EQUAL(m_responses.size(), 1);
@@ -354,8 +354,8 @@
   };
 
   fib::Entry* entry = m_fib.insert("/hello").first;
-  entry->addOrUpdateNextHop(*m_faceTable.get(face1), 101);
-  entry->addOrUpdateNextHop(*m_faceTable.get(face2), 202);
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face1), 101);
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face2), 202);
 
   testWithImplicitFaceId(ControlParameters().setName("/hello").setFaceId(0), face1);
   BOOST_REQUIRE_EQUAL(m_responses.size(), 1);
@@ -385,7 +385,8 @@
     receiveInterest(req);
   };
 
-  m_fib.insert("/hello").first->addOrUpdateNextHop(*m_faceTable.get(face1), 101);
+  fib::Entry* entry = m_fib.insert("/hello").first;
+  m_fib.addOrUpdateNextHop(*entry, *m_faceTable.get(face1), 101);
 
   testRemoveNextHop(makeParameters("/hello", face2 + 100));
   BOOST_REQUIRE_EQUAL(m_responses.size(), 1); // face does not exist
@@ -410,8 +411,8 @@
     Name prefix = Name("test").appendSegment(i);
     actualPrefixes.insert(prefix);
     fib::Entry* fibEntry = m_fib.insert(prefix).first;
-    fibEntry->addOrUpdateNextHop(*m_faceTable.get(addFace()), std::numeric_limits<uint8_t>::max() - 1);
-    fibEntry->addOrUpdateNextHop(*m_faceTable.get(addFace()), std::numeric_limits<uint8_t>::max() - 2);
+    m_fib.addOrUpdateNextHop(*fibEntry, *m_faceTable.get(addFace()), std::numeric_limits<uint8_t>::max() - 1);
+    m_fib.addOrUpdateNextHop(*fibEntry, *m_faceTable.get(addFace()), std::numeric_limits<uint8_t>::max() - 2);
   }
 
   receiveInterest(Interest("/localhost/nfd/fib/list").setCanBePrefix(true));
diff --git a/tests/daemon/table/cleanup.t.cpp b/tests/daemon/table/cleanup.t.cpp
index 911de1c..d23bb9b 100644
--- a/tests/daemon/table/cleanup.t.cpp
+++ b/tests/daemon/table/cleanup.t.cpp
@@ -49,7 +49,7 @@
     Name name = Name("/P").appendVersion(i);
 
     fib::Entry* fibEntry = fib.insert(name).first;
-    fibEntry->addOrUpdateNextHop(*face1, 0);
+    fib.addOrUpdateNextHop(*fibEntry, *face1, 0);
 
     shared_ptr<Interest> interest = makeInterest(name);
     shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
@@ -88,24 +88,24 @@
   BOOST_CHECK_EQUAL(fib.size(), 0);
 
   fib::Entry* entryA = fib.insert("/A").first;
-  entryA->addOrUpdateNextHop(*face1, 0);
-  entryA->addOrUpdateNextHop(*face2, 0);
+  fib.addOrUpdateNextHop(*entryA, *face1, 0);
+  fib.addOrUpdateNextHop(*entryA, *face2, 0);
   // {'/A':[1,2]}
 
   fib::Entry* entryB = fib.insert("/B").first;
-  entryB->addOrUpdateNextHop(*face1, 0);
+  fib.addOrUpdateNextHop(*entryB, *face1, 0);
   // {'/A':[1,2], '/B':[1]}
 
   fib::Entry* entryC = fib.insert("/C").first;
-  entryC->addOrUpdateNextHop(*face2, 1);
+  fib.addOrUpdateNextHop(*entryC, *face2, 1);
   // {'/A':[1,2], '/B':[1], '/C':[2]}
 
   fib::Entry* entryB1 = fib.insert("/B/1").first;
-  entryB1->addOrUpdateNextHop(*face1, 0);
+  fib.addOrUpdateNextHop(*entryB1, *face1, 0);
   // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
 
   fib::Entry* entryB12 = fib.insert("/B/1/2").first;
-  entryB12->addOrUpdateNextHop(*face1, 0);
+  fib.addOrUpdateNextHop(*entryB12, *face1, 0);
   // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
 
   // ---- close face1 ----
diff --git a/tests/daemon/table/fib.t.cpp b/tests/daemon/table/fib.t.cpp
index 33cbdfe..101b3b9 100644
--- a/tests/daemon/table/fib.t.cpp
+++ b/tests/daemon/table/fib.t.cpp
@@ -42,29 +42,53 @@
 
 BOOST_AUTO_TEST_CASE(FibEntry)
 {
-  Name prefix("ndn:/pxWhfFza");
+  NameTree nameTree;
+  Fib fib(nameTree);
+
+  Name prefix("/pxWhfFza");
   shared_ptr<Face> face1 = make_shared<DummyFace>();
   shared_ptr<Face> face2 = make_shared<DummyFace>();
 
-  Entry entry(prefix);
+  Face* expectedFace = nullptr;
+  uint64_t expectedCost = 0;
+  size_t nNewNextHopSignals = 0;
+
+  fib.afterNewNextHop.connect(
+    [&] (const Name& prefix1, const NextHop& nextHop) {
+      ++nNewNextHopSignals;
+      BOOST_CHECK_EQUAL(prefix1, prefix);
+      BOOST_CHECK_EQUAL(&nextHop.getFace(), expectedFace);
+      BOOST_CHECK_EQUAL(nextHop.getCost(), expectedCost);
+    });
+
+  Entry& entry = *fib.insert(prefix).first;
+
   BOOST_CHECK_EQUAL(entry.getPrefix(), prefix);
 
   // []
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 0);
 
-  entry.addOrUpdateNextHop(*face1, 20);
+  expectedFace = face1.get();
+  expectedCost = 20;
+
+  fib.addOrUpdateNextHop(entry, *face1, 20);
   // [(face1,20)]
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 1);
   BOOST_CHECK_EQUAL(&entry.getNextHops().begin()->getFace(), face1.get());
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getCost(), 20);
+  BOOST_CHECK_EQUAL(nNewNextHopSignals, 1);
 
-  entry.addOrUpdateNextHop(*face1, 30);
+  fib.addOrUpdateNextHop(entry, *face1, 30);
   // [(face1,30)]
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 1);
   BOOST_CHECK_EQUAL(&entry.getNextHops().begin()->getFace(), face1.get());
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getCost(), 30);
+  BOOST_CHECK_EQUAL(nNewNextHopSignals, 1);
 
-  entry.addOrUpdateNextHop(*face2, 40);
+  expectedFace = face2.get();
+  expectedCost = 40;
+
+  fib.addOrUpdateNextHop(entry, *face2, 40);
   // [(face1,30), (face2,40)]
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 2);
   {
@@ -80,9 +104,11 @@
 
     ++it;
     BOOST_CHECK(it == entry.getNextHops().end());
+
+    BOOST_CHECK_EQUAL(nNewNextHopSignals, 2);
   }
 
-  entry.addOrUpdateNextHop(*face2, 10);
+  fib.addOrUpdateNextHop(entry, *face2, 10);
   // [(face2,10), (face1,30)]
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 2);
   {
@@ -98,27 +124,28 @@
 
     ++it;
     BOOST_CHECK(it == entry.getNextHops().end());
+
+    BOOST_CHECK_EQUAL(nNewNextHopSignals, 2);
   }
 
-  entry.removeNextHop(*face1);
+  Fib::RemoveNextHopResult status = fib.removeNextHop(entry, *face1);
   // [(face2,10)]
+  BOOST_CHECK(status == Fib::RemoveNextHopResult::NEXTHOP_REMOVED);
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 1);
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getFace().getId(), face2->getId());
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getCost(), 10);
 
-  entry.removeNextHop(*face1);
+  status = fib.removeNextHop(entry, *face1);
   // [(face2,10)]
+  BOOST_CHECK(status == Fib::RemoveNextHopResult::NO_SUCH_NEXTHOP);
   BOOST_CHECK_EQUAL(entry.getNextHops().size(), 1);
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getFace().getId(), face2->getId());
   BOOST_CHECK_EQUAL(entry.getNextHops().begin()->getCost(), 10);
 
-  entry.removeNextHop(*face2);
+  status = fib.removeNextHop(entry, *face2);
   // []
-  BOOST_CHECK_EQUAL(entry.getNextHops().size(), 0);
-
-  entry.removeNextHop(*face2);
-  // []
-  BOOST_CHECK_EQUAL(entry.getNextHops().size(), 0);
+  BOOST_CHECK(status == Fib::RemoveNextHopResult::FIB_ENTRY_REMOVED);
+  BOOST_CHECK(fib.findExactMatch(prefix) == nullptr);
 }
 
 BOOST_AUTO_TEST_CASE(Insert_LongestPrefixMatch)