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
 {
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 4d9d05f..cc80bba 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -19,21 +19,21 @@
   Name prefix("ndn:/pxWhfFza");
   shared_ptr<Face> face1 = make_shared<DummyFace>();
   shared_ptr<Face> face2 = make_shared<DummyFace>();
-  
+
   fib::Entry entry(prefix);
-  BOOST_CHECK(entry.getPrefix().equals(prefix));
-  
+  BOOST_CHECK_EQUAL(entry.getPrefix(), prefix);
+
   const fib::NextHopList& nexthops1 = entry.getNextHops();
   // []
   BOOST_CHECK_EQUAL(nexthops1.size(), 0);
-  
+
   entry.addNextHop(face1, 20);
   const fib::NextHopList& nexthops2 = entry.getNextHops();
   // [(face1,20)]
   BOOST_CHECK_EQUAL(nexthops2.size(), 1);
   BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1);
   BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20);
-  
+
   entry.addNextHop(face1, 30);
   const fib::NextHopList& nexthops3 = entry.getNextHops();
   // [(face1,30)]
@@ -80,26 +80,26 @@
         break;
     }
   }
-  
+
   entry.removeNextHop(face1);
   const fib::NextHopList& nexthops6 = entry.getNextHops();
   // [(face2,10)]
   BOOST_CHECK_EQUAL(nexthops6.size(), 1);
   BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2);
   BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10);
-  
+
   entry.removeNextHop(face1);
   const fib::NextHopList& nexthops7 = entry.getNextHops();
   // [(face2,10)]
   BOOST_CHECK_EQUAL(nexthops7.size(), 1);
   BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2);
   BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10);
-  
+
   entry.removeNextHop(face2);
   const fib::NextHopList& nexthops8 = entry.getNextHops();
   // []
   BOOST_CHECK_EQUAL(nexthops8.size(), 0);
-  
+
   entry.removeNextHop(face2);
   const fib::NextHopList& nexthops9 = entry.getNextHops();
   // []
@@ -114,61 +114,66 @@
   Name nameABC ("ndn:/A/B/C");
   Name nameABCD("ndn:/A/B/C/D");
   Name nameE   ("ndn:/E");
-  
+
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
 
   NameTree nameTree(1024);
   Fib fib(nameTree);
   // []
+  BOOST_CHECK_EQUAL(fib.size(), 0);
 
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry
-  
+
   insertRes = fib.insert(nameEmpty);
   BOOST_CHECK_EQUAL(insertRes.second, true);
   BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty);
   // ['/']
-  
+  BOOST_CHECK_EQUAL(fib.size(), 1);
+
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
-  
+
   insertRes = fib.insert(nameA);
   BOOST_CHECK_EQUAL(insertRes.second, true);
   BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
   // ['/', '/A']
-  
+  BOOST_CHECK_EQUAL(fib.size(), 2);
+
   insertRes = fib.insert(nameA);
   BOOST_CHECK_EQUAL(insertRes.second, false);
   BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
   // ['/', '/A']
+  BOOST_CHECK_EQUAL(fib.size(), 2);
 
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-  
+
   entry = fib.findLongestPrefixMatch(nameABCD);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-  
+
   insertRes = fib.insert(nameABC);
   BOOST_CHECK_EQUAL(insertRes.second, true);
   BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC);
   // ['/', '/A', '/A/B/C']
+  BOOST_CHECK_EQUAL(fib.size(), 3);
 
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-  
+
   entry = fib.findLongestPrefixMatch(nameAB);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-  
+
   entry = fib.findLongestPrefixMatch(nameABCD);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC);
-  
+
   entry = fib.findLongestPrefixMatch(nameE);
   BOOST_REQUIRE(static_cast<bool>(entry));
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
@@ -178,38 +183,39 @@
 {
   shared_ptr<Face> face1 = make_shared<DummyFace>();
   shared_ptr<Face> face2 = make_shared<DummyFace>();
+  Name nameEmpty("ndn:/");
   Name nameA("ndn:/A");
   Name nameB("ndn:/B");
-  
+
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
-  
+
   NameTree nameTree(1024);
   Fib fib(nameTree);
-  // {'/':[]}
-  
+  // {}
+
   insertRes = fib.insert(nameA);
   insertRes.first->addNextHop(face1, 0);
   insertRes.first->addNextHop(face2, 0);
-  // {'/':[], '/A':[1,2]}
+  // {'/A':[1,2]}
 
   insertRes = fib.insert(nameB);
   insertRes.first->addNextHop(face1, 0);
-  // {'/':[], '/A':[1,2], '/B':[1]}
-  
+  // {'/A':[1,2], '/B':[1]}
+  BOOST_CHECK_EQUAL(fib.size(), 2);
+
   fib.removeNextHopFromAllEntries(face1);
-  // {'/':[], '/A':[2], '/B':[]}
-  
+  // {'/A':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 1);
+
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
   const fib::NextHopList& nexthopsA = entry->getNextHops();
   BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
   BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
-  
+
   entry = fib.findLongestPrefixMatch(nameB);
-  BOOST_CHECK_EQUAL(entry->getPrefix(), nameB);
-  const fib::NextHopList& nexthopsB = entry->getNextHops();
-  BOOST_CHECK_EQUAL(nexthopsB.size(), 0);
+  BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
 }
 
 void
