[ndnSIM] LFU and LRU replacement policies

[Saran Tarnoi]

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/7875b9ba/attachment.html>