diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 2c1b657..e575694 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -349,14 +349,22 @@
 {
   NFD_LOG_TRACE("evictItem()");
 
-  if (!m_cleanupIndex.get<unsolicited>().empty() &&
-      (*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited())
-  {
-    NFD_LOG_TRACE("Evict from unsolicited queue");
+  if (!m_cleanupIndex.get<unsolicited>().empty()) {
+    CleanupIndex::index<unsolicited>::type::const_iterator firstSolicited =
+      m_cleanupIndex.get<unsolicited>().upper_bound(false);
 
-    eraseFromSkipList(*m_cleanupIndex.get<unsolicited>().begin());
-    m_cleanupIndex.get<unsolicited>().erase(m_cleanupIndex.get<unsolicited>().begin());
-    return true;
+    if (firstSolicited != m_cleanupIndex.get<unsolicited>().begin()) {
+      --firstSolicited;
+      BOOST_ASSERT((*firstSolicited)->isUnsolicited());
+      NFD_LOG_TRACE("Evict from unsolicited queue");
+
+      eraseFromSkipList(*firstSolicited);
+      m_cleanupIndex.get<unsolicited>().erase(firstSolicited);
+      return true;
+    }
+    else {
+      BOOST_ASSERT(!(*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited());
+    }
   }
 
   if (!m_cleanupIndex.get<byStaleness>().empty() &&
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 67cc611..f683a20 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -64,6 +64,15 @@
   {
     return entry1->isUnsolicited();
   }
+
+  bool
+  operator()(bool isUnsolicited, const cs::Entry* entry) const
+  {
+    if (isUnsolicited)
+      return true;
+    else
+      return !entry->isUnsolicited();
+  }
 };
 
 // tags
diff --git a/tests/daemon/table/cs.cpp b/tests/daemon/table/cs.cpp
index 3592290..1f95894 100644
--- a/tests/daemon/table/cs.cpp
+++ b/tests/daemon/table/cs.cpp
@@ -81,7 +81,6 @@
   BOOST_CHECK_EQUAL(cs.size(), 4);
 }
 
-
 BOOST_AUTO_TEST_CASE(DuplicateInsertion)
 {
   Cs cs;
@@ -187,6 +186,42 @@
   BOOST_CHECK_EQUAL(found->getName(), name2);
 }
 
+BOOST_AUTO_TEST_CASE(Bug2043) // eviction order of unsolicited packets
+{
+  Cs cs(3);
+
+  cs.insert(*makeData("/a"), true);
+  cs.insert(*makeData("/b"), true);
+  cs.insert(*makeData("/c"), true);
+  BOOST_CHECK_EQUAL(cs.size(), 3);
+
+  cs.insert(*makeData("/d"), true);
+  BOOST_CHECK_EQUAL(cs.size(), 3);
+
+  const Data* oldestData = cs.find(Interest("/a"));
+  const Data* newestData = cs.find(Interest("/c"));
+  BOOST_CHECK(oldestData == 0);
+  BOOST_CHECK(newestData != 0);
+}
+
+BOOST_AUTO_TEST_CASE(UnsolicitedWithSolicitedEvictionOrder)
+{
+  Cs cs(3);
+
+  cs.insert(*makeData("/a"), true);
+  cs.insert(*makeData("/b"), false);
+  cs.insert(*makeData("/c"), true);
+  BOOST_CHECK_EQUAL(cs.size(), 3);
+
+  cs.insert(*makeData("/d"), true);
+  BOOST_CHECK_EQUAL(cs.size(), 3);
+
+  const Data* oldestData = cs.find(Interest("/a"));
+  const Data* newestData = cs.find(Interest("/c"));
+  BOOST_CHECK(oldestData == 0);
+  BOOST_CHECK(newestData != 0);
+}
+
 //even max size
 BOOST_AUTO_TEST_CASE(ReplacementEvenSize)
 {