diff --git a/rib/face-entry.hpp b/rib/face-entry.hpp
new file mode 100644
index 0000000..88531f6
--- /dev/null
+++ b/rib/face-entry.hpp
@@ -0,0 +1,70 @@
+/* -*- 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
+ *
+ * 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_RIB_FACE_ENTRY_HPP
+#define NFD_RIB_FACE_ENTRY_HPP
+
+namespace nfd {
+namespace rib {
+
+/** \class FaceEntry
+ *  \brief represents a route for a name prefix
+ */
+class FaceEntry
+{
+public:
+  FaceEntry()
+    : faceId(0)
+    , origin(0)
+    , flags(0)
+    , cost(0)
+    , expires(time::steady_clock::TimePoint::min())
+  {
+  }
+
+public:
+  uint64_t faceId;
+  uint64_t origin;
+  uint64_t flags;
+  uint64_t cost;
+  time::steady_clock::TimePoint expires;
+};
+
+inline bool
+compareFaceIdAndOrigin(const FaceEntry& entry1, const FaceEntry& entry2)
+{
+  return (entry1.faceId == entry2.faceId && entry1.origin == entry2.origin);
+}
+
+inline bool
+compareFaceId(const FaceEntry& entry, const uint64_t faceId)
+{
+  return (entry.faceId == faceId);
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_ENTRY_HPP
diff --git a/rib/rib-entry.cpp b/rib/rib-entry.cpp
new file mode 100644
index 0000000..db72d37
--- /dev/null
+++ b/rib/rib-entry.cpp
@@ -0,0 +1,131 @@
+/* -*- 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
+ *
+ * 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 "rib-entry.hpp"
+
+#include <ndn-cxx/management/nfd-control-command.hpp>
+
+namespace nfd {
+namespace rib {
+
+RibEntry::FaceList::iterator
+RibEntry::findFace(const FaceEntry& face)
+{
+  return std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, face));
+}
+
+bool
+RibEntry::insertFace(const FaceEntry& entry)
+{
+  iterator it = findFace(entry);
+
+  if (it == end())
+    {
+      m_faces.push_back(entry);
+      return true;
+    }
+  else
+    {
+      return false;
+    }
+}
+
+bool
+RibEntry::eraseFace(const FaceEntry& face)
+{
+  RibEntry::iterator it = std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, face));
+  if (it != m_faces.end())
+    {
+      m_faces.erase(it);
+      return true;
+    }
+  else
+    {
+      return false;
+    }
+}
+
+bool
+RibEntry::hasFaceId(const uint64_t faceId) const
+{
+  RibEntry::const_iterator it = std::find_if(cbegin(), cend(), bind(&compareFaceId, _1, faceId));
+
+  return (it != cend());
+}
+
+void
+RibEntry::addChild(shared_ptr<RibEntry> child)
+{
+  BOOST_ASSERT(!static_cast<bool>(child->getParent()));
+  child->setParent(this->shared_from_this());
+  m_children.push_back(child);
+}
+
+void
+RibEntry::removeChild(shared_ptr<RibEntry> child)
+{
+  BOOST_ASSERT(child->getParent().get() == this);
+  child->setParent(shared_ptr<RibEntry>());
+  m_children.remove(child);
+}
+
+RibEntry::FaceList::iterator
+RibEntry::eraseFace(FaceList::iterator face)
+{
+  return m_faces.erase(face);
+}
+
+std::ostream&
+operator<<(std::ostream& os, const FaceEntry& entry)
+{
+  os << "FaceEntry("
+     << " faceid: " << entry.faceId
+     << " origin: " << entry.origin
+     << " cost: " << entry.cost
+     << " flags: " << entry.flags
+     << " expires in: " << (entry.expires - time::steady_clock::now())
+     << ")";
+
+  return os;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const RibEntry& entry)
+{
+  os << "RibEntry{\n";
+  os << "\tName:  " << entry.getName() << "\n";
+
+  for (RibEntry::FaceList::const_iterator faceIt = entry.cbegin(); faceIt != entry.cend(); ++faceIt)
+    {
+      os << "\t" << (*faceIt) << "\n";
+    }
+
+  os << "}";
+
+  return os;
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/rib-entry.hpp b/rib/rib-entry.hpp
new file mode 100644
index 0000000..4726a04
--- /dev/null
+++ b/rib/rib-entry.hpp
@@ -0,0 +1,188 @@
+/* -*- 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
+ *
+ * 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_RIB_RIB_ENTRY_HPP
+#define NFD_RIB_RIB_ENTRY_HPP
+
+#include "face-entry.hpp"
+
+namespace nfd {
+namespace rib {
+
+/** \class RibEntry
+ *  \brief represents a namespace
+ */
+class RibEntry : public enable_shared_from_this<RibEntry>
+{
+public:
+  typedef std::list<FaceEntry> FaceList;
+  typedef FaceList::iterator iterator;
+  typedef FaceList::const_iterator const_iterator;
+
+  RibEntry()
+  {
+  }
+
+  void
+  setName(const Name& prefix);
+
+  const Name&
+  getName() const;
+
+  shared_ptr<RibEntry>
+  getParent() const;
+
+  bool
+  hasParent() const;
+
+  void
+  addChild(shared_ptr<RibEntry> child);
+
+  void
+  removeChild(shared_ptr<RibEntry> child);
+
+  std::list<shared_ptr<RibEntry> >&
+  getChildren();
+
+  bool
+  hasChildren() const;
+
+  /** \brief inserts a new face into the entry's face list
+   *  If another entry already exists with the same faceId and origin,
+   *  the new face is not inserted.
+   *  \return{ true if the face is inserted, false otherwise }
+   */
+  bool
+  insertFace(const FaceEntry& face);
+
+  /** \brief erases a FaceEntry with the same faceId and origin
+   *  \return{ true if the face is removed, false otherwise }
+   */
+  bool
+  eraseFace(const FaceEntry& face);
+
+  /** \brief erases a FaceEntry with the passed iterator
+   *  \return{ an iterator to the element that followed the erased iterator }
+   */
+  iterator
+  eraseFace(FaceList::iterator face);
+
+  bool
+  hasFaceId(const uint64_t faceId) const;
+
+  FaceList&
+  getFaces();
+
+  iterator
+  findFace(const FaceEntry& face);
+
+  const_iterator
+  cbegin() const;
+
+  const_iterator
+  cend() const;
+
+  iterator
+  begin();
+
+  iterator
+  end();
+
+private:
+  void
+  setParent(shared_ptr<RibEntry> parent);
+
+private:
+  Name m_name;
+  std::list<shared_ptr<RibEntry> > m_children;
+  shared_ptr<RibEntry> m_parent;
+  FaceList m_faces;
+  FaceList m_inheritedFaces;
+};
+
+inline void
+RibEntry::setName(const Name& prefix)
+{
+  m_name = prefix;
+}
+
+inline const Name&
+RibEntry::getName() const
+{
+  return m_name;
+}
+
+inline void
+RibEntry::setParent(shared_ptr<RibEntry> parent)
+{
+  m_parent = parent;
+}
+
+inline shared_ptr<RibEntry>
+RibEntry::getParent() const
+{
+  return m_parent;
+}
+
+inline std::list<shared_ptr<RibEntry> >&
+RibEntry::getChildren()
+{
+  return m_children;
+}
+
+inline RibEntry::FaceList&
+RibEntry::getFaces()
+{
+  return m_faces;
+}
+
+inline RibEntry::const_iterator
+RibEntry::cbegin() const
+{
+  return m_faces.begin();
+}
+
+inline RibEntry::const_iterator
+RibEntry::cend() const
+{
+  return m_faces.end();
+}
+
+inline RibEntry::iterator
+RibEntry::begin()
+{
+  return m_faces.begin();
+}
+
+inline RibEntry::iterator
+RibEntry::end()
+{
+  return m_faces.end();
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_ENTRY_HPP
diff --git a/rib/rib-manager.cpp b/rib/rib-manager.cpp
index a84d7f6..b89b619 100644
--- a/rib/rib-manager.cpp
+++ b/rib/rib-manager.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-manager.hpp"
 #include "core/global-io.hpp"
@@ -216,28 +216,27 @@
       return;
     }
 
-  RibEntry ribEntry;
-  ribEntry.name = parameters.getName();
-  ribEntry.faceId = parameters.getFaceId();
-  ribEntry.origin = parameters.getOrigin();
-  ribEntry.cost = parameters.getCost();
-  ribEntry.flags = parameters.getFlags();
-  ribEntry.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
+  FaceEntry faceEntry;
+  faceEntry.faceId = parameters.getFaceId();
+  faceEntry.origin = parameters.getOrigin();
+  faceEntry.cost = parameters.getCost();
+  faceEntry.flags = parameters.getFlags();
+  faceEntry.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
 
-  NFD_LOG_TRACE("register prefix: " << ribEntry);
+  NFD_LOG_TRACE("register prefix: " << faceEntry);
 
-  // For right now, just pass the options to fib as it is,
-  // without processing flags. Later options will be first added to
-  // Rib tree, then nrd will generate fib updates based on flags and then
-  // will add next hops one by one..
-  m_managedRib.insert(ribEntry);
+  /// \todo For right now, just pass the options to fib as is
+  ///       without processing flags. Later, options will first be added to
+  ///       Rib tree, nrd will generate fib updates based on flags, and
+  ///       will then add next hops one by one.
+  m_managedRib.insert(parameters.getName(), faceEntry);
   m_nfdController.start<ndn::nfd::FibAddNextHopCommand>(
     ControlParameters()
-      .setName(ribEntry.name)
-      .setFaceId(ribEntry.faceId)
-      .setCost(ribEntry.cost),
-    bind(&RibManager::onRegSuccess, this, request, parameters, ribEntry),
-    bind(&RibManager::onCommandError, this, _1, _2, request, ribEntry));
+      .setName(parameters.getName())
+      .setFaceId(faceEntry.faceId)
+      .setCost(faceEntry.cost),
+    bind(&RibManager::onRegSuccess, this, request, parameters, faceEntry),
+    bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
 }
 
 void
