diff --git a/rib/rib.cpp b/rib/rib.cpp
index 4dc4175..f47d840 100644
--- a/rib/rib.cpp
+++ b/rib/rib.cpp
@@ -1,12 +1,12 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014  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
+ * Copyright (c) 2014,  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.
@@ -21,7 +21,7 @@
  *
  * 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 "rib.hpp"
 
@@ -29,6 +29,7 @@
 namespace rib {
 
 Rib::Rib()
+  : m_nItems(0)
 {
 }
 
@@ -37,84 +38,270 @@
 {
 }
 
-static inline bool
-compareNameFaceProtocol(const RibEntry& entry1, const RibEntry& entry2)
-{
-  return (entry1.name == entry2.name &&
-          entry1.faceId == entry2.faceId &&
-          entry1.origin == entry2.origin);
-}
-
-
 Rib::const_iterator
-Rib::find(const RibEntry& entry) const
+Rib::find(const Name& prefix) const
 {
-  RibTable::const_iterator it = std::find_if(m_rib.begin(), m_rib.end(),
-                                             bind(&compareNameFaceProtocol, _1, entry));
-  if (it == m_rib.end())
+  return m_rib.find(prefix);
+}
+
+shared_ptr<FaceEntry>
+Rib::find(const Name& prefix, const FaceEntry& face) const
+{
+  RibTable::const_iterator ribIt = m_rib.find(prefix);
+
+  // Name prefix exists
+  if (ribIt != m_rib.end())
     {
-      return end();
+      shared_ptr<RibEntry> entry(ribIt->second);
+
+      RibEntry::const_iterator faceIt = std::find_if(entry->begin(), entry->end(),
+                                                     bind(&compareFaceIdAndOrigin, _1, face));
+
+      if (faceIt != entry->end())
+        {
+          return make_shared<FaceEntry>(*faceIt);
+        }
     }
-  else
-    return it;
+
+  return shared_ptr<FaceEntry>();
 }
 
 
 void
-Rib::insert(const RibEntry& entry)
+Rib::insert(const Name& prefix, const FaceEntry& face)
 {
-  RibTable::iterator it = std::find_if(m_rib.begin(), m_rib.end(),
-                                       bind(&compareNameFaceProtocol, _1, entry));
-  if (it == m_rib.end())
+  RibTable::iterator ribIt = m_rib.find(prefix);
+
+  // Name prefix exists
+  if (ribIt != m_rib.end())
     {
-      m_rib.push_front(entry);
+      shared_ptr<RibEntry> entry(ribIt->second);
+
+      RibEntry::iterator faceIt = std::find_if(entry->getFaces().begin(),
+                                               entry->getFaces().end(),
+                                               bind(&compareFaceIdAndOrigin, _1, face));
+
+      if (faceIt == entry->end())
+        {
+          // New face
+          entry->insertFace(face);
+          m_nItems++;
+
+          // Register with face lookup table
+          m_faceMap[face.faceId].push_back(entry);
+        }
+      else
+        {
+          // Entry exists, update other fields
+          faceIt->flags = face.flags;
+          faceIt->cost = face.cost;
+          faceIt->expires = face.expires;
+        }
     }
-  else
+  else // New name prefix
     {
-      // entry exist, update other fields
-      it->flags = entry.flags;
-      it->cost = entry.cost;
-      it->expires = entry.expires;
+      shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));
+
+      m_rib[prefix] = entry;
+      m_nItems++;
+
+      entry->setName(prefix);
+      entry->insertFace(face);
+
+      // Find prefix's parent
+      shared_ptr<RibEntry> parent = findParent(prefix);
+
+      // Add self to parent's children
+      if (static_cast<bool>(parent))
+        {
+          parent->addChild(entry);
+        }
+
+      RibEntryList children = findDescendants(prefix);
+
+      for (std::list<shared_ptr<RibEntry> >::iterator child = children.begin();
+           child != children.end(); ++child)
+        {
+          if ((*child)->getParent() == parent)
+            {
+              // Remove child from parent and inherit parent's child
+              if (static_cast<bool>(parent))
+                {
+                  parent->removeChild((*child));
+                }
+
+              entry->addChild((*child));
+            }
+        }
+
+      // Register with face lookup table
+      m_faceMap[face.faceId].push_back(entry);
     }
 }
 
 
 void
