diff --git a/daemon/table/fib-entry.cpp b/daemon/table/fib-entry.cpp
index 6a9b686..1628d96 100644
--- a/daemon/table/fib-entry.cpp
+++ b/daemon/table/fib-entry.cpp
@@ -42,7 +42,6 @@
   it->setCost(cost);
 
   this->sortNextHops();
-
 }
 
 void
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index aac8fc5..48b09d6 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -11,6 +11,11 @@
 
 namespace nfd {
 
+class NameTree;
+namespace name_tree {
+class Entry;
+}
+
 namespace fib {
 
 /** \class NextHopList
@@ -37,6 +42,10 @@
   const NextHopList&
   getNextHops() const;
 
+  /// whether this Entry has any nexthop
+  bool
+  hasNextHops() const;
+
   bool
   hasNextHop(shared_ptr<Face> face) const;
 
@@ -56,6 +65,10 @@
 private:
   Name m_prefix;
   NextHopList m_nextHops;
+
+  shared_ptr<name_tree::Entry> m_nameTreeEntry;
+  friend class nfd::NameTree;
+  friend class nfd::name_tree::Entry;
 };
 
 
@@ -71,6 +84,12 @@
   return m_nextHops;
 }
 
+inline bool
+Entry::hasNextHops() const
+{
+  return !m_nextHops.empty();
+}
+
 } // namespace fib
 } // namespace nfd
 
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index eea7641..7397c60 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -37,7 +37,7 @@
     return std::make_pair(entry, false);
   entry = make_shared<fib::Entry>(prefix);
   nameTreeEntry->setFibEntry(entry);
-  m_nItems++;
+  ++m_nItems;
   return std::make_pair(entry, true);
 }
 
@@ -79,19 +79,32 @@
   shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
   if (static_cast<bool>(nameTreeEntry))
   {
-    nameTreeEntry->eraseFibEntry(nameTreeEntry->getFibEntry());
-    m_nItems--;
+    nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
+    --m_nItems;
+  }
+}
+
+void
+Fib::erase(const fib::Entry& entry)
+{
+  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(entry);
+  if (static_cast<bool>(nameTreeEntry))
+  {
+    nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
+    --m_nItems;
   }
 }
 
 void
 Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
 {
-  for (NameTree::const_iterator it = 
-    m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); it++)
-  {
+  for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
+       &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); ++it) {
     shared_ptr<fib::Entry> entry = it->getFibEntry();
     entry->removeNextHop(face);
+    if (!entry->hasNextHops()) {
+      this->erase(*entry);
+    }
   }
 }
 
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 0399833..5e2e03d 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -66,9 +66,13 @@
   size() const;
 
 private:
+  void
+  erase(const fib::Entry& entry);
+
+private:
   NameTree& m_nameTree;
   size_t m_nItems;
-  
+
   /** \brief The empty FIB entry.
    *
    *  This entry has no nexthops.
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
index 673be47..dd7bf4b 100644
--- a/daemon/table/name-tree-entry.cpp
+++ b/daemon/table/name-tree-entry.cpp
@@ -46,18 +46,15 @@
 }
 
 void
-Entry::setFibEntry(shared_ptr<fib::Entry> fib)
+Entry::setFibEntry(shared_ptr<fib::Entry> fibEntry)
 {
-  m_fibEntry = fib;
-}
-
-bool
-Entry::eraseFibEntry(shared_ptr<fib::Entry> fib)
-{
-  if (m_fibEntry != fib)
-    return false;
-  m_fibEntry.reset();
-  return true;
+  if (static_cast<bool>(m_fibEntry)) {
+    m_fibEntry->m_nameTreeEntry.reset();
+  }
+  m_fibEntry = fibEntry;
+  if (static_cast<bool>(m_fibEntry)) {
+    m_fibEntry->m_nameTreeEntry = this->shared_from_this();
+  }
 }
 
 void
@@ -102,7 +99,13 @@
 void
 Entry::setStrategyChoiceEntry(shared_ptr<strategy_choice::Entry> strategyChoiceEntry)
 {
+  if (static_cast<bool>(m_strategyChoiceEntry)) {
+    m_strategyChoiceEntry->m_nameTreeEntry.reset();
+  }
   m_strategyChoiceEntry = strategyChoiceEntry;
+  if (static_cast<bool>(m_strategyChoiceEntry)) {
+    m_strategyChoiceEntry->m_nameTreeEntry = this->shared_from_this();
+  }
 }
 
 } // namespace name_tree
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index cca1908..e3c72f2 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -45,7 +45,7 @@
 /**
  * \brief Name Tree Entry Class
  */
-class Entry : noncopyable
+class Entry : public enable_shared_from_this<Entry>, noncopyable
 {
   // Make private members accessible by Name Tree
   friend class nfd::NameTree;
@@ -80,14 +80,11 @@
   isEmpty() const;
 
   void
-  setFibEntry(shared_ptr<fib::Entry> fib);
+  setFibEntry(shared_ptr<fib::Entry> fibEntry);
 
   shared_ptr<fib::Entry>
   getFibEntry() const;
 
-  bool
-  eraseFibEntry(shared_ptr<fib::Entry> fib);
-
   void
   insertPitEntry(shared_ptr<pit::Entry> pit);
 
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 5d11c27..430ed3c 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -498,8 +498,10 @@
         }
 
       // process other buckets
-      int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
-      for (newLocation = newLocation; newLocation < m_nameTree.m_nBuckets; newLocation++)
+
+      for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
+           newLocation < static_cast<int>(m_nameTree.m_nBuckets);
+           ++newLocation)
         {
           // process each bucket
           name_tree::Node* node = m_nameTree.m_buckets[newLocation];
@@ -637,6 +639,9 @@
       m_entry = m_nameTree.m_end;
       return *this;
     }
+
+  BOOST_ASSERT(false); // unknown type
+  return *this;
 }
 
 } // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 1a30b2b..3d0de70 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -100,6 +100,9 @@
   shared_ptr<name_tree::Entry>
   findExactMatch(const Name& prefix) const;
 
+  shared_ptr<name_tree::Entry>
+  findExactMatch(const fib::Entry& fibEntry) const;
+
   /**
    * \brief Erase a Name Tree Entry if this entry is empty.
    * \details If a Name Tree Entry contains no Children, no FIB, no PIT, and
@@ -143,7 +146,8 @@
   */
   const_iterator
   partialEnumerate(const Name& prefix,
-                   const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree()) const;
+                   const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
+                         name_tree::AnyEntrySubTree()) const;
 
   /**
    * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
@@ -203,13 +207,13 @@
     operator!=(const const_iterator& other) const;
 
   private:
-    bool                                        m_shouldVisitChildren;
     const NameTree&                             m_nameTree;
     shared_ptr<name_tree::Entry>                m_entry;
     shared_ptr<name_tree::Entry>                m_subTreeRoot;
     shared_ptr<name_tree::EntrySelector>        m_entrySelector;
     shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
     NameTree::IteratorType                      m_type;
+    bool                                        m_shouldVisitChildren;
   };
 
 private:
@@ -250,6 +254,12 @@
   return m_nBuckets;
 }
 
+inline shared_ptr<name_tree::Entry>
+NameTree::findExactMatch(const fib::Entry& fibEntry) const
+{
+  return fibEntry.m_nameTreeEntry;
+}
+
 inline NameTree::const_iterator
 NameTree::begin() const
 {