[ndnSIM] How to modify LFU

Alex Afanasyev alexander.afanasyev at ucla.edu
Thu May 2 19:11:33 PDT 2013

Hi Shenglan,

First, I would say that the current implementation of LFU is far from ideal.  May be Aaron can tell you more about the potential issues with the way LFU is implemented.

Do you have a specific design of how MFU should be implemented?  What is the data structure that can track frequencies?  How these frequencies can be updated, when (how often).  What is "frequency" in the first place (= what is your time period).  Another question that you may or may not have answer to is about how exactly you are planning to communicate to downstream nodes.  What do you mean by "pushing the most frequent content"?  Would it be part of the forwarding strategy or something else?

You can try to read the current code of lfu-policy.  What is basically happening is that each item in the content store is organized (in addition to normal name-based trie-like organization) as a multi-set (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L75) = the data structure that keeps order of items.  The order is maintained based on "frequency counter" value (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L71), which is assigned to 0 when item is added to the content store (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L103) and incremented every time an item is looked up (https://github.com/NDN-Routing/ndnSIM/blob/master/utils/trie/lfu-policy.h#L119).   The "missing" part is periodic "flushing" of this freshness counter, so the popular items in the past don't stay on the way of new items.

Btw. I'm not 100% convinced that "pushing" most frequent content downstream is actually content store task.  Could it be a specialized application/forwarding strategy module that periodically polls content store with normal LFU policy and do something with the most popular content?


On May 2, 2013, at 6:33 PM, 陈胜蓝 <blindeafer at 163.com> wrote:

> Hi Alex,
> I want to implement a mfu-policy,and creat a new function to push the most frequently content to downstream node.
> Would you like to give me some advice?
> Best regards,
> Shenglan

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

More information about the ndnSIM mailing list