diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
index 9e1c1cd..c8bd357 100644
--- a/daemon/table/cs-entry-impl.cpp
+++ b/daemon/table/cs-entry-impl.cpp
@@ -35,7 +35,6 @@
 }
 
 EntryImpl::EntryImpl(shared_ptr<const Data> data, bool isUnsolicited)
-  : queueType(QUEUE_NONE)
 {
   this->setData(data, isUnsolicited);
   BOOST_ASSERT(!this->isQuery());
diff --git a/daemon/table/cs-entry-impl.hpp b/daemon/table/cs-entry-impl.hpp
index 0732047..d061f88 100644
--- a/daemon/table/cs-entry-impl.hpp
+++ b/daemon/table/cs-entry-impl.hpp
@@ -26,9 +26,7 @@
 #ifndef NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
 #define NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
 
-#include "cs-internal.hpp"
 #include "cs-entry.hpp"
-#include "core/scheduler.hpp"
 
 namespace nfd {
 namespace cs {
@@ -69,11 +67,6 @@
   bool
   isQuery() const;
 
-public:
-  QueueType queueType;
-  QueueIt queueIt;
-  scheduler::EventId moveStaleEvent;
-
 private:
   Name m_queryName;
 };
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
index 7df3d06..3f22bcd 100644
--- a/daemon/table/cs-internal.hpp
+++ b/daemon/table/cs-internal.hpp
@@ -38,18 +38,7 @@
 class EntryImpl;
 
 typedef std::set<EntryImpl> Table;
-typedef Table::const_iterator TableIt;
-
-typedef std::list<TableIt> Queue;
-typedef Queue::iterator QueueIt;
-
-enum QueueType {
-  QUEUE_UNSOLICITED,
-  QUEUE_STALE,
-  QUEUE_FIFO,
-  QUEUE_MAX,
-  QUEUE_NONE = QUEUE_MAX
-};
+typedef Table::const_iterator iterator;
 
 } // namespace cs
 } // namespace nfd
