diff --git a/daemon/table/cleanup.cpp b/daemon/table/cleanup.cpp
index 104bdf1..5a45bf7 100644
--- a/daemon/table/cleanup.cpp
+++ b/daemon/table/cleanup.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016,  Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -36,7 +36,7 @@
   for (const name_tree::Entry& nte : nt) {
     fib::Entry* fibEntry = nte.getFibEntry();
     if (fibEntry != nullptr) {
-      fib.removeNextHop(*fibEntry, face);
+      fib.removeNextHopByFace(*fibEntry, face);
     }
 
     for (const auto& pitEntry : nte.getPitEntries()) {
diff --git a/daemon/table/fib-entry.cpp b/daemon/table/fib-entry.cpp
index c2e299f..cf14936 100644
--- a/daemon/table/fib-entry.cpp
+++ b/daemon/table/fib-entry.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016,  Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -35,43 +35,52 @@
 }
 
 NextHopList::iterator
-Entry::findNextHop(const Face& face)
+Entry::findNextHop(const Face& face, uint64_t endpointId)
 {
   return std::find_if(m_nextHops.begin(), m_nextHops.end(),
-                      [&face] (const NextHop& nexthop) {
-                        return &nexthop.getFace() == &face;
+                      [&face, endpointId] (const NextHop& nexthop) {
+                        return &nexthop.getFace() == &face && nexthop.getEndpointId() == endpointId;
                       });
 }
 
 bool
-Entry::hasNextHop(const Face& face) const
+Entry::hasNextHop(const Face& face, uint64_t endpointId) const
 {
-  return const_cast<Entry*>(this)->findNextHop(face) != m_nextHops.end();
+  return const_cast<Entry*>(this)->findNextHop(face, endpointId) != m_nextHops.end();
 }
 
 void
-Entry::addNextHop(Face& face, uint64_t cost)
+Entry::addOrUpdateNextHop(Face& face, uint64_t endpointId, uint64_t cost)
 {
-  auto it = this->findNextHop(face);
+  auto it = this->findNextHop(face, endpointId);
   if (it == m_nextHops.end()) {
-    m_nextHops.emplace_back(face);
+    m_nextHops.emplace_back(face, endpointId);
     it = std::prev(m_nextHops.end());
   }
-
   it->setCost(cost);
   this->sortNextHops();
 }
 
 void
-Entry::removeNextHop(const Face& face)
+Entry::removeNextHop(const Face& face, uint64_t endpointId)
 {
-  auto it = this->findNextHop(face);
+  auto it = this->findNextHop(face, endpointId);
   if (it != m_nextHops.end()) {
     m_nextHops.erase(it);
   }
 }
 
 void
+Entry::removeNextHopByFace(const Face& face)
+{
+  auto it = std::remove_if(m_nextHops.begin(), m_nextHops.end(),
+                           [&face] (const NextHop& nexthop) {
+                             return &nexthop.getFace() == &face;
+                           });
+  m_nextHops.erase(it, m_nextHops.end());
+}
+
+void
 Entry::sortNextHops()
 {
   std::sort(m_nextHops.begin(), m_nextHops.end(),
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index 24489b9..2b86f66 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2018,  Regents of the University of California,
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -74,32 +74,36 @@
     return !m_nextHops.empty();
   }
 
-  /** \return whether there is a NextHop record for \p face
+  /** \return whether there is a NextHop record for \p face with the given \p endpointId
    */
   bool
-  hasNextHop(const Face& face) const;
+  hasNextHop(const Face& face, uint64_t endpointId) const;
 
   /** \brief adds a NextHop record
    *
-   *  If a NextHop record for \p face already exists, its cost is updated.
+   *  If a NextHop record for \p face and \p endpointId already exists,
+   *  its cost is updated.
    */
   void
-  addNextHop(Face& face, uint64_t cost);
+  addOrUpdateNextHop(Face& face, uint64_t endpointId, uint64_t cost);
 
-  /** \brief removes a NextHop record
-   *
-   *  If no NextHop record for face exists, do nothing.
+  /** \brief removes the NextHop record for \p face with the given \p endpointId
    */
   void
-  removeNextHop(const Face& face);
+  removeNextHop(const Face& face, uint64_t endpointId);
+
+  /** \brief removes all NextHop records on \p face for any \p endpointId
+   */
+  void
+  removeNextHopByFace(const Face& face);
 
 private:
   /** \note This method is non-const because mutable iterators are needed by callers.
    */
   NextHopList::iterator
-  findNextHop(const Face& face);
+  findNextHop(const Face& face, uint64_t endpointId);
 
-  /** \brief sorts the nexthop list
+  /** \brief sorts the nexthop list by cost
    */
   void
   sortNextHops();
diff --git a/daemon/table/fib-nexthop.cpp b/daemon/table/fib-nexthop.cpp
index e554362..e456c15 100644
--- a/daemon/table/fib-nexthop.cpp
+++ b/daemon/table/fib-nexthop.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016,  Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -28,8 +28,9 @@
 namespace nfd {
 namespace fib {
 
-NextHop::NextHop(Face& face)
+NextHop::NextHop(Face& face, uint64_t endpointId)
   : m_face(&face)
+  , m_endpointId(endpointId)
   , m_cost(0)
 {
 }
diff --git a/daemon/table/fib-nexthop.hpp b/daemon/table/fib-nexthop.hpp
index 83b774f..313508d 100644
--- a/daemon/table/fib-nexthop.hpp
+++ b/daemon/table/fib-nexthop.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016,  Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -39,7 +39,7 @@
 {
 public:
   explicit
-  NextHop(Face& face);
+  NextHop(Face& face, uint64_t endpointId);
 
   Face&
   getFace() const
@@ -48,6 +48,12 @@
   }
 
   uint64_t
+  getEndpointId() const
+  {
+    return m_endpointId;
+  }
+
+  uint64_t
   getCost() const
   {
     return m_cost;
@@ -61,6 +67,7 @@
 
 private:
   Face* m_face;
+  uint64_t m_endpointId;
   uint64_t m_cost;
 };
 
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 7b6d21a..ccde921 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2018,  Regents of the University of California,
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -134,16 +134,28 @@
 }
 
 void
-Fib::removeNextHop(Entry& entry, const Face& face)
+Fib::eraseIfEmpty(Entry& entry)
 {
-  entry.removeNextHop(face);
-
   if (!entry.hasNextHops()) {
     name_tree::Entry* nte = m_nameTree.getEntry(entry);
     this->erase(nte, false);
   }
 }
 
+void
+Fib::removeNextHop(Entry& entry, const Face& face, uint64_t endpointId)
+{
+  entry.removeNextHop(face, endpointId);
+  this->eraseIfEmpty(entry);
+}
+
+void
+Fib::removeNextHopByFace(Entry& entry, const Face& face)
+{
+  entry.removeNextHopByFace(face);
+  this->eraseIfEmpty(entry);
+}
+
 Fib::Range
 Fib::getRange() const
 {
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 4b94c21..cfdc4f1 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2014-2018,  Regents of the University of California,
+ * Copyright (c) 2014-2019,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -105,10 +105,15 @@
   void
   erase(const Entry& entry);
 
-  /** \brief removes the NextHop record for face
+  /** \brief removes the NextHop record for \p face with a given \p endpointId
    */
   void
-  removeNextHop(Entry& entry, const Face& face);
+  removeNextHop(Entry& entry, const Face& face, uint64_t endpointId);
+
+  /** \brief removes the NextHop record for \p face for any \p endpointId
+   */
+  void
+  removeNextHopByFace(Entry& entry, const Face& face);
 
 public: // enumeration
   typedef boost::transformed_range<name_tree::GetTableEntry<Entry>, const name_tree::Range> Range;
@@ -144,6 +149,11 @@
   void
   erase(name_tree::Entry* nte, bool canDeleteNte = true);
 
+  /** \brief erase \p entry if it contains no nexthop record
+   */
+  void
+  eraseIfEmpty(Entry& entry);
+
   Range
   getRange() const;