diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 3672b66..660ae72 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -144,8 +144,11 @@
 Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
 {
   for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
-       &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); ++it) {
+       &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end();) {
     shared_ptr<fib::Entry> entry = it->getFibEntry();
+
+    ++it; // need to be advance before `erase`, otherwise the iterator can be invalidated
+
     entry->removeNextHop(face);
     if (!entry->hasNextHops()) {
       this->erase(*entry);
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 027f852..0832a31 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -86,6 +86,7 @@
 
   ~NameTree();
 
+public: // information
   /**
    * \brief Get the number of occupied entries in the Name Tree
    */
@@ -101,6 +102,13 @@
   getNBuckets() const;
 
   /**
+   * \brief Dump all the information stored in the Name Tree for debugging.
+   */
+  void
+  dump(std::ostream& output) const;
+
+public: // mutation
+  /**
    * \brief Look for the Name Tree Entry that contains this name prefix.
    * \details Starts from the shortest name prefix, and then increase the
    * number of name components by one each time. All non-existing Name Tree
@@ -108,28 +116,48 @@
    * \param prefix The querying name prefix.
    * \return The pointer to the Name Tree Entry that contains this full name
    * prefix.
+   * \note Existing iterators are unaffected.
    */
   shared_ptr<name_tree::Entry>
   lookup(const Name& prefix);
 
   /**
-   * \brief Exact match lookup for the given name prefix.
-   * \return a null shared_ptr if this prefix is not found;
-   * otherwise return the Name Tree Entry address
-   */
-  shared_ptr<name_tree::Entry>
-  findExactMatch(const Name& prefix) const;
-
-  /**
    * \brief Delete a Name Tree Entry if this entry is empty.
    * \param entry The entry to be deleted if empty.
    * \note This function must be called after a table entry is detached from Name Tree
    *       entry. The function deletes a Name Tree entry if nothing is attached to it and
    *       it has no children, then repeats the same process on its ancestors.
+   * \note Existing iterators, except those pointing to deleted entries, are unaffected.
    */
   bool
   eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
 
+public: // shortcut access
+  /// get NameTree entry from attached FIB entry
+  shared_ptr<name_tree::Entry>
+  get(const fib::Entry& fibEntry) const;
+
+  /// get NameTree entry from attached PIT entry
+  shared_ptr<name_tree::Entry>
+  get(const pit::Entry& pitEntry) const;
+
+  /// get NameTree entry from attached Measurements entry
+  shared_ptr<name_tree::Entry>
+  get(const measurements::Entry& measurementsEntry) const;
+
+  /// get NameTree entry from attached StrategyChoice entry
+  shared_ptr<name_tree::Entry>
+  get(const strategy_choice::Entry& strategyChoiceEntry) const;
+
+public: // matching
+  /**
+   * \brief Exact match lookup for the given name prefix.
+   * \return a null shared_ptr if this prefix is not found;
+   * otherwise return the Name Tree Entry address
+   */
+  shared_ptr<name_tree::Entry>
+  findExactMatch(const Name& prefix) const;
+
   /**
    * \brief Longest prefix matching for the given name
    * \details Starts from the full name string, reduce the number of name component
@@ -146,15 +174,13 @@
                          name_tree::AnyEntry()) const;
 
   /**
-   * \brief Resize the hash table size when its load factor reaches a threshold.
-   * \details As we are currently using a hand-written hash table implementation
-   * for the Name Tree, the hash table resize() function should be kept in the
-   * name-tree.hpp file.
-   * \param newNBuckets The number of buckets for the new hash table.
+   * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
    */
-  void
-  resize(size_t newNBuckets);
+  const_iterator
+  findAllMatches(const Name& prefix,
+                 const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
 
+public: // enumeration
   /**
    * \brief Enumerate all the name prefixes stored in the Name Tree.
    */
@@ -169,39 +195,13 @@
                    const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
                          name_tree::AnyEntrySubTree()) const;
 
-  /**
-   * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
-   */
-  const_iterator
-  findAllMatches(const Name& prefix,
-                 const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
-
-  /**
-   * \brief Dump all the information stored in the Name Tree for debugging.
-   */
-  void
-  dump(std::ostream& output) const;
-
-  shared_ptr<name_tree::Entry>
-  get(const fib::Entry& fibEntry) const;
-
-  shared_ptr<name_tree::Entry>
-  get(const pit::Entry& pitEntry) const;
-
-  shared_ptr<name_tree::Entry>
-  get(const measurements::Entry& measurementsEntry) const;
-
-  shared_ptr<name_tree::Entry>
-  get(const strategy_choice::Entry& strategeChoiceEntry) const;
-
   const_iterator
   begin() const;
 
   const_iterator
   end() const;
 
-  enum IteratorType
-  {
+  enum IteratorType {
     FULL_ENUMERATE_TYPE,
     PARTIAL_ENUMERATE_TYPE,
     FIND_ALL_MATCHES_TYPE
@@ -249,6 +249,17 @@
   };
 
 private:
+  /**
+   * \brief Resize the hash table size when its load factor reaches a threshold.
+   * \details As we are currently using a hand-written hash table implementation
+   * for the Name Tree, the hash table resize() function should be kept in the
+   * name-tree.hpp file.
+   * \param newNBuckets The number of buckets for the new hash table.
+   */
+  void
+  resize(size_t newNBuckets);
+
+private:
   size_t                        m_nItems;  // Number of items being stored
   size_t                        m_nBuckets; // Number of hash buckets
   size_t                        m_minNBuckets; // Minimum number of hash buckets
@@ -309,9 +320,9 @@
 }
 
 inline shared_ptr<name_tree::Entry>
-NameTree::get(const strategy_choice::Entry& strategeChoiceEntry) const
+NameTree::get(const strategy_choice::Entry& strategyChoiceEntry) const
 {
-  return strategeChoiceEntry.m_nameTreeEntry;
+  return strategyChoiceEntry.m_nameTreeEntry;
 }
 
 inline NameTree::const_iterator
diff --git a/tests/daemon/table/fib.cpp b/tests/daemon/table/fib.cpp
index d40f15d..35fcd3e 100644
--- a/tests/daemon/table/fib.cpp
+++ b/tests/daemon/table/fib.cpp
@@ -223,9 +223,36 @@
   // {'/A':[1,2], '/B':[1]}
   BOOST_CHECK_EQUAL(fib.size(), 2);
 
+  insertRes = fib.insert("/C");
+  insertRes.first->addNextHop(face2, 1);
+  // {'/A':[1,2], '/B':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 3);
+
+  insertRes = fib.insert("/B/1");
+  insertRes.first->addNextHop(face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 4);
+
+  insertRes = fib.insert("/B/1/2");
+  insertRes.first->addNextHop(face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 5);
+
+  insertRes = fib.insert("/B/1/2/3");
+  insertRes.first->addNextHop(face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/3':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 6);
+
+  insertRes = fib.insert("/B/1/2/3/4");
+  insertRes.first->addNextHop(face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/2/3':[1], '/B/1/2/3/4':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 7);
+
+  /////////////
+
   fib.removeNextHopFromAllEntries(face1);
-  // {'/A':[2]}
-  BOOST_CHECK_EQUAL(fib.size(), 1);
+  // {'/A':[2], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 2);
 
   entry = fib.findLongestPrefixMatch(nameA);
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
diff --git a/tests/daemon/table/name-tree.cpp b/tests/daemon/table/name-tree.cpp
index 0a6f986..cd1d894 100644
--- a/tests/daemon/table/name-tree.cpp
+++ b/tests/daemon/table/name-tree.cpp
@@ -109,7 +109,7 @@
   BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
 }
 
-BOOST_AUTO_TEST_CASE(NameTreeBasic)
+BOOST_AUTO_TEST_CASE(Basic)
 {
   size_t nBuckets = 16;
   NameTree nt(nBuckets);
@@ -239,7 +239,7 @@
   BOOST_CHECK_EQUAL(nt.size(), 8);
 }
 
-BOOST_AUTO_TEST_CASE(NameTreeIteratorFullEnumerate)
+BOOST_AUTO_TEST_CASE(IteratorFullEnumerate)
 {
   size_t nBuckets = 1024;
   NameTree nt(nBuckets);
@@ -387,7 +387,7 @@
   return std::make_pair(first, second);
 }
 
-BOOST_AUTO_TEST_CASE(NameTreeIteratorPartialEnumerate)
+BOOST_AUTO_TEST_CASE(IteratorPartialEnumerate)
 {
   typedef NameTree::const_iterator const_iterator;
 
@@ -467,7 +467,8 @@
 
   // No NameA
   // No SubTree from NameAB
-  const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
+  const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA,
+    &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
   hasA   = false;
   hasAB  = false;
   hasAB1 = false;
@@ -516,7 +517,8 @@
 
   // No NameA
   // No SubTree from NameAC
-  const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
+  const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA,
+    &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
   hasA   = false;
   hasAB  = false;
   hasAB1 = false;
@@ -564,7 +566,8 @@
   BOOST_CHECK_EQUAL(counter, 4);
 
   // No Subtree from NameA
-  const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoSubNameA);
+  const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA,
+    &predicate_NameTreeEntry_NoSubNameA);
 
   hasA   = false;
   hasAB  = false;
@@ -648,7 +651,8 @@
   bool hasF = false;
 
   counter = 0;
-  const_iterator itExample = nameTreeExample.partialEnumerate(nameA, &predicate_NameTreeEntry_Example);
+  const_iterator itExample = nameTreeExample.partialEnumerate(nameA,
+    &predicate_NameTreeEntry_Example);
 
   for (; itExample != nameTreeExample.end(); itExample++)
   {
@@ -688,7 +692,7 @@
 }
 
 
-BOOST_AUTO_TEST_CASE(NameTreeIteratorFindAllMatches)
+BOOST_AUTO_TEST_CASE(IteratorFindAllMatches)
 {
   size_t nBuckets = 16;
   NameTree nt(nBuckets);
@@ -780,7 +784,7 @@
   BOOST_CHECK_EQUAL(counter, 7);
 }
 
-BOOST_AUTO_TEST_CASE(NameTreeHashTableResizeShrink)
+BOOST_AUTO_TEST_CASE(HashTableResizeShrink)
 {
   size_t nBuckets = 16;
   NameTree nameTree(nBuckets);
@@ -796,6 +800,63 @@
   BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
 }
 
+// .lookup should not invalidate iterator
+BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterLookup)
+{
+  NameTree nt;
+  nt.lookup("/A/B/C");
+  nt.lookup("/E");
+
+  Name nameB("/A/B");
+  std::set<Name> seenNames;
+  for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
+    BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
+    if (it->getPrefix() == nameB) {
+      nt.lookup("/D");
+    }
+  }
+
+  BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/E"), 1);
+
+  seenNames.erase("/D"); // /D may or may not appear
+  BOOST_CHECK(seenNames.size() == 5);
+}
+
+// .eraseEntryIfEmpty should not invalidate iterator
+BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterErase)
+{
+  NameTree nt;
+  nt.lookup("/A/B/C");
+  nt.lookup("/A/D/E");
+  nt.lookup("/A/F/G");
+  nt.lookup("/H");
+
+  Name nameD("/A/D");
+  std::set<Name> seenNames;
+  for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
+    BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
+    if (it->getPrefix() == nameD) {
+      nt.eraseEntryIfEmpty(nt.findExactMatch("/A/F/G")); // /A/F/G and /A/F are erased
+    }
+  }
+
+  BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/D"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/A/D/E"), 1);
+  BOOST_CHECK_EQUAL(seenNames.count("/H"), 1);
+
+  seenNames.erase("/A/F"); // /A/F may or may not appear
+  seenNames.erase("/A/F/G"); // /A/F/G may or may not appear
+  BOOST_CHECK(seenNames.size() == 7);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace tests