@@ -253,19 +252,18 @@
       return;
     }
 
-  RibEntry ribEntry;
-  ribEntry.name = parameters.getName();
-  ribEntry.faceId = parameters.getFaceId();
-  ribEntry.origin = parameters.getOrigin();
+  FaceEntry faceEntry;
+  faceEntry.faceId = parameters.getFaceId();
+  faceEntry.origin = parameters.getOrigin();
 
-  NFD_LOG_TRACE("unregister prefix: " << ribEntry);
+  NFD_LOG_TRACE("unregister prefix: " << faceEntry);
 
   m_nfdController.start<ndn::nfd::FibRemoveNextHopCommand>(
     ControlParameters()
-      .setName(ribEntry.name)
-      .setFaceId(ribEntry.faceId),
-    bind(&RibManager::onUnRegSuccess, this, request, parameters, ribEntry),
-    bind(&RibManager::onCommandError, this, _1, _2, request, ribEntry));
+      .setName(parameters.getName())
+      .setFaceId(faceEntry.faceId),
+    bind(&RibManager::onUnRegSuccess, this, request, parameters, faceEntry),
+    bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
 }
 
 void
@@ -316,7 +314,7 @@
 void
 RibManager::onCommandError(uint32_t code, const std::string& error,
                            const shared_ptr<const Interest>& request,
-                           const RibEntry& ribEntry)
+                           const FaceEntry& faceEntry)
 {
   NFD_LOG_ERROR("NFD returned an error: " << error << " (code: " << code << ")");
 
@@ -336,13 +334,13 @@
     }
 
   sendResponse(request->getName(), response);