diff --git a/tests/table/name-tree.cpp b/tests/table/name-tree.cpp
index e44c401..d03f4af 100644
--- a/tests/table/name-tree.cpp
+++ b/tests/table/name-tree.cpp
@@ -18,53 +18,46 @@
 {
   Name prefix("ndn:/named-data/research/abc/def/ghi");
 
-  name_tree::Entry npe(prefix);
-  BOOST_CHECK_EQUAL(npe.getPrefix(), prefix);
+  shared_ptr<name_tree::Entry> npe = make_shared<name_tree::Entry>(prefix);
+  BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
 
   // examine all the get methods
 
-  uint32_t hash = npe.getHash();
+  uint32_t hash = npe->getHash();
   BOOST_CHECK_EQUAL(hash, 0);
 
-  shared_ptr<name_tree::Entry> parent = npe.getParent();
+  shared_ptr<name_tree::Entry> parent = npe->getParent();
   BOOST_CHECK(!static_cast<bool>(parent));
 
-  std::vector<shared_ptr<name_tree::Entry> >& childList = npe.getChildren();
+  std::vector<shared_ptr<name_tree::Entry> >& childList = npe->getChildren();
   BOOST_CHECK_EQUAL(childList.size(), 0);
 
-  shared_ptr<fib::Entry> fib = npe.getFibEntry();
+  shared_ptr<fib::Entry> fib = npe->getFibEntry();
   BOOST_CHECK(!static_cast<bool>(fib));
 
-  std::vector< shared_ptr<pit::Entry> >& pitList = npe.getPitEntries();
+  std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
   BOOST_CHECK_EQUAL(pitList.size(), 0);
 
   // examine all the set method
 
-  npe.setHash(12345);
-  BOOST_CHECK_EQUAL(npe.getHash(), 12345);
+  npe->setHash(12345);
+  BOOST_CHECK_EQUAL(npe->getHash(), 12345);
 
   Name parentName("ndn:/named-data/research/abc/def");
   parent = make_shared<name_tree::Entry>(parentName);
-  npe.setParent(parent);
-  BOOST_CHECK_EQUAL(npe.getParent(), parent);
+  npe->setParent(parent);
+  BOOST_CHECK_EQUAL(npe->getParent(), parent);
 
   // Insert FIB
 
   shared_ptr<fib::Entry> fibEntry(new fib::Entry(prefix));
   shared_ptr<fib::Entry> fibEntryParent(new fib::Entry(parentName));
 
-  npe.setFibEntry(fibEntry);
-  BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
+  npe->setFibEntry(fibEntry);
+  BOOST_CHECK_EQUAL(npe->getFibEntry(), fibEntry);
 
-  // Erase a FIB that does not exist
-  BOOST_CHECK_EQUAL(npe.
-  eraseFibEntry(fibEntryParent), false);
-  BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
-
-  // Erase the FIB that exists
-  BOOST_CHECK_EQUAL(npe.
-  eraseFibEntry(fibEntry), true);
-  BOOST_CHECK(!static_cast<bool>(npe.getFibEntry()));
+  npe->setFibEntry(shared_ptr<fib::Entry>());
+  BOOST_CHECK(!static_cast<bool>(npe->getFibEntry()));
 
   // Insert a PIT
 
@@ -74,29 +67,29 @@
   Name prefix3("ndn:/named-data/research/abc/def");
   shared_ptr<pit::Entry> PitEntry3(make_shared<pit::Entry>(prefix3));
 
-  npe.insertPitEntry(PitEntry);
-  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+  npe->insertPitEntry(PitEntry);
+  BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
 
-  npe.insertPitEntry(PitEntry2);
-  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 2);
+  npe->insertPitEntry(PitEntry2);
+  BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 2);
 
-  BOOST_CHECK_EQUAL(npe.
+  BOOST_CHECK_EQUAL(npe->
   erasePitEntry(PitEntry), true);
-  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+  BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
 
   // erase a PIT Entry that does not exist
 
-  BOOST_CHECK_EQUAL(npe.
+  BOOST_CHECK_EQUAL(npe->
   erasePitEntry(PitEntry3), false);
-  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+  BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
 
-  BOOST_CHECK_EQUAL(npe.
+  BOOST_CHECK_EQUAL(npe->
   erasePitEntry(PitEntry2), true);
-  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 0);
+  BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
 
   // erase a PIT Entry that does not exist any more
 
-  BOOST_CHECK_EQUAL(npe.
+  BOOST_CHECK_EQUAL(npe->
   erasePitEntry(PitEntry2), false);
 }