[ndnSIM] LFU and LRU replacement policies

[Saran Tarnoi]

Hi Alex,

Thanks for your reply.
I think I can explain the results now, namely, it is the nature of LFU
replacement policy.
Since LFU, in ndnSIM, uses the popularity index of the stored content as
the eviction criterion, it may be some content objects which have the same
lowest popularity index at the same time.
As a result, one of them is evicted from the cache when more room is
needed, and that content object will never obtain the popularity index it
should have had throughout the simulation time.
Besides, ZipfMandelbrot consumer app has inevitably imperfection of the
generated interest popularity unless the we simulate a large enough
simulation.
The above could be the reason why only the minority of popular content
didn't follow my understanding.
However, please don't hesitate to let me know if I'm wrong.

For the detail of LFU implementation in that paper, I found that they used
LFU-Aging, which tries to evict the content object that used to be popular
from a cache and keep the new popular in the cache.
In other words, it also includes the aging of content to be criterion for
replacement.
In ndnSIM, we assume a static traffic model, so I think LFU aging is not
necessary now.
However, if we can model varying traffic (regarding content popularity),
LFU-Aging will be strongly needed.

Hope this help and any comment is very welcome.
Thanks for your time.

Regards,
Saran Tarnoi



2013/6/22 Alex Afanasyev <alexander.afanasyev at ucla.edu>

> Hi Saran,
>
> Could it be related to the fact that current implementation of LFU is not
> really the right one?  E.g., the current "rate" is not really a rate, but
> merely a popularity index since item got into the cache.   To make it real
> frequency, we need to define some period and do periodic recalculation of
> rates...
>
> Do you know the details of LFU implementation used in the paper?
>
> ---
> Alex
>
> On Jun 21, 2013, at 2:40 AM, Saran Tarnoi <sarantarnoi at gmail.com> wrote:
>
> Hi All,
>
> I tested some experiments to see how each replacement policy change the
> traffic.
> Specifically, I want to study filtering effect in hierarchical caches.
>
> Unfortunately, I got some unexplainable results and hope that someone can
> kindly emphasize them.
>
> Theoretically, LFU evicts the "least frequently used" item from a cache
> when the cache needs more room for an item, while LRU discards the least
> recently used item.
> In page 58 of a legendary paper "*On Filter Effects in Web Caching
>  Hierarchies,"* they clearly showed that LFU more effectively filters the
> popular items out from the Zipf-like traffic than LRU does.
>
> By using ndnSIM, the results do not follow those in the paper.
> I found that some (minority of) interests asking for very popular items
> are not filtered by LFU cache, they still go to the next CCN router while
> the ones asking for less popular items are filtered effectively.
>
> ZipfMandelbrot consumer app generates interest traffic by reducing the
> popularity of particular interests proportionally to the their index
> sequence.
> In other words,  "/prefix/1" is generated more frequently than
> "/prefix/2", "/prefix/3", ..., "/prefix/N".
>
> I found that some interests with "/prefix/a" cannot find their target item
> in the cache while some interests with prefix "/prefix/a-i" and
> "/prefix/a+i" can, where i > 0.
>
> I think it should not be so in the cache with LFU implemented.
> Thus I infer from the results that LFU does not always evict the "least
> frequently used" from the content store.
> It seems to me that sometimes it can even randomly discard some of more
> frequently used items from the cache.
> This is the fact of LFU, the imperfection of my experiment, or a bug in
> Lfu policy?
>
> For LRU, I found that a more popular item can be found in the cache with a
> higher possibility than those of less popular items, so it is reasonable.
>
> If I misunderstand the logic of LFU, please let me know.
>
> Sorry for the long question.
> Thank you so much for your time.
>
> --
> Regards,
> Saran Tarnoi
>
>
>


-- 
Regards,
Saran Tarnoi
Graduate Student
Department of Informatics
The Graduate University for Advanced Studies (Sokendai)
Tokyo, Japan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndnsim/attachments/20130624/7908cc54/attachment.html>