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.
diff --git a/tests/daemon/face/dummy-face.hpp b/tests/daemon/face/dummy-face.hpp
index 34f2d09..e4c68b3 100644
--- a/tests/daemon/face/dummy-face.hpp
+++ b/tests/daemon/face/dummy-face.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014-2015,  Regents of the University of California,
+ * Copyright (c) 2014-2016,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -55,7 +55,7 @@
             ndn::nfd::LinkType linkType = ndn::nfd::LINK_TYPE_POINT_TO_POINT);
 
   /** \brief changes face state
-   *  \pre current state is not CLOSED or FAILED
+   *  \throw std::runtime_error state transition is invalid
    */
   void
   setState(FaceState state);
diff --git a/tests/daemon/table/cleanup.t.cpp b/tests/daemon/table/cleanup.t.cpp
new file mode 100644
index 0000000..0df019c
--- /dev/null
+++ b/tests/daemon/table/cleanup.t.cpp
@@ -0,0 +1,186 @@
+/* -*- 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 "table/cleanup.hpp"
+#include "fw/forwarder.hpp"
+
+#include "tests/test-common.hpp"
+#include "tests/daemon/face/dummy-face.hpp"
+
+namespace nfd {
+namespace tests {
+
+using namespace nfd::tests;
+
+BOOST_AUTO_TEST_SUITE(Table)
+BOOST_FIXTURE_TEST_SUITE(TestCleanup, BaseFixture)
+
+BOOST_AUTO_TEST_SUITE(FaceRemoval)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+  NameTree nameTree(16);
+  Fib fib(nameTree);
+  Pit pit(nameTree);
+  shared_ptr<Face> face1 = make_shared<DummyFace>();
+
+  for (uint64_t i = 0; i < 300; ++i) {
+    Name name = Name("/P").appendVersion(i);
+
+    fib::Entry* fibEntry = fib.insert(name).first;
+    fibEntry->addNextHop(*face1, 0);
+
+    shared_ptr<Interest> interest = makeInterest(name);
+    shared_ptr<pit::Entry> pitEntry = pit.insert(*interest).first;
+    if ((i & 0x01) != 0) {
+      pitEntry->insertOrUpdateInRecord(face1, *interest);
+    }
+    if ((i & 0x02) != 0) {
+      pitEntry->insertOrUpdateOutRecord(face1, *interest);
+    }
+  }
+  BOOST_CHECK_EQUAL(fib.size(), 300);
+  BOOST_CHECK_EQUAL(pit.size(), 300);
+
+  cleanupOnFaceRemoval(nameTree, fib, pit, *face1);
+  BOOST_CHECK_EQUAL(fib.size(), 0);
+  BOOST_CHECK_EQUAL(pit.size(), 300);
+  for (const pit::Entry& pitEntry : pit) {
+    BOOST_CHECK_EQUAL(pitEntry.hasInRecords(), false);
+    BOOST_CHECK_EQUAL(pitEntry.hasOutRecords(), false);
+  }
+}
+
+BOOST_AUTO_TEST_CASE(RemoveFibNexthops)
+{
+  Forwarder forwarder;
+  NameTree& nameTree = forwarder.getNameTree();
+  Fib& fib = forwarder.getFib();
+
+  shared_ptr<Face> face1 = make_shared<DummyFace>();
+  shared_ptr<Face> face2 = make_shared<DummyFace>();
+  forwarder.addFace(face1);
+  forwarder.addFace(face2);
+
+  // {}
+  size_t nNameTreeEntriesBefore = nameTree.size();
+  BOOST_CHECK_EQUAL(fib.size(), 0);
+
+  fib::Entry* entryA = fib.insert("/A").first;
+  entryA->addNextHop(*face1, 0);
+  entryA->addNextHop(*face2, 0);
+  // {'/A':[1,2]}
+
+  fib::Entry* entryB = fib.insert("/B").first;
+  entryB->addNextHop(*face1, 0);
+  // {'/A':[1,2], '/B':[1]}
+
+  fib::Entry* entryC = fib.insert("/C").first;
+  entryC->addNextHop(*face2, 1);
+  // {'/A':[1,2], '/B':[1], '/C':[2]}
+
+  fib::Entry* entryB1 = fib.insert("/B/1").first;
+  entryB1->addNextHop(*face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
+
+  fib::Entry* entryB12 = fib.insert("/B/1/2").first;
+  entryB12->addNextHop(*face1, 0);
+  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
+
+  // ---- close face1 ----
+  face1->close();
+  BOOST_CHECK_EQUAL(face1->getState(), face::FaceState::CLOSED);
+  // {'/A':[2], '/C':[2]}
+  BOOST_CHECK_EQUAL(fib.size(), 2);
+
+  const fib::Entry& foundA = fib.findLongestPrefixMatch("/A");
+  BOOST_CHECK_EQUAL(foundA.getPrefix(), "/A");
+  BOOST_CHECK_EQUAL(foundA.getNextHops().size(), 1);
+  BOOST_CHECK_EQUAL(&foundA.getNextHops().begin()->getFace(), face2.get());
+
+  BOOST_CHECK_EQUAL(fib.findLongestPrefixMatch("/B").getPrefix(), "/");
+
+  // ---- close face2 ----
+  face2->close();
+  BOOST_CHECK_EQUAL(face2->getState(), face::FaceState::CLOSED);
+  BOOST_CHECK_EQUAL(fib.size(), 0);
+  BOOST_CHECK_EQUAL(nameTree.size(), nNameTreeEntriesBefore);
+}
+
+BOOST_AUTO_TEST_CASE(DeletePitInOutRecords)
+{
+  Forwarder forwarder;
+  Pit& pit = forwarder.getPit();
+
+  shared_ptr<Face> face1 = make_shared<DummyFace>();
+  shared_ptr<Face> face2 = make_shared<DummyFace>();
+  forwarder.addFace(face1);
+  forwarder.addFace(face2);
+
+  // {}
+  BOOST_CHECK_EQUAL(pit.size(), 0);
+
+  shared_ptr<Interest> interestA = makeInterest("/A");
+  shared_ptr<pit::Entry> entryA = pit.insert(*interestA).first;
+  entryA->insertOrUpdateInRecord(face1, *interestA);
+  entryA->insertOrUpdateInRecord(face2, *interestA);
+  entryA->insertOrUpdateOutRecord(face1, *interestA);
+  entryA->insertOrUpdateOutRecord(face2, *interestA);
+  // {'/A':[1,2]}
+
+  shared_ptr<Interest> interestB = makeInterest("/B");
+  shared_ptr<pit::Entry> entryB = pit.insert(*interestB).first;
+  entryB->insertOrUpdateInRecord(face1, *interestB);
+  entryB->insertOrUpdateOutRecord(face1, *interestB);
+  // {'/A':[1,2], '/B':[1]}
+
+  shared_ptr<Interest> interestC = makeInterest("/C");
+  shared_ptr<pit::Entry> entryC = pit.insert(*interestC).first;
+  entryC->insertOrUpdateInRecord(face2, *interestC);
+  entryC->insertOrUpdateOutRecord(face2, *interestC);
+  // {'/A':[1,2], '/B':[1], '/C':[2]}
+  BOOST_CHECK_EQUAL(pit.size(), 3);
+
+  // ---- close face1 ----
+  face1->close();
+  BOOST_CHECK_EQUAL(face1->getState(), face::FaceState::CLOSED);
+  // {'/A':[2], '/B':[], '/C':[2]}
+  BOOST_CHECK_EQUAL(pit.size(), 3);
+
+  shared_ptr<pit::Entry> foundA = pit.find(*interestA);
+  BOOST_REQUIRE(foundA != nullptr);
+  BOOST_REQUIRE_EQUAL(foundA->getInRecords().size(), 1);
+  BOOST_CHECK_EQUAL(foundA->getInRecords().front().getFace(), face2);
+  BOOST_REQUIRE_EQUAL(foundA->getOutRecords().size(), 1);
+  BOOST_CHECK_EQUAL(foundA->getOutRecords().front().getFace(), face2);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // FaceRemovalCleanup
+
+BOOST_AUTO_TEST_SUITE_END() // TestCleanup
+BOOST_AUTO_TEST_SUITE_END() // Table
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/fib.t.cpp b/tests/daemon/table/fib.t.cpp
index 46a3bca..204c5a3 100644
--- a/tests/daemon/table/fib.t.cpp
+++ b/tests/daemon/table/fib.t.cpp
@@ -214,71 +214,6 @@
   BOOST_CHECK_EQUAL(fib.findLongestPrefixMatch(mABCD).getPrefix(), "/A/B/C");
 }
 
-BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries)
-{
-  shared_ptr<Face> face1 = make_shared<DummyFace>();
-  shared_ptr<Face> face2 = make_shared<DummyFace>();
-
-  NameTree nameTree;
-  Fib fib(nameTree);
-  // {}
-
-  Entry* entryA = fib.insert("/A").first;
-  entryA->addNextHop(*face1, 0);
-  entryA->addNextHop(*face2, 0);
-  // {'/A':[1,2]}
-
-  Entry* entryB = fib.insert("/B").first;
-  entryB->addNextHop(*face1, 0);
-  // {'/A':[1,2], '/B':[1]}
-  BOOST_CHECK_EQUAL(fib.size(), 2);
-
-  Entry* entryC = fib.insert("/C").first;
-  entryC->addNextHop(*face2, 1);
-  // {'/A':[1,2], '/B':[1], '/C':[2]}
-  BOOST_CHECK_EQUAL(fib.size(), 3);
-
-  Entry* entryB1 = fib.insert("/B/1").first;
-  entryB1->addNextHop(*face1, 0);
-  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
-  BOOST_CHECK_EQUAL(fib.size(), 4);
-
-  Entry* entryB12 = fib.insert("/B/1/2").first;
-  entryB12->addNextHop(*face1, 0);
-  // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
-  BOOST_CHECK_EQUAL(fib.size(), 5);
-
-  /////////////
-
-  fib.removeNextHopFromAllEntries(*face1);
-  // {'/A':[2], '/C':[2]}
-  BOOST_CHECK_EQUAL(fib.size(), 2);
-
-  const Entry& foundA = fib.findLongestPrefixMatch("/A");
-  BOOST_CHECK_EQUAL(foundA.getPrefix(), "/A");
-  const NextHopList& nexthopsA = foundA.getNextHops();
-  BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
-  BOOST_CHECK_EQUAL(&nexthopsA.begin()->getFace(), face2.get());
-
-  BOOST_CHECK_EQUAL(fib.findLongestPrefixMatch("/B").getPrefix(), "/");
-}
-
-BOOST_AUTO_TEST_CASE(RemoveNextHopFromManyEntries)
-{
-  NameTree nameTree(16);
-  Fib fib(nameTree);
-  shared_ptr<Face> face1 = make_shared<DummyFace>();
-
-  for (uint64_t i = 0; i < 300; ++i) {
-    Entry* entry = fib.insert(Name("/P").appendVersion(i)).first;
-    entry->addNextHop(*face1, 0);
-  }
-  BOOST_CHECK_EQUAL(fib.size(), 300);
-
-  fib.removeNextHopFromAllEntries(*face1);
-  BOOST_CHECK_EQUAL(fib.size(), 0);
-}
-
 void
 validateFindExactMatch(Fib& fib, const Name& target)
 {