diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index 48b09d6..5c80b7e 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -30,7 +30,7 @@
 /** \class Entry
  *  \brief represents a FIB entry
  */
-class Entry : public StrategyInfoHost, noncopyable
+class Entry : noncopyable
 {
 public:
   explicit
diff --git a/daemon/table/fib-nexthop.hpp b/daemon/table/fib-nexthop.hpp
index 4dc2b65..72fa687 100644
--- a/daemon/table/fib-nexthop.hpp
+++ b/daemon/table/fib-nexthop.hpp
@@ -9,7 +9,6 @@
 
 #include "common.hpp"
 #include "face/face.hpp"
-#include "strategy-info-host.hpp"
 
 namespace nfd {
 namespace fib {
@@ -17,20 +16,20 @@
 /** \class NextHop
  *  \brief represents a nexthop record in FIB entry
  */
-class NextHop : public StrategyInfoHost
+class NextHop
 {
 public:
   explicit
   NextHop(shared_ptr<Face> face);
-  
+
   NextHop(const NextHop& other);
-  
+
   shared_ptr<Face>
   getFace() const;
-  
+
   void
   setCost(uint32_t cost);
-  
+
   uint32_t
   getCost() const;
 
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index 5661961..b411f79 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -94,6 +94,9 @@
   std::vector<shared_ptr<pit::Entry> >&
   getPitEntries();
 
+  const std::vector<shared_ptr<pit::Entry> >&
+  getPitEntries() const;
+
   /**
    * \brief Erase a PIT Entry
    * \details The address of this PIT Entry is required
@@ -184,6 +187,12 @@
   return m_pitEntries;
 }
 
+inline const std::vector<shared_ptr<pit::Entry> >&
+Entry::getPitEntries() const
+{
+  return m_pitEntries;
+}
+
 inline shared_ptr<measurements::Entry>
 Entry::getMeasurementsEntry() const
 {
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index 9ce2c99..db4d498 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -94,11 +94,12 @@
   }
 
   Strategy& oldStrategy = entry->getStrategy();
+
+  Strategy& parentStrategy = this->findEffectiveStrategy(prefix.getPrefix(-1));
+  this->changeStrategy(entry, oldStrategy.shared_from_this(), parentStrategy.shared_from_this());
+
   nameTreeEntry->setStrategyChoiceEntry(shared_ptr<Entry>());
   --m_nItems;
-
-  Strategy& parentStrategy = this->findEffectiveStrategy(prefix);
-  this->changeStrategy(entry, oldStrategy.shared_from_this(), parentStrategy.shared_from_this());
 }
 
 shared_ptr<const Name>
@@ -138,7 +139,7 @@
   shared_ptr<strategy_choice::Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
   if (static_cast<bool>(entry))
     return entry->getStrategy();
-  nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry, 
+  nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
                                &predicate_NameTreeEntry_hasStrategyChoiceEntry);
   BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
   return nameTreeEntry->getStrategyChoiceEntry()->getStrategy();
@@ -187,6 +188,52 @@
   entry->setStrategy(strategy);
 }
 
+/** \brief a predicate that decides whether StrategyInfo should be reset
+ *
+ *  StrategyInfo on a NameTree entry needs to be reset,
+ *  if its effective strategy is covered by the changing StrategyChoice entry.
+ */
+static inline std::pair<bool,bool>
+predicate_nameTreeEntry_needResetStrategyChoice(const name_tree::Entry& nameTreeEntry,
+                                            const name_tree::Entry& rootEntry)
+{
+  if (&nameTreeEntry == &rootEntry) {
+    return std::make_pair(true, true);
+  }
+  if (static_cast<bool>(nameTreeEntry.getStrategyChoiceEntry())) {
+    return std::make_pair(false, false);
+  }
+  return std::make_pair(true, true);
+}
+
+static inline void
+clearStrategyInfo_pitFaceRecord(const pit::FaceRecord& pitFaceRecord)
+{
+  const_cast<pit::FaceRecord&>(pitFaceRecord).clearStrategyInfo();
+}
+
+static inline void
+clearStrategyInfo_pitEntry(shared_ptr<pit::Entry> pitEntry)
+{
+  pitEntry->clearStrategyInfo();
+  std::for_each(pitEntry->getInRecords().begin(), pitEntry->getInRecords().end(),
+                &clearStrategyInfo_pitFaceRecord);
+  std::for_each(pitEntry->getOutRecords().begin(), pitEntry->getOutRecords().end(),
+                &clearStrategyInfo_pitFaceRecord);
+}
+
+static inline void
+clearStrategyInfo(const name_tree::Entry& nameTreeEntry)
+{
+  NFD_LOG_TRACE("clearStrategyInfo " << nameTreeEntry.getPrefix());
+
+  std::for_each(nameTreeEntry.getPitEntries().begin(), nameTreeEntry.getPitEntries().end(),
+                &clearStrategyInfo_pitEntry);
+  if (static_cast<bool>(nameTreeEntry.getMeasurementsEntry())) {
+    nameTreeEntry.getMeasurementsEntry()->clearStrategyInfo();
+  }
+}
+
 void
 StrategyChoice::changeStrategy(shared_ptr<strategy_choice::Entry> entry,
                                shared_ptr<fw::Strategy> oldStrategy,
@@ -197,9 +244,11 @@
     return;
   }
 
-  // TODO delete incompatible StrategyInfo
-  NFD_LOG_WARN("changeStrategy(" << entry->getPrefix() << ") " <<
-               "runtime strategy change not implemented");
+  std::for_each(m_nameTree.partialEnumerate(entry->getPrefix(),
+                           bind(&predicate_nameTreeEntry_needResetStrategyChoice,
+                                _1, boost::cref(*m_nameTree.get(*entry)))),
+                m_nameTree.end(),
+                &clearStrategyInfo);
 }
 
 } // namespace nfd