-  m_managedRib.erase(ribEntry);
+  m_managedRib.erase(request->getName(), faceEntry);
 }
 
 void
 RibManager::onRegSuccess(const shared_ptr<const Interest>& request,
                          const ControlParameters& parameters,
-                         const RibEntry& ribEntry)
+                         const FaceEntry& faceEntry)
 {
   ControlResponse response;
 
@@ -350,7 +348,7 @@
   response.setText("Success");
   response.setBody(parameters.wireEncode());
 
-  NFD_LOG_TRACE("onRegSuccess: registered " << ribEntry);
+  NFD_LOG_TRACE("onRegSuccess: registered " << faceEntry);
 
   sendResponse(request->getName(), response);
 }
@@ -359,7 +357,7 @@
 void
 RibManager::onUnRegSuccess(const shared_ptr<const Interest>& request,
                            const ControlParameters& parameters,
-                           const RibEntry& ribEntry)
+                           const FaceEntry& faceEntry)
 {
   ControlResponse response;
 
@@ -367,10 +365,10 @@
   response.setText("Success");
   response.setBody(parameters.wireEncode());
 
-  NFD_LOG_TRACE("onUnRegSuccess: unregistered " << ribEntry);
+  NFD_LOG_TRACE("onUnRegSuccess: unregistered " << faceEntry);
 
   sendResponse(request->getName(), response);
-  m_managedRib.erase(ribEntry);
+  m_managedRib.erase(request->getName(), faceEntry);
 }
 
 void
