diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 1bb2ebe..2fbc93c 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -28,6 +28,7 @@
 #include "core/logger.hpp"
 #include "core/random.hpp"
 #include "strategy.hpp"
+#include "table/cleanup.hpp"
 #include <boost/random/uniform_int_distribution.hpp>
 
 namespace nfd {
@@ -60,7 +61,7 @@
   });
 
   m_faceTable.beforeRemove.connect([this] (Face& face) {
-    m_fib.removeNextHopFromAllEntries(face);
+    cleanupOnFaceRemoval(m_nameTree, m_fib, m_pit, face);
   });
 }
 
diff --git a/daemon/table/cleanup.cpp b/daemon/table/cleanup.cpp
new file mode 100644
index 0000000..0ba0725
--- /dev/null
+++ b/daemon/table/cleanup.cpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD 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.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "cleanup.hpp"
+
+namespace nfd {
+
+void
+cleanupOnFaceRemoval(NameTree& nt, Fib& fib, Pit& pit, const Face& face)
+{
+  std::multimap<size_t, weak_ptr<name_tree::Entry>> maybeEmptyNtes;
+
+  // visit FIB and PIT entries in one pass of NameTree enumeration
+  for (const name_tree::Entry& nte : nt) {
+    fib::Entry* fibEntry = nte.getFibEntry();
+    if (fibEntry != nullptr) {
+      fib.removeNextHop(*fibEntry, face);
+    }
+
+    for (const auto& pitEntry : nte.getPitEntries()) {
+      pit.deleteInOutRecords(pitEntry, face);
+    }
+
+    if (nte.getFibEntry() == nullptr && !nte.hasPitEntries()) {
+      maybeEmptyNtes.emplace(nte.getPrefix().size(), const_pointer_cast<name_tree::Entry>(nte.shared_from_this()));
+    }
+  }
+
+  // try to erase longer names first, so that children are erased before parent is checked
+  for (auto i = maybeEmptyNtes.rbegin(); i != maybeEmptyNtes.rend(); ++i) {
+    shared_ptr<name_tree::Entry> nte = i->second.lock();
+    // nte may have been erased when its last child is erased
+    if (nte != nullptr) {
+      nt.eraseEntryIfEmpty(nte);
+    }
+  }
+}
+
+} // namespace nfd
diff --git a/daemon/table/cleanup.hpp b/daemon/table/cleanup.hpp
new file mode 100644
index 0000000..3c84482
--- /dev/null
+++ b/daemon/table/cleanup.hpp
@@ -0,0 +1,52 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD 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.
+ *
+ * NFD 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
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_CLEANUP_HPP
+#define NFD_DAEMON_TABLE_CLEANUP_HPP
+
+#include "name-tree.hpp"
+#include "fib.hpp"
+#include "pit.hpp"
+
+namespace nfd {
+
+/** \brief cleanup tables when a face is destroyed
+ *
+ *  This function enumerates the NameTree, calls Fib::removeNextHop for each FIB entry,
+ *  calls Pit::deleteInOutRecords for each PIT entry, and finally
+ *  deletes any name tree entries that have become empty.
+ *
+ *  \note It's a design choice to let Fib and Pit classes decide what to do with each entry.
+ *        This function is only responsible for implementing the enumeration procedure.
+ *        The benefit of having this function instead of doing the enumeration in Fib and Pit
+ *        classes is to perform both FIB and PIT cleanups in one pass of NameTree enumeration,
+ *        so as to reduce performance overhead.
+ */
+void
+cleanupOnFaceRemoval(NameTree& nt, Fib& fib, Pit& pit, const Face& face);
+
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CLEANUP_HPP
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 2df3122..890bbbe 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -130,10 +130,14 @@
 }
 
 void
-Fib::erase(shared_ptr<name_tree::Entry> nte)
+Fib::erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte)
 {
+  BOOST_ASSERT(nte != nullptr);
+
   nte->setFibEntry(nullptr);
-  m_nameTree.eraseEntryIfEmpty(nte);
+  if (canDeleteNte) {
+    m_nameTree.eraseEntryIfEmpty(nte);
+  }
   --m_nItems;
 }
 