diff --git a/daemon/table/cs-policy-priority-fifo.cpp b/daemon/table/cs-policy-priority-fifo.cpp
new file mode 100644
index 0000000..e7231a9
--- /dev/null
+++ b/daemon/table/cs-policy-priority-fifo.cpp
@@ -0,0 +1,157 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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 "cs-policy-priority-fifo.hpp"
+#include "cs.hpp"
+#include <ndn-cxx/util/signal.hpp>
+
+namespace nfd {
+namespace cs {
+namespace priority_fifo {
+
+const std::string PriorityFifoPolicy::POLICY_NAME = "fifo";
+
+PriorityFifoPolicy::PriorityFifoPolicy()
+  : Policy(POLICY_NAME)
+{
+}
+
+void
+PriorityFifoPolicy::doAfterInsert(iterator i)
+{
+  this->attachQueue(i);
+  this->evictEntries();
+}
+
+void
+PriorityFifoPolicy::doAfterRefresh(iterator i)
+{
+  this->detachQueue(i);
+  this->attachQueue(i);
+}
+
+void
+PriorityFifoPolicy::doBeforeErase(iterator i)
+{
+  this->detachQueue(i);
+}
+
+void
+PriorityFifoPolicy::doBeforeUse(iterator i)
+{
+  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+}
+
+void
+PriorityFifoPolicy::evictEntries()
+{
+  BOOST_ASSERT(this->getCs() != nullptr);
+
+  while (this->getCs()->size() > this->getLimit()) {
+    this->evictOne();
+  }
+}
+
+void
+PriorityFifoPolicy::evictOne()
+{
+  BOOST_ASSERT(!m_queues[QUEUE_UNSOLICITED].empty() ||
+               !m_queues[QUEUE_STALE].empty() ||
+               !m_queues[QUEUE_FIFO].empty());
+
+  iterator i;
+  if (!m_queues[QUEUE_UNSOLICITED].empty()) {
+    i = m_queues[QUEUE_UNSOLICITED].front();
+  }
+  else if (!m_queues[QUEUE_STALE].empty()) {
+    i = m_queues[QUEUE_STALE].front();
+  }
+  else if (!m_queues[QUEUE_FIFO].empty()) {
+    i = m_queues[QUEUE_FIFO].front();
+  }
+
+  this->detachQueue(i);
+  this->emitSignal(beforeEvict, i);
+}
+
+void
+PriorityFifoPolicy::attachQueue(iterator i)
+{
+  BOOST_ASSERT(m_entryInfoMap.find(i) == m_entryInfoMap.end());
+
+  EntryInfo* entryInfo = new EntryInfo();
+  if (i->isUnsolicited()) {
+    entryInfo->queueType = QUEUE_UNSOLICITED;
+  }
+  else if (i->isStale()) {
+    entryInfo->queueType = QUEUE_STALE;
+  }
+  else {
+    entryInfo->queueType = QUEUE_FIFO;
+
+    if (i->canStale()) {
+      entryInfo->moveStaleEventId = scheduler::schedule(i->getData().getFreshnessPeriod(),
+                                              bind(&PriorityFifoPolicy::moveToStaleQueue, this, i));
+    }
+  }
+
+  Queue& queue = m_queues[entryInfo->queueType];
+  entryInfo->queueIt = queue.insert(queue.end(), i);
+  m_entryInfoMap[i] = entryInfo;
+}
+
+void
+PriorityFifoPolicy::detachQueue(iterator i)
+{
+  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+
+  EntryInfo* entryInfo = m_entryInfoMap[i];
+  if (entryInfo->queueType == QUEUE_FIFO) {
+    scheduler::cancel(entryInfo->moveStaleEventId);
+  }
+
+  m_queues[entryInfo->queueType].erase(entryInfo->queueIt);
+  m_entryInfoMap.erase(i);
+}
+
+void
+PriorityFifoPolicy::moveToStaleQueue(iterator i)
+{
+  BOOST_ASSERT(m_entryInfoMap.find(i) != m_entryInfoMap.end());
+
+  EntryInfo* entryInfo = m_entryInfoMap[i];
+  BOOST_ASSERT(entryInfo->queueType == QUEUE_FIFO);
+
+  m_queues[QUEUE_FIFO].erase(entryInfo->queueIt);
+
+  entryInfo->queueType = QUEUE_STALE;
+  Queue& queue = m_queues[QUEUE_STALE];
+  entryInfo->queueIt = queue.insert(queue.end(), i);
+  m_entryInfoMap[i] = entryInfo;
+}
+
+} // namespace priorityfifo
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-policy-priority-fifo.hpp b/daemon/table/cs-policy-priority-fifo.hpp
new file mode 100644
index 0000000..93ae884
--- /dev/null
+++ b/daemon/table/cs-policy-priority-fifo.hpp
@@ -0,0 +1,133 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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_DAEMON_TABLE_CS_POLICY_FIFO_HPP
+#define NFD_DAEMON_TABLE_CS_POLICY_FIFO_HPP
+
+#include "cs-policy.hpp"
+#include "common.hpp"
+#include "core/scheduler.hpp"
+
+namespace nfd {
+namespace cs {
+namespace priority_fifo {
+
+typedef std::list<iterator> Queue;
+typedef Queue::iterator QueueIt;
+
+enum QueueType {
+  QUEUE_UNSOLICITED,
+  QUEUE_STALE,
+  QUEUE_FIFO,
+  QUEUE_MAX
+};
+
+struct EntryInfo
+{
+  QueueType queueType;
+  QueueIt queueIt;
+  scheduler::EventId moveStaleEventId;
+};
+
+struct EntryItComparator
+{
+  bool
+  operator()(const iterator& a, const iterator& b) const
+  {
+    return *a < *b;
+  }
+};
+
+typedef std::map<iterator, EntryInfo*, EntryItComparator> EntryInfoMapFifo;
+
+/** \brief Priority Fifo cs replacement policy
+ *
+ * The entries that get removed first are unsolicited Data packets,
+ * which are the Data packets that got cached opportunistically without preceding
+ * forwarding of the corresponding Interest packet.
+ * Next, the Data packets with expired freshness are removed.
+ * Last, the Data packets are removed from the Content Store on a pure FIFO basis.
+ */
+class PriorityFifoPolicy : public Policy
+{
+public:
+  PriorityFifoPolicy();
+
+public:
+  static const std::string POLICY_NAME;
+
+private:
+  virtual void
+  doAfterInsert(iterator i) DECL_OVERRIDE;
+
+  virtual void
+  doAfterRefresh(iterator i) DECL_OVERRIDE;
+
+  virtual void
+  doBeforeErase(iterator i) DECL_OVERRIDE;
+
+  virtual void
+  doBeforeUse(iterator i) DECL_OVERRIDE;
+
+  virtual void
+  evictEntries() DECL_OVERRIDE;
+
+private:
+  /** \brief evicts one entry
+   *  \pre CS is not empty
+   */
+  void
+  evictOne();
+
+  /** \brief attaches the entry to an appropriate queue
+   *  \pre the entry is not in any queue
+   */
+  void
+  attachQueue(iterator i);
+
+  /** \brief detaches the entry from its current queue
+   *  \post the entry is not in any queue
+   */
+  void
+  detachQueue(iterator i);
+
+  /** \brief moves an entry from FIFO queue to STALE queue
+   */
+  void
+  moveToStaleQueue(iterator i);
+
+private:
+  Queue m_queues[QUEUE_MAX];
+  EntryInfoMapFifo m_entryInfoMap;
+};
+
+} // namespace priorityfifo
+
+using priority_fifo::PriorityFifoPolicy;
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_POLICY_FIFO_HPP
\ No newline at end of file
diff --git a/daemon/table/cs-policy.cpp b/daemon/table/cs-policy.cpp
new file mode 100644
index 0000000..9726269
--- /dev/null
+++ b/daemon/table/cs-policy.cpp
@@ -0,0 +1,79 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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 "cs-policy.hpp"
+#include "cs.hpp"
+
+namespace nfd {
+namespace cs {
+
+Policy::Policy(const std::string& policyName)
+  : m_policyName(policyName)
+{
+}
+
+Policy::~Policy()
+{
+}
+
+void
+Policy::setLimit(size_t nMaxEntries)
+{
+  BOOST_ASSERT(nMaxEntries > 0);
+  m_limit = nMaxEntries;
+
+  this->evictEntries();
+}
+
+void
+Policy::afterInsert(iterator i)
+{
+  BOOST_ASSERT(m_cs != nullptr);
+  this->doAfterInsert(i);
+}
+
+void
+Policy::afterRefresh(iterator i)
+{
+  BOOST_ASSERT(m_cs != nullptr);
+  this->doAfterRefresh(i);
+}
+
+void
+Policy::beforeErase(iterator i)
+{
+  BOOST_ASSERT(m_cs != nullptr);
+  this->doBeforeErase(i);
+}
+
+void
+Policy::beforeUse(iterator i)
+{
+  BOOST_ASSERT(m_cs != nullptr);
+  this->doBeforeUse(i);
+}
+
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-policy.hpp b/daemon/table/cs-policy.hpp
new file mode 100644
index 0000000..4beb114
--- /dev/null
+++ b/daemon/table/cs-policy.hpp
@@ -0,0 +1,191 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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_DAEMON_TABLE_CS_POLICY_HPP
+#define NFD_DAEMON_TABLE_CS_POLICY_HPP
+
+#include "cs-internal.hpp"
+#include "cs-entry-impl.hpp"
+
+namespace nfd {
+namespace cs {
+
+class Cs;
+
+/** \brief represents a CS replacement policy
+ */
+class Policy : noncopyable
+{
+public:
+  explicit
+  Policy(const std::string& policyName);
+
+  virtual
+  ~Policy();
+
+  const std::string&
+  getName() const;
+
+public:
+  /** \brief gets cs
+   */
+  Cs*
+  getCs() const;
+
+  /** \brief sets cs
+   */
+  void
+  setCs(Cs *cs);
+
+  /** \brief gets hard limit (in number of entries)
+   */
+  size_t
+  getLimit() const;
+
+  /** \brief sets hard limit (in number of entries)
+   *  \post getLimit() == nMaxEntries
+   *  \post cs.size() <= getLimit()
+   *
+   *  The policy may evict entries if necessary.
+   */
+  void
+  setLimit(size_t nMaxEntries);
+
+  /** \brief emits when an entry is being evicted
+   *
+   *  A policy implementation should emit this signal to cause CS to erase the entry from its index.
+   *  CS should connect to this signal and erase the entry upon signal emission.
+   */
+  signal::Signal<Policy, iterator> beforeEvict;
+
+  /** \brief invoked by CS after a new entry is inserted
+   *  \post cs.size() <= getLimit()
+   *
+   *  The policy may evict entries if necessary.
+   *  During this process, \p i might be evicted.
+   */
+  void
+  afterInsert(iterator i);
+
+  /** \brief invoked by CS after an existing entry is refreshed by same Data
+   *
+   *  The policy may witness this refresh to make better eviction decisions in the future.
+   */
+  void
+  afterRefresh(iterator i);
+
+  /** \brief invoked by CS before an entry is erased due to management command
+   *  \warning CS must not invoke this method if an entry is erased due to eviction.
+   */
+  void
+  beforeErase(iterator i);
+
+  /** \brief invoked by CS before an entry is used to match a lookup
+   *
+   *  The policy may witness this usage to make better eviction decisions in the future.
+   */
+  void
+  beforeUse(iterator i);
+
+protected:
+  /** \brief invoked after a new entry is created in CS
+   *
+   *  When overridden in a subclass, a policy implementation should decide whether to accept \p i.
+   *  If \p i is accepted, it should be inserted into a cleanup index.
+   *  Otherwise, \p beforeEvict signal should be emitted with \p i to inform CS to erase the entry.
+   *  A policy implementation may decide to evict other entries by emitting \p beforeEvict signal,
+   *  in order to keep CS size under limit.
+   */
+  virtual void
+  doAfterInsert(iterator i) = 0;
+
+  /** \brief invoked after an existing entry is refreshed by same Data
+   *
+   *  When overridden in a subclass, a policy implementation may witness this operation
+   *  and adjust its cleanup index.
+   */
+  virtual void
+  doAfterRefresh(iterator i) = 0;
+
+  /** \brief invoked before an entry is erased due to management command
+   *  \note This will not be invoked for an entry being evicted by policy.
+   *
+   *  When overridden in a subclass, a policy implementation should erase \p i
+   *  from its cleanup index without emitted \p afterErase signal.
+   */
+  virtual void
+  doBeforeErase(iterator i) = 0;
+
+  /** \brief invoked before an entry is used to match a lookup
+   *
+   *  When overridden in a subclass, a policy implementation may witness this operation
+   *  and adjust its cleanup index.
+   */
+  virtual void
+  doBeforeUse(iterator i) = 0;
+
+  /** \brief evicts zero or more entries
+   *  \post CS size does not exceed hard limit
+   */
+  virtual void
+  evictEntries() = 0;
+
+protected:
+  DECLARE_SIGNAL_EMIT(beforeEvict)
+
+private:
+  std::string m_policyName;
+  size_t m_limit;
+  Cs* m_cs;
+};
+
+inline const std::string&
+Policy::getName() const
+{
+  return m_policyName;
+}
+
+inline Cs*
+Policy::getCs() const
+{
+  return m_cs;
+}
+
+inline void
+Policy::setCs(Cs *cs)
+{
+  m_cs = cs;
+}
+
+inline size_t
+Policy::getLimit() const
+{
+  return m_limit;
+}
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_POLICY_HPP
\ No newline at end of file
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index a63d33e..9ea3d8b 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -24,9 +24,9 @@
  */
 
 #include "cs.hpp"
+#include "cs-policy-priority-fifo.hpp"
 #include "core/logger.hpp"
 #include "core/algorithm.hpp"
-#include <numeric>
 
 NFD_LOG_INIT("ContentStore");
 
@@ -44,18 +44,38 @@
 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Cs::const_iterator>));
 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
 
-Cs::Cs(size_t nMaxPackets)
-  : m_limit(nMaxPackets)
+unique_ptr<Policy>
+makeDefaultPolicy()
 {
-  BOOST_ASSERT(nMaxPackets > 0);
+  return unique_ptr<Policy>(new PriorityFifoPolicy());
+}
+
+Cs::Cs(size_t nMaxPackets, unique_ptr<Policy> policy)
+{
+  this->setPolicyImpl(policy);
+  m_policy->setLimit(nMaxPackets);
 }
 
 void
 Cs::setLimit(size_t nMaxPackets)
 {
-  BOOST_ASSERT(nMaxPackets > 0);
-  m_limit = nMaxPackets;
-  this->evict();
+  m_policy->setLimit(nMaxPackets);
+}
+
+size_t
+Cs::getLimit() const
+{
+  return m_policy->getLimit();
+}
+
+void
+Cs::setPolicy(unique_ptr<Policy> policy)
+{
+  BOOST_ASSERT(policy != nullptr);
+  BOOST_ASSERT(m_policy != nullptr);
+  size_t limit = m_policy->getLimit();
+  this->setPolicyImpl(policy);
+  m_policy->setLimit(limit);
 }
 
 bool
@@ -73,26 +93,25 @@
     }
   }
 
-  bool isNewEntry = false; TableIt it;
+  bool isNewEntry = false;
+  iterator it;
   // use .insert because gcc46 does not support .emplace
   std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
   EntryImpl& entry = const_cast<EntryImpl&>(*it);
 
+  entry.updateStaleTime();
+
   if (!isNewEntry) { // existing entry
-    this->detachQueue(it);
     // XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
     if (entry.isUnsolicited() && !isUnsolicited) {
       entry.unsetUnsolicited();
     }
+
+    m_policy->afterRefresh(it);
   }
-  entry.updateStaleTime();
-  this->attachQueue(it);
-
-  // check there are same amount of entries in the table and in queues
-  BOOST_ASSERT(m_table.size() == std::accumulate(m_queues, m_queues + QUEUE_MAX, 0U,
-      [] (size_t sum, const Queue queue) { return sum + queue.size(); }));
-
-  this->evict(); // XXX The new entry could be evicted, but it shouldn't matter.
+  else {
+    m_policy->afterInsert(it);
+  }
 
   return true;
 }
@@ -109,13 +128,13 @@
   bool isRightmost = interest.getChildSelector() == 1;
   NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
 
-  TableIt first = m_table.lower_bound(prefix);
-  TableIt last = m_table.end();
+  iterator first = m_table.lower_bound(prefix);
+  iterator last = m_table.end();
   if (prefix.size() > 0) {
     last = m_table.lower_bound(prefix.getSuccessor());
   }
 
-  TableIt match = last;
+  iterator match = last;
   if (isRightmost) {
     match = this->findRightmost(interest, first, last);
   }
@@ -129,39 +148,40 @@
     return;
   }
   NFD_LOG_DEBUG("  matching " << match->getName());
+  m_policy->beforeUse(match);
   hitCallback(interest, match->getData());
 }
 
-TableIt
-Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
 {
   return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
 }
 
-TableIt
-Cs::findRightmost(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findRightmost(const Interest& interest, iterator first, iterator last) const
 {
   // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
   // If there is a match in that sub-namespace, the leftmost match is returned;
   // otherwise, loop continues.
 
   size_t interestNameLength = interest.getName().size();
-  for (TableIt right = last; right != first;) {
-    TableIt prev = std::prev(right);
+  for (iterator right = last; right != first;) {
+    iterator prev = std::prev(right);
 
     // special case: [first,prev] have exact Names
     if (prev->getName().size() == interestNameLength) {
       NFD_LOG_TRACE("  find-among-exact " << prev->getName());
-      TableIt matchExact = this->findRightmostAmongExact(interest, first, right);
+      iterator matchExact = this->findRightmostAmongExact(interest, first, right);
       return matchExact == right ? last : matchExact;
     }
 
     Name prefix = prev->getName().getPrefix(interestNameLength + 1);
-    TableIt left = m_table.lower_bound(prefix);
+    iterator left = m_table.lower_bound(prefix);
 
     // normal case: [left,right) are under one-component-longer prefix
     NFD_LOG_TRACE("  find-under-prefix " << prefix);
-    TableIt match = this->findLeftmost(interest, left, right);
+    iterator match = this->findLeftmost(interest, left, right);
     if (match != right) {
       return match;
     }
@@ -170,97 +190,22 @@
   return last;
 }
 
-TableIt
-Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const
+iterator
+Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
 {
   return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
 }
 
 void
-Cs::attachQueue(TableIt it)
+Cs::setPolicyImpl(unique_ptr<Policy>& policy)
 {
-  EntryImpl& entry = const_cast<EntryImpl&>(*it);
+  m_policy = std::move(policy);
+  m_beforeEvictConnection = m_policy->beforeEvict.connect([this] (iterator it) {
+      m_table.erase(it);
+    });
 
-  if (entry.queueType != QUEUE_NONE) {
-    this->detachQueue(it);
-  }
-
-  if (entry.isUnsolicited()) {
-    entry.queueType = QUEUE_UNSOLICITED;
-  }
-  else if (entry.isStale()) {
-    entry.queueType = QUEUE_STALE;
-  }
-  else {
-    entry.queueType = QUEUE_FIFO;
-
-    if (entry.canStale()) {
-      entry.moveStaleEvent = scheduler::schedule(entry.getData().getFreshnessPeriod(),
-                             bind(&Cs::moveToStaleQueue, this, it));
-    }
-  }
-
-  Queue& queue = m_queues[entry.queueType];
-  entry.queueIt = queue.insert(queue.end(), it);
-}
-
-void
-Cs::detachQueue(TableIt it)
-{
-  EntryImpl& entry = const_cast<EntryImpl&>(*it);
-
-  BOOST_ASSERT(entry.queueType != QUEUE_NONE);
-
-  if (entry.queueType == QUEUE_FIFO) {
-    scheduler::cancel(entry.moveStaleEvent);
-  }
-
-  m_queues[entry.queueType].erase(entry.queueIt);
-  entry.queueType = QUEUE_NONE;
-}
-
-void
-Cs::moveToStaleQueue(TableIt it)
-{
-  EntryImpl& entry = const_cast<EntryImpl&>(*it);
-
-  BOOST_ASSERT(entry.queueType == QUEUE_FIFO);
-  m_queues[QUEUE_FIFO].erase(entry.queueIt);
-
-  entry.queueType = QUEUE_STALE;
-  Queue& queue = m_queues[QUEUE_STALE];
-  entry.queueIt = queue.insert(queue.end(), it);
-}
-
-std::tuple<TableIt, std::string>
-Cs::evictPick()
-{
-  if (!m_queues[QUEUE_UNSOLICITED].empty()) {
-    return std::make_tuple(m_queues[QUEUE_UNSOLICITED].front(), "unsolicited");
-  }
-  if (!m_queues[QUEUE_STALE].empty()) {
-    return std::make_tuple(m_queues[QUEUE_STALE].front(), "stale");
-  }
-  if (!m_queues[QUEUE_FIFO].empty()) {
-    return std::make_tuple(m_queues[QUEUE_FIFO].front(), "fifo");
-  }
-
-  BOOST_ASSERT(false);
-  return std::make_tuple(m_table.end(), "error");
-}
-
-
-void
-Cs::evict()
-{
-  while (this->size() > m_limit) {
-    TableIt it; std::string reason;
-    std::tie(it, reason) = this->evictPick();
-
-    NFD_LOG_DEBUG("evict " << it->getName() << " " << reason);
-    this->detachQueue(it);
-    m_table.erase(it);
-  }
+  m_policy->setCs(this);
+  BOOST_ASSERT(m_policy->getCs() == this);
 }
 
 void
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 5e3bfbe..5a24bde 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -48,19 +48,25 @@
 #ifndef NFD_DAEMON_TABLE_CS_HPP
 #define NFD_DAEMON_TABLE_CS_HPP
 
+#include "cs-policy.hpp"
+#include "cs-internal.hpp"
 #include "cs-entry-impl.hpp"
+#include <ndn-cxx/util/signal.hpp>
 #include <boost/iterator/transform_iterator.hpp>
 
 namespace nfd {
 namespace cs {
 
+unique_ptr<Policy>
+makeDefaultPolicy();
+
 /** \brief represents the ContentStore
  */
 class Cs : noncopyable
 {
 public:
   explicit
-  Cs(size_t nMaxPackets = 10);
+  Cs(size_t nMaxPackets = 10, unique_ptr<Policy> policy = makeDefaultPolicy());
 
   /** \brief inserts a Data packet
    *  \return true
@@ -97,9 +103,20 @@
   /** \return capacity (in number of packets)
    */
   size_t
-  getLimit() const
+  getLimit() const;
+
+  /** \brief changes cs replacement policy
+   *  \pre size() == 0
+   */
+  void
+  setPolicy(unique_ptr<Policy> policy);
+
+  /** \return cs replacement policy
+   */
+  Policy*
+  getPolicy() const
   {
-    return m_limit;
+    return m_policy.get();
   }
 
   /** \return number of stored packets
@@ -128,7 +145,7 @@
 
   /** \brief ContentStore iterator (public API)
    */
-  typedef boost::transform_iterator<EntryFromEntryImpl, TableIt, const Entry&> const_iterator;
+  typedef boost::transform_iterator<EntryFromEntryImpl, iterator, const Entry&> const_iterator;
 
   const_iterator
   begin() const
@@ -146,54 +163,28 @@
   /** \brief find leftmost match in [first,last)
    *  \return the leftmost match, or last if not found
    */
-  TableIt
-  findLeftmost(const Interest& interest, TableIt left, TableIt right) const;
+  iterator
+  findLeftmost(const Interest& interest, iterator left, iterator right) const;
 
   /** \brief find rightmost match in [first,last)
    *  \return the rightmost match, or last if not found
    */
-  TableIt
-  findRightmost(const Interest& interest, TableIt first, TableIt last) const;
+  iterator
+  findRightmost(const Interest& interest, iterator first, iterator last) const;
 
   /** \brief find rightmost match among entries with exact Names in [first,last)
    *  \return the rightmost match, or last if not found
    */
-  TableIt
-  findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
+  iterator
+  findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const;
 
-private: // cleanup
-  /** \brief attaches an entry to a suitable cleanup queue
-   *  \note if the entry is already attached to a queue, it's automatically detached
-   */
   void
-  attachQueue(TableIt it);
-
-  /** \brief detaches an entry from its current cleanup queue
-   *  \warning if the entry is unattached, this will cause undefined behavior
-   */
-  void
-  detachQueue(TableIt it);
-
-  /** \brief moves an entry from FIFO queue to STALE queue
-   */
-  void
-  moveToStaleQueue(TableIt it);
-
-  /** \brief picks an entry for eviction
-   */
-  std::tuple<TableIt, std::string/*reason*/>
-  evictPick();
-
-  /** \brief evicts zero or more entries so that number of stored entries
-   *         is not greater than capacity
-   */
-  void
-  evict();
+  setPolicyImpl(unique_ptr<Policy>& policy);
 
 private:
-  size_t m_limit;
   Table m_table;
-  Queue m_queues[QUEUE_MAX];
+  unique_ptr<Policy> m_policy;
+  ndn::util::signal::ScopedConnection m_beforeEvictConnection;
 };
 
 } // namespace cs