diff --git a/rib/rib-manager.hpp b/rib/rib-manager.hpp
index bcd43d7..7721436 100644
--- a/rib/rib-manager.hpp
+++ b/rib/rib-manager.hpp
@@ -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/>.
- **/
+ */
 
 #ifndef NFD_RIB_RIB_MANAGER_HPP
 #define NFD_RIB_RIB_MANAGER_HPP
@@ -110,17 +110,17 @@
   void
   onCommandError(uint32_t code, const std::string& error,
                  const shared_ptr<const Interest>& request,
-                 const RibEntry& ribEntry);
+                 const FaceEntry& faceEntry);
 
   void
   onRegSuccess(const shared_ptr<const Interest>& request,
                const ControlParameters& parameters,
-               const RibEntry& ribEntry);
+               const FaceEntry& faceEntry);
 
   void
   onUnRegSuccess(const shared_ptr<const Interest>& request,
                  const ControlParameters& parameters,
-                 const RibEntry& ribEntry);
+                 const FaceEntry& faceEntry);
 
   void
   onNrdCommandPrefixAddNextHopSuccess(const Name& prefix);
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;
 }
diff --git a/rib/rib.hpp b/rib/rib.hpp
index 7c19c9f..37136bc 100644
--- a/rib/rib.hpp
+++ b/rib/rib.hpp
@@ -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,61 +21,46 @@
  *
  * 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_RIB_RIB_HPP
 #define NFD_RIB_RIB_HPP
 
 #include "common.hpp"
