diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index cc40f24..ce22c22 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -17,6 +17,7 @@
 Forwarder::Forwarder()
   : m_lastFaceId(0)
   , m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
+  , m_fib(m_nameTree)
   , m_pit(m_nameTree)
 {
   m_strategy = make_shared<fw::BestRouteStrategy>(boost::ref(*this));
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 3df2d41..5130c76 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -117,7 +117,7 @@
 private:
   FaceId m_lastFaceId;
   std::map<FaceId, shared_ptr<Face> > m_faces;
-  
+
   NameTree     m_nameTree;
   Fib          m_fib;
   Pit          m_pit;
diff --git a/daemon/mgmt/fib-manager.cpp b/daemon/mgmt/fib-manager.cpp
index 0b20c02..27707d7 100644
--- a/daemon/mgmt/fib-manager.cpp
+++ b/daemon/mgmt/fib-manager.cpp
@@ -179,7 +179,7 @@
   NFD_LOG_INFO("delete result: OK"
                << " prefix: " << options.getName());
 
-  m_managedFib.remove(options.getName());
+  m_managedFib.erase(options.getName());
   setResponse(response, 200, "Success", options.wireEncode());
 }
 
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 481df77..9c7a611 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -9,55 +9,42 @@
 #include "measurements-entry.hpp"
 
 namespace nfd {
-
-Fib::Fib()
+Fib::Fib(NameTree& nameTree)
+  : m_nameTree(nameTree)
+  , m_nItems(0)
 {
-  std::pair<shared_ptr<fib::Entry>, bool> pair_rootEntry_dummy =
-    this->insert(Name());
-  m_rootEntry = pair_rootEntry_dummy.first;
+  m_rootEntry = (this->insert(Name())).first;
 }
 
 Fib::~Fib()
 {
 }
 
-static inline bool
-predicate_FibEntry_eq_Name(const shared_ptr<fib::Entry>& entry,
-  const Name& name)
-{
-  return entry->getPrefix().equals(name);
-}
-
 std::pair<shared_ptr<fib::Entry>, bool>
 Fib::insert(const Name& prefix)
 {
-  std::list<shared_ptr<fib::Entry> >::iterator it = std::find_if(
-    m_table.begin(), m_table.end(),
-    bind(&predicate_FibEntry_eq_Name, _1, prefix));
-  if (it != m_table.end()) return std::make_pair(*it, false);
-
-  shared_ptr<fib::Entry> entry = make_shared<fib::Entry>(prefix);
-  m_table.push_back(entry);
+  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
+  shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
+  if (static_cast<bool>(entry))
+    return std::make_pair(entry, false);
+  entry = make_shared<fib::Entry>(prefix);
+  nameTreeEntry->setFibEntry(entry);
+  m_nItems++;
   return std::make_pair(entry, true);
 }
 
-static inline const shared_ptr<fib::Entry>&
-accumulate_FibEntry_longestPrefixMatch(
-  const shared_ptr<fib::Entry>& bestMatch,
-  const shared_ptr<fib::Entry>& entry, const Name& name)
-{
-  if (!entry->getPrefix().isPrefixOf(name)) return bestMatch;
-  if (bestMatch->getPrefix().size() < entry->getPrefix().size()) return entry;
-  return bestMatch;
-}
-
 shared_ptr<fib::Entry>
 Fib::findLongestPrefixMatch(const Name& prefix) const
 {
-  shared_ptr<fib::Entry> bestMatch =
-    std::accumulate(m_table.begin(), m_table.end(), m_rootEntry,
-    bind(&accumulate_FibEntry_longestPrefixMatch, _1, _2, prefix));
-  return bestMatch;
+  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findLongestPrefixMatch(prefix);
+  while (static_cast<bool>(nameTreeEntry))
+  {
+    if (static_cast<bool>(nameTreeEntry->getFibEntry()))
+      return nameTreeEntry->getFibEntry();
+    else
+      nameTreeEntry = nameTreeEntry->getParent();
+  }
+  return m_rootEntry;
 }
 
 shared_ptr<fib::Entry>
@@ -75,35 +62,34 @@
 shared_ptr<fib::Entry>
 Fib::findExactMatch(const Name& prefix) const
 {
-  std::list<shared_ptr<fib::Entry> >::const_iterator it =
-    std::find_if(m_table.begin(), m_table.end(),
-                 bind(&predicate_FibEntry_eq_Name, _1, prefix));
-
-  if (it != m_table.end())
-    {
-      return *it;
-    }
+  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
+  if (static_cast<bool>(nameTreeEntry))
+    return nameTreeEntry->getFibEntry();
   return shared_ptr<fib::Entry>();
 }
 
 void
-Fib::remove(const Name& prefix)
+Fib::erase(const Name& prefix)
 {
-  m_table.remove_if(bind(&predicate_FibEntry_eq_Name, _1, prefix));
-}
-
-static inline void
-FibEntry_removeNextHop(shared_ptr<fib::Entry> entry,
-  shared_ptr<Face> face)
-{
-  entry->removeNextHop(face);
+  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
+  if (static_cast<bool>(nameTreeEntry))
+  {
+    nameTreeEntry->eraseFibEntry(nameTreeEntry->getFibEntry());
+    m_nItems--;
+  }
 }
 
 void
 Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
 {
-  std::for_each(m_table.begin(), m_table.end(),
-    bind(&FibEntry_removeNextHop, _1, face));
+  shared_ptr<fib::Entry> entry;
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry > > > res = m_nameTree.fullEnumerate();
+  for (int i = 0; i < res->size(); i++)
+  {
+    entry = (*res)[i]->getFibEntry();
+    if (static_cast<bool>(entry))
+      entry->removeNextHop(face);
+  }
 }
 
 
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 2661911..166eb1b 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -8,18 +8,25 @@
 #define NFD_TABLE_FIB_HPP
 
 #include "fib-entry.hpp"
-#include "pit-entry.hpp"
-#include "measurements-entry.hpp"
+#include "name-tree.hpp"
 
 namespace nfd {
 
+namespace measurements {
+class Entry;
+}
+namespace pit {
+class Entry;
+}
+
 /** \class Fib
  *  \brief represents the FIB
  */
 class Fib : noncopyable
 {
 public:
-  Fib();
+  explicit
+  Fib(NameTree& nameTree);
 
   ~Fib();
 
@@ -46,7 +53,7 @@
   findExactMatch(const Name& prefix) const;
 
   void
-  remove(const Name& prefix);
+  erase(const Name& prefix);
 
   /** \brief removes the NextHop record for face in all entrites
    *  This is usually invoked when face goes away.
@@ -55,11 +62,21 @@
   void
   removeNextHopFromAllEntries(shared_ptr<Face> face);
 
+  size_t
+  size() const;
+
 private:
   shared_ptr<fib::Entry> m_rootEntry;
-  std::list<shared_ptr<fib::Entry> > m_table;
+  NameTree& m_nameTree;
+  size_t m_nItems; // Number of items being stored
 };
 
+inline size_t
+Fib::size() const
+{
+  return m_nItems;
+}
+
 } // namespace nfd
 
 #endif // NFD_TABLE_FIB_HPP
diff --git a/tests/mgmt/fib-manager.cpp b/tests/mgmt/fib-manager.cpp
index 00043d2..9905f8a 100644
--- a/tests/mgmt/fib-manager.cpp
+++ b/tests/mgmt/fib-manager.cpp
@@ -166,7 +166,8 @@
 BOOST_AUTO_TEST_CASE(TestFireInterestFilter)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -185,7 +186,8 @@
 BOOST_AUTO_TEST_CASE(MalformedCommmand)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -206,7 +208,8 @@
 BOOST_AUTO_TEST_CASE(UnsupportedVerb)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -237,7 +240,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -271,7 +275,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -305,7 +310,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -329,7 +335,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -361,7 +368,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -403,7 +411,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -437,7 +446,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -491,7 +501,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace,
                           this, _1),
@@ -566,7 +577,8 @@
 BOOST_AUTO_TEST_CASE(Insert)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -664,7 +676,8 @@
 BOOST_AUTO_TEST_CASE(Delete)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
@@ -758,7 +771,8 @@
   addFace(face3);
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -788,7 +802,8 @@
 BOOST_AUTO_TEST_CASE(RemoveNoFace)
 {
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                           face);
@@ -818,7 +833,8 @@
   addFace(make_shared<DummyFace>());
 
   shared_ptr<InternalFace> face(make_shared<InternalFace>());
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   FibManager manager(fib,
                      bind(&FibManagerFixture::getFace, this, _1),
                      face);
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 1615876..0be6492 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -118,7 +118,8 @@
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
 
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   // ['/']
   
   entry = fib.findLongestPrefixMatch(nameA);
@@ -175,7 +176,8 @@
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
   
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   // {'/':[]}
   
   insertRes = fib.insert(nameA);
@@ -228,7 +230,8 @@
 
 BOOST_AUTO_TEST_CASE(FindExactMatch)
 {
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   fib.insert("/A");
   fib.insert("/A/B");
   fib.insert("/A/B/C");
@@ -240,20 +243,22 @@
 
   validateNoExactMatch(fib, "/does/not/exist");
 
-  Fib gapFib;
+  NameTree gapNameTree(1024);
+  Fib gapFib(nameTree);
   fib.insert("/X");
   fib.insert("/X/Y/Z");
 
   validateNoExactMatch(gapFib, "/X/Y");
 
-  Fib emptyFib;
+  NameTree emptyNameTree(1024);
+  Fib emptyFib(emptyNameTree);
   validateNoExactMatch(emptyFib, "/nothing/here");
 }
 
 void
 validateRemove(Fib& fib, const Name& target)
 {
-  fib.remove(target);
+  fib.erase(target);
 
   shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
   if (static_cast<bool>(entry))
@@ -264,15 +269,17 @@
 
 BOOST_AUTO_TEST_CASE(Remove)
 {
-  Fib emptyFib;
+  NameTree emptyNameTree(1024);
+  Fib emptyFib(emptyNameTree);
 
-  emptyFib.remove("/does/not/exist"); // crash test
+  emptyFib.erase("/does/not/exist"); // crash test
 
   validateRemove(emptyFib, "/");
 
-  emptyFib.remove("/still/does/not/exist"); // crash test
+  emptyFib.erase("/still/does/not/exist"); // crash test
 
-  Fib fib;
+  NameTree nameTree(1024);
+  Fib fib(nameTree);
   fib.insert("/A");
   fib.insert("/A/B");
   fib.insert("/A/B/C");
@@ -292,11 +299,12 @@
   validateRemove(fib, "/A");
   validateFindExactMatch(fib, "/");
 
-  Fib gapFib;
+  NameTree gapNameTree(1024);
+  Fib gapFib(gapNameTree);
   gapFib.insert("/X");
   gapFib.insert("/X/Y/Z");
 
-  gapFib.remove("/X/Y"); //should do nothing
+  gapFib.erase("/X/Y"); //should do nothing
   validateFindExactMatch(gapFib, "/X");
   validateFindExactMatch(gapFib, "/X/Y/Z");
 }