@@ -151,28 +155,19 @@
 {
   shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
   if (nte != nullptr) {
+    // don't try to erase s_emptyEntry
     this->erase(nte);
   }
 }
 
 void
-Fib::removeNextHopFromAllEntries(const Face& face)
+Fib::removeNextHop(Entry& entry, const Face& face)
 {
-  std::list<Entry*> toErase;
+  entry.removeNextHop(face);
 
-  auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
-  for (const name_tree::Entry& nte : enumerable) {
-    Entry* entry = nte.getFibEntry();
-    entry->removeNextHop(face);
-    if (!entry->hasNextHops()) {
-      toErase.push_back(entry);
-      // entry needs to be erased, but we must wait until the enumeration ends,
-      // because otherwise NameTree iterator would be invalidated
-    }
-  }
-
-  for (Entry* entry : toErase) {
-    this->erase(*entry);
+  if (!entry.hasNextHops()) {
+    shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+    this->erase(nte, false);
   }
 }
 
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index bfe6684..df2bfeb 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -93,15 +93,10 @@
   void
   erase(const Entry& entry);
 
-  /** \brief removes the NextHop record for face in all entries
-   *
-   *  This is usually invoked when face is destroyed.
-   *  Removing the last NextHop in a FIB entry will erase the FIB entry.
-   *
-   *  \todo change parameter type to Face&
+  /** \brief removes the NextHop record for face
    */
   void
-  removeNextHopFromAllEntries(const Face& face);
+  removeNextHop(Entry& entry, const Face& face);
 
 public: // enumeration
   class const_iterator;
@@ -158,7 +153,7 @@
   findLongestPrefixMatch(shared_ptr<name_tree::Entry> nte) const;
 
   void
-  erase(shared_ptr<name_tree::Entry> nameTreeEntry);
+  erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte = true);
 
 private:
   NameTree& m_nameTree;
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 5db1ce2..57cbf53 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -124,17 +124,35 @@
 }
 
 void
-Pit::erase(shared_ptr<pit::Entry> pitEntry)
+Pit::erase(shared_ptr<pit::Entry> entry)
 {
-  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.getEntry(*pitEntry);
-  BOOST_ASSERT(nameTreeEntry != nullptr);
+  this->erase(entry, true);
+}
 
-  nameTreeEntry->erasePitEntry(pitEntry);
-  m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
+void
+Pit::erase(shared_ptr<pit::Entry> entry, bool canDeleteNte)
+{
+  shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(*entry);
+  BOOST_ASSERT(nte != nullptr);
 
+  nte->erasePitEntry(entry);
+  if (canDeleteNte) {
+    m_nameTree.eraseEntryIfEmpty(nte);
+  }
   --m_nItems;
 }
 
+void
+Pit::deleteInOutRecords(shared_ptr<pit::Entry> entry, const Face& face)
+{
+  BOOST_ASSERT(entry != nullptr);
+
+  entry->deleteInRecord(face);
+  entry->deleteOutRecord(face);
+
+  /// \todo decide whether to delete PIT entry if there's no more in/out-record left
+}
+
 Pit::const_iterator
 Pit::begin() const
 {
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index cea528f..cbfac86 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -81,7 +81,12 @@
    *  \brief erases a PIT Entry
    */
   void
-  erase(shared_ptr<pit::Entry> pitEntry);
+  erase(shared_ptr<pit::Entry> entry);
+
+  /** \brief deletes in-record and out-record for face
+   */
+  void
+  deleteInOutRecords(shared_ptr<pit::Entry> entry, const Face& face);
 
 public: // enumeration
   class const_iterator;
@@ -140,6 +145,12 @@
   };
 
 private:
+  /**
+   *  \brief erases a PIT Entry
+   */
+  void
+  erase(shared_ptr<pit::Entry> pitEntry, bool canDeleteNte);
+
   /** \brief finds or inserts a PIT entry for Interest
    *  \param interest the Interest; must be created with make_shared if allowInsert
    *  \param allowInsert whether inserting new entry is allowed.