+#include "rib-entry.hpp"
 #include <ndn-cxx/management/nfd-control-command.hpp>
 
 namespace nfd {
 namespace rib {
 
-class RibEntry
-{
-public:
-  RibEntry()
-    : faceId(0)
-    , origin(0)
-    , flags(0)
-    , cost(0)
-    , expires(time::steady_clock::TimePoint::min())
-  {
-  }
-
-public:
-  Name name;
-  uint64_t faceId;
-  uint64_t origin;
-  uint64_t flags;
-  uint64_t cost;
-  time::steady_clock::TimePoint expires;
-};
-
 /** \brief represents the RIB
  */
 class Rib : noncopyable
 {
 public:
-  typedef std::list<RibEntry> RibTable;
+  typedef std::list<shared_ptr<RibEntry> > RibEntryList;
+  typedef std::map<Name, shared_ptr<RibEntry> > RibTable;
   typedef RibTable::const_iterator const_iterator;
+  typedef std::map<uint64_t, std::list<shared_ptr<RibEntry> > > FaceLookupTable;
 
   Rib();
 
   ~Rib();
 
   const_iterator
-  find(const RibEntry& entry) const;
+  find(const Name& prefix) const;
+
+  shared_ptr<FaceEntry>
+  find(const Name& prefix, const FaceEntry& face) const;
 
   void
-  insert(const RibEntry& entry);
+  insert(const Name& prefix, const FaceEntry& face);
 
   void
-  erase(const RibEntry& entry);
+  erase(const Name& prefix, const FaceEntry& face);
 
   void
-  erase(uint64_t faceId);
+  erase(const uint64_t faceId);
 
   const_iterator
   begin() const;
@@ -86,13 +71,29 @@
   size_t
   size() const;
 
-  size_t
+  bool
   empty() const;
 
+
+  shared_ptr<RibEntry>
+  findParent(const Name& prefix) const;
+
+  /** \brief finds namespaces under the passed prefix
+   *  \return{ a list of entries which are under the passed prefix }
+   */
+  std::list<shared_ptr<RibEntry> >
+  findDescendants(const Name& prefix) const;
+
+  RibTable::iterator
+  eraseEntry(RibTable::iterator it);
+
+  void
+  eraseEntry(const Name& name);
+
 private:
-  // Note: Taking a list right now. A Trie will be used later to store
-  // prefixes
   RibTable m_rib;
+  FaceLookupTable m_faceMap;
+  size_t m_nItems;
 };
 
 inline Rib::const_iterator
@@ -110,18 +111,24 @@
 inline size_t
 Rib::size() const
 {
-  return m_rib.size();
+  return m_nItems;
 }
 
-inline size_t
+inline bool
 Rib::empty() const
 {
   return m_rib.empty();
 }
 
 std::ostream&
+operator<<(std::ostream& os, const FaceEntry& entry);
+
+std::ostream&
 operator<<(std::ostream& os, const RibEntry& entry);
 
+std::ostream&
+operator<<(std::ostream& os, const Rib& rib);
+
 } // namespace rib
 } // namespace nfd
 
diff --git a/tests/rib/rib.cpp b/tests/rib/rib.cpp
index a8a0110..c3b0eab 100644
--- a/tests/rib/rib.cpp
+++ b/tests/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/rib.hpp"
 
@@ -33,62 +33,296 @@
 
 BOOST_FIXTURE_TEST_SUITE(Rib, nfd::tests::BaseFixture)
 
