docs: Documentation update
Change-Id: I6f916eb822a59e980e8fb1134886c3431755119c
diff --git a/docs/source/cs.rst b/docs/source/cs.rst
index 6098337..b118822 100644
--- a/docs/source/cs.rst
+++ b/docs/source/cs.rst
@@ -1,60 +1,187 @@
.. _content store:
-Content Store
-+++++++++++++
+NFD's Content Store
+++++++++++++++++++++
-ndnSIM comes with several different in-memory :ndnsim:`content store <ndn::ContentStore>` implementations, featuring different cache replacement policies.
+The current implementation of NFD's Content Store uses a `skip list
+<http://en.wikipedia.org/wiki/Skip_list>`_ as its underlying data structure. Skip lists are a
+probabilistic alternative to balanced trees. Skip lists are balanced by virtue of a random
+number generator. Its average insertion and lookup complexity is O(log n). CS entries are
+placed in the Skip List in ascending order (by Name).
-.. note:
+The current implementation evicts CS entries based on prioritized FIFO (First In First Out)
+strategy. 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. Lastly, the Data
+packets are removed from the Content Store on a pure FIFO basis. This cache replacement policy
+is currently hard-coded; it is intended to be replaceable in the future by the NFD developer
+team.
- The default content store uses LRU replacement policity and constrained with 100 cached ContentObjects.
-
-To select a particular content store and configure its capacity, use :ndnsim:`SetContentStore <ndn::StackHelper::SetContentStore>` helper method
-
-Simple content stores
-^^^^^^^^^^^^^^^^^^^^^
-
-Least Recently Used (LRU) (default)
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Lru`.
-
-Usage example:
+The only currently available option to control behavior of NFD's Content Store is to set its
+maximum size using :ndnsim:`StackHelper::setCsSize()`:
.. code-block:: c++
- ndnHelper.SetContentStore ("ns3::ndn::cs::Lru",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
+ ndnHelper.setCsSize(<max-size-in-packets>);
+ ...
+ ndnHelper.Install(nodes);
-First-In-First-Out (FIFO)
-~~~~~~~~~~~~~~~~~~~~~~~~~
+Examples:
-Implementation name: :ndnsim:`ndn::cs::Fifo`
+- Effectively disable NFD content store an all nodes
-Usage example:
+ Minimum allowed value for NFD content store size is 1. If 0 is specified, it will be assumed
+ that the old content store implementation should be used.
.. code-block:: c++
- ndnHelper.SetContentStore ("ns3::ndn::cs::Fifo",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
+ ndnHelper.setCsSize(1);
+ ...
+ ndnHelper.Install(nodes);
-Random
-~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Random`
-
-Usage example:
+- Set CS size 100 on node1, size 1000 on node1, and size 2000 on all other nodes:
.. code-block:: c++
- ndnHelper.SetContentStore ("ns3::ndn::cs::Random",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
+ ndnHelper.setCsSize(100);
+ ndnHelper.Install(node1);
+
+ ndnHelper.setCsSize(1000);
+ ndnHelper.Install(node2);
+
+ NodeContainer allOtherNodes;
+ for (NodeList::Iterator i = NodeList::Begin(); i != NodeList::End(); ++i) {
+ if (*i != node1 && *i != node2) {
+ allOtherNodes.Add(*i);
+ }
+ }
+ ndnHelper.Install(allOtherNodes);
+
+CS entry
+~~~~~~~~
+
+The Data packet, along with other necessary fields, are stored in a CS entry. Each entry
+contains:
+
+- the Data packet
+- flag indicating whether the Data packet is unsolicited
+- the timestamp at which the cached Data becomes stale
+
+CS
+~~
+
+A multi-index container is maintained in order to support the prioritized FIFO cache
+replacement policy. In this way, pointers to the Data packets in a particular order are
+kept. Note that this multi-index container is completely separated from the skip list
+container, which indexes Content Store entries by name.
+
+The container (Cs::CleanupIndex) currently supports indexing of unsolicited Data packets,
+indexing by packet staleness and indexing by packet arrival time. Calculation of the indexes is
+performed in the container during the Data packet insertion (Cs::insert) in the Content Store.
+
+Eviction (Cs::evictItem) is performed during the insertion when the CS is full, and when the
+capacity is decreased by management. We decided not to perform periodical cleanups, because its
+CPU overhead causes jitter in packet forwarding.
+
+In the current version of NFD, cache replacement policy can be modified by adding different
+indexes in the Cs::CleanupIndex container (refer to Boost.multiIndex documentation) and
+implementing additional logic in Cs::evictItem function.
+
+For more detailed specification refer to the `NFD Developer's Guide
+<http://named-data.net/wp-content/uploads/2014/07/NFD-developer-guide.pdf>`_, section 3.2.
+
+Old Content Store Implementations
++++++++++++++++++++++++++++++++++
+
+NFD's content store implementation takes full consideration of Interest selectors, however is
+not yet flexible when it comes to cache replacement policies. Feature to extend CS flexibility
+is currently in active development (refer to `Issue #2219 on NFD Redmine
+<http://redmine.named-data.net/issues/2219>`_) and for the time being, we have ported the old
+ndnSIM 1.0 content store implementations to the new code base. These implementations feature
+different cache replacement policies, but have very limited support for Interest selectors. If
+your scenario relies on proper selector processing, do not use these implementations as the
+simulation results most likely be incorrect.
+
+To select old content store implementations, use :ndnsim:`StackHelper::SetOldContentStore`:
+
+.. code-block:: c++
+
+ ndnHelper.SetOldContentStore("<content store implementation>",
+ ["<optional parameter>", "<optional parameter's value>" [, ...]]);
+ ...
+ ndnHelper.Install (nodes);
+
+Available old content store implementations are listed in the following table:
+
+
++----------------------------------------------+----------------------------------------------------------+
+| **Simple content stores** |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Lru`` | **Least recently used (LRU) (default)** |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Fifo`` | First-in-first-Out (FIFO) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Lfu`` | Least frequently used (LFU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Random`` | Random |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Nocache`` | Policy that completely disables caching |
++----------------------------------------------+----------------------------------------------------------+
++----------------------------------------------+----------------------------------------------------------+
+| **Content stores with entry lifetime tracking** |
+| |
+| These policies allow evaluation of CS enties lifetime (i.e., how long entries stay in CS) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Stats::Lru`` | Least recently used (LRU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Stats::Fifo`` | Least frequently used (LFU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Stats::Lfu`` | Random |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Stats::Random`` | Policy that completely disables caching |
++----------------------------------------------+----------------------------------------------------------+
++----------------------------------------------+----------------------------------------------------------+
+| **Content stores respecting freshness field of Data packets** |
+| |
+| These policies cache Data packets only for the time indicated by FreshnessPeriod. |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Freshness::Lru`` | Least recently used (LRU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Freshness::Fifo`` | Least frequently used (LFU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Freshness::Lfu`` | Random |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Freshness::Random`` | Policy that completely disables caching |
++----------------------------------------------+----------------------------------------------------------+
++----------------------------------------------+----------------------------------------------------------+
+| **Content store realization that probabilistically accepts data packet into CS (placement policy)** |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Probability::Lru`` | Least recently used (LRU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Probability::Fifo`` | Least frequently used (LFU) |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Probability::Lfu`` | Random |
++----------------------------------------------+----------------------------------------------------------+
+| ``ns3::ndn::cs::Probability::Random`` | Policy that completely disables caching |
++----------------------------------------------+----------------------------------------------------------+
+
+Examples:
+
+
+- Select simple LRU policy on node1, simple FIFO policy on node2, and simple random policy on
+ other nodes with maximum CS sizes of 10000 packets:
+
+ .. code-block:: c++
+
+ ndnHelper.SetOldContentStore("ns3::ndn::cs::Lru", "MaxSize", "10000");
+ ndnHelper.Install(node1);
+
+ ndnHelper.SetOldContentStore("ns3::ndn::cs::Fifo", "MaxSize", "10000");
+ ndnHelper.Install(node2);
+
+ ndnHelper.SetOldContentStore("ns3::ndn::cs::Random", "MaxSize", "10000");
+ ...
+ ndnHelper.Install(otherNodes);
.. note::
@@ -64,179 +191,37 @@
If ``MaxSize`` is set to 0, then no limit on ContentStore will be enforced
-Nocache
-~~~~~~~
-
-:ndnsim:`Trivial implementation <ndn::cs::Nocache>` of the ContentStore that does not really do any caching.
-
-Usage example:
+- Disable CS on node2
.. code-block:: c++
- ndnHelper.SetContentStore ("ns3::ndn::cs::Nocache");
- ...
- ndnHelper.Install (nodes);
+ ndnHelper.SetOldContentStore("ns3::ndn::cs::Nocache");
+ ndnHelper.Install(node3);
-Content stores with entry lifetime tracking
-^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-In order to evaluate lifetime of the content store entries, the special versions of the content store need to be used:
-
-Least Recently Used (LRU)
-~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Stats::Lru`.
-
-Usage example:
+- Track lifetime of CS entries (must use ``ns3::ndn::cs::*::LifetimeStats`` policy):
.. code-block:: c++
void
- CacheEntryRemoved (std::string context, Ptr<const ndn::cs::Entry> entry, Time lifetime)
+ CacheEntryRemoved(std::string context, Ptr<const ndn::cs::Entry> entry, Time lifetime)
{
- std::cout << entry->GetName () << " " << lifetime.ToDouble (Time::S) << "s" << std::endl;
+ std::cout << entry->GetName() << " " << lifetime.ToDouble(Time::S) << "s" << std::endl;
}
...
- ndnHelper.SetContentStore ("ns3::ndn::cs::Stats::Lru",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
+ ndnHelper.SetOldContentStore("ns3::ndn::cs::Stats::Lru", "MaxSize", "10000");
+ ...
+ ndnHelper.Install(nodes);
// connect to lifetime trace
- Config::Connect ("/NodeList/*/$ns3::ndn::cs::Stats::Lru/WillRemoveEntry", MakeCallback (CacheEntryRemoved));
+ Config::Connect("/NodeList/*/$ns3::ndn::cs::Stats::Lru/WillRemoveEntry", MakeCallback(CacheEntryRemoved));
+- Get aggregate statistics of CS hit/miss ratio (works with any policy)
-First-In-First-Out (FIFO)
-~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Stats::Fifo`.
-
-Usage example:
+ The simplest way tro track CS hit/miss statistics is to use :ndnsim:`CsTracer`, in more
+ details described in :ref:`Metrics Section <cs trace helper>`.
.. code-block:: c++
- void
- CacheEntryRemoved (std::string context, Ptr<const ndn::cs::Entry> entry, Time lifetime)
- {
- std::cout << entry->GetName () << " " << lifetime.ToDouble (Time::S) << "s" << std::endl;
- }
-
- ...
-
- ndnHelper.SetContentStore ("ns3::ndn::cs::Stats::Fifo",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
-
- // connect to lifetime trace
- Config::Connect ("/NodeList/*/$ns3::ndn::cs::Stats::Fifo/WillRemoveEntry", MakeCallback (CacheEntryRemoved));
-
-Random
-~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Stats::Random`
-
-Usage example:
-
- .. code-block:: c++
-
- void
- CacheEntryRemoved (std::string context, Ptr<const ndn::cs::Entry> entry, Time lifetime)
- {
- std::cout << entry->GetName () << " " << lifetime.ToDouble (Time::S) << "s" << std::endl;
- }
-
- ...
-
- ndnHelper.SetContentStore ("ns3::ndn::cs::Stats::Random",
- "MaxSize", "10000");
- ...
- ndnHelper.Install (nodes);
-
- // connect to lifetime trace
- Config::Connect ("/NodeList/*/$ns3::ndn::cs::Stats::Random/WillRemoveEntry", MakeCallback (CacheEntryRemoved));
-
-.. _Content Store respecting freshness field of ContentObjects:
-
-Content stores respecting freshness field of ContentObjects
-^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-If simulations need Content Store which respects freshness of ContentObjects, the following versions of content store should be used:
-
-.. note:
-
- Please note that currently, Freshness granularity is 1 second and maximum value is 65535 second. Value means infinity.
-
-Least Recently Used (LRU)
-~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Freshness::Lru`.
-
-Usage example:
-
- .. code-block:: c++
-
- ...
-
- ndnHelper.SetContentStore ("ns3::ndn::cs::Freshness::Lru",
- "MaxSize", "10000");
- ...
-
-First-In-First-Out (FIFO)
-~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Freshness::Fifo`
-
-Usage example:
-
- .. code-block:: c++
-
- ...
-
- ndnHelper.SetContentStore ("ns3::ndn::cs::Freshness::Fifo",
- "MaxSize", "10000");
- ...
-
-Random
-~~~~~~
-
-Implementation name: :ndnsim:`ndn::cs::Freshness::Random`
-
-Usage example:
-
- .. code-block:: c++
-
- ...
-
- ndnHelper.SetContentStore ("ns3::ndn::cs::Freshness::Random",
- "MaxSize", "10000");
- ...
-
-Example
-~~~~~~~
-
-The following example demonstrates a basic usage of a customized content store (``ndn-simple-with-content-freshness.cc``).
-In this scenario two simple consumers (both installed on a consumer node) continually request the same data packet.
-When Data producer specify unlimited freshness, Content keeps getting satisfied from local caches, while if freshness is specified, Interests periodically are getting through to the Data producer.
-
-.. aafig::
- :aspect: 60
- :scale: 120
-
- +----------+ +--------+ +----------+
- | | 1Mbps | | 1Mbps | |
- | Consumer |<-------------->| Router |<-------------->| Producer |
- | | 10ms | | 10ms | |
- +----------+ +--------+ +----------+
-
-
-.. literalinclude:: ../../examples/ndn-simple-with-content-freshness.cc
- :language: c++
- :linenos:
- :lines: 20-27,43-
-
-To run this scenario, use the following command::
-
- NS_LOG=DumbRequester:ndn.cs.Freshness.Lru ./waf --run=ndn-simple-with-content-freshness
+ CsTracer::InstallAll("cs-trace.txt", Seconds(1));