-Rib::erase(const RibEntry& entry)
+Rib::erase(const Name& prefix, const FaceEntry& face)
 {
-  RibTable::iterator it = std::find_if(m_rib.begin(), m_rib.end(),
-                                       bind(&compareNameFaceProtocol, _1, entry));
+  RibTable::iterator ribIt = m_rib.find(prefix);
+
+  // Name prefix exists
+  if (ribIt != m_rib.end())
+    {
+      shared_ptr<RibEntry> entry(ribIt->second);
+
+      if (entry->eraseFace(face))
+        {
+          m_nItems--;
+
+          // If this RibEntry no longer has this faceId, unregister from face lookup table
+          if (!entry->hasFaceId(face.faceId))
+            {
+              m_faceMap[face.faceId].remove(entry);
+            }
+
+          // If a RibEntry's facelist is empty, remove it from the tree
+          if (entry->getFaces().size() == 0)
+            {
+              eraseEntry(ribIt);
+            }
+        }
+    }
+}
+
+void
+Rib::erase(const uint64_t faceId)
+{
+  FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
+
+  // No RIB entries have this face
+  if (lookupIt == m_faceMap.end())
+    {
+      return;
+    }
+
+  RibEntryList& ribEntries = lookupIt->second;
+
+  // For each RIB entry that has faceId, remove the face from the entry
+  for (RibEntryList::iterator entryIt = ribEntries.begin(); entryIt != ribEntries.end(); ++entryIt)
+    {
+      shared_ptr<RibEntry> entry = *entryIt;
+
+      // Find the faces in the entry
+      for (RibEntry::iterator faceIt = entry->begin(); faceIt != entry->end(); ++faceIt)
+        {
+          if (faceIt->faceId == faceId)
+            {
+              faceIt = entry->eraseFace(faceIt);
+            }
+        }
+
+        // If a RibEntry's facelist is empty, remove it from the tree
+        if (entry->getFaces().size() == 0)
+          {
+            eraseEntry(m_rib.find(entry->getName()));
+          }
+    }
+
+  // Face no longer exists, remove from face lookup table
+  FaceLookupTable::iterator entryToDelete = m_faceMap.find(faceId);
+
+  if (entryToDelete != m_faceMap.end())
+    {
+      m_faceMap.erase(entryToDelete);
+    }
+}
+
+shared_ptr<RibEntry>
+Rib::findParent(const Name& prefix) const
+{
+  for (int i = prefix.size() - 1; i >= 0; i--)
+    {
+      RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
+      if (it != m_rib.end())
+        {
+          return (it->second);
+        }
+    }
+
+  return shared_ptr<RibEntry>();
+}
+
+std::list<shared_ptr<RibEntry> >
+Rib::findDescendants(const Name& prefix) const
+{
+  std::list<shared_ptr<RibEntry> > children;
+
+  RibTable::const_iterator it = m_rib.find(prefix);
+
   if (it != m_rib.end())
     {
-      m_rib.erase(it);
+      ++it;
+      for (; it != m_rib.end(); ++it)
+        {
+          if (prefix.isPrefixOf(it->first))
+            {
+              children.push_back((it->second));
+            }
+          else
+            {
+              break;
+            }
+        }
     }
+
+  return children;
 }
 
-void
-Rib::erase(uint64_t faceId)
+Rib::RibTable::iterator
+Rib::eraseEntry(RibTable::iterator it)
 {
-  // Keep it simple for now, with Trie this will be changed.
-  RibTable::iterator it = m_rib.begin();
-  while (it != m_rib.end())
-  {
-    if (it->faceId == faceId)
-      it = m_rib.erase(it);
-    else
-      ++it;
-  }
+  // Entry does not exist
+  if (it == m_rib.end())
+    {
+      return m_rib.end();
+    }
+
+  shared_ptr<RibEntry> entry(it->second);
+
+  shared_ptr<RibEntry> parent = entry->getParent();
+
+  // Remove self from parent's children
+  if (static_cast<bool>(parent))
+    {
+      parent->removeChild(entry);
+    }
+
+  std::list<shared_ptr<RibEntry> > children = entry->getChildren();
+
+  for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
+    {
+      // Remove children from self
+      entry->removeChild(*child);
+
+      // Update parent's children
+      if (static_cast<bool>(parent))
+        {
+          parent->addChild(*child);
+        }
+    }
+
+  // Must save and advance iterator to return a valid iterator
+  RibTable::iterator nextIt = it;
+  nextIt++;
+
+  m_rib.erase(it);
+
+  return nextIt;
 }
 
 std::ostream&
-operator<<(std::ostream& os, const RibEntry& entry)
+operator<<(std::ostream& os, const Rib& rib)
 {
-  os << "RibEntry("
-     << "name: " << entry.name
-     << " faceid: " << entry.faceId
-     << " origin: " << entry.origin
-     << " cost: " << entry.cost
-     << " flags: " << entry.flags
-     << " expires in: " << (entry.expires - time::steady_clock::now())
-     << ")";
+  for (Rib::RibTable::const_iterator it = rib.begin(); it != rib.end(); ++it)
+    {
+      os << *(it->second) << "\n";
+    }
 
   return os;
 }