+BOOST_AUTO_TEST_CASE(RibEntry)
+{
+  rib::RibEntry entry;
+
+  rib::FaceEntry face1;
+  face1.faceId = 1;
+  face1.origin = 0;
+
+  entry.insertFace(face1);
+  BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+  FaceEntry face2;
+  face2.faceId = 1;
+  face2.origin = 128;
+
+  entry.insertFace(face2);
+  BOOST_CHECK_EQUAL(entry.getFaces().size(), 2);
+
+  entry.eraseFace(face1);
+  BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+  BOOST_CHECK(entry.findFace(face1) == entry.getFaces().end());
+  BOOST_CHECK(entry.findFace(face2) != entry.getFaces().end());
+
+  entry.insertFace(face2);
+  BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+  BOOST_CHECK_EQUAL(entry.eraseFace(face1), false);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_Parent)
+{
+  rib::Rib rib;
+
+  FaceEntry root;
+  Name name1("/");
+  root.faceId = 1;
+  root.origin = 20;
+  rib.insert(name1, root);
+
+  FaceEntry entry1;
+  Name name2("/hello");
+  entry1.faceId = 2;
+  entry1.origin = 20;
+  rib.insert(name2, entry1);
+
+  FaceEntry entry2;
+  Name name3("/hello/world");
+  entry2.faceId = 3;
+  entry2.origin = 20;
+  rib.insert(name3, entry2);
+
+  shared_ptr<rib::RibEntry> ribEntry = rib.findParent(name3);
+  BOOST_REQUIRE(static_cast<bool>(ribEntry));
+  BOOST_CHECK_EQUAL(ribEntry->getFaces().front().faceId, 2);
+
+  ribEntry = rib.findParent(name2);
+  BOOST_REQUIRE(static_cast<bool>(ribEntry));
+  BOOST_CHECK_EQUAL(ribEntry->getFaces().front().faceId, 1);
+
+  FaceEntry entry3;
+  Name name4("/hello/test/foo/bar");
+  entry2.faceId = 3;
+  entry2.origin = 20;
+  rib.insert(name4, entry3);
+
+  ribEntry = rib.findParent(name4);
+  BOOST_CHECK(ribEntry != shared_ptr<rib::RibEntry>());
+  BOOST_CHECK(ribEntry->getFaces().front().faceId == 2);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_Children)
+{
+  rib::Rib rib;
+
+  FaceEntry entry1;
+  Name name1("/");
+  entry1.faceId = 1;
+  entry1.origin = 20;
+  rib.insert(name1, entry1);
+
+  FaceEntry entry2;
+  Name name2("/hello/world");
+  entry2.faceId = 2;
+  entry2.origin = 20;
+  rib.insert(name2, entry2);
+
+  FaceEntry entry3;
+  Name name3("/hello/test/foo/bar");
+  entry3.faceId = 3;
+  entry3.origin = 20;
+  rib.insert(name3, entry3);
+
+  BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().size(), 2);
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getChildren().size(), 0);
+  BOOST_CHECK_EQUAL((rib.find(name3)->second)->getChildren().size(), 0);
+
+  FaceEntry entry4;
+  Name name4("/hello");
+  entry4.faceId = 4;
+  entry4.origin = 20;
+  rib.insert(name4, entry4);
+
+  BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().size(), 1);
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getChildren().size(), 0);
+  BOOST_CHECK_EQUAL((rib.find(name3)->second)->getChildren().size(), 0);
+  BOOST_CHECK_EQUAL((rib.find(name4)->second)->getChildren().size(), 2);
+
+  BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().front()->getName(), "/hello");
+  BOOST_CHECK_EQUAL((rib.find(name4)->second)->getParent()->getName(), "/");
+
+  BOOST_REQUIRE(static_cast<bool>((rib.find(name2)->second)->getParent()));
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getParent()->getName(), name4);
+  BOOST_REQUIRE(static_cast<bool>((rib.find(name3)->second)->getParent()));
+  BOOST_CHECK_EQUAL((rib.find(name3)->second)->getParent()->getName(), name4);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseFace)
+{
+  rib::Rib rib;
+
+  FaceEntry entry1;
+  Name name1("/");
+  entry1.faceId = 1;
+  entry1.origin = 20;
+  rib.insert(name1, entry1);
+
+  FaceEntry entry2;
+  Name name2("/hello/world");
+  entry2.faceId = 2;
+  entry2.origin = 20;
+  rib.insert(name2, entry2);
+
+  FaceEntry entry3;
+  Name name3("/hello/world");
+  entry3.faceId = 1;
+  entry3.origin = 20;
+  rib.insert(name3, entry3);
+
+  FaceEntry entry4;
+  Name name4("/not/inserted");
+  entry4.faceId = 1;
+  entry4.origin = 20;
+
+  rib.erase(name4, entry4);
+  rib.erase(name1, entry1);
+
+  BOOST_CHECK(rib.find(name1) == rib.end());
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 2);
+
+  rib.erase(name2, entry2);
+
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().front().faceId, 1);
+
+  rib.erase(name3, entry3);
+
+  BOOST_CHECK(rib.find(name2) == rib.end());
+
+  rib.erase(name4, entry4);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseRibEntry)
+{
+  rib::Rib rib;
+
+  FaceEntry entry1;
+  Name name1("/");
+  entry1.faceId = 1;
+  entry1.origin = 20;
+  rib.insert(name1, entry1);
+
+  FaceEntry entry2;
+  Name name2("/hello");
+  entry2.faceId = 2;
+  entry2.origin = 20;
+  rib.insert(name2, entry2);
+
+  FaceEntry entry3;
+  Name name3("/hello/world");
+  entry3.faceId = 1;
+  entry3.origin = 20;
+  rib.insert(name3, entry3);
+
+  shared_ptr<rib::RibEntry> ribEntry1 = rib.find(name1)->second;
+  shared_ptr<rib::RibEntry> ribEntry2 = rib.find(name2)->second;
+  shared_ptr<rib::RibEntry> ribEntry3 = rib.find(name3)->second;
+
+  BOOST_CHECK(ribEntry1->getChildren().front() == ribEntry2);
+  BOOST_CHECK(ribEntry3->getParent() == ribEntry2);
+
+  rib.erase(name2, entry2);
+  BOOST_CHECK(ribEntry1->getChildren().front() == ribEntry3);
+  BOOST_CHECK(ribEntry3->getParent() == ribEntry1);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseByFaceId)
+{
+  rib::Rib rib;
+
+  FaceEntry entry1;
+  Name name1("/");
+  entry1.faceId = 1;
+  entry1.origin = 20;
+  rib.insert(name1, entry1);
+
+  FaceEntry entry2;
+  Name name2("/hello/world");
+  entry2.faceId = 2;
+  entry2.origin = 20;
+  rib.insert(name2, entry2);
+
+  FaceEntry entry3;
+  Name name3("/hello/world");
+  entry3.faceId = 1;
+  entry3.origin = 20;
+  rib.insert(name3, entry3);
+
+  rib.erase(1);
+  BOOST_CHECK(rib.find(name1) == rib.end());
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+
+  rib.erase(3);
+  BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+
+  rib.erase(2);
+  BOOST_CHECK(rib.find(name2) == rib.end());
+
+  rib.erase(3);
+}
+
 BOOST_AUTO_TEST_CASE(Basic)
 {
   rib::Rib rib;
 
-  RibEntry entry1;
-  entry1.name = "/hello/world";
+  FaceEntry entry1;
+  Name name1("/hello/world");
   entry1.faceId = 1;
   entry1.origin = 20;
   entry1.cost = 10;
   entry1.flags = ndn::nfd::ROUTE_FLAG_CHILD_INHERIT | ndn::nfd::ROUTE_FLAG_CAPTURE;
   entry1.expires = time::steady_clock::now() + time::milliseconds(1500);
 
-  rib.insert(entry1);
+  rib.insert(name1, entry1);
   BOOST_CHECK_EQUAL(rib.size(), 1);
 
-  rib.insert(entry1);
+  rib.insert(name1, entry1);
   BOOST_CHECK_EQUAL(rib.size(), 1);
 
-  RibEntry entry2;
-  entry2.name = "/hello/world";
+  FaceEntry entry2;
+  Name name2("/hello/world");
   entry2.faceId = 1;
   entry2.origin = 20;
   entry2.cost = 100;
   entry2.flags = ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
   entry2.expires = time::steady_clock::now() + time::seconds(0);
 
-  rib.insert(entry2);
+  rib.insert(name2, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 1);
 
   entry2.faceId = 2;
-  rib.insert(entry2);
+  rib.insert(name2, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 2);
 
-  entry2.name = "/foo/bar";
-  rib.insert(entry2);
+  BOOST_CHECK(rib.find(name1)->second->hasFaceId(entry1.faceId));
+  BOOST_CHECK(rib.find(name1)->second->hasFaceId(entry2.faceId));
+
+  Name name3("/foo/bar");
+  rib.insert(name3, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 3);
 
   entry2.origin = 1;
-  rib.insert(entry2);
+  rib.insert(name3, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 4);
 
-  rib.erase(entry2);
+  rib.erase(name3, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 3);
 
-  entry2.name = "/hello/world";
-  rib.erase(entry2);
+  Name name4("/hello/world");
+  rib.erase(name4, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 3);
 
   entry2.origin = 20;
-  rib.erase(entry2);
+  rib.erase(name4, entry2);
   BOOST_CHECK_EQUAL(rib.size(), 2);
 
-  BOOST_CHECK(rib.find(entry2) == rib.end());
-  BOOST_CHECK(rib.find(entry1) != rib.end());
+  BOOST_CHECK(rib.find(name2, entry2) == shared_ptr<rib::FaceEntry>());
+  BOOST_CHECK(rib.find(name1, entry1) != shared_ptr<rib::FaceEntry>());
 
-  rib.erase(entry1);
+  rib.erase(name1, entry1);
   BOOST_CHECK_EQUAL(rib.size(), 1);
 }