[ndnSIM] LFU and LRU replacement policies

[Alex Afanasyev]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndnsim/attachments/20130621/cd52cf0d/attachment.html>