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");
 }