<div dir="ltr">Hi Alex,<div><br></div><div style>Thanks for your reply.</div><div style>I think I can explain the results now, namely, it is the nature of LFU replacement policy.</div><div style>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.</div>
<div style>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.</div><div style>Besides, ZipfMandelbrot consumer app has inevitably imperfection of the generated interest popularity unless the we simulate a large enough simulation. </div>
<div style>The above could be the reason why only the minority of popular content didn't follow my understanding.</div><div style>However, please don't hesitate to let me know if I'm wrong.</div><div style><br>
</div><div style>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. </div>
<div style>In other words, it also includes the aging of content to be criterion for replacement.</div><div style>In ndnSIM, we assume a static traffic model, so I think LFU aging is not necessary now.</div><div style>However, if we can model varying traffic (regarding content popularity), LFU-Aging will be strongly needed.</div>
<div style><br></div><div style>Hope this help and any comment is very welcome.</div><div style>Thanks for your time.</div><div style><br></div><div style>Regards,</div><div style>Saran Tarnoi <br></div><div style><br></div>
<div class="gmail_extra"><br><br><div class="gmail_quote">2013/6/22 Alex Afanasyev <span dir="ltr"><<a href="mailto:alexander.afanasyev@ucla.edu" target="_blank">alexander.afanasyev@ucla.edu</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">Hi Saran,<div><br></div><div>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...  </div>
<div><br></div><div>Do you know the details of LFU implementation used in the paper?</div><div><br></div><div>---</div><div>Alex</div><div><div class="h5"><div><br><div><div>On Jun 21, 2013, at 2:40 AM, Saran Tarnoi <<a href="mailto:sarantarnoi@gmail.com" target="_blank">sarantarnoi@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div dir="ltr">Hi All,<div><br></div><div>I tested some experiments to see how each replacement policy change the traffic.</div><div>Specifically, I want to study filtering effect in hierarchical caches.</div>
<div><br>
</div><div>Unfortunately, I got some unexplainable results and hope that someone can kindly emphasize them.</div><div><br></div><div>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.</div>

<div>In page 58 of a legendary paper "<b>On <em style="color:rgb(221,75,57);font-style:normal">Filter Effects</em> in Web <em style="color:rgb(221,75,57);font-style:normal">Caching</em> Hierarchies,"</b> they clearly showed that LFU more effectively filters the popular items out from the Zipf-like traffic than LRU does.</div>

<div><br></div><div>By using ndnSIM, the results do not follow those in the paper.</div><div>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.</div>

<div><br></div><div>ZipfMandelbrot consumer app generates interest traffic by reducing the popularity of particular interests proportionally to the their index sequence.</div><div>In other words,  "/prefix/1" is generated more frequently than "/prefix/2", "/prefix/3", ..., "/prefix/N".</div>

<div><br></div><div>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.</div>

<div><br></div><div>I think it should not be so in the cache with LFU implemented.</div><div>Thus I infer from the results that LFU does not always evict the "least frequently used" from the content store.</div>

<div>It seems to me that sometimes it can even randomly discard some of more frequently used items from the cache.</div><div>This is the fact of LFU, the imperfection of my experiment, or a bug in Lfu policy?</div>
<div><br></div><div>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.</div><div><br></div><div>If I misunderstand the logic of LFU, please let me know.</div>

<div><div><br></div><div>Sorry for the long question.</div><div>Thank you so much for your time.</div><div><br></div>-- <br><div dir="ltr">Regards,<div>Saran Tarnoi</div></div>
</div></div>
</blockquote></div><br></div></div></div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div dir="ltr">Regards,<div>Saran Tarnoi</div><div>Graduate Student</div><div>Department of Informatics</div><div>
The Graduate University for Advanced Studies (Sokendai)</div><div>Tokyo, Japan</div></div>
</div></div>